C-Kommentare aufbrechen

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Ich möchte nun ein Beispiel zeigen, bei dem das Aufbrechen der kritischen Schleife schwieriger ist. In der Programmiersprache C beginnen Kommentare mit /* und enden mit */. Sie können mehrere Zeilen umfassen, dürfen aber nicht verschachtelt sein. (Auch in C++, Java, C# und PHP gibt es diese Art von Kommentaren.) Ein Ausdruck, der C-Kommentare erkennt, kann recht nützlich sein, und sei es nur für ein Filterprogramm, das solche Kommentare entfernt. Bei diesem Problem bin ich zuerst auf meine Methode des Aufbrechens von Schleifen gestoßen, eine Technik, die seither fester Bestandteil meines Regex-Arsenals ist.

Aufbrechen oder nicht ...

Die Technik des Schleifenaufbrechens habe ich in den frühen 90ern entwickelt. Zuvor galt ein regulärer Ausdruck zum Erkennen von C-Kommentaren als schwierig, wenn nicht gar unmöglich; meine Lösung wurde daher schnell zur Standardmethode. Als in Perl die genügsamen, nicht-gierigen Quantoren eingeführt wurden, gab es plötzlich einen viel einfacheren Weg: mit einem nicht-gierigen Punkt in ˹/\*.*?\*/˼.

Hätte es die genügsamen Quantoren schon früher gegeben, hätte ich die »Schleifen aufbrechen«-Methode wohl nie entdeckt, weil das Problem dann nicht als drängend empfunden worden wäre. Dennoch war die Methode auch mit frühen Versionen von nicht-gierigen Quantoren wertvoll, weil sie schnellere reguläre Ausdrücke ergab: Sie waren je nach Test 50 % schneller bis 3,6 mal so schnell.

Mit der heutigen, hochoptimierten Regex-Maschine von Perl ist der Vorsprung dahin. Mit modernem Perl ist die Version mit den nicht-gierigen Quantoren zwischen 50 % schneller bis zu 5,5 mal so schnell. Heute verwende ich für ein Problem wie die Kommentare in C den einfacheren Ausdruck ˹/\*.*?\*/˼.

Ist also die »Schleifen aufbrechen«-Methode nutzlos geworden? Wenn der Regex-Dialekt keine genügsamen Quantoren kennt, ist die Methode noch immer die erste Wahl. Außerdem sind nur wenige Regex-Maschinen so gut optimiert wie die von Perl: In allen anderen Programmiersprachen, die ich getestet habe, ist die Version mit der »Schleifen aufbrechen«-Methode schneller als die mit den nicht-gierigen Quantoren – manchmal bis zu 60 mal schneller! Die Technik ist zweifellos nützlich, darum wird sie im Rest des Kapitels am Beispiel der C-Kommentare eingehend illustriert.

Innerhalb von C-Kommentaren gibt es keine mit Backslash geschützten Zeichen wie bei Strings in Anführungszeichen, also sollten die Dinge eigentlich einfacher liegen. Leider ist dem nicht so, weil */, das »schließende Anführungszeichen«, aus mehr als einem Zeichen besteht. Ein plumper Ansatz wie ˹/\*[^*]*\*/˼ funktioniert nicht, weil in einer Zeile wie /** Das ist ein Kommentar **/ die zusätzlichen ›*‹ und insbesondere der zweitletzte Stern absolut zulässig sind. Wir müssen schon etwas differenzierter vorgehen.

Augenschmerzen

Ausdrücke wie ˹/\*[^*]*\*/˼ sind extrem schwer lesbar. Die vielen Backslashes und Sternchen verursachen Augenschmerzen. Unglücklicherweise ist ja der Stern sowohl Teil des Begrenzer-Symbols als auch ein Regex-Metazeichen. Damit der folgende Abschnitt etwas lesbarer wird, verwende ich ab sofort nur noch /x...x/ statt /*...*/ als Kommentar-Begrenzer. Mit diesem rein kosmetischen Eingriff wird ˹/\*[^*]*\*/˼ zum leichter lesbaren ˹/x[^x]*x/˼. Die Ausdrücke werden komplizierter werden, und Ihre Augen werden es Ihnen danken.

Ein direkter Ansatz

In Regex-Methoden aus der Praxis (unter Eingefassten Text erkennen) hatte ich für das Vorgehen bei eingefasstem Text empfohlen:

  1. Finde die öffnenden Begrenzungszeichen.
  2. Finde den eigentlichen Text (das heißt »alles, was nicht zum schließenden Begrenzer gehört«).
  3. Finde die schließenden Begrenzungszeichen.

Unsere Pseudo-Kommentare mit /x und x/ als öffnende und schließende Begrenzer scheinen darauf zu passen. Die Schwierigkeiten beginnen mit der Umsetzung der Formulierung »alles, was nicht zum schließenden Begrenzer gehört«. Wenn die Begrenzer einzelne Zeichen sind, nimmt man einfach eine negierte Zeichenklasse, die auf alles außer auf den schließenden Begrenzer passt. Für mehrbuchstabige Begrenzer ist eine Zeichenklasse nicht geeignet, aber wenn negatives Lookahead unterstützt wird, kann man so etwas wie ˹(?:(?!x/).)*˼ benutzen. Das ist in Worten ausgedrückt so etwas wie ˹(alles, aber nicht x/)*˼.

Damit erhalten wir die Regex ˹/x(?:(?!x/).)*x/˼ zum Erkennen von C-Kommentaren. Das funktioniert gut, ist aber etwas langsam. (Bei manchen von meinen Tests mehrere hundertmal langsamer als die schnellste Version, die wir später entwickeln.) Der Ansatz ist auch deswegen nicht besonders interessant, weil jeder Regex-Dialekt, der das Lookahead unterstützt, fast ganz sicher auch die nicht-gierigen Quantoren kennt. Wenn also Effizienz wichtig ist, wird man stattdessen ˹/x.*?x/˼ verwenden.

Gibt es, wenn wir nach den drei Schritten von oben fortfahren, eine andere Möglichkeit, alles bis zum ersten x/ zu finden? Es gibt zwei übliche Varianten, das Problem des Matchings bis zum nächsten x/ anzugehen. Eine Methode betrachtet x als Anfang des schließenden Begrenzers. Damit sucht man nach allem, was kein x ist, und lässt außerdem ein x dann zu, wenn ihm kein Schrägstrich folgt. So wird die Formulierung »alles, was nicht zum schließenden Begrenzer gehört« zu:

  • Alles außer x: ˹[^x]˼
  • x, außer wenn darauf ein Schrägstrich folgt: ˹x[^/]˼

Das ergibt ˹([^x]|x[^/]) für den eigentlichen Text und ˹/x([^x]|x[^/])*x/˼ für den ganzen Pseudo-Kommentar. Wir werden aber sehen, dass das nicht funktioniert.

Bei der anderen Methode wird der Schrägstrich als das Endezeichen betrachtet, aber nur, wenn davor ein x steht. Damit wird »alles, was nicht zum schließenden Begrenzer gehört« zu:

  • Alles außer einem Schrägstrich: ˹[^/]˼
  • Ein Schrägstrich, solange kein x davorsteht: ˹[^x]/˼

Das ergibt ˹([^/]|[^x]/) für den eigentlichen Text und ˹/x([^/]|[^x]/)*x/˼ für den ganzen Kommentar.

Leider funktioniert auch das nicht.

Für den ersten Fall, ˹/x([^x]|x[^/])*x/˼, betrachten wir ›/xxfooxx/‹. Nachdem ›foo erkannt wurde, passt das zweitletzte x auf ˹x[^/]˼, da stimmt noch alles. Dann aber erkennt ˹x[^/]˼ den Text xx/, der das x enthält, das zum End-Begrenzer gehört. Das Matching überliest also dieses Endezeichen und fährt weiter fort (bis zum Ende des nächsten Kommentars, so es denn einen gibt).

Bei ˹/x([^/]|[^x]/)*x/˼ lautet das Gegenbeispiel /x/foo/x/ (das Ganze ist ein Kommentar und müsste erkannt werden). Außerdem schießt diese Regex über das Ziel hinaus, wenn dem Endezeichen unmittelbar ein Schrägstrich folgt, ähnlich wie bei der obigen Methode. Das dabei auftretende Backtracking ist hübsch kompliziert, und deshalb überlasse ich es Ihnen herauszufinden, warum die Regex ˹/x([^/]|[^x]/)*x/˼ das Folgende findet:

jahre = tage /x div x//365; /x kein Schaltjahr x/

Reparatur

Schauen wir, ob wir diese Ausdrücke nicht doch noch zusammenflicken können. Beim ersten passt das ˹x[^/]˼ ungewollt auf ...xx/, das zum Begrenzer gehört. Bei ˹/x([^x]|x+[^/])*x/˼ würde das Plus bewirken, dass ˹x+[^/]˼ auch auf eine ganze Serie von x passt, die von etwas anderem als einem Schrägstrich gefolgt sind. Das passiert in der Tat, aber infolge des Backtrackings kann dieses »etwas anderes als ein Schrägstrich« auch ein x sein. Zunächst passt das gierige ˹x+˼ tatsächlich auf das letzte x, aber durch das Backtracking muss es wieder zurückgegeben werden, weil dadurch ein Matching des ganzen Ausdrucks erreicht wird. Bei einem String wie dem folgenden wird zu viel erkannt:

/xx A xx/ foo() /xx B xx/

Die Lösung erinnert an etwas, das ich schon mal betont habe: Formulieren Sie genau. Wenn wir sagen: »x, gefolgt von einem Nicht-Schrägstrich«, dann meinen wir implizit, dass dieser Nicht-Schrägstrich auch kein x sein darf. Also schreiben wir exakt das: ˹x+[^/x. Wie gewünscht stoppt das vor ›...xxx/‹, dem letzten x vor einem Schrägstrich. Genauer gesagt stoppt es vor irgendwelchen x, nämlich bei ›...▵xxx/‹. Der Unterausdruck für das End-Zeichen erwartet aber nur ein x, wir müssen also ein Pluszeichen einfügen, damit auch dieser Fall erkannt wird.

Damit erhalten wir ˹/x([^x]|x+[^/x])*x+/˼, einen Ausdruck, der unsere Pseudo-Kommentare erkennt.

Deutsch ins Regexische übersetzen

Bei Ein direkter Ansatz werden zwei Methoden besprochen, mit denen man C-Kommentare finden kann. Dabei hatte ich die Formulierungen

x, außer wenn darauf ein Schrägstrich folgt: ˹x[^/]˼

und

Ein Schrägstrich, solange kein x davorsteht: ˹[^x]/˼ benutzt.

Das ist informell – die deutsche Beschreibung unterscheidet sich ziemlich von dem, was die regulären Ausdrücke bewirken. Sehen Sie den Unterschied?

Betrachten Sie für den ersten Fall den String ›regex‹ – sicherlich ein x, auf das kein Schrägstrich folgt, aber dieser String würde von ˹x[^/]˼ nicht erkannt. Die Zeichenklasse muss auf ein Zeichen passen. Dieses Zeichen darf zwar kein Schrägstrich sein, aber doch immerhin etwas, und nach dem x in ›regex‹ kommt nichts. Die zweite Formulierung ist dazu analog. Das gewünschte Verhalten ist das der Regex-Beispiele, also liegt der Fehler bei der Umsetzung ins Deutsche.

Wenn Lookahead unterstützt wird, ist »x, außer wenn darauf ein Schrägstrich folgt« ganz einfach ˹x(?!/)˼. Wenn nicht, käme ˹x([^/]|$)˼ zupass. Das erkennt noch immer ein Zeichen nach dem x oder aber auch ein Zeilenende. Mit Lookbehind wäre ein »Schrägstrich, außer wenn davor ein x steht« der Ausdruck ˹(?<!x)/˼; ohne Lookbehind müsste man so etwas wie ˹(^|[^x]) nehmen.

Wir werden keine dieser Methoden in unserem Beispiel mit den C-Kommentaren verwenden, aber es ist gut zu wissen, wie sie arbeiten.

Puh! Verwirrend, nicht wahr? Für richtige Kommentare (mit * statt x) wird

˹/\*([^*]|\*+[^/*])*\*+/˼

benötigt, was noch schlimmer aussieht. Das ist in der Tat nicht einfach zu verstehen – beim Lesen von komplizierten regulären Ausdrücken muss man sich schon etwas konzentrieren!

Die C-Schleife aufbrechen

Um das effizienter zu gestalten, wollen wir auch hier die Schleife aufbrechen. Die folgende Tabelle zeigt die Unterausdrücke, die wir in das Rezept einsetzen können.

Tabelle: Schleife aufbrechen: Komponenten für C-Kommentare.

Element Wir wollen Regex
˹öffnend normal*( speziell normal*)* schließend˼
öffnend Anfang des Kommentars /x
normal* Text im Kommentar, bis und mit einem oder mehreren ›x‹ [^x]*x+
speziell etwas, was kein Schrägstrich ist (und auch kein ›x‹) [^/x]
schließend Schrägstrich am Ende /

Wie im Beispiel mit den Internet-Domains darf auch hier das Element ˹normal nicht auf »gar nichts« passen. Bei den Domainnamen lag es daran, dass die Namen keine leeren Strings sein dürfen. Hier liegt es an der Art, wie wir die mehrbuchstabigen Begrenzer behandeln. Wir stellen sicher, dass jede normal-Sequenz mit dem ersten Zeichen dieses zweibuchstabigen Begrenzers aufhört. Außerdem darf speziell nicht auf eines der Zeichen passen, aus denen der Begrenzer zusammengesetzt ist.

Ins Schema eingesetzt, ergibt sich:

˹/x[^x]*x+([^/x][^x]*x+)*/˼

Sehen Sie die markierte Stelle? Die Regex-Maschine kann auf zwei Arten bis zu diesem Punkt vorstoßen (genau wie beim Ausdruck in Methode 2: Die kritische Schleife im größeren Zusammenhang betrachten): entweder, beim ersten Mal, indem sie das ˹/x[^x]*x+˼ am Anfang abarbeitet oder durch die Schleife, die durch den Stern in (...)* gebildet wird. In jedem Fall sind wir an einem Kontrollpunkt: Eben wurde ein x erkannt, und wir sind vielleicht kurz vor dem Ende des Kommentars. Wenn das nächste Zeichen ein Schrägstrich ist, sind wir fertig. Wenn es ein anderes Zeichen ist (aber auch kein x), dann wissen wir, dass das x ein Fehlalarm war und wir bis zum nächsten x (oder einer Reihe von solchen) weitermachen können. Dann sind wir wieder an der exakt gleichen Stelle in der Regex.

Zurück in die Realität

˹/x[^x]*x+([^/x][^x]*x+)*/˼ ist noch nicht ganz gebrauchsfertig. Zunächst sehen richtige Kommentare aus wie /*...*/ und nicht wie /x...x/. Das ist trivial – ersetzen Sie einfach x durch \* (in einer Zeichenklasse nur durch *):

˹/\*[^*]*\*+([^/*][^*]*\*+)*/˼

Kommentare im C-Stil umfassen oft mehrere Zeilen. Wenn der zu prüfende Text mehrere logische Zeilen (mit Newlines) enthält, ist das gar kein Problem: Unsere Regex funktioniert auch dann. Mit Werkzeugen, die wie egrep streng zeilenweise vorgehen, ist da allerdings nicht viel zu machen. In den meisten anderen Programmen kann man mit dieser Regex durchaus auch mehrzeilige Kommentare behandeln, sie beispielsweise entfernen.

In der Praxis ergibt sich aber ein wesentlich kniffligeres Problem. Unsere Regex kennt C-Kommentare, aber sie weiß rein gar nichts über die restliche Struktur eines C-Programms. Insbesondere kennt sie Strings in C nicht und stolpert deshalb über Zeilen wie:

const char *cstart = "/*", *cend = "*/";

Wir werden dieses Beispiel im nächsten Abschnitt weiter ausbauen.

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:
   

Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln