POSIX und der »längste früheste Treffer«

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

Der POSIX-Standard verlangt sehr klar, dass von mehreren möglichen Treffern, die am selben Ort beginnen, der erkannt werden muss, der auf die meisten Zeichen im String passt.

Der Standard benutzt die Formulierung »longest of the leftmost«, etwa »der längste Treffer unter denen, die am weitesten links beginnen«. (Anmerkung: Es ist unmöglich, einen Standard korrekt zu übersetzen; gültig ist immer die Originalsprache. Die in diesem Buch gewählte Übersetzung »längster frühester Treffer« (ohne Komma, »längster« beschreibt die »frühesten Treffer« näher) wird deshalb immer nur in Anführungszeichen geschrieben. (Anm. d. Ü.)) POSIX-Standards äußern sich nicht zur Implementation, sie legen allein das geforderte Verhalten fest. Mit einem DFA ist das sicher einfach zu erreichen, was aber soll ein Programmierer machen, der aus anderen Gründen einen NFA für sein Werkzeug wählt? Ein POSIX-konformer NFA muss den ganzen String motorradfahren erkennen – und alle Fortsetzungszeilen, auch wenn dies dem »natürlichen« Vorgehen eines NFA widerspricht.

Eine traditionelle NFA-Maschine hält an, sobald sie den ersten Treffer findet. Was passiert, wenn sie zusätzlich auch noch alle verbliebenen gespeicherten Zustände ausprobiert? Jedes Mal, wenn so ein Versuch wieder ans Ende der Regex vorstößt, ergibt sich ein neuer Treffer für den ganzen Ausdruck. Nachdem alle Möglichkeiten durchprobiert sind, wird einfach der längste der gefundenen Treffer zurückgegeben. Damit haben wir einen POSIX-NFA.

Ein NFA, auf das erste Beispiel angesetzt, speichert nach dem Erkennen von ˹(rad)?˼ den Zustand bei ˹motor(rad)?▵(radfahren)?˼ in der Regex und bei motor▵radfahren im String ab und weiß, dass von da ein neuer Versuch gestartet werden kann. Ein traditioneller NFA findet als vollständigen Treffer motorradfahren, ein POSIX-NFA macht weiter und testet alle möglichen Varianten durch und wird dabei irgendwann auch motorradfahren erreichen.

Unter Perl werden Sie einen Trick kennenlernen, mit dem Sie den traditionellen NFA von Perl dazu zwingen können, sich wie ein POSIX-NFA zu verhalten und den längsten Treffer zu finden (siehe Den längsten frühesten Treffer finden).

  

<< zurück

vor >>