Atomare Assertionen

• » Home
• »Regular Expressions
• » Assertionen, nicht zurückverfolgende Teilausdrücke

Eine Assertion ist eine Behauptung, die wahr oder falsch, an der aktuellen Stelle erfüllt oder nicht erfüllt sein kann. Es gibt atomare Assertionen der Breite Null, die sich nur für die Beschreibung der aktuellen Position innerhalb des Gesamttextes interessieren, etwa die Überprüfung auf Anfang/Ende der Zeile oder eines Wortes. Die Suche nach a findet alle Buchstaben an beliebigen Positionen innerhalb ihrer Wörter. Die Suche nach \ba findet nur jene a an Wortanfängen oder am Anfang des Dokuments. Der durch \b gefundene Übergang zwischen einem Wort- und einem Nicht-Wort-Zeichen enthält selbst keine Zeichen, deshalb die Breite Null. Wird das Suchmuster \b auf die Zeichenfolge Wir lernen RegEx angewandt, so liefert der RegEx-Trainer sechs jeweils leere Ergebniszeilen aus - für jedes der drei Worte wird Wortbeginn und -ende erkannt. Da Ergebnisse der Länge Null nicht unterstrichen dargestellt werden können, erleichtert es den Umgang mit solchen Assertionen der Breite Null, wenn man anschließend .{0,1} notiert. Dies versucht, ein folgendes Zeichen zu finden und gibt sich auch damit zufrieden, falls am Zeilenende dieses nicht mehr durch den Punkt gefunden wird. Nun werden alle Anfangsbuchstaben sowie die dazwischenliegenden letzten Leerzeichen unterstrichen. Die atomaren Assertionen sind im wesentlichen selbsterklärend, näheres zur Multiline-Option findet sich im Kapitel über Optionen und Kommentare .

Lookahead/Lookbehind - Assertionen

Eine zweite Form von Assertionen stellen die Lookahead- und Lookbehind-Assertionen dar. Sie prüfen von der aktuellen Position aus vorwärts (ahead) oder rückwärts (behind), ob eine Zeichenfolge vorhanden (positiv) oder nicht vorhanden (negativ) ist. Damit gibt es die vier Fälle von positiven ((?=...)) und negativen ((?!...)) Lookahead sowie positiven ((?<=...)) und negativen ((?<!...)) Lookbehind-Assertionen. Im Gegensatz zu den direkt notierten Suchmustern wird jedoch ein positives Ergebnis nicht aufgezeichnet. An einem Beispiel deutlich gemacht: Eine Suche nach 'ver' sowie einem beliebigen Zeichen, eingesetzt in die vier Assertionstypen und angewandt auf die Zeichenfolge Wir verarbeiten Texte, liefert die folgenden Ergebnisse:

Typ	Suchmuster	Ergebnis	Zahl der Fundstellen
Positive Lookahead-Assertion	(?=ver).	Wir verarbeiten Texte	1
Negative Lookahead-Assertion	(?!ver).	Wir verarbeiten Texte	20
Positive Lookbehind-Assertion	(?<=ver).	Wir verarbeiten Texte	1
Negative Lookbehind-Assertion	(?<!ver).	Wir verarbeiten Texte	20

Immer wird von der aktuellen Position geprüft, ob vorwärts oder rückwärt die Zeichenfolge folgt oder nicht folgt. Insbesondere wird, verzichtet man auf zusätzliche gierige Quantifikatoren, bei der negativen Suche jede einzelne Position gefunden, die nicht in der gewünschten Form an die Zeichenfolge angrenzt. Bei der positiven Lookahead-Assertion fällt auf, daß sie der direkten Suche nach ver ähnelt. Letztere würde jedoch sofort die gesamte Zeichenfolge als Ergebnis ausgeben und für die nächste Suche vor dem folgenden 'a' postieren, wohingegen die Assertion vor dem 'ver' bleibt und mit dem Punkt den ersten Buchstaben dieser Zeichenfolge findet. Eine Suche der Form (?=v)[^v] führt also immer dazu, daß keine Stelle gefunden wird, da zunächst eine Position vor einem 'v', anschließend ein Zeichen <> v gefordert wird.

Nicht zurückverfolgende Teilausdrücke (nonbacktracking subexpression)

