Reguläre Ausdrücke: Der gierige Punkt, fehlende Anker und verschachtelte Wiederholung

Ein regulärer Ausdruck beschreibt ein Textmuster. Die Engine ist das Programm, das dieses Muster auswertet. Schalter verändern einzelne Regeln, etwa die Unterscheidung zwischen Groß- und Kleinschreibung. Zum richtigen Ergebnis gehören neben dem Muster auch Regex-Engine, Schalter und aufgerufene Methode. Eine Teilzeichenfolge zu finden ist eine andere Aufgabe als die vollständige Eingabe zu prüfen.

Ein passendes Beispiel belegt weder korrekte Treffergrenzen noch eine akzeptable Laufzeit. Die folgenden Beispiele verwenden JavaScript, sofern keine andere Sprache genannt ist.

Gierig ist der Quantor

Ein Quantor legt fest, wie oft ein Teil des Musters vorkommen darf. Eine gierige Wiederholung versucht zuerst, möglichst viel passenden Text zu erfassen; eine faule Wiederholung beginnt mit möglichst wenig. Beide können diese Auswahl verändern, damit der restliche Ausdruck passt.

Der Punkt . trifft ein Zeichen; * wiederholt diesen Treffer gierig. In JavaScript bleiben Zeilentrenner ohne den dotAll-Schalter s ausgeschlossen. Ein wörtlicher Punkt wird als \. geschrieben. Bei zwei Verweisen mit doppelten Anführungszeichen kann href="(.*)" vom ersten öffnenden bis zum letzten schließenden Anführungszeichen reichen und das dazwischenliegende HTML einschließen.

href="(.*?)" versucht kürzere Gruppeninhalte zuerst. href="([^"]*)" schließt doppelte Anführungszeichen dagegen ausdrücklich aus dem Wert aus. Im abgebildeten Beispiel entstehen jeweils zwei Treffer, sofern die aufgerufene Methode alle Treffer sucht. Beide Muster ersetzen keinen HTML-Parser: Andere Anführungszeichen, Zeichenreferenzen und Dokumentstruktur erfordern für robuste Auswertung einen passenden Parser.

Eine verneinte Zeichenklasse garantiert nicht allgemein rücksprungfreie Auswertung. Beispielsweise kann [^,]+a ein bereits verbrauchtes Zeichen zurückgeben, damit das abschließende a passt. Im Linkbeispiel ist die ausdrücklich gesetzte Grenze am Anführungszeichen der entscheidende Vorteil.

Der Mehrzeilenschalter begrenzt keine Zeichenklasse

[^&] enthält Zeilenumbrüche, weil diese Zeichen keine Und-Zeichen sind. m verändert Anker, aber nicht die von der Klasse erfassten Zeichen. Der erste Ausdruck liefert deshalb einen Treffer über beide Zeilen. Der ausdrückliche Ausschluss von CR und LF ergibt zwei Treffer:

const text = 'utm_source=newsletter\nutm_medium=email';
const broad = [...text.matchAll(/^utm_([a-z_]+)=([^&]+)$/gm)];
const bounded = [...text.matchAll(/^utm_([a-z_]+)=([^&\r\n]+)$/gm)];
console.log(broad.length);   // 1
console.log(bounded.length); // 2
console.log(broad[0][2] === 'newsletter\nutm_medium=email'); // true
console.log(/^[0-9]+$/.test('123\n')); // false (JavaScript, no m)
console.log(/^[0-9]+$/m.test('bad\n123\nbad')); // true: one valid line

Das begrenzte Beispiel beschreibt ein bewusst einfaches Zeilenformat mit nichtleerem Wert. Leerzeichen bleiben erlaubt; [^&\s]+ würde zusätzlich Leerzeichen und weitere Leerraumzeichen ausschließen und damit eine andere Regel festlegen. CRLF-Eingaben und erlaubte Leerwerte benötigen eigene Tests. Echte URL-Abfragezeichenfolgen lassen sich mit einem URL-Parser und URLSearchParams einschließlich Dekodierung und mehrfacher Schlüssel auswerten.

Validierung braucht eine Prüfung der gesamten Eingabe

Eine Suche nach [0-9]+ trifft innerhalb von abc123def. JavaScript /^[0-9]+$/ ohne m beschränkt den gesamten Wert auf ASCII-Ziffern. Mit m genügt eine passende Zeile innerhalb einer sonst ungültigen Eingabe. Alternativen benötigen außerdem Gruppierung: ^(?:yes|no)$ wendet beide Anker auf beide Alternativen an.

Anker prüfen eine Position, etwa den Anfang oder das Ende der Eingabe, ohne dabei ein Zeichen zu verbrauchen. Die Ankerregeln unterscheiden sich. In Python trifft $ auch unmittelbar vor einem abschließenden Zeilenumbruch; re.fullmatch(r"[0-9]+", value) prüft ausdrücklich die gesamte Zeichenfolge. PCRE2/PHP erlaubt \A[0-9]+\z. In Ruby sind ^ und $ auch ohne Schalter Zeilenanker; für die gesamte Eingabe stehen \A und \z. Rubys Schalter m steuert dotAll, anders als der JavaScript-Schalter für Zeilenanker.

Mehrdeutige Wiederholung kann viel Rechenzeit kosten

Backtracking bedeutet: Wenn der restliche Ausdruck nicht passt, kehrt die Auswertung zu einer früheren Entscheidung zurück und versucht eine andere Möglichkeit. Dadurch können zahlreiche Aufteilungen desselben Textes durchprobiert werden. ^(a+)+$ gegen eine Folge von a mit abschließendem ! ist eine typische riskante Struktur. Ohne die überflüssige äußere Wiederholung akzeptiert ^a+$ dieselben gültigen Zeichenfolgen. Die konkrete Dauer hängt von Engine, Optimierungen, Eingabe und Grenzen ab; eine allgemeine Dreißig-Zeichen-Schwelle existiert nicht.

Verschachtelung allein beweist keine exponentielle Laufzeit und ist auch nicht die einzige Ursache langsamer Auswertung. Eine unverankerte Suche nach a+$ kann bei langer unpassender Eingabe viele Startpositionen versuchen. Das Entfernen einer Verschachtelung rechtfertigt deshalb keine allgemeine Linearitätszusage. Überlappende Alternativen und ein teurer erfolgloser Zweig vor einem erfolgreichen Zweig sind ebenfalls relevant.

Muster wie (.*,)*$ erlauben null Wiederholungen und können bei einer Suche einen leeren Endtreffer liefern. Die Einteilung in immer schnelle Treffer und ausschließlich langsames vollständiges Scheitern greift deshalb zu kurz. Ein fauler Quantor verändert die Suchreihenfolge, beseitigt mehrdeutige Aufteilungen aber nicht grundsätzlich.

Tests und Grenzen gehören zum Entwurf

Nützliche Fälle umfassen gültige Eingaben, zwei Vorkommen, ungültige Präfixe und Suffixe, Leerwerte, CR/LF, Unicode-Ziffern, fehlende Trennzeichen und lange Beinahetreffer. Erwartungswerte sollten Gruppeninhalte und Trefferpositionen einschließen, nicht nur einen Wahrheitswert. Drei Beispiele sind ein Anfang, kein Vollständigkeitsnachweis.

Potenziell teure Muster gehören in isolierte Tests mit zunächst kleinen Eingaben und einer festen externen Zeitgrenze oder einem unterstützten Engine-Timeout. Grenzen für Eingabe und Mustergröße bleiben sinnvoll. Ein Timeout ist ein zu behandelnder Fehler, kein Beweis für einen ungültigen Text.