Den Typ der Regex-Maschine bestimmen

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

Weil bestimmte Features nur von einem Maschinentyp unterstützt werden und sich bestimmte Maschinentypen in Grenzsituationen besonders verhalten, kann man oft mit ein paar Testausdrücken den Maschinentyp herausfinden. (Wenn man das nicht könnte, spielte es ja auch gar keine Rolle, welchen Maschinentyp man benutzt.) An dieser Stelle im Buch verstehen Sie wahrscheinlich nicht, warum die folgenden Tests so verlaufen, wie sie es tun, aber ich möchte Ihnen dennoch diese Testausdrücke nicht vorenthalten, falls Ihr Programm in der Tabelle Einige Programme und ihre Regex-Maschinentypen nicht aufgeführt ist.

Traditioneller NFA oder nicht?

Die am weitesten verbreitete Regex-Maschine ist der traditionelle NFA-Typus, und dieser lässt sich meist recht einfach identifizieren. Werden nicht-gierige Quantoren (siehe Nicht-gierige, »genügsame« Quantoren) unterstützt? Wenn ja, handelt es sich fast sicher um einen traditionellen NFA. Sie werden sehen, dass nicht-gierige Quantoren bei einem DFA nicht möglich sind, und bei einem POSIX-NFA widersprechen sie dem Standard. Wenn Sie ganz sicher sein wollen, wenden Sie die Regex ˹nfa|nfa●not˼ auf den String ›nfa●not‹ an – wenn der Treffer ›nfa‹ ist, handelt es sich um einen traditionellen NFA. Wenn der gesamte String ›nfa●not‹ erkannt wird, ist es ein POSIX-NFA oder ein DFA.

DFA oder POSIX-NFA?

Die Unterscheidung zwischen POSIX-NFA und DFA ist meist genauso einfach. Einfangende Klammern und Rückwärtsreferenzen werden von DFAs nicht unterstützt, das kann schon einmal ein Hinweis sein, aber es gibt auch Hybridsysteme, die normalerweise einen DFA verwenden, aber einen NFA, wenn Klammern oder Rückwärtsreferenzen auftauchen.

Der folgende Test kann eine ganze Menge aussagen. Wenden Sie die Regex ˹X(.+)+X˼ auf einen String wie ›=XX======================‹ an, hier als Beispiel mit egrep:

echo =XX========================================= | egrep 'X(.+)+X'

Wenn das länger dauert, handelt es sich um einen NFA (wenn Sie mit der Methode aus dem letzten Abschnitt einen traditionellen NFA ausgeschlossen haben, muss es wohl ein POSIX-NFA sein). Wenn das Resultat sofort ausgegeben wird, handelt es sich um einen DFA (oder aber einen raffinierten NFA, dessen Optimierer die Situation erkennt). Wird eine Warnung wie »Stack overflow« ausgegeben oder die Mustersuche sonst wie abgebrochen? Dann ist es ein NFA.

  

<< zurück

vor >>