Nicht-gierige Quantoren

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

Diese Probleme ergeben sich, weil die normalen Quantoren gierig sind. Manche NFAs unterstützen nicht-gierige Quantoren (siehe den Abschnitt Nicht-gierige, genügsame Quantoren), dabei ist *? die nicht-gierige Version von *. Mit einem genügsamen ˹<B>.*?</B>˼ und dem String

...<B>Millionen</B> und <B>Abermillionen</B> von Sonnen...

funktioniert das so: Nachdem das ˹<B>˼ gepasst hat, entscheidet das ˹.*˼ sofort, dass es auf gar nichts passen muss, und der Automat gibt die Kontrolle an das folgende ˹<˼ weiter.

Dieses ˹<˼ passt an dieser Position nicht, und durch Backtracking ist jetzt wieder das genügsame ˹.*?˼ an der Reihe. Diesem stehen noch weitere Möglichkeiten offen, es kann ja auch auf mehr als gar kein Zeichen passen. Damit passt es jetzt auf ...<B>Millionen..., und wieder versucht ˹<˼, auf das nächste Zeichen zu passen. Das geht schief, und so wiederholt sich der Zyklus zehnmal, bis das ˹.*?˼ Millionen erkannt hat, dann passt das folgende ˹<˼ (und auch der ganze Unterausdruck ˹</B>˼). Damit haben wir einen Treffer gefunden:

...<B>Millionen</B> und <B>Abermillionen</B> von Sonnen...

Sie haben gesehen, dass das gierige Verhalten der Quantoren manchmal äußerst nützlich ist, dass es einem aber auch in die Quere kommen kann. »Genügsame« Versionen dieser Quantoren sind in gewissen Situationen ideal, weil man damit Dinge erreichen kann, die sonst nur sehr schwer oder gar nicht realisierbar wären. Ich sehe dennoch oft Programme von ungeübten Programmierern, in denen die nicht-gierigen Quantoren in ungeeigneten Situationen verwendet werden. Auch die eben gezeigte Lösung kann in bestimmten Fällen falsch sein. Was geschieht, wenn wir ˹<B>.*?</B>˼ auf den folgenden Text anwenden?

...<B>Millionen und <B>Abermillionen<B> von Sonnen...

Das ergibt den unterstrichenen Treffer, der sehr wahrscheinlich nicht der ist, den man erwartet. In ˹.*?˼ gibt es nichts, das verbieten würde, auch auf <B> zu passen.

Das ist ein Musterbeispiel dafür, warum ein nicht-gieriger Quantor sehr oft kein guter Ersatz für eine negierte Zeichenklasse ist. Beim Beispiel mit ˹".*"˼ wird mit der negierten Zeichenklasse ˹[^"]˼ (statt des Punkts) ausdrücklich verboten, auf irgendeines der Trennzeichen zu passen – das können wir mit der aktuellen Regex nicht.

Mit einem negativen Lookahead-Konstrukt (sofern es unterstützt wird, siehe Lookhead; Lookbehind) können wir etwas Äquivalentes zur negierten Zeichenklasse aufbauen. Für sich genommen, testet der Ausdruck ˹(?!<B>)˼, dass sich an der aktuellen Position kein <B> befindet. An solchen Stellen wollen wir aber, dass der Punkt in ˹<B>.*?</B>˼ passt; wenn wir den Punkt durch ˹((?!<B>).)˼ ersetzen, erhalten wir eine Regex, die mit dem Punkt auf ein beliebiges Zeichen passt, aber nur dann, wenn wir das nicht mit dem Lookahead-Konstrukt verbieten. Zusammengesetzt sieht die Regex schon verwirrend aus, ich verwende daher den Modus »Freie Form« (siehe Der Modus »Freie Form«) mit Kommentaren:

Mit einer kleinen Anpassung im Lookahead-Konstrukt können wir auch einen normalen, gierigen Quantor verwenden, was für viele einfacher verständlich ist:

Das Lookahead-Konstrukt verbietet, dass der Teil zwischen den Begrenzungszeichen auf </B> oder auf <B> passt. Damit ist das Problem gelöst, das wir zunächst mit nicht-gierigen Quantoren zu lösen versuchten; wir können also einen normalen, gierigen Quantor verwenden. Auch diese Regex kann noch weiter verbessert werden; wir werden auf das Beispiel unter Die Kunst, reguläre Ausdrücke zu schreiben zurückkommen (siehe unter Beispiele zum Aufbrechen von Schleifen).