Rekursive reguläre Ausdrücke

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

Fast alle Aspekte des Regex-Dialekts von PHP wurden in allgemeiner Form unter Features und Dialekte behandelt, aber der Dialekt hält doch noch eine Überraschung bereit, die sonst nirgends zu finden ist: rekursive reguläre Ausdrücke.

Die Sequenz ˹(?R)˼ bedeutet »Wende die ganze Regex an diesem Punkt rekursiv an«, und ˹(?num)˼ bedeutet »Wende den Unterausdruck mit der Nummer num an diesem Punkt rekursiv an«. Zur zweiten Version gibt es auch die Variante mit benannten Klammerausdrücken, dafür wird die Notation ˹(?P>name)˼ verwendet.

In den nächsten Abschnitten werden einige Anwendungen für rekursive Ausdrücke vorgestellt. Rekursion spielt auch im größeren Programmbeispiel mit XML-Tags unter Tags auf korrekte Verschachtelung prüfen eine entscheidende Rolle.

Text mit verschachtelten Klammern parsen

Das Paradebeispiel für rekursive reguläre Ausdrücke sind Strings mit beliebig verschachtelten Klammern. Hier ist eine Möglichkeit: ˹(?:[^()]++|\((?R)\))*˼.

Diese Regex passt auf eine beliebige Anzahl der zwei Alternativen. Die erste, ˹[^()]++˼, passt auf alles außer Klammern. In diesem Fall wird die possessive Version des + verwendet, sonst könnte wegen des äußeren ˹(?:...)*˼ ein »ewiges Matching« eintreten (siehe Zurück zur Realität).

Bei der anderen Alternative, ˹\((?R)\)˼, wird es interessant. Diese Alternative passt auf ein Klammerpaar mit beliebigem Inhalt (allerdings mit korrekt verschachtelten Klammern). Der »beliebige Inhalt« ist wiederum das, worauf die ganze Regex passt, deshalb können wir einfach ˹(?R)˼ verwenden und die ganze aktuelle Regex rekursiv auf den Klammerinhalt anwenden.

Das funktioniert ganz gut, aber man muss beim Erweitern dieser Regex sehr vorsichtig vorgehen, weil jede Erweiterung rekursiv beim Aufruf von ˹(?R)˼ erneut angewandt wird.

Zum Beispiel könnte man auf die Idee kommen, mit dieser Regex einen ganzen String auf korrekt verschachtelte Klammern zu prüfen. Dazu könnte man sie einfach in ˹^...$˼ verpacken und so einen Treffer für den »ganzen String« erzwingen. Das ist ein Fehler, denn die hinzugefügten Zeilenanker könnten bei einem rekursiven Aufruf niemals passen.

Rekursiver Aufruf mit nummerierten Klammern

Das Konstrukt ˹(?R)˼ bezieht sich auf den gesamten regulären Ausdruck. Mit ˹(?num)˼ ist es möglich, für den rekursiven Aufruf nur den Unterausdruck aus der num-ten Klammer zu verwenden. (Anmerkung: Um ganz genau zu sein: ˹(?num)˼ braucht nicht unbedingt ein rekursiver Aufruf zu sein, anders gesagt, das Konstrukt ˹(?num)˼ muss selbst nicht unbedingt Teil des Unterausdrucks in der num-ten Klammer sein, es darf auch außerhalb dieses Klammerausdrucks vorkommen.)

Da die nullte Klammer einfach die ganze Regex ist, bedeutet ˹(?0)˼ dasselbe wie ˹(?R)˼.

Mit dieser Technik lässt sich das Problem aus dem vorhergehenden Abschnitt lösen: Wir verpacken die Regex zunächst in ein Klammerpaar und fügen erst dann die Zeilenanker ˹^...$˼ hinzu. Statt ˹(?R)˼ nehmen wir für den rekursiven Aufruf ˹(?1)˼. Damit wird nur der Teil der Regex in den eben hinzugefügten äußeren Klammern rekursiv verwendet, und dieser enthält die Zeilenanker nicht: ˹^((?:[^()]++|\((?1)\))*)$˼

