Alternierungen I und Backtracking

• » Home
• »Regular Expressions
• » Alternierungen, Zurückverfolgen

Es gibt Fälle, in welchen es wünschenswert ist, nach einem von mehreren Ausdrücken zu suchen. Eine solche Alternierung kann mit | erreicht werden. So findet \b(und|oder)\b die beiden Ergebnisse Kaffee und Milch oder Zucker - undenkbar!. Bei diesem Konzept ist wesentlich, zu verstehen, daß das Analysemodul an jeder Stelle zunächst bis zu drei Zeichen vorwärts sucht, um ein 'und' zu finden, hierbei jedoch die Ausgangsposition zwischenspeichert. Wurde die erste Zeichenfolge nicht gefunden, so wird zur ursprünglichen Stelle zurückgesprungen und versucht, den zweiten Ausdruck nach dem | zu finden. Erst wenn dieser Vergleich ebenfalls scheitert, wird ein Zeichen weitergewandert und das ganze Procedere wiederholt, bis das Ende der Zeichenfolge erreicht ist. So werden beim letzten undenkbar zwar die ersten drei Zeichen gefunden. Da anschließend jedoch kein Wechsel zwischen Wort und Nicht-Wort folgt, wird auf das erste 'u' zurückgegangen und dieses auf 'oder' geprüft. Wird nach \b(und\b|oder\b|undenk) gesucht, so wird der letzte Ausdruck gefunden.

 

Beachten Sie, daß im Fall von Alternierungen das Backtracking als Sprung erfolgt: Scheitert die Suche nach und, folgt jedoch im Suchmuster |oder, so wird um jene drei Zeichen zurückgesprungen, die für die Suche nach und bereits verarbeitet wurden. Das Backtracking bei gierigen Quantifikatoren geht dagegen Zeichen um Zeichen rückwärts. Folgen deshalb auf gierige Quantifikatoren weitere Zeichen, so wird die gesamte Zeichenfolge von der aktuellen Position bis zum Ende, am Ende beginnend, rückwärts Zeichen um Zeichen verarbeitet, bevor das endgültige Mißlingen ausgegeben bzw. weiterverarbeitet wird.

 

Ein Beispiel: Die Suche nach a.+c liefert abcdef. Das erste 'a' wird auf der Position 1 gefunden, also wird diese zwischengespeichert. Aufgrund '.+' gibt es einen Sprung zum Ende, dreimal wird ein 'c' vergeblich gesucht und dieses schließlich auf Position 3 gefunden. Bei der Suche nach a.+g gibt es dagegen mit dem Start 'a' fünf negative Versuche, bis die Suche ausgehend von diesem 'a' endgültig gescheitert ist und zum 'b' auf der zweiten Position weitergewandert wird. Das 'b' ist kein 'a', eine Alternierung gibt es auf dieser Position auch nicht, also kann die zweite Position nicht als Startposition für eine Weiterverarbeitung genutzt werden, es wird zur dritten Position gewechselt. Dies wiederholt sich, so daß kein Suchergebnis (im RegEx-Trainer: Keine Zeile) gefunden wird. Wird das Suchmuster auf eine Zeichenfolge abacadaeaf angewandt, so wird fünf Mal, ausgehend von jedem der fünf 'a', zum Ende gesprungen und die dazwischenliegende Zeichenfolge rückwärts durchsucht.

Alternierungen II

Bei Alternierungen mit | wird implizit alles links und rechts von dem senkrechten Strich geklammert, sofern nicht '|' selbst innerhalb einer begrenzenden Klammer notiert ist. Ma|eier findet deshalb Frau Maier und Herr Meier gehen zusammen essen, erst das Suchmuster M(a|e)ier findet das wohl intendierte Ergebnis Frau Maier und Herr Meier gehen zusammen essen. Theoretisch ist es auch denkbar, daß Maier|Meier genutzt wird. Allerdings ist diese Lösung schlechter als die obige Version, da bei einer Eingabe Maienberger zunächst vier Zeichen geprüft werden, ehe diese Position als ungültig verworfen wird. Falls in solchen Ausdrücken nicht der Einzelbuchstabe (a|e), sondern nur das Gesamtergebnis (Maier|Meier) interessiert, so sind diese Alternierungen, die verschiedene Schreibweisen innerhalb eines Wortes erfassen, gute Kandidaten für die Verwendung von nicht aufzeichnenden Teilgruppen. Damit wird der Ausdruck M(?:a|e)ier genutzt. Sollen auch die Varianten i/y erfaßt werden, so ist schließlich M(?:a|e)(?:i|y)er zu verwenden und findet Maier/Mayer/Meyer/Meier.

 

