Vergleichsverhalten
Aktualisiert: November 2007
Das .NET Framework-Modul für reguläre Ausdrücke (Suchmodul) ist ein zurückverfolgendes Modul zur Suche mithilfe regulärer Ausdrücke, das ein herkömmliches NFA (Nondeterministic Finite Automaton)-Modul beinhaltet, wie es auch von Perl, Python, Emacs und Tcl verwendet wird. Dadurch unterscheidet es sich von schnelleren, aber vom Umfang her beschränkten DFA (Deterministic Finite Automaton)-Modulen, die reine reguläre Ausdrücke verwenden, wie z. B. awk, egrep oder lex. Es unterscheidet sie außerdem von standardisierten, aber langsameren POSIX NFAs.
Drei Strategien für Suchmodule mit regulären Ausdrücken
In diesem Abschnitt werden die Vor- und Nachteile von drei verschiedenen Modultypen beschrieben, und es wird erläutert, warum das .NET Framework-Modul ein herkömmliches NFA-Modul implementiert.
DFA-Module arbeiten linear, da sie keine Rückverfolgung benötigen (und daher niemals dasselbe Zeichen zweimal überprüfen). Sie können gewährleisten, dass die längstmögliche Zeichenfolge gefunden wird. Da jedoch DFA-Module nur endliche Zustände enthalten, können sie keine Muster mit Rückverweisen finden. Teilausdrücke werden auch nicht gefunden, da DFA-Module keine explizite Erweiterung erstellen.
Herkömmliche NFA-Module arbeiten mit so genannten "gierigen" (greedy) Rückverfolgungsalgorithmen, die alle möglichen Erweiterungen eines regulären Ausdrucks in einer festen Reihenfolge überprüfen und die erste Übereinstimmung akzeptieren. Da ein herkömmliches NFA-Modul im Falle eines erfolgreichen Suchergebnisses eine spezielle Erweiterung eines regulären Ausdrucks erstellt, können Teilausdrücke ausgewertet und somit Übereinstimmungen mit Rückverweisen gefunden werden. Allerdings kann ein herkömmliches NFA aufgrund der Rückverfolgung exakt den gleichen Zustand mehrmals über unterschiedliche Pfade erreichen. Das Resultat ist im ungünstigsten Fall ein exponentiell verlangsamtes Laufzeitverhalten. Da durch ein herkömmliches NFA das erste Suchergebnis akzeptiert wird, können weitere (möglicherweise längere) Übereinstimmungen unentdeckt bleiben.
POSIX-NFA-Module arbeiten wie herkömmliche NFA-Module, jedoch mit einem Unterschied: Die Rückverfolgung wird so lange fortgesetzt, bis gewährleistet ist, dass die längstmögliche Übereinstimmung gefunden wurde. Aus diesem Grund ist ein POSIX-NFA-Modul langsamer als ein herkömmliches NFA-Modul. Außerdem ist es nicht möglich, durch eine Änderung der Reihenfolge bei der Rückverfolgungssuche einem kürzeren Suchergebnis Vorrang vor einem längeren zu geben.
Herkömmliche NFA-Module werden von Programmierern meist bevorzugt, da sie aussagekräftiger als DFA-Module oder POSIX-NFA-Module sind. Obwohl sie im ungünstigsten Fall langsam sind, kann durch die Verwendung von Suchmustern, die Mehrdeutigkeiten vermeiden und das Zurückverfolgen einschränken, ein lineares oder polynomisches Laufzeitverhalten erreicht werden.
Funktionen des .NET Framework-Moduls
Um die Vorteile eines herkömmlichen NFA-Moduls voll ausschöpfen zu können, beinhaltet das .NET Framework-Modul für reguläre Ausdrücke einen vollständigen Satz von Konstrukten, mit deren Hilfe Programmierer das Rückverfolgungsmodul steuern können. Diese Konstrukte können dazu verwendet werden, Übereinstimmungen schneller zu finden oder spezielle Erweiterungen eines regulären Ausdrucks anderen vorzuziehen.
Weitere Funktionen:
So genannte "träge" (lazy) Quantifizierer: ??, *?, +?, {n,m}?. Diese veranlassen das Rückverfolgungsmodul, zuerst die kleinste Anzahl an Wiederholungen zu berücksichtigen. Im Gegensatz dazu wird bei "gierigen" Quantifizierern die maximale Anzahl an Wiederholungen zuerst berücksichtigt.
Positives Lookahead. Dadurch kann das Rückverfolgungsmodul zu einer Textstelle zurückzukehren, nachdem ein Teilausdruck ausgewertet wurde. Um einen Text vollständig zu durchsuchen, empfiehlt es sich, unterschiedliche Muster von derselben Startposition aus anzuwenden.
Negatives Lookahead. Dadurch wird es möglich, nur dann eine Übereinstimmung zu einem Ausdruck zu erhalten, wenn ein Teilausdruck kein Ergebnis liefert. Dies ist besonders effektiv bei einer verzweigten Suche, da oftmals ein Ausdruck für einen auszuschließenden Fall viel einfacher ist als ein Ausdruck für Fälle, die nicht ausgeschlossen werden dürfen. (Beispielsweise ist es schwierig, einen Ausdruck für Wörter zu finden, die nicht mit "un" beginnen).
Bedingte Auswertung. Dadurch kann mit mehreren Alternativmustern gesucht werden, in Abhängigkeit von den Ergebnissen früherer Übereinstimmungen mit Teilausdrücken. Dies ermöglicht den effektiveren Einsatz von Rückverweisen, z. B. für den Fall, dass genau dann eine Übereinstimmung für eine rechte Klammer vorliegt, wenn vorher eine linke Klammer in einem Teilausdruck gefunden wurde.
Nicht zurückverfolgende Teilausdrücke (so genannte "gierige" Teilausdrücke). Dadurch wird bei der Rückverfolgung sichergestellt, dass nur die erste Übereinstimmung mit einem Teilausdruck geliefert wird, so als wäre der Teilausdruck unabhängig von dem vollständigen Ausdruck. Ohne dieses Konstrukt könnte das Verhalten eines Teilausdrucks durch zurückverfolgende Suchläufe über den längeren Ausdruck beeinflusst werden.
Suche von rechts nach links. Dies ist hilfreich bei der Suche von rechts nach links (anstelle von links nach rechts) oder in Fällen, in denen es effektiver ist, auf der rechten Seite eines Musters mit der Suche zu beginnen.
Positives und negatives Lookbehind. Dies ist ähnlich wie Lookahead. Reguläre Ausdrücke gestatten uneingeschränkte Lookbehinds, da eine vollständige Suche nach Übereinstimmungen von rechts nach links möglich ist.