Regel 2: Die normalen Quantoren sind gierig

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

Bis hierhin war das Finden von Treffern recht einfach. Aber auch langweilig – man kann einfach nicht sehr viel ohne die Metazeichen wie Stern, Plus, Alternation usw. machen. Um diese zu verstehen, brauchen Sie etwas mehr Hintergrundinformationen.

Zunächst müssen Sie wissen, dass die normalen Quantoren (?, *, +, {min,max}) gierig sind. Wenn sich so ein Quantor auf einen Unterausdruck wie das a in ˹a?˼, das ˹(expr in ˹(expr)*˼ oder das ˹[0-9]˼ in ˹[0-9]+˼ bezieht, dann gibt es eine Mindest- und eine Maximalgröße von Treffern, auf die dieser Unterausdruck passen kann. Das wurde schon in den letzten Kapiteln erwähnt – hier wird als Regel formuliert, dass diese Quantoren immer versuchen, so viel Text wie möglich zu erkennen. (Bei einigen Dialekten gibt es neben den normalen auch andere Typen von Quantoren, um die geht es hier aber nicht.)

Mit anderen Worten: Die Standard-Quantoren begnügen sich mit der verlangten Mindestanzahl nur dann, wenn es nicht anders geht. Sonst versuchen sie, so viele Zeichen wie nur möglich abzukriegen – bis zum erlaubten Maximum natürlich. Nur wenn andere, spätere Teile der Regex dadurch nicht mehr passen könnten, geben sich Quantoren mit weniger zufrieden. Ein einfaches Beispiel: ˹\b\w+e\b˼ sucht nach Wörtern, die auf e enden, wie etwa Programme. Das ˹\w+˼ allein würde gern das ganze Wort »fressen«, aber dann würde das e am Ende nicht mehr passen. Damit der komplette reguläre Ausdruck erfolgreich passt, muss sich das ˹\w+˼ mit Programme begnügen, nur dann passt das ˹e\b˼ und damit die ganze Regex.

Es kann auch so weit kommen, dass der gierige Quantor auf überhaupt nichts mehr passt (sofern dies mit dem Stern, Fragezeichen oder dem Intervall {0,max} zugelassen wird). Allerdings tritt dieser Fall nur ein, wenn das von späteren Teilen der Regex erzwungen wird. Von sich aus wird ein Quantor immer versuchen, auf mehr Zeichen als die minimal geforderten zu passen; deshalb nennt man sie gierig.

Dieses gierige Verhalten hat viele angenehme (manchmal aber auch lästige) Auswirkungen. Es erklärt, warum zum Beispiel ˹[0-9]+˼ auf die ganze Zahl in März1998 passt. Wenn die 1 einmal gefunden ist, hat das Pluszeichen sein minimales Plansoll erfüllt. Weil es aber gierig ist, versucht es, auf so viele Zeichen wie möglich zu passen; dies gelingt auch mit 998. Am Ende des Strings endet auch der Treffer, weil ˹[0-9]˼ nicht auf das Stringende passt.

Ein betreffendes Beispiel

Natürlich geht das auch mit anderen Dingen als nur mit Zahlen. Nehmen wir an, Sie haben eine Zeile aus einem E-Mail-Header und wollen überprüfen, ob es sich um die Betreffzeile handelt. Wie in einem früheren Kapitel (siehe unter Ein kleines Mail-Programm) benutzen Sie einfach ˹^Subject:˼. Wenn Sie aber ˹^Subject:(.*)˼ benutzen, können Sie später auf den Text des Betreffs zurückgreifen, indem Sie die vom benutzten Werkzeug gespeicherten Daten aus dem geklammerten Unterausdruck auswerten (zum Beispiel mit $1 in Perl). (Anmerkung: In diesem Beispiel wird das gierige Verhalten der Quantoren im Zusammenhang mit einfangenden Klammern beschrieben, daher gilt dies nur für NFA-Maschinen (nur NFAs unterstützen einfangende Klammern). Der Punkt, der sich auf die Gier bezieht, gilt allerdings für alle Arten von Maschinen.)

Bevor wir uns anschauen, warum das ˹.*˼ auf den ganzen Betreff passt, muss klar sein, dass der reguläre Ausdruck als Ganzes bereits erfolgreich ist. ˹^Subject:˼ wurde schon gefunden, und dahinter kommt nichts, was den Erfolg dieses Matchings noch gefährden könnte. ˹.*˼ wird immer passen, weil für den Stern auch das Resultat »nichts gefunden« ein erfolgreicher Treffer ist.

Warum ist denn das ˹.*˼ dabei, wenn es doch nichts zum Erfolg oder Misserfolg des regulären Ausdrucks beiträgt? Wir wissen, dass der Stern gierig ist; er versucht, den Punkt auf so viele Zeichen wie möglich anzuwenden, und hier nutzen wir es aus, um $1 »auszufüllen«. Die Klammern tragen nichts zur Logik dieser Mustersuche bei. Wenn mit ˹.*˼ das Stringende erreicht wird, bleibt nichts mehr übrig, auf das der Punkt passen könnte. Der Quantor hört auf und überlässt das Feld weiteren Elementen aus dem regulären Ausdruck (auch wenn der Punkt auf nichts mehr passt, könnte es sein, dass allenfalls weiter rechts noch Teile des regulären Ausdrucks auf etwas passen könnten). Da in diesem Fall aber keine weiteren Elemente auftreten, weiß die Regex-Maschine, dass ein Treffer gefunden wurde.

Zu gierig

Zurück zur Vorstellung der über alle Maßen gefräßigen gierigen Quantoren. Wie sähe das aus, wenn wir ein zweites ˹.*˼ anfügten: ˹^Subject:(.*).*˼? Die Antwort ist einfach: Es ändert sich gar nichts. Das erste ˹.*˼ (in den Klammern) ist so gierig, dass es bereits alle Zeichen des Betreff-Textes erkannt hat, und damit bleibt für das zweite ˹.*˼ nichts übrig, worauf es passen könnte. Das macht nichts aus, weil sich der Stern in harten Zeiten auch mit gar nichts zufriedengibt. Wäre das zweite ˹.*˼ eingeklammert, würde das entsprechende $2 immer leer sein.

Bedeutet das nun, dass nach einem ˹.*˼ in einem regulären Ausdruck nie etwas passen kann? Nein, natürlich nicht. Wie Sie beim Beispiel mit ˹\w+e˼ gesehen haben, ist es möglich, dass spätere Elemente eines regulären Ausdrucks die gierigen Quantoren zwingen, Zeichen zurückzugeben, dass sie sozusagen Treffer aberkennen, wenn es dazu dient, dass die Regex als Ganzes erfolgreich passen kann.

Der Ausdruck ˹^.*([0-9][0-9])˼ findet die zwei letzten Ziffern im String, wo immer sie auftreten, und speichert sie in $1. Und das funktioniert so: Zunächst erkennt ˹.*˼ den ganzen String. Weil aber das folgende ˹([0-9][0-9])˼ vorgeschrieben ist, sagt es ungefähr: »Hallo, du hast zu viel genommen! Gib etwas zurück, damit ich auch eine Chance bekomme, auf Zeichen zu passen!« Gierige Komponenten versuchen zunächst, so viel wie möglich für sich selbst zu kriegen, sie beugen sich aber dem übergeordneten Ziel, dass der ganze Ausdruck passen soll. Sie sind aber hartnäckig und tun das nur unter Zwang.

Wenn wir also ˹^.*([0-9][0-9])˼ auf den String ›etwa20Zeichenlang‹ anwenden, erkennt ˹.*˼ wieder zunächst den ganzen String. Weil aber das erste ˹[0-9]˼ nach einer Ziffer sucht, fordert es das ›g‹ (das letzte Zeichen, das erkannt wurde) zurück. Das passt nicht, also muss ˹.*˼ ein weiteres Zeichen zurückgeben, das n in lang. Das wiederholt sich noch zwölfmal, bis mit 0 eine Ziffer erkannt wird.

Damit ist wohl das erste ˹[0-9]˼ zufrieden (es findet eine Ziffer, 0), aber nicht das zweite. Das ˹.*˼ muss noch weitere Zeichen abgeben, damit der reguläre Ausdruck als Ganzes passen kann. Diesmal ist es die 2, die vom ersten ˹[0-9]˼ erkannt wird; die 0 wird für das zweite ˹[0-9]˼ freigegeben, der ganze Ausdruck passt auf ›etwa20Zeichen...‹, und in $1 wird ›20‹ eingetragen.

Wer zuerst kommt, mahlt zuerst

Wir könnten versucht sein, den Ausdruck so abzuändern, dass nicht nur die letzten zwei Ziffern, sondern die ganze letzte Ziffernreihe im String erkannt würde: ˹^.*([0-9]+)˼. Wenn wir diese Regex auf den String ›Copyright 2003.‹ anwenden – was wird von den Klammern aufgefangen? Auflösung siehe Lösung 17.

Bis zu den letzten Details

Ich sollte hier einiges aufklären. Wendungen wie »das ˹.*˼ muss abgeben ...« oder »˹[0-9]˼ erzwingt ...« sind etwas irreführend. Ich habe diese Formulierungen benutzt, weil sie leicht verständlich sind und weil das Resultat tatsächlich der Realität entspricht. Was aber wirklich hinter den Kulissen abläuft, hängt von der verwendeten Maschine ab, von DFA oder NFA. Also wird es langsam Zeit zu sehen, worum es sich hier eigentlich handelt.

  

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