Backtracking

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

Get Reguläre Ausdrücke, 3rd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.