Bei den Alternierungen ist zu beachten, daß sie von links nach rechts ausgewertet werden. Hierbei kann es zu unerwünschten Effekten kommen, falls ein zuerst zu prüfender Ausdruck gleichzeitig ein Teil eines später zu testenden Ausdrucks ist. Das Suchmuster ins|insge findet insbesondere arbeiten wir insgeheim exzessiv, da es zunächst 'ins' prüft und beim erfolgreichen Vergleich den zweiten Ausdruck nicht mehr näher betrachtet, sondern vor das erste Zeichen nach der aktuellen Fundstelle wechselt. Die Umkehrung insge|ins prüft zunächst den längeren der beiden Ausdrücke und findet an der zweiten Fundstelle diesen, hier wird die kürzere Version ignoriert. Damit produziert das zweite Suchmuster insbesondere arbeiten wir insgeheim exzessiv als Ergebnis.

If-Then-Else- bzw. Ja/Nein-Verzweigungen

Der Ausdruck A|B läßt sich folgendermaßen als Wenn-Dann-Bedingung interpretieren:

Prüfe A, falls erfolgreich, gehe weiter. Falls A nicht erfüllt ist, prüfe B.

A läßt sich also interpretieren als If-Bedingung mit einem leeren Then-Zweig, hier wird die Auswertung sofort nach dem Gesamtausdruck fortgesetzt. Der Else-Zweig enthält das zusätzliche Kriterium B, so daß dieser Zweig nicht in jedem Fall, sondern nur beim Vorliegen von B ausgeführt wird. 'Ausführen' müßte in diesem Zusammenhang als 'Fortsetzung des Prüfens anstelle eines Abbruchs' interpretiert werden.
Es ist denkbar, daß nach dem erfolgreichen Prüfen von A eine weitere Bedingung C getestet werden soll, so daß der bislang fiktive Then-Zweig ebenfalls ein zusätzliches Kriterium erhält. Diese kann jedoch nicht an A als AC angehängt werden, da der vordere Teil bereits dann verworfen werden soll, falls nur A nicht erfüllt ist. Ferner darf sie nicht hinter den bisherigen Ausdruck notiert werden, da sie im Fall eines erfolgreichen B übersprungen werden muß. Eine solche Anforderung läßt sich mit dem Konstrukt (?(  )  |  ) realisieren. Die erste Bedingung wird implizit als Lookahead-Klausel interpretiert, so daß der gefundene Wert im Then-Abschnitt eventuell erneut notiert werden muß.
Das Konstrukt (?(a)ab|cd) findet ab abc acd bc cd ad. Auf jeder Position wird in Form einen positiven Lookahead geprüft ob ein 'a' gefunden werden kann, falls ja, muß auf das bereits gefundene 'a' ein 'b' folgen, um einen Gesamterfolg sicherzustellen. Beim Mißerfolg wird die Phrase 'cd' gesucht. ac/ad werden damit übersprungen, da nur 'b' als folgender Ausdruck erlaubt ist. Jedes 'c', auf das nicht ein 'd' folgt, wird ebenfalls ignoriert.

 

Ein interessanteres Beispiel ist das Suchmuster \bgeehrte(?(r )(r Herr)|( Frau)). Es sucht nach dem Wortanfang 'geehrte', wie er in Briefen verwendet wird und prüft, ob anschließend ein 'r ' folgt. Gilt dies, so muß ein 'Herr' angesprochen werden, ansonsten eine 'Frau' gefunden werden. Werden die inneren Ausdrücke als positive Lookahead notiert, so ergibt sich geehrte(?(r )(?=r Herr)|(?= Frau)) mit denselben Fundstellen. Dieser Ausdruck läßt sich durch einfaches Ersetzen der positiven durch die negative Lookahead-Version nutzen, um nun alle semantisch inadäquaten Ausdrücke auszugeben: geehrte(?(r )(?!r Herr)|(?! Frau)) findet Sehr geehrte Herr Müller ebenso wie Sehr geehrter Frau Maier, die korrekten Kombinationen werden übersprungen. Da zuletzt auf eine Assertion geprüft wird und diese nicht aufzeichnend ist, wird als Suchergebnis nur geehrte ausgegeben. Die Aufzeichnung des folgenden fehlerhaften Ausdrucks läßt sich auch nicht durch eine zusätzliche Klammer erzwingen. Sollen diese nicht mehr bekannten Werte ('Frrau', 'Heer') zusätzlich verarbeitet werden, so kann man entsprechende Ausdrücke anfügen: geehrte(?(r )(?!r Herr)|(?! Frau))(r{0,1})\s+?(.+?\b).
(r{0,1}) gibt an, ob ein 'r' notiert wurde. Das folgende Wort wird vom trägen Quantifikator (.+?\b) in einer weiteren Variablen abgelegt.

 

Eine verallgemeinerte Form der If/Then/Else-Verarbeitung kann in der Form (?((?'if'  ))(?'then'  )|(?'else'  )) notiert werden. Diese Version stellt keinen neuen Inhalt dar, sondern fügt dem If-Konstrukt lediglich benannte Gruppen hinzu.