Der unterstrichene Teil der Regex ist der Inhalt der ersten Klammer, und nur dieser Teil wird jedes Mal rekursiv angewendet, wenn ˹(?1)˼ erreicht wird.

Das folgende Programmstück gibt aus, ob der Text in der Variablen $text korrekt verschachtelte Klammern enthält:

Rekursiver Aufruf mit benannten Klammern

Wenn der Unterausdruck, der rekursiv angewandt werden soll, in einen benannten Klammerausdruck (siehe Benannte Unterausdrücke) eingepackt ist, kann die Notation (?P>name) verwendet werden (statt (?num) wie bisher). Damit wird unser Beispiel zu:

˹^(?P<krempel>(?:[^()]++|\((?P>krempel)\))*)$˼

Das ist recht kompliziert, aber mit dem x-Modifikator wird es lesbarer (siehe unter Pattern-Modifikatoren):

Ergänzendes zu possessiven Quantoren

Noch eine Bemerkung zu den possessiven Quantoren in der ursprünglichen Regex. Wenn der Stern bei der äußeren Klammer ˹(?:...)*˼ possessiv wäre, könnten wir auf das zweite ›+‹ in ˹[^()]++˼ verzichten. Damit diese Regex nicht in das schwarze Loch des »ewigen Matchings« gerät, muss mindestens einer der Quantoren possessiv sein. Wenn weder possessive Quantoren noch atomare Klammern (siehe Atomare Gruppen und possessive Quantoren verwenden) zur Verfügung stehen, müsste man den Quantor der ersten Alternative weglassen: ˹(?:[^()]|\((?R)\))*˼

Das ist zwar nicht so effizient, aber dafür wird das ewige Matching vermieden. Schneller wird die Regex wieder, wenn man die »Schleife aufbrechen«-Technik aus Die Kunst, reguläre Ausdrücke zu schreiben anwendet (siehe Die Schleife aufbrechen), das ergibt die Regex: ˹[^()]*(?:\((?R)\)[^()]*)*˼

Kein Backtracking mitten in die Rekursion

Im preg-Dialekt von PHP wird der rekursiv aufgerufene Unterausdruck so behandelt, als ob er in atomare Klammern verpackt wäre (siehe Atomare Gruppen und possessive Quantoren verwenden). Wenn die rekursive Klammer Text erkannt hat, der durch den Backtracking-Mechanismus teilweise zurückgegeben werden müsste, um einen Gesamttreffer zu finden – dann ist das eben kein Gesamttreffer, sondern ein Fehlschlag.

Das Wort »teilweise« im letzten Satz ist wichtig. Der Backtracking-Mechanismus kann durchaus Text, der auf eine rekursive Klammer gepasst hat, zurückgeben, aber nur den vollständigen Text. Verboten ist nur ein Backtracking zu einer Position mitten in den rekursiven Aufruf hinein.

Ein verschachteltes Klammerpaar finden

Wir haben gesehen, wie man eine Zeile auf korrekt verschachtelte Klammern prüft; hier der Vollständigkeit halber noch eine Regex, die in einem Text ein Klammerpaar erkennt, das wieder verschachtelte Klammerpaare enthalten kann: ˹\((?:[^()]++|(?R))*\)˼

Das Beispiel verwendet die gleichen Zutaten wie vorhin, diesmal aber etwas anders angeordnet. Wenn dieser Ausdruck als Teil einer größeren Regex eingesetzt werden soll, muss er wie vorhin in Klammern verpackt werden, und der rekursive Aufruf der ganzen Regex mit ˹(?R)˼ muss durch ˹(?1)˼ ersetzt werden (oder durch die Nummer der entsprechenden Klammer).