"Vorgehensweise von NFA Maschinen" und "Backtracking"
[Seminarthemen WS07/08] [Übersicht] [Zurück]
Vorgehensweise von NFA Maschinen
Maschinen sind für das Verarbeiten von regulären Ausdrücken und Strings verantwortlich. NFA-Maschinen finden in den meisten Skript- und Programmiersprachen ihren Einsatz. Die andere, so genannte DFA Maschine, wird z.B. nur in egrep oder awk eingesetzt. NFA-Maschinen sind Regex-gesteuert. Das heißt NFA-Maschinen gehen den regulären Ausdruck Element für Element durch, sie arbeiten dabei von links nach rechts und vergleichen das aktuelle Element mit dem aktuellen Text aus dem String. Passt das Element auf den Text, setzt die Maschine beim nächsten Element fort und prüft weiter, bis alle Elemente passen. Dann passt der reguläre Ausdruck auch als Ganzes. Oder es wird festgestellt, dass der reguläre Ausdruck nicht passt.
[top]
Backtracking
Wenn die NFA-Maschine Alternativen hat, merkt diese sich die Alternativen bzw. markiert den Punkt, an dem sie Alternativen hat. Stellt sich ein Weg als Sackgasse heraus, kann die Maschine zu diesen Punkten zurückkehren und einen anderen Weg ausprobieren. Gibt es bei einer Alternative keinen richtigen Weg, muss die Maschine noch weiter zurück. Der Vorgang wird so lange wiederholt, bis der richtige Weg gefunden wurde oder festgestellt wird, dass es keinen passenden Weg gibt; mit anderen Worten: ob ein ganzer regulärer Ausdruck passt oder nicht.
Diese gespeicherten Punkte heißen Zustände. Von einem Zustand aus kann ein neuer Versuch mit einer Alternative begonnen werden. Es wird die Position im String und auch die im Regex gespeichert.
[top]