NFA, DFA und POSIX
(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)
Der »längste früheste Treffer«
Fassen wir noch einmal das Verhalten eines DFA zusammen: Wenn das Getriebe einen DFA auf einen bestimmten Punkt im String ansetzt, findet dieser den von da aus längstmöglichen Treffer, und damit hat es sich. Weil dies von den möglichen Treffern der längste und auch derjenige ist, der am weitesten links beginnt, sprechen wir vom »längsten frühesten Treffer«.
Wirklich der längste Treffer
Was der längste Treffer ist, betrifft nicht nur die Alternation. Betrachten wir, wie ein NFA den regulären Ausdruck ˹motor(rad)?(radfahren)?˼ auf den String motorradfahren anwendet. Der NFA findet zunächst einen lokalen Treffer für ˹motor˼, dann passt das gierige ˹(rad)?˼, und damit bleibt nur noch übrig, den Ausdruck ˹(radfahren)?˼ mit fahren zu vergleichen. Das passt nicht, macht aber nichts, denn der Ausdruck ist optional, und schon sind wir am Ende der Regex. Der traditionelle NFA findet also motorradfahren und kümmert sich nicht um die gespeicherten Zustände (bei einem POSIX-NFA ist das anders, wie Sie bald sehen werden).
Ein DFA dagegen findet das längere motorradfahren. Ein NFA würde diesen Treffer auch finden, wenn das erste ˹(rad)?˼ irgendwie zurückgegeben würde. Dann käme das ˹(radfahren)?˼ zum Zuge. Ein traditioneller NFA tut das nicht, ein DFA schon, denn es ist der längste mögliche Treffer beim aktuellen Versuch. Der DFA kann das, weil er zu jedem Zeitpunkt die Übersicht über alle möglichen Treffer hat und so den längsten auswählen kann.
Ich habe dieses Beispiel gewählt, weil man darüber in einfachen Worten reden kann. Aber dieser Punkt spielt schon eine Rolle, auch in der Praxis. Eine häufige Situation ist zum Beispiel die, dass man bei einem Matching auch Fortsetzungszeilen erwischen will. Häufig ist es in Konfigurationsdateien und Ähnlichem erlaubt, eine einzige logische Zeile mit einem Backslash vor dem Newline auf weitere Zeilen zu verteilen, wie etwa in:
SRC=array.c builtin.c eval.c field.c gawkmisc.c io.c main.c \
missing.c msg.c node.c re.c version.c
Um eine einfache »var = wert«-Zeile zu finden, würde man wohl etwas wie ˹^\w+=.*˼ benutzen, aber das kümmert sich nicht um Fortsetzungszeilen (ich nehme für dieses Beispiel an, dass der Punkt nicht auf das Newline passt). Damit dies auch mit Fortsetzungszeilen funktioniert, könnte man ein ˹(\\\n.*)*˼ an die Regex anhängen. Wir erhalten so ˹^\w+=.*(\\\n.*)*˼. Das soll offenbar auf jede weitere Zeile passen, sofern diese auf ein Newline mit Backslash davor folgt. Das sieht vernünftig aus, wird aber mit einem traditionellen NFA nicht funktionieren. Wenn das erste ˹.*˼ das erste Zeilenende erreicht, ist es schon über den Backslash hinaus, und keines von den neuen Elementen in der Regex erzwingt ein Backtracking (siehe unter Regel 2: Die normalen Quantoren sind gierig). Dagegen findet ein DFA tatsächlich den mehrzeiligen Treffer, und zwar ganz einfach deshalb, weil es der längstmögliche ist.
Wenn nicht-gierige Quantoren unterstützt werden, könnte man versuchen, diese hier einzusetzen, zum Beispiel wie in ˹^\w+=.*?(\\\n.*?)*˼. So wird auf Backslash und Newline getestet, bevor der Punkt überhaupt irgendwelche Zeichen erkannt hat. So könnte der Unterausdruck ˹\\˼ tatsächlich noch passen. Leider funktioniert auch das nicht. Ein nicht-gieriger Quantor passt nur auf etwas Optionales, wenn er dazu gezwungen wird. Aber in diesem Fall sind alle Elemente nach dem ˹=˼ optional, es gibt gar nichts, was dem nicht-gierigen Stern irgendetwas aufzwingen würde. Die gesamte Regex mit den nicht-gierigen Quantoren erkennt nur gerade ›SRC=‹, und das ist sicher nicht die Lösung.
Man kann diesem Problem mit anderen Methoden beikommen; wir werden dieses Beispiel unter Regex-Methoden aus der Praxis wieder antreffen (siehe unter Einige kleine Beispiele).
<< zurück | vor >> |
Tipp der data2type-Redaktion: Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an: |
Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.
O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln