Gespeicherte Zustände

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

In der NFA-Terminologie heißen die Brotbrocken gespeicherte Zustände (saved states). Ein Zustand beschreibt eine Situation, von der aus ein neuer Versuch mit einer anderen Variante begonnen werden kann. Er enthält sowohl die Position im String als auch die Position in der Regex an einem Punkt, an dem eine noch nicht ausgewertete Möglichkeit beginnt. Weil das die Grundlage für das NFA-Matching bildet, erläutere ich dies nochmals ausführlicher mit anderen Beispielen. Wem die bisherige Beschreibung genügt, der mag das Folgende überspringen.

Ein Treffer ohne Backtracking

Wir betrachten ein einfaches Beispiel: ˹ab?c˼ wird auf abc angewendet. Nachdem das ˹a˼ am Anfang gefunden wurde, ist der aktuelle Zustand folgender:

im Text: ›a▵bc‹

in der Regex: ˹a▵b?c˼

Nun kommt in der Regex das ˹b?˼ an die Reihe, und die Maschine muss entscheiden, ob mit ˹b˼ ein Versuch gemacht werden soll. Weil das Fragezeichen gierig ist, wird dieser Versuch gestartet, nicht aber, ohne den Zustand

im Text: ›a▵bc‹

in der Regex: ˹ab?▵c˼

in der bisher leeren Liste von gespeicherten Zuständen abzulegen. Damit kann die Maschine später zu diesem Punkt genau hinter dem ˹b?˼ zurückkehren bzw. zum Punkt genau vor dem b im String (mit anderen Worten, zum aktuellen Zustand). Dadurch wird das Fragezeichen übersprungen.

Nachdem die Maschine hier Brotbröcklein zurückgelassen hat, wird auf das in der Regex folgende ˹b˼ getestet; der neue aktuelle Zustand sieht so aus:

im Text: ›ab▵c‹

in der Regex: ˹ab?▵c˼

Auch das ˹c˼ am Ende passt, und damit haben wir einen Treffer für den ganzen regulären Ausdruck erzielt. Der eine gespeicherte Zustand wird nicht mehr benötigt und einfach weggeworfen.

Ein Treffer nach einem Backtracking

Wenn der zu prüfende String ›ac‹ ist, wäre hier bis zum Versuch mit ˹b˼ alles gleich. Dieses Mal wird aber kein b im String gefunden. Damit hat sich der begonnene Weg, der vom Versuch mit ˹...?˼ ausging, als Sackgasse herausgestellt. Da es gespeicherte Zustände gibt, bedeutet dieser »lokale Fehlschlag« nicht automatisch auch einen globalen. Die Maschine führt ein Backtracking durch, damit wird der zuletzt gespeicherte Zustand zum neuen aktuellen Zustand. In diesem Fall ist das der Zustand:

im Text: ›a▵c‹

in der Regex: ˹ab?▵c˼

Dieser wurde als noch nicht getesteter, möglicher Weg gespeichert, bevor der Test mit ˹b˼ begonnen wurde. Dieses Mal passt ˹c˼ auf c, und wir haben einen Treffer für den ganzen regulären Ausdruck.

Ein Fehlschlag

Nun betrachten wir den gleichen Ausdruck, angewandt auf den String abX. Vor dem Versuch mit ˹b˼ wird wegen des Fragezeichens der Zustand

im Text: ›a▵bX‹

in der Regex: ˹ab?▵c˼

abgespeichert. Das ˹b˼ passt, aber diese Straße führt später in eine Sackgasse, weil das ˹c˼ nicht auf das X passt. Dieser lokale Fehlschlag führt zum Backtracking zum gespeicherten Zustand. Die Maschine vergleicht nun ˹c˼ mit dem b, dem durch das Backtracking sozusagen »der Treffer aberkannt« wurde. Auch dieser Test schlägt natürlich fehl. Wenn jetzt andere gespeicherte Zustände vorhanden wären, würden weitere Backtrackings ausgeführt; in diesem einfachen Beispiel ist es nur einer, und damit ist der gesamte Versuch an der aktuellen Position fehlgeschlagen.

Sind wir jetzt fertig? Nein, denn das »Getriebe« wird nun zum nächsten Zeichen weiterschalten und den ganzen regulären Ausdruck erneut auf den restlichen Teil des Strings loslassen. Das kann in gewisser Weise als Pseudo-Backtracking angesehen werden. Das Matching wird bei

im Text: ›a▵bX‹

in der Regex: ˹▵ab?c˼

wieder aufgenommen. Die ganze Regex wird hier neu appliziert, aber wie vorher enden alle Versuche im Nichts. Nachdem die nächsten zwei Versuche (von ab▵X und abX▵ ausgehend) auch fehlschlagen, wird für das ganze Problem ein negatives Resultat zurückgegeben.

Ein ›genügsamer‹, nicht-gieriger Treffer

Wir kehren zum ursprünglichen Beispiel zurück, diesmal aber mit einem nicht-gierigen Quantor: ˹ab??c˼ wird auf abc angewendet.

im Text: ›a▵bc‹

in der Regex: ˹a▵b??c˼

Jetzt kommt der Teil ˹b??˼ zum Zuge, und die Maschine muss entscheiden, ob sie die Möglichkeit ˹b˼ ausprobiert oder überspringt. Da ein nicht-gieriger Quantor vorhanden ist (??), wird die Möglichkeit beim ersten Versuch nicht ausprobiert. Damit an diesem Punkt später die andere Möglichkeit ausprobiert werden kann, wird

im Text: ›a▵bc‹

in der Regex: ˹a▵bc˼

in die noch leere Liste von gespeicherten Zuständen aufgenommen. Damit kann die Maschine später an der Position genau vor dem b im Text den Versuch mit ˹b˼ machen. (Wir wissen, dass das passen wird, aber die Regex-Maschine weiß das noch nicht; sie weiß auch nicht, dass sie diesen Versuch dereinst ausführen wird.) Wenn der Zustand abgespeichert ist, geht die Maschine weiter:

im Text: ›a▵bc‹

in der Regex: ˹ab??▵c˼

Das ˹c˼ passt nicht auf ›b‹, die Maschine muss also wirklich mittels Backtracking zu dem einen gespeicherten Zustand zurück.

im Text: ›a▵bc‹

in der Regex: ˹a▵bc˼

Dieses Mal wird die Möglichkeit tatsächlich ausprobiert. Diese passt, und das ˹c˼ danach passt auf das ›c‹. Wir haben den gleichen globalen Treffer erzielt wie mit dem gierigen Quantor, aber auf einem anderen Weg.

  

<< zurück

vor >>