Zwei wichtige Regeln beim Backtracking

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

Die Idee hinter dem Backtracking ist recht einfach, aber in der Praxis gibt es einige Feinheiten, die wichtig sind. Nämlich: Was soll die Maschine zuerst wählen, wenn mehrere Möglichkeiten offenstehen? Und: Welche der gespeicherten Möglichkeiten soll versucht werden, wenn Backtracking erzwungen wird? Die erste Frage wird durch das folgende Prinzip beantwortet:

In Situationen, bei denen eine Wahl zwischen »die Möglichkeit ausprobieren« und »die Möglichkeit nicht ausprobieren« besteht – wie etwa bei Unterausdrücken mit einem Quantor –, wird die Maschine bei einem gierigen Quantor die Möglichkeit zunächst immer ausprobieren, bei einem nicht-gierigen Quantor dagegen als Erstes die Möglichkeit überspringen.

Diese Regel hat weitreichende Auswirkungen. Zunächst erklärt sie, warum Quantoren gierig sind, wenn auch nicht ganz vollständig. Um das zu verstehen, müssen wir wissen, welcher der (vielleicht sehr zahlreichen) gespeicherten Wege beschritten wird, wenn das Backtracking einsetzt. Einfach ausgedrückt:

Wenn das Backtracking durch einen Fehlschlag ausgelöst wird, wird die zuletzt gespeicherte Möglichkeit angesteuert. Das ist ein LIFO-Verhalten.

In der Brotbrocken-Analogie ist das sehr klar: Wenn sich ein Weg als Sackgasse herausstellt, geht man zurück bis zum letzten Brotkrümel, nicht weiter. Die übliche Analogie zu LIFOs ist ein Stapel, und auch diese stimmt. Zum Beispiel ist bei Tellern im Küchenschrank der zuletzt aufgestapelte Teller auch der, den man als ersten wieder herausnimmt.

  

<< zurück

vor >>