Backtracking bei Lookaround

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

Es ist wahrscheinlich nicht auf den ersten Blick klar, dass auch das Lookaround (unter Erweiterte einführende Beispiele eingeführt, siehe Große Zahlen in Dreiergruppen aufteilen: Lookaround) eng mit atomaren Gruppen und possessiven Quantoren verwandt ist. Es gibt vier Typen von Lookaround: jeweils positive und negative Versionen von Lookahead und von Lookbehind. Sie testen, ob ihr Unterausdruck ab der aktuellen Position (Lookahead) oder bis zu dieser Position (Lookbehind) passen kann oder nicht.

Wenn wir ein bisschen tiefer schürfen – wie funktioniert das Lookaround in unserer NFA-Welt von gespeicherten Zuständen und Backtracking? Wenn ein Unterausdruck in einer Lookaround-Klammer angewendet wird, geschieht das in einer eigenen, kleinen Welt. Es werden, wenn notwendig, Zustände abgespeichert und Backtracking-Operationen ausgeführt. Was passiert, wenn der ganze Unterausdruck ausgewertet ist und gepasst hat? Beim positiven Lookaround wird der ganze Unterausdruck als Erfolg gewertet, und beim negativen Lookaround als Fehlschlag. In beiden Fällen geht es nur darum, ob ein Treffer für den Lookaround-Unterausdruck gefunden wurde (und wir haben eben gesagt, dass das so ist), und die ganze »kleine Welt« des Lookaround inklusive aller dabei gespeicherten Zustände wird einfach weggeworfen.

Und was passiert, wenn der Ausdruck in der Lookaround-Klammer nicht passt? Weil er nur in seiner »kleinen Welt« arbeitet, sind ihm nur die Zustände zugänglich, die innerhalb der Lookaround-Klammer erzeugt wurden. Wenn beim Backtracking der Anfang dieser Klammer erreicht wird, bedeutet das, dass der aktuelle Unterausdruck nicht passt. Bei positivem Lookaround bedeutet das einen Fehlschlag, bei negativem Lookaround einen Erfolg. In beiden Fällen sind aber keine gespeicherten Zustände mehr vorhanden, die vom Lookaround-Konstrukt herrühren – sonst wäre ja dieses Konstrukt nicht vollständig ausgewertet worden –; die ganze »kleine Welt« hat also wie von selbst aufgehört zu existieren.

In allen Fällen bleiben also von einem Lookaround-Konstrukt keinerlei gespeicherte Zustände zurück. Wenn am Ende der Lookaround-Klammer wie beim erfolgreichen positiven Lookahead noch gespeicherte Zustände vorhanden sind, werden diese beim Verlassen der Klammer weggeworfen. Wo ist uns dieses Wegwerfen von Zuständen schon begegnet? Natürlich: bei den atomaren Gruppen und den possessiven Quantoren.

Atomare Gruppen mit positivem Lookahead imitieren

Bei Dialekten, die atomare Gruppen unterstützen, ist dies wohl vor allem eine akademische Übung. Bei den anderen Dialekten gilt Folgendes: Wenn positiver Lookahead unterstützt wird und wenn innerhalb eines Lookahead-Konstrukts einfangende Klammern vorkommen dürfen (das ist bei den meisten Dialekten so, nicht aber bei Tcl), dann kann man damit atomare Gruppen oder possessive Quantoren emulieren. ˹(?>Regex kann durch ˹(?=(Regex))\1˼ ersetzt werden. Vergleichen wir beispielsweise ˹^(?>\w+):˼ mit ˹^(?=(\w+))\1:˼.

Bei der Version mit Lookahead versucht ˹\w+˼, so viel wie möglich abzukriegen, ein ganzes Wort. Weil es in einem Lookaround-Konstrukt vorkommt, werden die dabei gespeicherten Zustände beim Erreichen der schließenden Klammer weggeworfen (So wie das auch bei einer atomaren Gruppe geschähe). Im Gegensatz zu einer atomaren Gruppe werden die vom Lookahead-Konstrukt erkannten Zeichen nicht Teil des Gesamttreffers (das ist ja der Zweck des Lookaheads), aber sie sind von den einfangenden Klammern gespeichert worden. Das ist der springende Punkt, denn wenn wir danach die Rückwärtsreferenz ˹\1˼ anwenden, wurde diese gerade vorher durch das Lookahead-Konstrukt definiert, deshalb ist auch garantiert, dass das ˹\1˼ passt. Mit diesem zusätzlichen Schritt wird eigentlich nur die aktuelle Position der Regex-Maschine hinter das bereits erkannte Wort verschoben.

Diese Methode ist etwas weniger effizient als echte atomare Klammern, weil mit ˹\1˼ schon vorher gefundener Text ein zweites Mal gesucht werden muss. Weil aber unnütze gespeicherte Zustände weggeworfen werden, ist die gesamte Regex dennoch schneller als ein bloßes ˹\w+:˼, wenn im Suchstring kein Doppelpunkt vorkommt.

  

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