Reguläre Ausdrücke

Kapitel 6
Die Kunst, reguläre Ausdrücke zu schreiben (S. 227-228)

Bei der Regex-gesteuerten Art des Matchings einer NFA-Maschine, wie man sie bei Perl, in den meisten Java-Packages, in den .NET-Sprachen, Python und PHP (und anderen, siehe auch die Tabelle auf Seite 149) ndet, können minimale Änderungen in einem regulären Ausdruck grofle Auswirkungen auf die gefundenen Treffer haben. Dinge, die bei einer DFA-Maschine schlicht keine Rolle spielen, werden zu kritischen Angelpunkten. Mit der bei NFAs möglichen Feinabstimmung kann man reguläre Ausdrücke nach fast künstlerischen Gesichtspunkten konstruieren, man kann aber durch die vielen Möglichkeiten auch verwirrt werden. Dieses Kapitel soll Ihnen helfen, diese Kunst zu erlernen.

Die Eckpfeiler sind Richtigkeit und Efzienz. Das bedeutet, genau den Treffer zu änden, den man enden will, und keinen anderen und das Ganze möglichst schnell. In den Kapiteln 4 und 5 ging es darum, wie man korrekte reguläre Ausdrücke schreibt. Hier befassen wir uns mit Fragen der Efzienz bei NFA-Maschinen und überlegen, wie wir deren Eigenheiten zu unseren Zwecken ausnutzen können. (Wenn es etwas zu DFAs zu sagen gibt, wird das kurz erwähnt, aber im Wesentlichen befasst sich dieses Kapitel mit NFAs.) Im Grunde genommen geht es darum, das Backtracking mit all seinen Auswirkungen zu verstehen und zu lernen, das Backtracking zu vermeiden, soweit dies möglich ist. Wenn wir die internen Vorgänge erst einmal genauer verstanden haben, können wir auch komplizierte Ausdrücke mit mehr Selbstvertrauen angehen.

Dieses Kapitel behandelt zunächst ein ausführliches Beispiel, das zeigt, wie wichtig diese ‹berlegungen sind. Eine Zusammenfassung des Backtracking-Mechanismus aus Kapitel 4, diesmal mit dem Augenmerk auf Efzienz-Fragen, bereitet auf die weiterführenden Methoden vor, mit denen man Backtracking besser behandelt. Dann werden einige bekannte interne Optimierungsmethoden vorgestellt, die grofle Auswirkungen auf die Efzienz eines Ausdrucks haben können, auflerdem wird gezeigt, wie man bei Werkzeugen, die solche Optimierungen verwenden, diese auch nutzbringend einsetzt. Abschlieflend stelle ich einige wirklich schnelle Tricks vor, die auch NFAs zu einem Raketenantrieb verhelfen.

Vergleiche und Backtrackings

Die hier vorgestellten Beispiele dienen nur als Illustrationen für Situationen, die beim Umgang mit regulären Ausdrücken häug auftreten.Wenn die Efzienz eines bestimmten Beispiels untersucht wird, gebe ich oft die Anzahl der während des Matchings ausgeführten Vergleiche an. Zum Beispiel braucht dieMustererkennung von marty mit dem String smarty sechs einzelne Vergleiche ñ im ersten Versuch wird m mit s verglichen (passt nicht), dann gibt es Treffer, wenn m mit m, a mit a usw. verglichen wird. Meist gebe ich auch die Anzahl der benötigten Backtracking-Operationen an in diesem Fall gar keine (man könnte allenfalls das implizite Backtracking beim neuen Ansetzen der Regex an der zweiten Position im String mitzählen). Exakte Zahlen gebe ich nicht deshalb an, weil sie wichtig wären, sondern weil sie doch mehr aussagen alsWendungen wie viele´, wenige´, besser als´, nicht zu viele´ usw. Ich möchte keinesfalls den Eindruck erwecken, dass das Schreiben von regulären Ausdrücken für NFAs eine ‹bung im Zählen von Vergleichen und Backtracking-Operationen sei, ich möchte nur einen Gradmesser für die Güte der Beispiele untereinander vorstellen. Diese Zahlen können sich auflerdem von Werkzeug zu Werkzeug und von Version zu Version unterscheiden.