Sql-und-Xml - Home

Regular Expressions

Gierige und träge Quantifikatoren für die Festlegung, wie oft ein Muster gefunden werden soll

An jeden beliebigen Ausdruck kann ein Quantifikator angehängt werden. Von diesen gibt es zwei Typen - vordefinierte (*, +, ?) einschließlich der trägen Form (*?, +?, ??) und selbstdefinierte, für deren Darstellung geschweifte Klammern genutzt werden. Zu beachten ist, daß der Stern-Operator '*' innerhalb von RegEx nicht den Platzhalter für ein beliebiges Zeichen darstellt, sondern nach null oder mehr Übereinstimmungen des vorstehenden Ausdrucks sucht.

Im Prinzip ist die Verwendung von Quantifikatoren höchst einfach: Fehlt ein Quantifikator, so wird das vorstehende Suchmuster genau einmal gefunden, um ein positives Ergebnis zu produzieren. Deshalb findet a, angewandt auf die Eingabe aaabaaca jedes einzelne 'a' als ein eigenständiges Ergebnis, so daß der RegEx-Trainer sechs Zeilen ausgibt: aaabaaca. Die Verwendung von a+ findet dagegen das erste 'a', der Quantifikator sorgt dafür, daß alle weiteren 'a' gefunden werden, so daß sich insgesamt drei Fundstellen ergeben: aaabaaca. Hier bilden zusammenhängende 'a' ein gemeinsames Ergebnis, die Positionen von b und c erzeugen keine Ergebniszeilen. Wird das Suchmuster a* genutzt, so ist das Ergebnis nicht mehr direkt darstellbar: Zunächst werden drei 'a' zusammengefaßt gefunden. Da kein 'a' mehr folgt, endet hier das erste Ergebnis. Die interne Position steht vor dem 'b'. Dieses ist kein 'a', die Suche nach 'kein a oder mehrere' ist also erfolgreich, so daß es eine neue Ergebniszeile im RegEx-Trainer gibt. Da das 'b' kein 'a' ist, kann dieser Ergebniszeile kein weiteres Zeichen hinzugefügt werden. Sie besteht aus einem Text der Länge Null und ist damit abgeschlossen. Anschließend wird die interne Position um ein Zeichen weitergeschoben. Es werden zwei 'a' gefunden und eine neue Ergebniszeile mit diesen erzeugt. Hier wiederholt sich das 'Null oder mehrere' an der Position vor dem 'c', schließlich wird das letzte 'a' als ein Ergebnis ausgegeben. Insgesamt gibt es also fünf Fundstellen, nicht, wie vielleicht erwartet, ebenfalls drei. Der '?'-Quantifikator gibt sich sogar mit keinem oder einem Ergebnis zufrieden. Als a? angewandt auf die Eingabenzeichenfolge liefert er jedes 'a' als eine einzelne Ergebniszeile der Länge 1. Zusätzlich sind die Positionen von 'b' und 'c' Fundstellen für 'kein a' und erzeugen Ergebniszeilen der Länge Null. Insgesamt erzeugt dieses Muster 8 Fundstellen.

Die bislang vorgestellten Quantifikatoren sind gierig, sie versuchen, möglichst viele Zeichen gemäß ihrer Definition zu finden. Ergänzt man sie um ein '?', so erzeugt dies die träge Version, die sich mit möglichst wenigen Fundstellen zufriedengibt. a+? findet nun ebenfalls jedes einzelne 'a' und gibt sechs Fundstellen der Länge 1 aus. Da sich '*?' sowie '??' bereits mit keinem Ergebnis zufriedengeben, liefern beide Suchmuster acht Ergebniszeilen der Länge Null.

Das Ergebnis, jedesmal angewandt auf die Zeichenfolge aaabaaca, läßt sich als Tabelle darstellen:

SuchmusterZahl der FundstellenFundstellen Länge Null
a60
a+30
a*52
a?88
a+?60
a*?88
a??88

Der Stern-Operator * und Null-Übereinstimmungen bei Zeilenwechseln

