Wie Regex-Maschinen arbeiten: Zusammenfassung

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

Wenn Sie alles in diesem Kapitel beim ersten Durchlesen verstanden haben, hatten Sie wohl schon vorher einige Vorkenntnisse von regulären Ausdrücken. Dieses Kapitel war ein harter Brocken, um es milde auszudrücken. Ich habe einige Zeit gebraucht, um das zu verstehen, und dann noch mal eine Weile, um es zu verstehen. Ich hoffe, dass es durch die knappe, aber vollständige Darstellung einfacher wird. Ich habe versucht, die Beispiele übersichtlich zu halten, ohne sie unzulässig zu vereinfachen – eine Falle, in die nur zu oft hineingetappt wird und die letztlich wirkliches Verstehen behindert. Dieses Kapitel ist dicht gepackt, deshalb habe ich in der folgenden Zusammenfassung viele Seitenverweise angegeben.

Es gibt zwei grundlegende Arbeitsweisen von Regex-Maschinen: den »Regex-gesteuerten NFA« (siehe NFA-Maschine: Regex-gesteuert) und den »textgesteuerten DFA« (siehe DFA-Maschine: Textgesteuert). Die ausgeschriebenen Abkürzungen finden Sie unter Ein erster Vergleich von NFA- und DFA-Maschinen.

Zusammen mit den Auswirkungen des POSIX-Standards (siehe unter POSIX und der »längste früheste Treffer«) ergeben sich für praktische Zwecke drei Typen von Maschinen:

  • Traditioneller NFA (benzinbetriebener, hochgezüchteter Motor)
  • POSIX-NFA (benzinbetriebener, standardkonformer Motor)
  • DFA (POSIX oder nicht) (Elektromotor, keine Macken)

Um die Möglichkeiten eines Werkzeugs voll auszunutzen, muss man wissen, welchen Maschinentyp es benutzt, und die Regex entsprechend anpassen. Der verbreitetste Typ ist der traditionelle NFA, gefolgt vom DFA. Die Tabelle Einige Programme und ihre Regex-Maschinentypen führt einige übliche Werkzeuge mit ihren Maschinentypen auf. Im Abschnitt Den Typ der Regex-Maschine bestimmen zeige ich, wie man die Provenienz der Maschine eines Werkzeugs selbst herausfinden kann.

Die eine oberste Regel, die für alle Maschinentypen gilt, heißt: Ein früherer Treffer hat Vorrang gegenüber einem, der weiter hinten im String beginnt. Dies liegt am »Getriebe«, das die eigentliche Regex auf jede Position des Strings neu ansetzt (siehe Das »Getriebe« schaltet zum nächsten Zeichen).

Für den Matching-Versuch, der von einer bestimmten Position ausgeht, gilt:

DFA – textgesteuerte Maschinen

DFAs finden den längsten möglichen Treffer, Punktum. Das war’s; wir danken für dieses Gespräch (siehe unter Der »längste früheste Treffer«). Sie sind konsistent, sehr schnell, und Diskussionen darüber sind langweilig (siehe unter Geschwindigkeit und Effizienz)

NFA – Regex-gesteuerte Maschinen

NFAs müssen sich durch ein Matching »durcharbeiten«. Die Seele eines NFA ist das Backtracking (siehe unter Backtracking, Backtracking und Gier). Die Metazeichen steuern den Vorgang der Mustererkennung: Die Quantoren (Stern, Plus usw.) sind gierig (siehe Regel 2: Die normalen Quantoren sind gierig). Die Alternation ist geordnet (siehe unter Ist die Alternation gierig?), bei POSIX-NFAs ist sie gierig.

POSIX-NFA

Er muss den längstmöglichen Treffer finden, Punktum. Langweilig wird es trotzdem nicht, weil man sich um die Effizienz kümmern muss (das Thema von Die Kunst, reguläre Ausdrücke zu schreiben).

Traditioneller NFA

Die ausdrucksstärkste Art von Regex-Maschine, weil durch die Regex-Steuerung exakt der Treffer gesucht werden kann, der von Interesse ist.

Das Verständnis der in diesem Kapitel behandelten Begriffe und Methoden ist die Grundlage zum Schreiben von korrekten und effizienten regulären Ausdrücken; und genau darum geht es unter Regex-Methoden aus der Praxis und Die Kunst, reguläre Ausdrücke zu schreiben.

  

<< 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