Bestandteile der Regex-Maschine

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

Ein Motor ist natürlich aus vielen Teilen aufgebaut. Man kann die Funktionsweise eines Motors nicht verstehen, wenn man nicht die wichtigsten Teile davon kennt. Bei regulären Ausdrücken sind diese Teile die verschiedenen Grundeinheiten – Literale, Quantoren (Stern, Fragezeichen usw.), Zeichenklassen, Klammern usw., wie unter Features und Dialekte erklärt wurde (siehe die Tabelle In diesem Abschnitt behandelte Konstrukte). Die Kombination dieser Teile und die Art und Weise, wie sie von der Maschine verwendet werden, machen eine Regex zu dem, was sie ist; also muss unser Augenmerk auf die Art gerichtet sein, wie diese Teile zusammenpassen und wie sie zusammenspielen. Die einzelnen Teile sind:

Literale (z.B. a \* ! 枝 ...)

Bei einem literalen Zeichen wie ˹z˼ oder ˹!˼ ist der Versuch, einen Treffer zu erzielen, einfach der: »Ist das Literal mit dem aktuellen Zeichen im String identisch?« Wenn die ganze Regex nur aus Literalen besteht, wie etwa ˹usa˼, wird das behandelt wie »˹u˼ und dann ˹s˼ und dann ˹a˼«. Wenn Groß- und Kleinbuchstaben gleich behandelt werden sollen, wenn also ˹b˼ auch auf B (oder umgekehrt) passen soll, wird es nur unwesentlich komplizierter. (Mit Unicode ergeben sich ein paar zusätzliche Schwierigkeiten, siehe Der Modus »Groß- und Kleinschreibung ignorieren«.)

Zeichenklassen, Punkt, Unicode-Eigenschaften usw.

Mit einer Zeichenklasse, dem Punkt, einer Unicode-Eigenschaft oder dergleichen (siehe Zeichenklassen und ähnliche Konstrukte) einen Treffer zu finden ist nicht viel schwieriger. Ganz egal, wie viele Zeichen eine Klasse umfasst, sie passt immer nur auf ein einzelnes Zeichen im String. (Anmerkung: Um genau zu sein, können POSIX-Kollationssequenzen auf mehrere Zeichen passen, wie wir in Features und Dialekte gesehen haben, aber das ist wohl die Ausnahme. Auch bestimmte Unicode-Zeichen können auf mehr als ein Zeichen passen, wenn ohne Rücksicht auf Groß- und Kleinschreibung gesucht wird (siehe Der Modus »Groß- und Kleinschreibung ignorieren«), aber die meisten Implementationen unterstützen das nicht.) Der Punkt ist nur eine Abkürzung für eine große Zeichenklasse, die alle oder fast alle Zeichen enthält (siehe Der Modus »Punkt passt auf alles«), also ist die Suche auch hier sehr einfach. Ganz analog ist es mit den Abkürzungen ˹\w˼, ˹\W˼ und ˹\d˼.

Einfangende Klammern

Wenn Klammern nur zum Einfangen von bereits gefundenem Text (und nicht zum Gruppieren) benutzt werden, haben sie keinen Einfluss darauf, wie das Matching vor sich geht.

Anker (z.B. ˹^˼ ˹\Z˼ ˹(?<=\d)˼ ...)

Es gibt zwei Arten von Ankern: einfache (^, $, \G, \b, ... siehe unter Anker und andere »Zusicherungen der Länge null«) und komplexere (Lookahead und Lookbehind, siehe Lookahead; Lookbehind)an. Bei den einfachen ist auch der Match-Vorgang einfacher, weil nur auf eine bestimmte Stelle im Suchstring getestet werden muss (^, \Z, ...) oder zwei nebeneinanderliegende Zeichen miteinander verglichen werden müssen (\<, \b, ...). Die Lookaround-Konstrukte können dagegen beliebig komplizierte Unterausdrücke enthalten, daher ist auch ihre Funktion beim Matching-Vorgang sehr komplex.

»Elektrische« Klammern, Rückswärtsreferenzen oder nicht-gierige Quantoren gibt es nicht

Ich wollte mich zunächst auf die Gemeinsamkeiten der Regex-Maschinen konzentrieren, kann es aber nicht lassen, eine Vorahnung auf Kommendes zu geben. »Einfangende« Klammern (und damit Rückwärtsreferenzen und die Funktionalität von $1) sind mit Additiven im Kraftstoff vergleichbar – es gibt sie nur für die NFA-Verbrennungsmotoren; bei Elektromotoren sind sie nicht sinnvoll einzusetzen. Mit den nicht-gierigen Quantoren ist es genau gleich. Die Art, wie eine DFA-Maschine arbeitet, lässt Rückwärtsreferenzen auf einfangende Klammern einfach nicht zu. (Anmerkung: Es gibt immerhin Kombinationen der zwei Haupttypen, die versuchen, das Beste aus beiden Lagern zu kombinieren. Das wird in der Box Geschwindigkeit von DFAs mit Features von NFAs: Regex-Nirwana? näher erläutert.) Damit ist erklärt, warum Werkzeuge, die mit DFAs arbeiten, diese Dinge nicht kennen. In awk, lex und egrep gibt es weder Rückwärtsreferenzen noch ein Gegenstück zu $1.

Sie haben aber vielleicht gesehen, dass egrep in der GNU-Version dennoch Rückwärtsreferenzen zulässt. Es kann das, weil es schlicht zwei Motoren unter der Haube hat! GNU egrep benutzt zunächst eine DFA-Maschine, um Muster zu finden. Wenn diese einen Treffer gefunden hat, wird die NFA-Maschine darauf angesetzt, die Rückwärtsreferenzen versteht. Später in diesem Kapitel werden Sie sehen, warum eine DFA-Maschine nicht mit Rückwärtsreferenzen umgehen kann und warum überhaupt Leute mit derart eingeschränkten Maschinen arbeiten. (Die DFA hat bestimmte Vorteile, zum Beispiel findet sie Treffer sehr schnell.)

  

<< zurück

vor >>