Die Wirkungsweise des Stern-Operators '*' darf nicht mit der Wirkung eines Platzhalter-* in einer Betriebssystem-Shell verwechselt werden. Denn '*' behandelt auch 0 Fundstellen als ein positives Resultat, wohingegen etwa die Dateisuche 'dir *.txt' als Ergebnis 'Datei nicht gefunden' ausgibt, falls das Verzeichnis keine Textdatei enthält. Ferner arbeitet RegEx immer zeichenorientiert, jede Einheit im Eingabestring, also jedes Unicode-Zeichen, wird verarbeitet. Das obige Beispiel der Suche nach 'a' ist noch insofern anschaulich, da es sich hierbei um ein konkretes Zeichen handelt. Wesentlich ist jedoch, den Quantifikator auch auf den Punkt als Platzhalterzeichen anzuwenden. Diese Kombination läßt sich am besten verständlich machen, indem man im RegEx-Trainer eine beliebige, aus zwei durch 'Return' getrennte Zeilen umfassende Zeichenfolge als zu durchsuchenden Text einträgt und das Suchmuster .* nutzt. Ohne weitere Optionen gilt der Punkt für jedes Zeichen mit Ausnahme des Zeilenumbruchs, der beide Zeilen trennt. Vielleicht wird erwartet, daß dieses Suchmuster zwei Ergebnisse findet und jede Zeile ausgibt. Tatsächlich werden jedoch drei Ergebnisse gefunden. Das erste und das dritte Ergebnis umfassen die erste und die zweite Zeile, dazwischen wird ein erfolgreiches Ergebnis mit einem String der Länge 0 ausgegeben. Der Punkt findet zunächst alle Zeichen bis zum Zeilenumbruch und stoppt, da der Zeilenumbruch ohne die SingleLine-Option nicht als gültiges Zeichen für den Punkt erkannt wird. Also ist das erste Ergebnis vollständig gefunden. Die interne Position steht nun direkt vor dem Zeilenumbruch. Hier folgt kein Zeichen und anschließend der nicht erkannte Zeilenumbruch, also ist die Suche mit einem Leerstring als Ergebnis erfolgreich. Dies ist das zweite positiv verarbeitete Resultat. Die interne Positionsmarkierung wird um ein Zeichen weiterbewegt und steht am Beginn der nächsten Zeile. Sie liefert das dritte Ergebnis.
Soll dieser Effekt vermieden werden, so ist der Quantifikator .+ zu nutzen. Dieser erfordert mindestens ein gefundenes Zeichen, damit ein Ergebnis gemeldet wird. Bei der zweiten Suche direkt vor dem Zeilenende wird kein Zeichen gefunden, das nächste Zeichen - der Zeilenumbruch - ist ungültig, also wurde nicht mindestens ein Zeichen gefunden. Folglich wird diese Position endgültig verworfen und für sie kein Ergebnis ausgegeben. Das Resultat sind die erwarteten zwei Zeilen. Dasselbe Ergebnis wird produziert, falls weitere Leerzeilen ohne Zeichen eingefügt werden.

Quantifikatoren und Klammern

Betrachten Sie die vier Suchmuster .+, (.+), (.)+ sowie ((.)+), angewandt auf die einfache Zeichenfolge abc. Der erste Ausdruck liefert die Eingabe als Ergebnis. Da keine Gruppe definiert wurde, gibt es nur die Standardgruppe mit der Nummer 0. Das zweite Suchmuster versucht, innerhalb der Klammern möglichst viele Zeichen zu finden, es verarbeitet die gesamte Eingabe und liefert als Wert der Gruppe 1 denselben Wert wie die Gruppe 0. Das dritte Suchmuster zeichnet für die Gruppe 1 zunächst das 'a' auf. Da der Quantifikator jedoch ein Weitergehen erzwingt und auch das 'b' ein gültiges Zeichen für den Punkt ist, überschreibt das 'b' den bereits zwischengespeicherten Wert 'a'. Dies wiederholt sich mit 'c', so daß das dritte Suchmuster 'c' als Wert der Gruppe 1 ausgibt. Das letzte Suchmuster kombiniert schließlich die Versionen 2 und drei. Die Gruppe 1 zeichnet die maximale Zeichenfolge auf, die Gruppe 2 enthält zusätzlich das zuletzt aufgezeichnete Zeichen.