Betrachten Sie das Suchmuster (?'test'a*)ab. Es sucht null oder mehrere 'a', gefolgt von einer Kombination 'ab'. Zusätzlich ist die Teilzeichenfolge mit 'test' benannt. Dies angewandt auf eine Zeichenfolge aaab führt zunächst dazu, daß 3 'a' verarbeitet werden, der Quantifikator ist gierig. Nun folgt kein 'a', also kann diese Teilzeichenfolge auf keinen Fall ein positives Ergebnis liefern, es wird mit der Rückwärtsverarbeitung begonnen. Die vom gierigen Quatifikator zwischengespeicherte Zeichenfolge wird um ein Zeichen verkürzt. Nun kann ein folgendes 'ab' gefunden werden, so daß als benannte Teilzeichenfolge 'test' aa gefunden wird.
Die Verwendung von gierigen Quantifikatoren führt nicht dazu, daß in jedem Fall die maximal vorhandene Teilzeichenfolge gespeichert wird. Dies gilt nur, falls nach dem Quantifikator kein weiteres Suchkriterium angegeben ist. Ist ein solches zusätzliches Kriterium angegeben, so wird zunächst versucht, dieses mit der maximalen Teilzeichenfolge zu erfüllen. Scheitert dies, wird die bereits aufgezeichnete maximale Teilzeichenfolge Position um Position verkürzt und jedesmal erneut geprüft, ob nun die weiteren Bedingungen erfüllbar sind. Dies stellt sicher, daß die längstmögliche Teilzeichenfolge gefunden wird.
Verwendet man das Suchmuster (?=(?'test'a*))\k'test'b, so scheint es dasselbe zu leisten. Ausgehend von der aktuellen Position werden die folgenden 'a' ermittelt und zwischengespeichert, ohne daß die Position verändert wird - es handelt sich um eine Lookahead-Assertion. Dann wird mit \k'test' genau die zwischengespeicherte Folge gefunden, anschließend folgt ein 'b', also ist die Suche erfolgreich. Es wird zumindest dasselbe Ergebnis ermittelt, welches bei der Verwendung von (?'test'a*)b ausgegeben wird. Schiebt man jedoch vor das 'b' noch ein weiteres 'a' ein, verwendet man also (?=(?'test'a*))\k'test'ab im Vergleich zum bereits diskutierten (?'test'a*)ab, so findet das erste pattern nichts mehr. Der Grund hierfür ist, daß Lookahead-Assertionen nicht in die Rückwärtsverarbeitung einbezogen werden. Das erwartete Scheitern mit dem zwischengespeicherten 'aaa' führt nicht dazu, daß mit einer verkürzten Version erneut probiert wird, stattdessen wird diese Position endgültig verworfen.
Dieses Verhalten läßt sich direkt erzwingen, falls nicht zurückverfolgende Teilausdrücke (nonbacktracking subexpressions) der Form (?>a*)ab genutzt werden, die allgemeine Darstellung lautet (?>   ). Startet das verarbeitende Modul eine Rückwärtsverarbeitung, so ist diese aufwendig. Ihr Scheitern stellt sich erst am Ende heraus, nachdem die zunächst aufgezeichnete Teilzeichenfolge Zeichen um Zeichen verkürzt wurde. Ist dagegen aus dem Kontext heraus bekannt, daß es ohnehin keine kürzeren Lösungen geben kann, so sollten stattdessen nicht zurückverfolgende Teilausdrücke genutzt werden. Sie beschleunigen die Verarbeitungdauer und werden auch als gierige Teilausdrücke (greedy subexpressions) bezeichnet.

Ein Beispiel: In VisualBasic bzw. VB.NET wird ein Befehl durch Return abgeschlossen. Um eine lange Zeile umzubrechen und auf mehrere Zeilen verteilen zu können, kann am Ende ' _' + Return notiert werden. Dann werden beide Zeilen als ein zusammenhängender Befehl interpretiert. Ein Beispiel:

Console.WriteLine( _
	"Hello World")

Wie läßt sich dies mit RegEx als eine zusammenhängende Zeile identifizieren? Die Befehle, die nur aus einer Zeile bestehen, sollen ignoriert werden.
.+ sucht nach allen Zeichen in einer Zeile, . findet keine Zeilenumbrüche. Die Suche mit .+ findet zwei Zeilen. Am Ende der Zeile kann mit (?<= _)\n.* zunächst zurückgeblickt werden, ob zuvor ein Leerzeichen sowie '_' notiert wurden. Falls ja, werden der folgenden Zeilenumbruch sowie alle Zeichen in dieser Zeile gefunden. Wird der letzte Ausdruck geklammert und mit '+' quantifiziert, so ist er erfüllt, falls die Zeile wie von der VB-Definition gefordert fortgesetzt wird. Da ein oder mehrere Ausdrücke erlaubt sind, werden alle Folgezeilen gefunden, die noch zu diesem Befehl gehören. Verwendet man stattdessen '*', so erfüllt auch ein einzeiliger Befehl diese Bedingung, diese Version interessiert derzeit nicht. Da die Teilzeichenfolge nicht weiterverarbeitet werden muß, wird sie nicht-aufzeichnend definiert ((?: )). Insgesamt ergibt sich der Ausdruck .+(?:(?<= _)\n.*)+.
Nur: Was macht der erste Ausdruck .+? Er findet jedes Zeichen mit Ausnahme des Zeilenendes. Da ein gieriger Quantifikator folgt, kann zum Zeilenende gesprungen und der folgende Teilausdruck geprüft werden. Handelt es sich um eine einzelne Zeile ohne ' _', so wird die gesamte Zeile Zeichen um Zeichen verkürzt, obwohl eine mögliche Kombination ' _' weder interessiert noch durch ein nachfolgendes '\n' positiv ausgewertet werden würde. Das Scheitern der Verarbeitung dieser Zeile steht also von vornherein fest. Dennoch wird die gesamte Zeile in die Rückwärtsverarbeitung einbezogen und nach jedem Abschneiden des aktuell letzten Zeichens erneut geprüft, ob die Folgebedingung erfüllt ist. Die bessere Lösung ist deshalb:

(?>.+)(?:(?<= _)\n.*)+

Dies wertet den Quantifikator nur einmal aus und setzt die Verarbeitung anschließend am Ende der Zeile fort.