Ausnutzen der geordneten Alternation

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

Zurück zum Beispiel ˹(\.\d\d[1-9]?)\d*˼ aus Gierig oder genügsam –- der Treffer geht vor. ˹\.\d\d[1-9]?˼ bedeutet eigentlich »entweder ˹\.\d\d˼ oder ˹\.\d\d[1-9]˼«, also könnten wir den ganzen Ausdruck mit einer Alternation so schreiben: ˹(\.\d\d|\.\d\d[1-9])\d*˼. (Dafür gibt es keinen triftigen Grund, es geht nur um ein Beispiel.) Ist das wirklich dasselbe wie ˹(\.\d\d[1-9]?)\d*˼ ? Bei gieriger Alternation ja, bei geordneter Alternation unterscheiden sich die zwei Varianten wesentlich.

Betrachten wir zunächst die geordnete Alternation. Wenn die erste Alternative passt, ˹\.\d\d˼, dann passt mit Sicherheit auch das folgende ˹\d*˼. Das kann auch eine dritte Ziffer ungleich null sein, die wir aber (Sie erinnern sich an die Problemstellung) innerhalb der Klammern erkennen wollen. Außerdem ist der erste Teil der zweiten Alternative eine genaue Kopie der ganzen ersten Alternative. Wenn also die erste fehlschlägt, wird es der zweiten mit Sicherheit nicht anders ergehen. Die Regex-Maschine wird es zwar versuchen, wird aber mit Sicherheit wieder einen lokalen Fehlschlag erleiden.

Wenn wir mit ˹(\.\d\d[1-9]|\.\d\d)\d*˼ die Alternativen vertauschen, erhalten wir zunächst einfach eine Kopie des ursprünglichen ˹(\.\d\d[1-9]?)\d*˼. Die Alternation ist aber durchaus sinnvoll, denn diesmal kann die zweite Alternative unter Umständen passen, auch wenn die erste fehlschlägt. Es handelt sich noch immer um eine geordnete Alternation, aber wir haben die Alternativen jetzt so angeordnet, dass der längste mögliche Treffer zuerst kommt, wie das bei gierigem Verhalten automatisch geschähe.

Indem wir den Ausdruck mit ˹[1-9]?˼ in zwei Alternativen aufgeteilt und die kürzere zuerst geschrieben haben, wurde eine Art nicht-gieriges Fragezeichen erzeugt. In diesem Fall ist das ohne Bedeutung, weil es keine Möglichkeit gibt, dass die zweite Alternative passen könnte, wenn die erste fehlschlägt. Ich sehe diesen Typus von falscher Alternative recht häufig, und es steckt immer ein Denkfehler dahinter, wenn man sie mit einem traditionellen NFA benutzt. In einem Buch habe ich das Beispiel ˹a*((ab)*|b*)˼ gefunden, mit dem etwas über Klammern bei einem traditionellen NFA erläutert werden sollte. Ein sehr einfältiges Beispiel, nicht? Die erste Alternative, ˹(ab)*˼, kann nie fehlschlagen, und damit sind alle weiteren Alternativen (nur ˹b*˼, in diesem Fall) völlig bedeutungslos. Man könnte auch

˹a*((ab)*|b*|.*|Fischers●Fritz●fischt●frische●Fische|[a-z])˼

dazunehmen, es käme exakt auf das Gleiche heraus. Was lernen wir daraus? Wenn bei geordneter Alternation mehrere Alternativen auf den gleichen Text passen können, muss man sich die Reihenfolge der Alternativen genau überlegen.

Fallen bei geordneter Alternation

Oft kann man das nicht-gierige Verhalten der Alternation für seine Zwecke ausnutzen, um durch eine raffinierte Formulierung der Regex genau das Matching zu erzielen, das man gerne haben möchte. Aber es gibt auch Fallen, in die man dabei hineintappen kann. Als Beispiel wollen wir ein Datum im Januar in der englischen Schreibweise wie ›Jan 31‹ erkennen. Wir fordern etwas Ausgefeilteres als nur gerade ˹Jan●[0123][0-9]˼, weil das »Daten« wie ›Jan 00‹ und ›Jan 39‹ erlaubt, aber solche wie ›Jan 7‹ nicht erkennt.

Das Problem wird am einfachsten in Teilstücke zerlegt. Für die Daten vom ersten bis zum neunten nehmen wir ˹0?[1-9]˼ und erlauben auch eine führende Null. Mit ˹[12][0-9]˼ erwischen wir die Zahlen von 10 bis 29 und mit ˹3[01]˼ die restlichen zwei. Zusammengesetzt erhalten wir ˹Jan● (0?[1-9]|[12][0-9]|3[01])˼.

Wie denken Sie, dass das auf ›Jan 31 is dad's birthday‹ passt? Wir erwarten natürlich ›Jan 31‹, aber wegen der geordneten Alternation wird nur ›Jan 3‹ erkannt. Erstaunt? Bei der ersten Alternative ˹0?[1-9]˼ passt das ˹0?˼ nicht, aber die Alternative passt dennoch, weil das folgende ˹[1-9]˼ die 3 von 31 erkennt. Da wir schon am Ende der Regex angekommen sind, ist das Matching komplett.

Hätten wir eine andere Reihenfolge gewählt oder wäre die Alternation gierig, hätte sich das Problem nicht gestellt. Diese Version funktioniert: ˹Jan●([12][0-9]|3[01]|0?[1-9])˼.

Ein anderer Ansatz ist ˹Jan●(31|[123]0|[012]?[1-9])˼. Wie bei der ersten Variante spielt auch hier die Reihenfolge der Alternativen eine entscheidende Rolle. Die dritte Version dagegen, ˹Jan● (0[1-9]|[12][0-9]?|3[01]?|[4-9])˼, arbeitet ohne Rücksicht darauf, wie die Alternativen angeordnet sind. Es kann interessant sein, diese drei Ausdrücke zu vergleichen. (Eine Übung, die ich Ihnen überlasse. Der folgende Kasten mag dabei nützlich sein.)

Ein paar Arten, ein Kalenderdatum zu zerstückeln

Ein paar Ansätze zum Problem »Kalenderdaten erkennen«. In den Kalendertabellen sind die Daten gleich unterlegt wie die zugehörigen Alternativen in der Regex.

  

<< zurück

vor >>