Die Kunst, reguläre Ausdrücke zu schreiben
(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)
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 Einige Programme und ihre Regex-Maschinentypen) findet, können minimale Änderungen in einem regulären Ausdruck große 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 Effizienz. Das bedeutet, genau den Treffer zu finden, den man finden will, und keinen anderen – und das Ganze möglichst schnell. Unter Wie Regex-Maschinen arbeiten und Regex-Methoden aus der Praxis ging es darum, wie man korrekte reguläre Ausdrücke schreibt. Hier befassen wir uns mit Fragen der Effizienz 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 Wie Regex-Maschinen arbeiten, diesmal mit dem Augenmerk auf Effizienz-Fragen, bereitet auf die weiterführenden Methoden vor, mit denen man Backtracking besser behandelt. Dann werden einige bekannte interne Optimierungsmethoden vorgestellt, die große Auswirkungen auf die Effizienz eines Ausdrucks haben können; außerdem wird gezeigt, wie man bei Werkzeugen, die solche Optimierungen verwenden, diese auch nutzbringend einsetzt. Abschließend 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äufig auftreten. Wenn die Effizienz eines bestimmten Beispiels untersucht wird, gebe ich oft die Anzahl der während des Matchings ausgeführten Vergleiche an. Zum Beispiel braucht die Mustererkennung 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 als Wendungen 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 außerdem von Werkzeug zu Werkzeug und von Version zu Version unterscheiden. Es geht deshalb um Größenordnungen und nicht um »genaue« Zahlen – die relative Leistung der verschiedenen Beispiele ist wichtig. Dabei müssen aber die Optimierungen berücksichtigt werden, die in ein bestimmtes Werkzeug eingebaut sind. Eine ausreichend schlaue Implementation kann herausfinden, dass eine bestimmte Regex nie passen kann, bevor sie mit dem eigentlichen Matching beginnt. (Sie kann beispielsweise feststellen, dass ein bestimmtes Zeichen, das von der Regex gefordert wird, nirgends im String vorkommt.) Ich beschreibe solche Optimierungen später in diesem Kapitel, aber die Lektion als Ganzes ist wohl wichtiger als all die speziellen Fälle.
Traditioneller NFA und POSIX-NFA
Auch den Maschinentyp (traditioneller oder POSIX-NFA) des benutzten Werkzeugs muss man im Auge behalten, wenn man Effizienz-Fragen abklärt, weil manche Überlegungen nur für einen Typ gelten. Eine Änderung ohne sichtbaren Effekt beim einen Maschinentyp kann sich beim anderen Typ sehr deutlich auswirken. Auch hier gilt, dass Sie eine solche Situation besser beurteilen können, wenn Sie die Grundlagen verstanden haben.
- Ein ernüchterndes Beispiel
- Backtracking global betrachtet
- Benchmarking
- Übliche Optimierungen
- Programmiermethoden für schnellere Ausdrücke
- Die Schleife aufbrechen
- Die frei fließende Regex
- Denken!
<< zurück | vor >> |
Tipp der data2type-Redaktion: Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an: |
Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.
O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln