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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
