Typen von Regex-Maschinen

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

Es gibt zwei fundamentale Typen von Regex-Maschinen: eine namens »DFA« (der Elektromotor in unserer Analogie) und eine namens »NFA« (der Verbrennungsmotor). Was NFA und DFA bedeuten, folgt bald, aber für den Moment sind das einfach zwei Namen wie Hans und Fritz. Oder Elektro und Benzin.

Beide Maschinen gibt es schon seit langer Zeit, aber analog zu Motoren wird der eine, der NFA-Typus, viel häufiger benutzt. Einen NFA unter der Haube haben die .NET-Sprachen, PHP, Ruby, Perl, Python, GNU Emacs, ed, sed, vi, die meisten Versionen von grep und auch einige wenige egrep- und awk-Programme. Den DFA-Typus findet man in den allermeisten Versionen von egrep und awk, außerdem bei lex und flex. Manche Systeme haben einen Hybridmotor und verwenden je nach Art der Aufgabe den einen oder den anderen Typus (oder wenden sogar einen Motor auf bestimmte Teile der Regex an, den anderen auf den Rest und versuchen so, das Letzte an Vielseitigkeit und Geschwindigkeit herauszuholen). Die folgende Tabelle führt die verwendeten Typen für eine Anzahl von Programmen auf. Wenn Ihr Programm nicht darunter ist, können Sie die Methode aus dem Abschnitt Den Typ der Regex-Maschine bestimmen anwenden.

Tabelle: Einige Programme und ihre Regex-Maschinentypen.

Maschinentyp	Programme
DFA	awk (die meisten Versionen), egrep (die meisten Versionen), flex, lex, MySQL, Procmail
Traditioneller NFA	GNU Emacs, Java, grep (die meisten Versionen), less, more, die .NET-Sprachen, die PCRE-Bibliothek, Perl, PHP (alle drei Regex-Pakete), Python, Ruby, sed (die meisten Versionen), vi
POSIX-NFA	mawk, die Programme von Mortice Kern Systems, GNU Emacs (falls gewünscht)
Hybrider NFA/DFA	GNU awk, GNU grep/egrep, Tcl

---

Wie Features und Dialekte gezeigt hat, haben zwanzig Jahre Entwicklung sowohl bei DFAs als auch bei NFAs eine große Menge unnötiger Varianten erzeugt. Eine unangenehme Situation. Der POSIX-Standard entstand, um diesem Zustand abzuhelfen, indem genau spezifiziert wurde, welche Metazeichen eine Maschine kennen muss, und vor allem, welche Resultate sie liefern muss. Abgesehen von Details, erfüllten DFAs (unsere Elektromotoren) diese Vorschriften bereits weitgehend, aber die Resultate, die traditionelle NFAs liefern, unterscheiden sich ziemlich deutlich von dem, was der Standard fordert. Für einen POSIX-konformen NFA sind recht weitgehende Anpassungen notwendig. Als Resultat können wir die Typen von Regex-Maschinen grob in drei Gruppen einteilen:

• DFA (POSIX oder nicht – auf jeden Fall ähnlich)
• Traditioneller NFA (der Normalfall: Perl, .NET, PHP, Java, Python, ...)
• POSIX-NFA

Der Ausdruck »POSIX« bezieht sich hier auf die Semantik der Mustersuche – wie sich eine Regex nach der im POSIX-Standard vorgeschriebenen Art verhält (das wird später in diesem Kapitel genauer besprochen). Verwechseln Sie das bitte nicht mit den POSIX-Features, den Klammerausdrücken, die im gleichen Standard genormt sind (siehe POSIX-Klammerausdruck »Zeichenklasse«: [[:alpha:]]). Bei vielen Programmen werden zwar die POSIX-Features unterstützt, es sind aber dennoch keine POSIX-Maschinen.

Alte (und relativ einfache) Programme wie egrep, awk und lex hatten normalerweise den elektrischen DFA-Antrieb; für diese hat der neue Standard nur den Status quo bestätigt – es waren keine radikalen Änderungen notwendig. Allerdings gab es benzinschluckende Versionen dieser Programme, die adaptiert werden mussten, wollten sie POSIX-konform sein. Die Verbrennungsmotoren, die die kalifornischen Abgasbestimmungen einhalten (POSIX-NFAs), sind zwar fein raus, was ihre Emissionen angeht, aber sie sind durch die notwendigen Anpassungen sehr fragil geworden. Während sie früher auch mit leicht verschobenen Elektrodenabständen liefen, tolerieren sie jetzt kaum Abweichungen. Benzin, das früher gut genug war, produziert jetzt Klopfen im Motor. Aber solange man diese Motoren gut pflegt, laufen sie problemlos. Und sauber.

Aus der Abteilung für Redundanz-Abteilung

An diesem Punkt bitte ich Sie, die Analogie zu Automotoren am Anfang des Kapitels noch einmal anzuschauen. Jeder Satz hat eine Verwandtschaft mit regulären Ausdrücken. Ein zweites Durchlesen gibt aber auch Anlass zu Fragen. Was soll das heißen, dass ein elektrischer DFA »einfach läuft«? Was für Umstände beeinflussen einen Benzin-NFA? Wie warte ich einen NFA? Was muss ich bei einem emissionsarmen POSIX-NFA beachten? Was ist ein Motor, der nicht mehr läuft, in der Welt der regulären Ausdrücke?

  

<< zurück

vor >>