Die frei fließende Regex

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

Wir haben gerade eine Regex aufgebaut, die zwar C-Kommentare erkennt, die aber versagt, wenn innerhalb von Strings in Anführungszeichen Kommentar-Begrenzer auftauchen, die gar keine sind. Ein Perl-Programmstück wie das folgende, das Kommentare aus C-Programmen entfernt, tut unter Umständen zu viel des Guten:

$prog =~ s{/\*[^*]*\*+(?:[^/*][^*]*\*+)*/}{}g; # Entfernt C-Kommentare (und anderes!)

Damit wird der Teil, auf den unsere Regex passt, aus dem Text in $prog entfernt (d.h. durch nichts ersetzt). Es gibt aber nichts, das unsere Regex daran hindert, ein Kommentarzeichen zu erkennen, das in einem String auftritt:

char *CommentStart = "/*"; /* Kommentar-Anfang */
char *CommentEnd = "*/"; /* Kommentar-Ende */

Hier sind die Kommentare, die wir finden wollten, halbfett dargestellt, und das, was die Regex wirklich findet, ist unterstrichen. Wenn die Maschine nach einem Treffer sucht, wird der Ausdruck an jeder Position im String angesetzt. Wirkliche Treffer können zwar nur bei einem Kommentar-Anfangszeichen beginnen, aber das Getriebe schiebt die Regex an eine Stelle mitten in einem String, die nur wie ein solches Anfangszeichen aussieht. Es wäre gut, wenn wir die Regex dazu bringen könnten, Strings in Anführungszeichen einfach zu ignorieren.

Eine helfende Hand führt die Maschine

Betrachten wir das Programmstück:

$KOMMENTAR = qr{/\*[^*]*\*+(?:[^/*][^*]*\*+)*/};  # erkennt Kommentare
$GAENSE    = qr{"(?:\\.|[^"\\])*"};               # erkennt Strings in Anführungszeichen
$text =~ s/$GAENSE|$KOMMENTAR//g;

Hier sind zwei Dinge neu. Zunächst ist der Regex-Operand $GAENSE|$KOMMENTAR aus zwei Variablen zusammengesetzt, die beide mit dem besonderen qr/.../-Operator von Perl initialisiert werden. Wenn reguläre Ausdrücke in String-Form angegeben werden, muss man vorsichtig vorgehen – wir hatten das unter Features und Dialekte erwähnt (siehe Strings als reguläre Ausdrücke).

In Perl gibt es diesen speziellen qr/.../-Operator, der seinen Operanden als Regex (und nicht als String) interpretiert, aber nicht anwendet. Er gibt eine Art »Regex-Objekt« zurück, das später als Teil eines größeren Ausdrucks eingesetzt werden kann. Das ist enorm praktisch, und wir hatten diese Eigenschaft unter Erweiterte einführende Beispiele (unter Eine Regex-Sammlung) bereits ausgenutzt. Wie bei m/.../ und s/.../.../ kann man die Trennzeichen selbst wählen (siehe unter E-Mail-Adressen »verlinken«); hier habe ich geschweifte Klammern verwendet.

Die andere Neuheit betrifft den $GAENSE-Teil. Wenn die Maschine einen Matching-Versuch bei einer Position beginnt, an der $GAENSE passen kann, wird es das auch tun. Damit werden Strings in Anführungszeichen überlesen. Die beiden Alternativen überlappen sich nirgends, und deshalb funktioniert das. An jedem Startpunkt für ein mögliches Matching tritt einer der folgenden Fälle ein:

  • Der Kommentar-Teil passt. Alles bis zu einem Kommentar-Endezeichen wird erkannt. Oder ...
  • Die Alternative für Strings in Anführungszeichen passt. Der ganze String wird erkannt. Oder ...
  • Nichts passt. Das uninteressante Zeichen wird nicht beachtet, das Getriebe geht zum nächsten Zeichen weiter.

Auf diese Art wird die eigentliche Regex nie innerhalb eines Strings in Anführungszeichen gestartet. Das ist der Schlüssel zum Erfolg. Nur – im Moment entfernt das Programmstück nicht nur Kommentare, sondern auch Strings aus dem C-Programm.

Auch das lässt sich lösen:

$KOMMENTAR = qr{/\*[^*]*\*+(?:[^/*][^*]*\*+)*/};  # erkennt Kommentare
$GAENSE    = qr{"(?:\\.|[^"\\])*"};               # erkennt Strings in Anführungszeichen
$text =~ s/($GAENSE)|$KOMMENTAR/$1/g;

Die einzigen Unterschiede zu vorhin sind:

  • Zusätzliche einfangende Klammern, die gefundenen Text in $1 speichern. Wenn die Kommentar-Alternative passt, enthält \1 den leeren String.
  • Der Ersatz-String der Substitution ist nun $1. Wenn die $GAENSE-Alternative passt, wird diese durch sich selbst ersetzt – die Substitution wird zum Null-Operator (aber sie verschiebt die aktuelle Position aus dem String heraus, gerade deshalb haben wir sie ja eingeführt). Wenn dagegen die Kommentar-Alternative erkannt wird, wird sie durch gar nichts ersetzt, also durch den leeren String in $1. (Anmerkung: Wenn in Perl das erste einfangende Klammerpaar nicht Teil des Treffers ist, bekommt $1 eine Art »kein Wert«, nämlich den Wert »undef«. Wenn dieser im Ersatztext interpoliert wird, benimmt er sich wie der Leerstring – und das ist genau das, was wir hier benötigen. Wenn Sie aber mit -w oder use warnings arbeiten (jeder gute Programmierer tut das), dann wird dabei eine Warnung ausgegeben. Diese können Sie vermeiden, indem Sie im Block mit dieser Regex ein ›no warnings;‹-Pragma einbauen oder indem Sie auf den besonderen Wert »undef« testen: $text =~ s/($GAENSE)|$KOMMENTAR/defined($1) ? $1 : /ge;)

Zuletzt müssen wir uns auch um die Konstanten in Hochkommas wie '\t' kümmern. Das ist einfach – wir fügen einfach eine weitere Alternative ganz analog zu Strings in Anführungszeichen an. Wenn unser Skript auch //-Kommentare wie in C++, Java oder C# korrekt behandeln soll, können wir das mit einer vierten Alternative ˹//[^\n]*˼ außerhalb der Klammern erledigen.

$KOMMENTAR  = qr{/\*[^*]*\*+(?:[^/*][^*]*\*+)*/};   # /*  C-Kommentar */
$KOMMENTAR2 = qr{//[^\n]*};                         # // C++/Java/C#-Kommentar
$GAENSE     = qr{"(?:\\.|[^"\\])*"};                # "String in Anführungszeichen"
$HOCHKOMMA  = qr{'(?:\\.|[^fl\\])*'};               # 'Hochkomma-String'
$text =~ s/($GAENSE|$HOCHKOMMA)|$KOMMENTAR|$KOMMENTAR2/$1/g;

Bereits diese Version ist recht schnell. Bei einem kleinen Test auf meinem betagten Rechner (Jahrgang 1997!) entfernt das Skript die Kommentare aus einer 16-Megabyte-Datei mit gut 500 000 Zeilen in 16,4 Sekunden. Das ist schnell, aber auch das werden wir noch verbessern.

Eine gut geführte Regex ist eine schnelle Regex

Mit ein bisschen Händchenhalten bringen wir die Maschine dazu, das Skript noch um einiges schneller zu verarbeiten. Betrachten wir normalen Text, also Programmzeilen, die weder Kommentare noch Strings enthalten. Bei jedem Zeichen testet die Maschine auf jede der vier Alternativen, und nur, wenn keine passt, geht das Getriebe zum nächsten Zeichen weiter. Hier wird viel eigentlich unnötige Arbeit aufgewendet.

Wir wissen nämlich, dass jede der Alternativen mit einem ganz bestimmten Zeichen beginnen muss: mit einem Schrägstrich, Hochkomma oder Anführungszeichen. Nur dieses Zeichen allein sagt noch nicht aus, ob hier wirklich ein Kommentar oder ein String beginnt, aber ohne ein solches Zeichen kann sicher keine der Alternativen passen. Statt dies auf dem langsamen, schmerzhaften Weg zu überprüfen, machen wir es der Regex-Maschine leichter und fügen ˹[^'"/]˼ als weitere Alternative hinzu. Eigentlich können wir gleich auf mehrere dieser Zeichen testen, also benutzen wir stattdessen ˹[^'"/]+˼. Wenn hier eine Warnlampe »Achtung: ewiges Matching« aufleuchtet, dann stimmt das nur, wenn wir in einer Schleife sind, die durch (...)* oder eine Abart davon erzeugt wird. In diesem Fall steht das [^'"/]+ aber für sich allein – es gibt kein folgendes Element, das durch Backtracking erkannte Zeichen wieder zurückfordern könnte. Damit besteht auch nicht die Gefahr, dass ein ewiges Matching auftreten könnte.

$SONST = qr{[^"'/]};  # keine der anderen Alternativen kann damit beginnen
  .
  . 
  .
$text =~ s/($GAENSE|$HOCHKOMMA|$SONST+)|$KOMMENTAR|$KOMMENTAR2/$1/g;

Aus Gründen, die sehr bald klar werden, habe ich den Plus-Quantor hinter das $SONST gesetzt und nicht im $SONST selbst.

Mit der hinzugefügten Alternative habe ich meinen Test wiederholt, und wahrhaftig: Durch diese kleine Änderung wurde die Regex fast viermal schneller! Wir haben die Regex sorgfältig konstruiert, so dass jetzt nicht mehr bei jedem Zeichen alle Alternativen durchgetestet werden müssen und erst danach zum nächsten Zeichen geschaltet werden kann. Es gibt noch immer Fälle wie ›c▵/3.14‹, bei denen diese Situation auftritt. Diese werden nach wie vor nach der alten, langsamen Methode behandelt.

Nun, es geht aber noch schneller.

  • Die am häufigsten benutzte Alternative wird wohl meistens ˹$SONST+˼ sein, also nehmen wir diese als erstes Element der Alternation. Das spielt für einen POSIX-NFA keine Rolle, weil dieser sowieso alle Alternativen auswerten muss, aber ein traditioneller NFA hört auf, sobald er einen Treffer gefunden hat. Warum sollen wir ihn länger als nötig nach relativ selten vorkommenden Mustern suchen lassen?
  • Nach einem String in Anführungszeichen oder Hochkommas ist es wahrscheinlich, dass zunächst wieder Zeichen aus der Klasse $SONST auftreten, bevor ein anderer String oder ein Kommentar kommt. Wenn wir zu jeder der String-Alternativen ein ˹$SONST*˼ hinzufügen, sagen wir der Regex-Maschine, dass sie mit dem gierigen Stern in $SONST potenziell sehr viele Zeichen erkennen kann, ohne in die äußere Schleife (die durch das /g gebildet wird) zurückzufallen.

    Das ist eine ähnliche Technik wie beim Aufbrechen der Schleife. Tatsächlich stammt viel vom Geschwindigkeitsgewinn beim Schleifenaufbrechen aus diesem Teilaspekt: Wir benutzen unser übergeordnetes Wissen über C-Programme dazu, die Regex-Maschine lokal optimiert zu programmieren.

    Beachten Sie, dass es sehr wichtig ist, dass das erste $SONST einen Plus-Quantor, die anderen dagegen einen Stern haben. Die Sterne sind notwendig, um aufeinanderfolgende Strings in Anführungszeichen oder Hochkommas zu erkennen. Wenn das Plus ein Stern wäre, würde das erste $SONST immer passen!

Mit diesen Änderungen erhalten wir:

˹($SONST+|$GAENSE$SONST*|$HOCHKOMMA$SONST*)|$KOMMENTAR|$KOMMENTAR2˼

Damit wird das Skript noch einmal etwa 5 % schneller.

Lehnen wir uns etwas zurück und überdenken die letzten zwei Änderungen. Wenn wir nach jedem gefundenen String gleich mit $SONST* auf normale Zeichen testen, dann kommt das ursprüngliche $SONST+ nur noch in zwei Situationen zum Zuge: ganz am Anfang des Strings und nach jedem erkannten Kommentar.

Man ist versucht zu denken: »Hm, den zweiten Fall können wir abdecken, indem wir den Kommentar-Ausdrücken ebenfalls ein $SONST* anhängen!« Schon, nur schütten wir damit das Kind mit dem Bade aus: Die $SONSTs müssen in den Klammern aufgefangen werden, alles außerhalb der Klammern wird ja gelöscht.

Wenn aber das vordere $SONST+ nur selten (ganz am Anfang, nach Kommentaren) gebraucht wird – wollen wir es wirklich am Anfang der Regex? Ich denke, das hängt von den Daten ab. Wenn ein Text mehr Kommentare als Strings in Anführungszeichen enthält, dann ist die aktuelle Version tatsächlich besser. Wenn die Häufigkeit umgekehrt ist, wäre es besser, den Unterausdruck weiter nach hinten zu verschieben. Mit meinen Testdaten schnitt die erste Möglichkeit tatsächlich besser ab. Die Umstellung macht etwa die Hälfte des Gewinns aus dem letzten Schritt zunichte.

Zusammenfassung

Sind wir damit fertig? Nie und nimmer! Immerhin sind die zwei Unterausdrücke für die Strings ideale Kandidaten für das Aufbrechen von Schleifen. Wenn wir dieser Methode schon einen langen Abschnitt in diesem Kapitel gewidmet haben, sollten wir sie auch anwenden. Mit den in unser Schema eingesetzten Ausdrücken

$GAENSE    = qr{"[^"\\]*(?:\\.[^"\\]*)*"};
$HOCHKOMMA = qr{'[^'\\]*(?:\\.[^'\\]*)*'};

sparen wir weitere 15 % ein. Mit wenigen Änderungen haben wir die Laufzeit von 16,4 auf 2,3 Sekunden gebracht – die Regex ist jetzt um mehr als den Faktor 7 schneller.

Diese letzte Änderung illustriert auch sehr gut, wie angenehm und übersichtlich es ist, wenn man eine große Regex aus Variablen aufbauen kann. Man kann die einzelnen Komponenten, beispielsweise $GAENSE, ziemlich unabhängig und isoliert von den anderen aufbauen und verändern und wird nicht durch andere Teile der Regex verwirrt. Es gibt noch immer Dinge, für die man die Regex als Ganzes betrachten muss (das Abzählen der Klammerpaare), aber dennoch ist die Technik äußerst nützlich.

Der qr/.../-Operator von Perl hilft dabei zusätzlich. Damit hat man in Perl so etwas wie Strings in Anführungszeichen, aber mit Schwergewicht auf regulären Ausdrücken. Exakt dieses Feature gibt es in anderen Sprachen nicht, aber in den meisten gibt es einen String-Typus, der sich besonders gut zum Aufbau von regulären Ausdrücken eignet (siehe dazu den Abschnitt Strings als reguläre Ausdrücke).

Sie werden den Aufbau von regulären Ausdrücken besonders zu schätzen wissen, wenn Sie die expandierte, vollständige Regex sehen. Sie steht hier aus Platzgründen auf zwei Zeilen:

([^"'/]+|"[^"\\]*(?:\\.[^"\\]*)*"[^"'/]*|'[^'\\]*
(?:\\.[^'\\]*)*'[^"'/]*)|/\*[^*]*\*+(?:[^/*][^*]*\*+)*/|//[^\n]*

  

<< 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