Kapitel 8. Ein paar Beispiele

Die fiktiven Programmiersprachen K und K++ kennen zwei Arten von Kommentaren. Da wäre die nur in K++ verwendete Art 'kk.*' (zwei einleitende 'k'), oder die in beiden Sprachen verwendete Form 'ko.*ok', wobei sich ein solcher Kommentar über mehrere Zeilen erstrecken kann. Es soll ein sed-Script erstellt werden, das solche Kommentare (warum auch immer!) entfernen soll.

Das Entfernen von K-Kommentaren benötigt ein paar Erklärungen. Nehmen wir einmal an, wir hätten den gesamten Kommentar im pattern space. Das Kommando 's/ko.*ok//' geht aus dem Grund nicht, weil die ansonsten nützliche Eigenschaft von REs, den längsten zutreffenden String zu nehmen, hier unerwünscht ist. Sind zwei vollständige Kommentare in einer Zeile vorhanden, dann würde auch der unschuldigerweise dazwischen stehende Code entfernt werden.

Der zweite Anlauf ist ein 's/ko\([^o][^k]\)*ok//g'. Achtung bei Konstrukten, welche Quantifikatoren ('*', '\+', '\{\}' ...) auf zwei oder mehrere Zeichen anwenden! Das Script arbeitet nur bei der Hälfte der Kommentare, und zwar bei jener Hälfte, welche eine gerade Anzahl von Zeichen beinhaltet. Vom Zorn gepackt, schreibt man dann Sachen wie 's/ko\([^o]*\(o[^k]\)*[^o]*\)*ok//g' welche zwar korrekt sind, aber völlig Praxisuntauglich. Ein solches Monsterprogramm kann allerhöchstens auf einem Großrechner vernünftig arbeiten. In diesen Situationen hilft es, eine verbale Beschreibung des Musters zu finden. Die könnte so aussehen: "Ein K-Kommentar beginnt mit 'ko', ihm folgen null oder mehr der oben beschriebenen Lesevorgängen [^o]\|o\+[^ok] plus einem Abschluss o\+k'. Auf sedisch übersetzt bekommt man 'ko\([^o]\|o\+[^ok]\)*o\+k'.

Nun muss nur noch sicher gestellt werden, dass nach einem 'ko'-Muster auch ein 'ok' im pattern space ist. Ist dem nicht so, dann sorgt der innere Loop (um das label append) dafür, dass ständig neue Zeilen mit dem 'N'-Befehl an den pattern space angehängt werden. Ein äußerer Loop (um das label test) sorgt dafür, dass jene Zeilen richtig behandelt werden, in denen ein Kommentar geschlossen und anschließend ein neues mehrzeiligen Kommentar wieder aufgemacht wird.

#!/bin/sed -f

#lösche K++-Kommentare
/^[[:blank:]]*kk.*/d
s/kk.*//g

#Wenn kein Kommentar gefunden wurde, dann nächster Zyklus.
: test
/ko/!b

#Hänge so lange neue Zeilen an den pattern space an,
#bis ein vollständiger Kommentar zusammengebracht wurde.
: append
/ok/!{N;b append;}

#lösche K-Kommentare die sich vollständig im pattern space befinden
s/ko\([^o]\|o\+[^ok]\)*o\+k//g

t test

Ein K-Kommentar beginnt mit 'ko', soweit ist alles klar. Anschließend folgt die längst mögliche Zeichenkette, die kein 'ok' enthält. Hier liegt der Hund begraben. Das abschließende 'ok' ist wieder trivial.

Nun zum Hund: Gesucht ist die längstmögliche Zeichenkette, auf welche der reguläre Ausdruck /ok/ nicht zutrifft. Es ist also gewissermaßen das Gegenteil von /ok/ gesucht.

Man kann sich nun in Anlehnung an ein prozedurales Vorgehen vorstellen, man suche das erste Auftreten von 'ok' innerhalb einer Zeichenkette. Dazu lese man immer wieder neue Zeichen von der Zeichenkette ein und untersuche die eingelesenen Zeichen.

Die gesuchte Teil-Zeichenkette besteht dann aus null oder mehreren "Lesevorgängen": Längste Zeichenkette ohne 'ok' = \(Lesevorgang\)*

Nach jedem Lesevorgang trifft man dann eine Fallunterscheidung, etwa von der Art: Es wurde kein 'o' eingelesen, es wurde ein 'o' aber kein 'k' eingelesen, etc. Man erhält so:

Lesevorgang = Fall_1 \| Fall_2 \| ... \| Fall_x

Wieder in Anlehnung an das prozedurale Vorgehen wird man zu Beginn der Überlegungen davon ausgehen, es werde pro Lesevorgang nur ein einzelnes Zeichen eingelesen. Ist dieses Zeichen dann von 'o' verschieden, trifft also der Ausdruck [^o] darauf zu, kann man mit dem nächsten Lesevorgang fortfahren, und man hat:

Fall_1 = [^o]

Ist das eingelesene Zeichen hingegen gleich 'o', dann könnte man in die Versuchung kommen, zu prüfen, ob sich das nächste Zeichen von 'k' unterscheidet, in der Annahme, damit einen weiteren Fall eines Lesevorganges vollständig abgehandelt zu haben: Den Fall o[^k] nämlich! Träfe dieser reguläre Ausdruck auf die immerhin bereits zwei eingelesenen Zeichen zu, dann ginge man zum nächsten Lesevorgang über.

