Verschachtelte Paare mit dynamischen regulären Ausdrücken erkennen

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

Die Hauptanwendung von dynamischen Konstrukten ist das Erkennen von beliebig tief verschachtelten klammerartigen Konstrukten (etwas, das zuvor mit regulären Ausdrücken unmöglich schien). Das Paradebeispiel dafür ist das Erkennen von Klammerausdrücken beliebiger Verschachtelungstiefe. Damit wir sehen, warum das so spannend ist, schauen wir uns erst an ein paar Beispielen an, warum das mit herkömmlichen regulären Ausdrücken nicht geht.

Diese einfache Regex erkennt Text in Klammern: ˹\(([^()])*\)˼. Innerhalb der Klammern sind weder öffnende noch schließende Klammern erlaubt, also keine verschachtelten Klammern (anders gesagt, die Regex erlaubt lediglich eine Verschachtelungstiefe von Null). Wir könnten dies in ein Regex-Objekt einbauen und wie im folgenden Beispiel verwenden:

Damit erkennt die Regex einen Funktionsaufruf wie »substr($str, 0, 3)«, nicht aber einen wie »substr($str, 0, (3+2))«, weil darin verschachtelte Klammern vorkommen. Wir erweitern unsere Regex so, dass sie diese erkennt und eine Verschachtelungstiefe von Eins erlaubt.

Wir wollen also eingeklammerten Text innerhalb der äußeren Klammer zulassen. Wir erweitern den Unterausdruck zwischen den äußeren Klammern, der bisher ˹[^()]˼ war, und fügen einen Unterausdruck hinzu, der geklammerten Text erkennt. Das ist ja gerade unser eben erzeugtes Objekt $Tiefe0. Damit können wir eine Regex für die Verschachtelungstiefe Eins aufbauen:

Die Regex $Tiefe0 ist genau die gleiche wie vorher; daraus bauen wir die Regex $Tiefe1 auf, die ihr eigenes Klammerpaar plus das Klammerpaar von $Tiefe0 erkennt. Das entspricht der Verschachtelungstiefe Eins.

Für die nächste Verschachtelungstiefe gehen wir nach dem gleichen Rezept vor und bekommen die Regex $Tiefe2, die aus $Tiefe1 aufgebaut ist (welche wiederum auf $Tiefe0 aufbaut):

Wir können das Spiel ewig weiterspielen:

In der folgenden Abbildung ist das Vorgehen für die ersten paar Verschachtelungstiefen illustriert.

Abbildung: Reguläre Ausdrücke für verschiedene Verschachtelungstiefen.

Es ist ganz interessant, sich die expandierten Ausdrücke für die verschiedenen Verschachtelungstiefen einmal anzusehen, hier beispielsweise für $Tiefe3:

Unschön, so etwas.

Zum Glück müssen wir uns da nicht hindurchkämpfen (das ist Sache der Maschine). Der Ansatz mit den Tiefe-Variablen funktioniert ganz gut bis zu einer bestimmten Verschachtelungstiefe, aber eben nicht für beliebige Verschachtelungen. (Wenn wir Verschachtelungen bis zur Tiefe X vorsehen, kommen uns sicher nach Murphys Gesetz Daten mit X+1-facher Verschachtelung unter.)

Mit dynamischen Regex-Konstrukten können wir das aber erreichen. Dazu müssen wir uns klarmachen, dass alle $Tiefe-Variablen nach der allerersten auf identische Weise aufgebaut sind: Wenn eine weitere Verschachtelungstiefe benötigt wird, baut man einfach die Variable der Zeile darüber ein. Wenn die Zeilen alle praktisch identisch sind, sollte es doch irgendwie möglich sein, »sich selbst« einzubauen. Wenn das gelänge, könnte man jede Verschachtelungstiefe bewältigen.

Genau so etwas ist mit dynamischen Regex-Konstrukten möglich. Wenn wir ein Regex-Objekt der in Art der $Tiefe-Variablen aufbauen, können wir aus dem Code-Konstrukt innerhalb der Regex darauf zugreifen. (Das Konstrukt kann jede Art von Perl-Code enthalten, solange das Resultat als Regex interpretiert werden kann; hier ist es Perl-Code, der lediglich ein bereits existierendes Regex-Objekt zurückgibt.) Wenn wir unser $Tiefe-artiges Regex-Objekt in $Tiefe_N haben, können wir mit ˹(??{$Tiefe_N})˼ darauf zugreifen:

Das passt auf beliebig verschachtelte Klammerausdrücke und kann anstelle unseres früheren $Tiefe0 benutzt werden:

Ha! Ein bisschen muss man die Hirnwindungen schon anstrengen, aber wenn es einmal geklickt hat, springen einem überall Anwendungen für diese Technik ins Auge.

Die grundlegende Technik kennen wir, jetzt geht es um die Feinheiten. Die einfangenden Klammern können wir durch nicht-einfangende oder besser gleich atomare Klammern ersetzen (wir fangen nichts ein, und das Backtracking spielt auch keine Rolle). Wenn wir atomare Klammern verwenden, können wir auch ˹[^()]˼ durch ˹[^()]+˼ ersetzen (sonst nicht, wir erhielten dann konkurrierende Quantoren und ein ewiges Matching, siehe unter Zurück zur Realität).

Als letzte Verbesserung verschiebe ich ˹\(˼ und ˹\)˼ so, dass sie das dynamische Konstrukt umschließen. So wird das dynamische Regex-Konstrukt nur dann aufgerufen, wenn es wirklich verschachtelte Klammern gibt. Die verbesserte Version sieht wie folgt aus:

Nun gibt es kein äußeres Klammerpaar ˹\(...\)˼ mehr, wir müssen es bei der Verwendung von $Tiefe_N explizit angeben. Dafür können wir die Regex jetzt auch dann anwenden, wenn Klammerpaare auftauchen könnten, nicht nur an Orten, wo bereits Klammerpaare sind.

Wir werden diese $Tiefe_N-Regex in einem Programm bei Possessive Quantoren in Perl nachbilden erneut benutzen.