Backtracking

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

Das Wesentliche beim NFA-Matching ist Folgendes: Die NFA-Maschine untersucht jeden Unterausdruck der Reihe nach. Wenn sie zwischen zwei Möglichkeiten entscheiden soll, wählt sie die eine, erinnert sich aber an die andere.

Solche Wahlmöglichkeiten gibt es bei jedem Quantor (der auf viele Arten passen kann) und bei jeder Alternation (welche Alternative soll jetzt ausprobiert werden, welche später).

Wenn die gewählte Richtung zum Ziel führt und auch der Rest der Regex passt, ist ein Treffer gefunden und die Mustersuche beendet. Wenn aber mit dieser Wahl kein Treffer gefunden wird, weiß die Maschine, wohin sie zurückkehren muss, um andere Möglichkeiten auszuprobieren. Auf diese Art kann der Automat alle möglichen Permutationen der Regex durchspielen (oder wenigstens so viele, bis ein Treffer gefunden wird). Dieses »Zurückkehren zu Verzweigungen« nennt man Backtracking.

Backtracking wie Hänsel und Gretel

Backtracking ist etwa wie das Zurücklassen von Brotbrocken an jeder Weggabelung. Wenn sich die gewählte Richtung als Sackgasse herausstellt, kann man den Weg zurückgehen, bis man Brotkrumen findet. Wenn auch dieser Weg eine Sackgasse ist, muss vielleicht weiter zurückgegangen werden, bis entweder der richtige Weg gefunden ist oder bis es keine Wege mehr gibt, die noch nicht beschritten worden sind.

Es gibt mehrere Situationen, in denen die Regex-Maschine zwischen zwei oder mehr Möglichkeiten wählen muss – die Alternation im Beispiel ist eine. Bei einem Regex-Element wie ˹...x?...˼ muss die Maschine entscheiden, ob sie ˹x˼ testen will oder ob sie das auf später verschiebt. Bei ˹...x+...˼ hat sie keine Wahl, dieser Weg muss genommen werden – das Plus verlangt mindestens ein Zeichen, das passt. Wenn aber ein erstes ˹x˼ gefunden wird, gibt es keine weitere Einschränkung mehr, und die Maschine muss entscheiden, ob jetzt nach einem zweiten ˹x˼ gesucht werden soll – und dann nach einem dritten, einem weiteren usw. An jeder derartigen Entscheidungsstelle lässt die Maschine ein symbolisches grimmsches Brotbröcklein zurück, als Erinnerungsstütze, dass hier noch andere Optionen möglich sind.

Ein bröckliges Beispiel

Wir betrachten wieder unsere ˹to(nite|knight|night)˼-Regex, angewendet auf den String ›hottonictonight!‹ (etwas gesucht, aber ein gutes Beispiel). Zunächst wird versucht, ob die erste Komponente ˹t˼ auf den Anfang des Strings passt. Sie passt nicht auf h, damit schlägt auch der ganze reguläre Ausdruck an dieser Position fehl. Das Getriebe schaltet zum nächsten Zeichen, auch das passt nicht, und zum dritten. Diesmal passt zwar das ˹t˼, aber das folgende ˹o˼ nicht, und daher schlägt der ganze Versuch fehl.

Der Versuch, der irgendwann später bei ...▵tonic... beginnt, ist interessanter. Nachdem das to erkannt wurde, hat die Maschine drei Alternativen vor sich. Sie wählt davon eine und merkt sich die Verzweigungsstelle, »lässt Brotkrumen zurück«, für den Fall, dass die gewählte Variante scheitert. Nehmen wir an, die Maschine wählt ˹nite˼. Dieser Unterausdruck zerfällt in »˹n˼ + ˹i˼ + ˹t˼ ...«, der bis zu ...toni▵c... vorstößt. Anders als bei den vorherigen Fehlschlägen bestehen jetzt aber noch Alternativen; die Maschine muss nicht zum Anfang zurück und im String ein Zeichen weiterschalten. Sie wählt die nächste Alternative, sagen wir ˹knight˼, diese schlägt aber sofort fehl. Übrig bleibt die dritte, ˹night˼, aber auch die passt irgendwann nicht mehr. Das war die letzte Möglichkeit, damit ist der ganze von ...▵tonic... ausgehende Versuch fehlgeschlagen, und das Getriebe muss zum nächsten Zeichen weiterschalten.

Wenn die Maschine bei ...▵tonight! angelangt ist, wird der neue Versuch wieder interessant. Diesmal passt die ˹night˼-Alternative bis zum Ende des regulären Ausdrucks. Damit hat der ganze reguläre Ausdruck gepasst, und die Maschine kann ein erfolgreiches Matching zurückgeben.

  

  

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