Backtracking und Gier

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

Bei Werkzeugen, die diese Art von Regex-gesteuerten NFA-Maschinen verwenden, ist es wichtig zu verstehen, wie das Backtracking abläuft. Damit kann man reguläre Ausdrücke schreiben, die einerseits natürlich tun, was sie sollen, es andererseits aber auch schnell erledigen. Wir haben gesehen, was bei ˹?˼ das gierige Verhalten ausmacht, nun werden wir die Gier des Sterns (und des Pluszeichens) untersuchen.

Backtracking beim Stern und beim Plus

Wenn wir die Regex ˹x*˼ als mehr oder weniger dasselbe wie ˹x?x?x?x?x?x?...˼ (oder besser ˹(x(x(x(x...?)?)?)?)?˼) betrachten, (Anmerkung: Sie erinnern sich, dass für eine DFA-Maschine das äußere Aussehen der Regex nur eine unwesentliche Rolle spielt. Für einen DFA sind die drei Formen identisch.) ist das nicht allzu verschieden vom eben Untersuchten. Bevor auf die durch den Stern quantifizierte Komponente getestet wird, speichert die Maschine den aktuellen Zustand ab, damit bei einem späteren Fehlschlagen darauf zurückgegriffen werden kann. Das wird wieder und wieder so gemacht, bis ein Test, der vom Stern eingeleitet wurde, irgendwann fehlschlägt.

Wenn wir also ˹[0-9]+˼ angewendet auf ›eine●1234●Zahl‹ verfolgen, wird ˹[0-9]˼ nach der 4 fehlschlagen. Bis dahin sind vier Zustände abgespeichert worden, die Maschine hat also vier Positionen im String, zu denen sie zurückkehren und die Suche neu aufnehmen kann:

eine 1▵234 Zahl
eine 12▵34 Zahl
eine 123▵4 Zahl
eine 1234▵ Zahl

Diese vier entstehen aus der Tatsache, dass der Versuch mit ˹[0-9]˼ an diesen Stellen optional ist. Wenn die Maschine beim Leerzeichen einen Fehlschlag findet, geht sie zurück zum letzten gespeicherten Zustand (dem letzten in der Liste) und macht bei ›eine●1234▵●Zahl‹ im Text und bei ˹[0-9]+▵˼ in der Regex weiter. Nun, das ist das Ende der Regex, aber die Maschine erkennt das erst jetzt. Nachdem die Regex vollständig durchlaufen ist, ist auch das Matching beendet, und wir haben einen Treffer gefunden.

In der obigen Liste fehlt die Position ›eine●▵1234●Zahl‹ im String, weil die erste Ziffer beim Plus-Quantor nicht optional ist. Wäre diese Position in der Liste, wenn wir die Regex ˹[0-9]*˼ benutzt hätten? (Achtung, Fangfrage!) Zur Auflösung siehe Lösung 11.

Ein größeres Beispiel neu betrachtet

Mit unserem genaueren Wissen wollen wir uns nun das ˹^.*([0-9][0-9])˼-Beispiel (siehe den Abschnitt Zu gierig) noch einmal vornehmen. Statt nur festzustellen, dass die »Gier« zu dem gefundenen Treffer führt, können wir das jetzt mit unseren Kenntnissen über die NFA-Mechanik exakt erklären.

Ich benutze ›CH-8032●Zürich‹ als Beispiel. Wenn das erfolgreich ˹.*˼ bis an das Ende des Strings vorgestoßen ist, gibt es vierzehn abgespeicherte Zustände, weil der Punkt mit dem Stern an 14 Stellen optionale (im Notfall nicht wirklich benötigte) Zeichen angetroffen hat. Diese Zustände besagen, dass die Maschine die Suche an der Stelle ˹^.*▵([0-9][0-9])˼ in der Regex und an allen 14 Positionen im String wieder aufnehmen kann.

Nun sind wir am Ende des Strings und testen auf das erste ˹[0-9]˼, was natürlich nicht geht. Kein Problem, wir haben einen abgespeicherten Zustand (sogar ein gutes Dutzend). Wir gehen mittels Backtracking zurück zum letzten gespeicherten Zustand, also zu dem, bevor das ˹.*˼ das h am Ende erkannt hatte. Das Zurücknehmen dieses lokalen Treffers, das »Un-Matching«, führt zum Test von ˹[0-9]˼ gegen h. Der geht schief.

Dieser Backtrack-und-Test-Zyklus geht weiter, bis die Maschine zurückkrebsend bei der 2 ankommt; dann passt das erste ˹[0-9]˼. Das zweite hingegen passt nicht, daher müssen wir weitere lokale Treffer zurücknehmen. Jetzt spielt es keine Rolle mehr, dass das erste ˹[0-9]˼ gerade vorhin noch gepasst hat; das Backtracking geht zu einem Zustand, der die Regex in der Position vor dem ersten ˹[0-9]˼ beschreibt. Dieser Zustand ist auch der mit der Position genau vor der 3, also passt das erste ˹[0-9]˼ erneut. Diesmal passt nämlich auch das zweite (auf die 2). Damit haben wir einen Treffer für den gesamten Ausdruck, nämlich ›CH-8032●Zürich‹, und der Variablen $1 wird 32 zugewiesen.

Ein paar Beobachtungen: Beim Backtracking wird nicht nur die Position in der Regex und im Text abgespeichert, sondern auch der Zustand jedes Klammerpaars mit dem von ihm gefundenen Text, damit die Maschine wieder zum gleichen Zustand zurückkehren kann. Bei diesem Beispiel gingen die Backtracks immer zum Zustand bei ˹^.*▵([0-9][0-9])˼ zurück. Was das Finden von Treffern angeht, ist das dasselbe wie ˹^.*▵[0-9][0-9]˼. Nun spielt es aber eine Rolle, ob beim Vor- und Zurückgehen in der Regex auch Klammern betreten und verlassen werden, denn jedes Mal muss der Wert nachgeführt werden, der schließlich $1 bestimmen wird, und das hat Auswirkungen auf die Effizienz der ganzen Operation.

Eine letzte Beobachtung, die Ihnen vielleicht schon ganz klar ist: Elemente, die von einem Stern (oder einem anderen gierigen Quantor) bestimmt werden, »fressen« zunächst immer so viel wie möglich, ohne Rücksicht darauf, was später in der Regex folgt. In unserem Beispiel weiß die Maschine bei ˹.*˼ nicht, dass sie vielleicht bei der ersten Ziffer aufhören sollte oder bei der zweitletzten Ziffer oder irgendwo sonst. Sie sucht blind nach passenden Zeichen, bis der Punkt am Ende nicht mehr passt. Wir hatten dieses Verhalten schon früher gesehen, als der ˹[0-9]+˼-Teil des Ausdrucks ˹^.*([0-9]+)˼ nie mehr als eine einzige Ziffer erkannt hatte (siehe den Abschnitt Zu gierig).

  

<< zurück

vor >>