Possessive Quantoren und atomare Gruppen

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

Das ›.625‹-Beispiel von Gierig oder genügsam -– der Treffer geht vor eröffnet ein paar wichtige Einsichten in die Arbeitsweise eines NFA und hat gezeigt, wie unsere naiven Ansätze vereitelt wurden. Manche Implementationen haben Features, die uns weiterhelfen könnten, dazu sind aber die Punkte aus der vorherigen Seite, Gier, Genügsamkeit, Backtracking: Die Essenz, unbedingte Voraussetzung. Lesen Sie bitte dort nach, wenn irgendetwas unklar ist.

Zurück also zum ›.625‹-Beispiel mit den Börsenkursen. Wir möchten die Regex so steuern können, dass die Maschine, wenn sie einmal bei der markierten Stelle ˹(\.\d\d[1-9]?)▵\d+˼ angekommen ist, nie mehr mittels Backtracking zurückgeht. Wir wollen also, dass ˹[1-9]˼ wann immer möglich passt, und wenn es einmal gepasst hat, wollen wir nicht, dass dieser lokale Treffer je wieder aufgegeben wird. Vielmehr möchten wir, dass die ganze Mustersuche zu einem Fehlschlag wird, als dass ein Zeichen, das einmal von ˹[1-9]˼ erkannt wurde, zurückgegeben wird. (Sie erinnern sich: Als diese Regex auf ›.625‹ angewendet wurde, gab die Maschine nicht auf, sondern ging zu einem gespeicherten Zustand zurück und fand eine andere, falsche Möglichkeit.)

Und wenn wir nur diese »falsche Möglichkeit« verhindern könnten (also verhindern, dass der Zustand des ˹?˼ gerade vor dem Versuch mit ˹[1-9]˼ abgespeichert würde)? Wenn es keinen gespeicherten Zustand gibt, würde ein lokaler Treffer bei ˹[1-9]˼ nicht mehr aufgegeben. Ja, genau das brauchen wir! Was passiert, wenn wir die Regex auf ›.5000‹ anwendeten? Das ˹[1-9]˼ würde nicht mehr passen, und in diesem Fall wollen wir, dass die Maschine zurückgeht und das ˹[1-9]˼ überspringt, damit das folgende ˹\d+˼ die überflüssigen Ziffern erkennt.

Das klingt fast nach zwei sich ausschließenden Wünschen, aber genau betrachtet wollen wir nur, dass die Möglichkeit »˹[1-9]˼ überspringen« dann nicht mehr betrachtet wird, wenn die Möglichkeit »˹[1-9]˼ passt« erfolgreich war. Wenn ˹[1-9]˼ einmal gepasst hat, soll der entsprechende Zustand aus der Liste der gespeicherten Zustände entfernt werden. Das geht tatsächlich, zumindest bei Regex-Dialekten, die entweder atomare Gruppen mit ˹(?>...)˼ (siehe den Abschnitt Atomare Klammern) oder possessive Quantoren wie ˹[1-9]?+˼ (siehe den Abschnitt Possessive Quantoren) unterstützen. Wir betrachten zuerst die atomaren Gruppen.

Atomare Gruppen mit ˹(?>...)˼

Im Wesentlichen verläuft die Mustersuche innerhalb von ˹(?>...)˼ ganz normal, aber wenn sich die Maschine erfolgreich durch die atomare Klammer hindurchgearbeitet hat (und also bei der schließenden Klammer angelangt ist), werden alle Zustände wieder gelöscht, die während dieses Vorgangs gespeichert wurden. Das bewirkt, dass die Maschine nie mehr zu einem Entscheidungspunkt innerhalb der Klammer zurückkehren kann. Der Text, der von der Klammer erkannt wurde, ist nun eine unveränderliche Einheit, die nur als Ganzes (atomar) zurückgegeben werden kann. Alle Zustände, die noch nicht ausprobierten Wegen entsprechen, werden beim erfolgreichen Verlassen der Klammer beseitigt. Sie sind damit dem Backtracking-Mechanismus entzogen.

Betrachten wir unser Beispiel mit einer atomaren Klammer, ˹(\.\d\d(?>[1-9]?))\d+˼. Innerhalb von atomaren Klammern verhalten sich die Quantoren ganz normal. Wenn also ˹[1-9]˼ nicht passt, kehrt die Maschine zum Zustand vor der »Passen oder überspringen«-Entscheidung zurück, die durch das ˹?˼ hervorgerufen wurde. In diesem Fall gibt es keine gespeicherten Zustände mehr, die beim Verlassen der Klammer fortgeworfen werden müssten (also keine Zustände, die während des Durcharbeitens der Klammer abgespeichert wurden).

