Ein Rezept zum Aufbrechen von Schleifen

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

Wenn wir das alles zusammenfügen, erhalten wir ˹"[^\\"]*(\\.[^\\"]*)*"˼ als Ausdruck, der Strings in Anführungszeichen erkennt, die geschützte Zeichen enthalten dürfen. Er erkennt exakt die gleichen Strings wie die frühere Version mit der Alternation und passt auch auf exakt die gleichen Strings nicht. Aber die Version mit der aufgebrochenen Schleife hat den Vorteil, dass sie während unserer Lebenszeit fertig wird. Sie ist effizienter und vermeidet das Problem des ewigen Matchings.

Das allgemeine Schema für solche Arten von Ausdrücken ist:

˹öffnend normal*(speziell normal*)* schließend˼

Ewiges Matching vermeiden

Drei wichtige Faustregeln sorgen dafür, dass bei ˹"[^\\"]*(\\.[^\\"]*)*"˼ nie ein ewiges Matching auftritt:

1. Der Anfang von ›speziell‹ und ›normal‹ darf nicht gleich sein

Die Unterausdrücke speziell und normal müssen so geschrieben sein, dass sie nicht an der gleichen Position passen können. In unserem laufenden Beispiel wird diese Regel befolgt. Normal ist ˹[^\\"]˼ und speziell ist ˹\\.˼. Diese können nie auf den gleichen String passen – der zweite Ausdruck fordert einen Backslash am Anfang, und der erste verbietet Backslashes explizit.

Andererseits können sowohl ˹\\.˼ als auch ˹[^"]˼ beginnend bei ›"Hallo▵\n"‹ einen lokalen Treffer erzielen und sind somit ungeeignete Unterausdrücke für speziell und normal. Wenn es eine Möglichkeit gibt, dass diese Treffer am gleichen Ort beginnen können, dann ist unklar, welcher Weg verfolgt werden soll, und daraus entsteht ein nicht-deterministisches Verhalten, ein ewiges Matching. Das ›m a k u d o n a r u d o‹-Beispiel (unter »Exponentielle« Mustersuche) illustriert diese Situation. Ein POSIX-NFA (oder auch ein traditioneller, wenn es keinen Treffer gibt) muss alle diese Permutationen und Möglichkeiten durchprobieren. Das wäre fatal, schließlich war ja der Grund für die Umformulierung gerade der, solche Situationen zu vermeiden.

Wenn wir sicherstellen, dass speziell und normal nie am gleichen Punkt passen können, dann wirkt speziell wie ein Kontrollpunkt, an dem ein mögliches nicht-deterministisches Verhalten von ˹(...)*˼ aufgehalten wird. Verschiedene Iterationen von ˹(...)*˼ könnten sich sonst um den gleichen Text streiten – genau das wird verhindert. Es gibt nur noch eine mögliche Sequenz von speziell und normal, auf die ein Text passen kann, und nicht mehr zigtausend mögliche Aufteilungen des Strings. Eine Sequenz zu überprüfen geht natürlich viel schneller als Tausende.

2. ›Speziell‹ muss mindestens ein Zeichen erkennen

Als zweites muss sichergestellt sein, dass speziell nicht auf »gar nichts« passen kann, es muss mindestens ein Zeichen aus dem String verbrauchen. Wenn es kein Zeichen verbrauchte, könnten aufeinanderfolgende Zeichen zu verschiedenen Iterationen des Sterns bei ˹(speziell normal*)*˼ passen, und das führt zurück zum (...*)*-Problem.

Die Wahl von beispielsweise ˹(\\.)*˼ für speziell verletzt diese Faustregel. Wenn wir versuchen, den berüchtigten Ausdruck ˹"[^\\"]*((\\.)*[^\\"]*)*"˼ auf ›Tubby‹ anzuwenden, muss die Maschine alle Permutationen ausprobieren, wie mehrere ˹[^\\"]*˼ auf ›Tubby‹ passen könnten, bis sicher ist, dass kein Treffer vorliegt. Weil speziell hier auch auf null Zeichen passen kann, fungiert es nicht als die Kontrollstelle, die es zu sein vorgibt.

3. ›Speziell‹ muss atomar sein

Text, der von einer Anwendung von speziell erkannt wird, darf nicht noch einmal von einer zweiten Anwendung erkannt werden. Nehmen wir als Problem das Erkennen von »leerem Raum« in Pascal-Programmen, also von Whitespace oder Kommentaren ({...} in Pascal). Die Regex für den Kommentar-Teil ist ˹\{[^}]*\}˼, und die ganze (ewige) Regex wäre ˹(\{[^}]*\}|●+)*˼. Hier könnte man speziell und normal so identifizieren:

speziell	normal
˹●+˼	˹\{[^}]*\}˼

In unser ˹normal*(speziell normal*)*˼-Rezept eingefügt, ergibt das den regulären Ausdruck ˹(\{[^}]*\})*(●+(\{[^}]*\})*)*˼. Wie passt dazu der String ›{Kommentar}●●●{noch●einer}●‹? Eine Reihe von Leerzeichen kann auf sehr viele verschiedene Arten passen: ein einziges ˹●+˼, viele ˹●+˼, von denen jedes nur ein einziges Leerzeichen erkennt, oder auch jede Kombination davon. Das ist völlig analog zur Situation bei ›m a k u d o n a r u d o‹.

Die Wurzel des Problems ist die, dass speziell auf eine kleine Menge Text passen kann, die Teil einer größeren Menge ist, auf die es auch passen kann. Durch die Klammerung mit (...)* ist das gleich auf vielerlei Arten möglich. Damit gibt es viele Wege, den gleichen Text zu erkennen – eine Pandorabüchse nicht-deterministischen Verhaltens.

Wenn es für die ganze Regex einen Treffer gibt, ist es wahrscheinlich, dass gleich der erste Versuch zutrifft, bei dem ein einziges ˹●+˼ alle Leerzeichen erkennt. Wenn es aber gar keinen Treffer gibt (in diesem Fall nur, wenn diese Regex Teil einer größeren ist, die fehlschlagen kann), dann muss die Maschine alle Permutationen der eigentlichen Regex ˹(●+)*˼ auf alle Leerzeichen-Reihen anwenden. Das braucht Zeit, und trotzdem wird kein Treffer gefunden. Weil speziell als Kontrollpunkt dienen sollte, gibt es nichts, was hier sein eigenes nicht-deterministisches Verhalten stoppt.

Die Lösung ist die, ein speziell zu wählen, das nur auf eine genaue Anzahl von Zeichen passt. Weil hier mindestens ein Leerzeichen gefordert ist, nehmen wir einfach ˹●˼ und überlassen vielleicht vorkommende weitere Leerzeichen dem umschließenden ˹(...)*˼. Das Beispiel dient zur Illustration, aber bei einer wirklichen Anwendung würde ich speziell und normal vertauschen und

˹●*(\{[^}]*\}●*)*˼

benutzen. Schließlich haben die meisten Pascal-Programme mehr Leerzeichen-Sequenzen als Kommentare, und es ist effizienter, die häufigere Variante als Normalfall zu behandeln.

Generelle Warnsignale

Wenn man diese Regeln einmal verstanden hat (dazu muss man sie vielleicht mehrmals durchlesen und eigene Erfahrungen sammeln), werden sie zu etwas wie Warnsignalen, anhand derer denen man mögliche »ewige Matchings« erkennt. Verschachtelte Quantoren wie ˹(...*)*˼ sind so ein Warnsignal, obschon es natürlich reguläre Ausdrücke gibt, in denen sie völlig gerechtfertigt sind, beispielsweise:

• ˹(Re:●*)*˼ findet eine Reihe von ›Re:‹ in einer Betreffzeile; wenn man eine hässliche Häufung wie ›Subject:●Re:●Re:●Re:●Hallo!‹ beseitigen will.
• ˹(●*\$[0-9]+)*˼ findet (optional durch Leerzeichen getrennte) Dollar-Beträge.
• ˹(.*\n)+˼ passt auf eine oder mehrere Zeilen. (Wenn aber der Punkt auf das Newline passt und danach ein lokaler Fehlschlag auftritt, ist dieser Ausdruck geradezu der Prototyp für ein ewiges Matching!)

Diese Beispiele sind gefahrlos, weil in jedem Fall ein Element vorhanden ist, das als Kontrollpunkt wirkt. Es gibt nicht »viele Wege, den gleichen Text zu erkennen«, und die Pandorabüchse bleibt zu. Im ersten Beispiel ist dieses Element ˹Re:˼, im zweiten das ˹\$˼ und im dritten das ˹\n˼ (wieder unter der Annahme, dass der Punkt nicht auf das Newline passt).

  

<< zurück

vor >>