Dargestellt als Tabelle:

SuchmusterWert Gruppe 0Wert Gruppe 1Wert Gruppe 2
.+abcnicht definiertnicht definiert
(.+)abcabcnicht definiert
(.)+abccnicht definiert
((.)+)abcabcc

Soll der gesamte Inhalt später weiterverarbeitet werden, so muß der Quantifikator innerhalb eines Klammerpaares notiert werden. Interessiert nur das letzte gefundene Zeichen, so muß der Quantikator herausgezogen werden. Die vierte Zeile kombiniert schließlich beide Anforderungen, falls sowohl die maximale Zeichenfolge als auch das letzte Zeichen benötigt wird.

Gierige (greedy) und träge (lazy) Quantifikatoren

Seien die Zeichenfolge Wir analysieren <b>RegEx</b> als <b>Sprache</b> zum Suchen und das Suchmuster <b>.*</b> gegeben. Es wird also zunächst nach dem Startelement '<b>', gefolgt von null oder mehr Zeichen, anschließend nach dem zugeordneten schließenden Element '</b>' gesucht. Die Intention ist, daß jedes Html-Element <b> mitsamt seinem Inhalt aufgelistet wird, es werden zwei Suchergebnisse erwartet.

Ein Einsetzen in den RegEx-Trainer liefert jedoch das einzelne Ergebnis:

Wir analysieren <b>RegEx</b> als <b>Sprache</b> zum Suchen

Es werden nicht zwei, sondern es wird nur ein einziges Ergebnis ausgegeben, welches jedoch den Bereich vom ersten öffnenden '<b>' bis zum letzten schließenden '</b>' umfaßt.

Jeder Quantifikator (*, +, ?) ist gierig (greedy), er versucht, so viel wie möglich zu verarbeiten, die maximale Zahl von Übereinstimmungen zu finden. Ist jedoch die minimale Zahl von Übereinstimmungen gewünscht so können die korrespondierenden Quantifikatoren (*?, +?, ??) genutzt werden, welche durch Anhängen eines Fragezeichens an den Quantifikator gebildet werden. Die Quantifikatoren werden durch das angehängte Fragezeichen träge (lazy). So findet <b>.*?</b> tatsächlich

Wir analysieren <b>RegEx</b> als <b>Sprache</b> zum Suchen

und gibt im RegEx-Trainer zwei gefundene Zeilen aus.

Man kann sich den Unterschied zwischen gierigen und trägen Quantifikatoren so vorstellen, daß gierige Quantifikatoren bei der Suche nach .* zum Ende der Eingabezeichenfolge springen, da der Punkt alles erfüllt und maximal gesucht werden soll. Folgt nach dem Quantifikator ein konkreter Ausdruck, etwa .*</b>, so muß rückwärts gesucht werden, bis das zusätzliche Muster gefunden wurde. Dies wird als Rückwärtsverarbeitung oder Zurückverfolgung (backtracking) bei der Verarbeitung von gierigen Quantifikatoren bezeichnet. Im obigen Fall wird durch die Auswertung von <b> zunächst ein <b> gefunden, dann folgt ein Punkt mit gierigem Quantifikator, also springt die Verarbeitung an das Ende der Eingabezeichenfolge und findet dort ein beliebiges, also passendes Zeichen. Würde nach <b>.* gesucht, so wäre die Suche nun erfolgreich beendet und würde Wir analysieren <b>RegEx</b> als <b>Sprache</b> zum Suchen zurückliefern. Da jedoch zusätzlich nach </b> zu suchen ist, wird von hinten her rückwärts nach dem ersten Auftreten dieser Zeichenfolge gesucht und das 'gierige Ergebnis' ausgegeben. Ein träger Quantifikator dagegen fängt unmittelbar nach der letzten Fundstelle, also direkt nach <b> an, nach </b> zu suchen, da .* bereits an der Grenze der zwischen der schließenden > und jedem folgenden Zeichen erfüllt ist.