Wenn dagegen das ˹[1-9]˼ eine Ziffer erkennt, passt die ganze Klammer beim ersten Versuch, aber der durch das Fragezeichen erzeugte gespeicherte Zustand ist immer noch vorhanden. Da dieser während der Klammer erzeugt wurde, wird er jetzt entfernt. Das würde z.B. bei ›.625 ‹ oder bei ›.625000‹ geschehen. Im letzteren Fall spielt das Entfernen der gespeicherten Zustände keine Rolle, weil das folgende ˹\d+˼ auf ›.625000‹ passt und die Regex-Maschine nicht mehr backtracken muss. Bei ›.625‹ aber wird kein Text für ˹\d+˼ gefunden. Die Maschine möchte mittels Backtracking Ziffern zurückholen, aber das geht nicht, weil der Zustand bei der »Passen oder überspringen«-Entscheidung fortgeworfen wurde. Es gibt überhaupt keine gespeicherten Zustände mehr, die Mustersuche schlägt als Ganzes fehl, und das ›.625‹ wird ganz nach unserer Absicht nicht verändert.

Atomare Gruppen: Die Essenz

In Gier, Genügsamkeit, Backtracking: Die Essenz heißt es, dass die gierigen oder nicht-gierigen Konstrukte keinen Einfluss darauf haben, welche Varianten durchprobiert werden, sie haben nur einen Einfluss darauf, in welcher Reihenfolge die Möglichkeiten getestet werden. Wenn sich die ganze Suche als Fehlschlag erweist, sind alle möglichen Wege begangen worden, ob gierig oder nicht.

Bei atomaren Gruppen wird das konzeptionell anders, weil hier vorher mögliche Wege eliminiert werden. Das Entfernen von gespeicherten Zuständen kann je nach Situation verschiedene Auswirkungen haben:

Kein Effekt

Wenn ein Treffer gefunden wird, bevor einer der eliminierten Zustände an die Reihe gekommen wäre, verläuft die Mustersuche wie ohne die atomaren Klammern. Genau das haben wir im vorigen Abschnitt bei ›.625000‹ erlebt: Es wurde ein globaler Treffer gefunden, ohne dass jemals ein gespeicherter Zustand reaktiviert werden musste.

Kein Treffer

Durch das Entfernen von Zuständen kann der Fall auftreten, dass gerade deswegen die Regex als Ganzes nicht mehr passt. Das haben wir beim Beispiel mit ›.625‹ gesehen.

Ein anderer Treffer

In bestimmten Fällen steuern die atomaren Klammern die Regex-Maschine zu einem anderen möglichen Treffer.

Schnellerer Fehlschlag

Wenn auch ohne die atomaren Klammern kein Treffer möglich ist, kann es sein, dass die Regex-Maschine diese Tatsache mit atomaren Klammern schneller herausfindet, weil sie weniger Möglichkeiten testen muss.

Eine kleine Aufgabe: Was bewirkt das Konstrukt ˹(?>.*?)˼? Was für Dinge werden damit erkannt? Zur Auflösung siehe Lösung 12.

Manche Zustände bleiben erhalten

Wenn die Regex-Maschine sich durch eine atomare Gruppe hindurchgearbeitet hat, werden nur die gespeicherten Zustände beseitigt, die während der atomaren Gruppe dazugekommen sind. Gespeicherte Zustände, die schon vorher da waren, bleiben unberührt. So kann der Text, der durch die gesamte atomare Gruppe erkannt wurde, ohne Weiteres vom Backtracking-Mechanismus zurückgegeben werden.

Schnellere Fehlschläge mit atomaren Gruppen

Wenn ˹^\w+:˼ auf ›Subject‹ angewendet wird, sehen wir sofort, dass das nie passen kann, weil im Text kein Doppelpunkt vorkommt. Die Regex-Maschine aber kommt erst nach vielen Versuchen zu diesem Ergebnis.

Wenn zum ersten Mal auf ˹:˼ geprüft wird, hat das ˹\w+˼ den ganzen String durchquert. Dabei wurde eine ganze Reihe von Zuständen abgespeichert – ein »Überspring mich«-Zustand für jedes Zeichen im String, das von ˹\w˼ und dem Pluszeichen gefunden wurde (außer dem ersten, dieses ist ja beim Plus obligatorisch). Wenn die Maschine beim letzten Zeichen angekommen ist und das ˹:˼ fehlschlägt, geht die Maschine zum letzten Zustand zurück:

im Text: ›Subjec▵t‹

in der Regex: ˹^\w+▵:˼