Aber hoppla! Das vorhin auf [^k] überprüfte Zeichen könnte ja wieder gleich 'o' sein, was zur Folge hätte, dass man beim nächsten Lesevorgang das zuerst eingelesene Zeichen auf 'k' überprüfen müsste. Solche Abhängigkeiten zwischen den Lesevorgängen sprengen aber das Konzept dieser Vorgehensweise und deuten darauf hin, dass der vorhergehende Lesevorgang im Prinzip weiter geführt werden muss.

Ist das erste Zeichen eines Lesevorganges also ein 'o', dann könnte diesem 'o' gleich eine ganze Folge weiterer 'o's folgen. Man muss also einen Ausdruck der Form o\+ einlesen, und zwar so lange, bis man endlich ein Zeichen findet, das sich von 'o' unterscheidet. Ist dann dieses Zeichen nicht nur von 'o', sondern auch von 'k' verschieden, dann hat man insgesamt einen Ausdruck der Form o\+[^ok] eingelesen:

Fall_2 = o\+[^ok]

Von da aus kann man nun problemlos mit dem nächsten Lesevorgang fortfahren. Da das erste Zeichen aber nur entweder 'o' oder dann eben nicht 'o' sein kein, treten neben Fall_1 und Fall_2 keine weiteren Fälle mehr hinzu:

Lesevorgang = Fall_1 \| Fall_2 = [^o]\|o\+[^ok]

Bei jedem Lesevorgang findet man also ein einzelnes Zeichen [^o] oder einen Ausdruck o\+[^ok]. Erst wenn eine 'o-Folge' mit dem Zeichen 'k' endet, wenn man also auf den "Abschluss" o\+k trifft, ist man am Ende.

Die null oder mehr Lesevorgänge [^o]\|o\+[^ok] liefern damit die längste Zeichenkette, die den Abschluss o\+k nicht enthalten. Obwohl damit das anfängliche Ziel, die längste Zeichenkette ohne 'ok' zu finden, knapp verfehlt worden ist, kann man mit diesen Überlegungen bequem den letztlich gesuchten Ausdruck eines K-Kommentars hinschreiben: Ein K-Kommentar beginnt mit 'ko', ihm folgen null oder mehr der oben beschriebenen Lesevorgängen [^o]\|o\+[^ok] plus einem Abschluss o\+k:

K-Kommentar = ko\([^o]\|o\+[^ok]\)*o\+k

Übrigens kann man mit dem bekannten Editor vim einen K-Kommentar einfach durch

K-Kommentar = ko.\{-}ok

definieren. Dabei bedeutet der Ausdruck .\{-}, dass, ähnlich wie bei .*, eine beliebige Zeichenkette gesucht ist, aber nicht die längste, sondern die kürzeste.

Vielen herzlichen Dank an Mathias Michaelis für dessen Beitrag zu diesem Tipp.

Gelogen habe ich nicht, als ich behauptete, mit REs könne man keinen elleff-verschlüsselten Vokal beschreiben - das stimmt schon. Aber sed kann. Und das auf eine sehr trickreiche Weise. Zuerst das Script, kommentiert wird danach.

sed -e 's/\([aeiou]\+\)l\1f\1/\1/g'

Wenn man diesen Kniff nicht schon einmal gesehen hat, muss man 2 (ich 3) mal hinschauen um zu verstehen, warum das funktioniert. Was mir an diesem Beispiel so gut gefällt ist, dass sobald die Klammer geschlossen wird, der Inhalt des eingeschlossenen Bereiches schon in '\1' bereit steht und somit verwendet werden kann - auch innerhalb der RE. Die RE wird somit zur Laufzeit verändert. Das zeigt einerseits wie leistungsfähig sed ist und andererseits, dass es auch manchmal recht knifflig sein kann, die Scripte anderer zu verstehen.

Diesen Trick verdanke ich Carlos Duarte - ein weiterer Anreiz, in sein sed tutorial hineinzuschauen.

In manchen Fällen muss man auf das n-te Feld einer Zeile zugreifen. Die Quantifikatoren '\{n\}' sind dabei sehr nützlich. Will man beispielsweise das 3. Wort einer Zeile an den Zeilenanfang setzen, ist das Konstrukt

sed -e 's/^\([^ ]* *\)\{2\}\([^ ]* \)/\2\1/g'

nicht richtig, da die Referenz '\1' nur das zweite Wort enthält, nicht aber das erste und zweite. Abhilfe schafft da ein weiteres Klammernpaar, wie im folgenden Script:

sed -e 's/^\(\([^ ]* *\)\{2\}\)\([^ ]* \)/\3\1/g'

Dabei ist '\3' die Referenz auf das zweite Wort ('\2' referenziert das letzte Wort in '\1'). Hierbei ist man schon an die Grenzen der Verständlichkeit eines sed-Scriptes gegangen, und es ist zu überlegen, ob man mit anderen Programmen wie zum Beispiel awk nicht besser bedient ist.

Danke an Tillmann Bitterberg für diesen Tip.