Bei Kombinationen von Quantifikatoren, unterbrochen von konkreten Zeichen, vervielfachen sich die Möglichkeiten. Man betrachte das Suchmuster <b>(.+)</b>(.+)c. Es liefert, ergänzt um alle vier Kombinationen von gierigen/trägen Quantifikatoren sowie angewandt auf den Beispielsatz, für jeden der vier denkbaren Fälle ein anderes Ergebnis:

SuchmusterGesamtergebnis(1)(2)
<b>(.+)</b>(.+)u<b>RegEx</b> als <b>Sprache</b> zum SuRegEx</b> als <b>Sprache zum S
<b>(.+?)</b>(.+)u<b>RegEx</b> als <b>Sprache</b> zum SuRegEx als <b>Sprache</b> zum S
<b>(.+)</b>(.+?)u<b>RegEx</b> als <b>Sprache</b> zuRegEx</b> als <b>Sprache z
<b>(.+?)</b>(.+?)u<b>RegEx</b> als <b>Sprache</b> zuRegEx als <b>Sprache</b> z

Im ersten Fall sind beide Quantifikatoren gierig, so daß zunächst der erste Ausdruck möglichst viel einsammelt und der zweite vom verbleibenden Rest ebenfalls möglichst viel findet. Im zweiten Fall ist der erste Quantifikator träge. In dem, was er übrig läßt, kommt jedoch das als letztes geforderte 'u' nicht vor, also gelangt der gierige zweite Quantifikator wieder zur gleichen Schlußposition und erhält zusätzlich einiges von dem, was ihm der erste Quantifikator übriggelassen hat. Der dritte Fall entspricht für den ersten Quantifikator der ersten Zeile, der zweite erhält minimal nur zwei Zeichen. Sind beide Quantifikatoren träge, so findet der erste dasselbe wie in Zeile zwei, beim zweiten Quantifikator verringert sich dies zusätzlich um 'm Su'.

Benutzerdefinierte Quantifikatoren

Benutzerdefinierte Quantifikatoren werden immer in der Form {Zahl[, [weitere Zahl]]} bzw. mit angehängtem Fragezeichen definiert. Wird nur eine einzige Zahl notiert, so soll das zuvor notierte Muster genau so oft gefunden werden. a{2} ist gleichbedeutend mit aa, bei komplizierteren Mustern ist die erste Notation einfacher und leichter zu ändern. Mit {m,n} kann das Muster mindestens m und bis zu n mal gefunden werden. Dieser Quantifikator ist gierig, so daß a{2,3} angewandt auf xaaaaa zwei Fundstellen liefert. Die erste Fundstelle umfaßt die ersten drei 'a', die zweite Fundstelle die beiden letzten. Der zugeordnete träge Quantifikator a{2,3}? gibt sich mit möglichst wenig zufrieden, so daß hier die erste und die zweite Fundstelle jeweils 2 'a' umfassen und das fünfte 'a' nicht mehr in das Ergebnis aufgenommen wird. Schließlich kann a{2,} notiert werden, dies fordert 2 oder mehr Wiederholungen. Angewandt auf das Beispiel wird eine Fundstelle mit fünf 'a' gefunden. Wird dieser Ausdruck mit '?' träge, so findet er wieder zwei Fundstellen mit je 'aa' als Ergebnis.

Eine grammatikalische Bemerkung zum Schluß: Im Internet findet sich wiederholt die Bezeichnung Quantifizierer als deutsche Übersetzung des englischen quantifier. Diese Übersetzung ist jedoch, obwohl sie bsp. in der Microsoft-NET-Dokumentation verwendet wird, falsch. Laut Duden gibt es den Begriff 'Quantifizierer' nicht. Im hiesigen Text wird durchweg Quantifikator verwendet.

© 2003-2016 Jürgen Auer, Berlin.