An diesem Punkt passt das ˹:˼ aber auch nicht auf das ›t‹. Diese Backtrack-Test-Schleife wiederholt sich, bis die Maschine beim ältesten Zustand angelangt ist:

im Text: ›S▵ubject‹

in der Regex: ˹^\w+▵:˼

Auch hier passt das ˹:˼ nicht, und endlich ist klar, dass die gesamte Regex nicht passt.

Dieses ganze Backtracking ist ein ganzes Stück Arbeit, das wir auf den ersten Blick als unnötig erkennen können. Wenn der Doppelpunkt nicht auf das letzte Zeichen passt, dann sicher auch nicht auf die Wort-Zeichen, die der Reihe nach vom ˹+˼ zurückgefordert werden.

Wenn wir wissen, dass die gespeicherten Zustände unnütz sind, wenn der Doppelpunkt am Ende nicht passt, können wir das der Regex-Maschine auch mitteilen: ˹^(?>\w+):˼. Mit der atomaren Klammer drücken wir unser »globales Wissen« aus und können so die Effizienz des lokalen ˹\w+˼ verbessern. Wenn ein Treffer gefunden wird, spielt die atomare Klammer keine Rolle; wenn nicht, gibt es keine gespeicherten Zustände, und die Maschine findet viel schneller heraus, dass kein Treffer möglich ist. (Eine gute Implementation kann diese Situation erkennen und diese Optimierung intern selbständig vornehmen, siehe den Abschnitt Automatische »Possessifizierung«.)

Unter Die Kunst, reguläre Ausdrücke zu schreiben (siehe unter Atomare Gruppen und possessive Quantoren verwenden) werden Sie sehen, dass diese Technik sehr nützlich ist, und das ist wahrscheinlich auch der häufigste Verwendungszweck von atomaren Klammern.

Possessive Quantoren: ?+, *+, ++ und {m,n}+

Possessive Quantoren sind zunächst einmal gierig, aber auch krankhaft geizig: Was sie einmal erkannt haben, geben sie nie mehr zurück. Bis ein von einem Pluszeichen quantisierter Unterausdruck durchgearbeitet ist, wird eine ganze Menge von Zuständen abgespeichert, wie Sie im Beispiel mit ˹^\w+˼ eben gesehen haben. Bei einem possessiven Pluszeichen werden diese Zustände sofort weggeworfen (bzw. gar nicht erst erzeugt).

Wie Sie vielleicht vermuten, sind die possessiven Quantoren den atomaren Klammern nahe verwandt. Ein possessiver Ausdruck wie ˹\w++˼ arbeitet so wie ˹(?>\w+)˼; es ist mehr eine Frage der Notation. (Anmerkung: Eine gute Implementation kann jedoch die possessive Version ein bisschen effizienter machen als den entsprechenden atomaren Klammerausdruck (siehe den Abschnitt Automatische »Possessifizierung«).) Mit diesen geizigen Quantoren kann man das Beispiel ˹^(?>\w+):˼ zu ˹^\w++:˼ umschreiben, und ˹(\.\d\d(?>[1-9]?))\d+˼ wird zu ˹(\.\d\d[1-9]?+)\d+˼.

Ist Ihnen der Unterschied zwischen ˹(?>M)+˼ und ˹(?>M+)˼ klar? Im ersten Fall werden die unbenutzten Zustände weggeworfen, die durch das ˹M˼ erzeugt wurden – das ist sinnlos, weil bei ˹M˼ überhaupt keine Wahlmöglichkeiten bestehen und daher keine Zustände erzeugt werden. Beim zweiten Fall werden die durch ˹M+˼ erzeugten Zustände eliminiert, das spart viele mögliche Wege ein.

Bei dieser Gegenüberstellung von ˹(?>M)+˼ und ˹(?>M+)˼ wird vielleicht klarer, dass der zweite Ausdruck mit ˹M++˼ vergleichbar ist. Wenn man kompliziertere possessive Ausdrücke wie ˹(\\"|[^"])*+˼ in die Form mit atomaren Gruppen überführen will, ist es nur zu verlockend, den bestehenden Klammern noch ein ›?>‹ hinzuzufügen: ˹(?>\\"|[^"])*˼. Der neue Ausdruck führt vielleicht sogar zum Ziel, aber er entspricht nicht dem ursprünglichen possessiven Konstrukt. Die zwei Versionen verhalten sich wie ˹M++˼ zu ˹(?>M)+˼. Um den vergleichbaren atomaren Ausdruck zu erhalten, muss man das »geizige« Plus entfernen und den Rest in eine atomare Klammer einpacken: ˹(?>(\\"|[^"])*)˼.

  

<< zurück

vor >>