<.+> gegen <b>bold</b> and <i>italic</i> findet nicht <b>. Es findet die gesamte Zeichenkette, vom ersten < bis zum allerletzten >. Nichts ist defekt. Genau das soll ein greedy Quantifizierer tun, und es ist auch der häufigste “Regex matcht zu viel”-Bug überhaupt. Sobald klar ist, was die Engine beim Lesen des Musters tut, hören dieser Bug und die meisten seiner Verwandten auf, Rätsel zu sein.

Wie eine Regex-Engine Ihr Muster Liest

Eine Regex-Engine vergleicht Ihr Muster nicht mit der Zeichenkette wie man zwei Zeichenketten auf Gleichheit vergleicht. Die Engines, die Sie täglich nutzen (re in Python, RegExp in JavaScript, PCRE, .NET, Java), sind regex-directed: Sie lesen das Muster von links nach rechts, Token für Token, und versuchen für jedes Token, Zeichen aus der Zeichenkette an der aktuellen Position zu konsumieren. Wenn ein Token passt, rückt die Engine sowohl den Muster-Zeiger als auch den Zeichenketten-Zeiger vor. Wenn ein Token fehlschlägt, macht die Engine Backtracking: Sie geht zum letzten Punkt zurück, an dem sie eine Wahl hatte, etwa ein Quantifizierer, der weniger Zeichen hätte matchen können, oder ein noch nicht probierter Alternationszweig, und probiert die andere Option.

Deshalb schluckt <.+> die ganze Zeile. .+ ist greedy, also nimmt es zuerst alle verbleibenden Zeichen der Zeichenkette, < und > eingeschlossen. Die Engine braucht immer noch ein literales >, um fertig zu werden, also gibt sie Zeichen vom Ende her einzeln zurück, bis das letzte > in der Zeichenkette sie erfüllt. Die Engine liefert die erste Übereinstimmung, die sie in dieser greedy-first-Reihenfolge findet. Für dieses Muster ist das die längstmögliche, nicht die, die auf den ersten Blick richtig aussieht.

Erst die greedy Option probieren, bei einem Fehlschlag einen Schritt zurückgehen: Diese eine Regel erklärt sowohl das normale alltägliche Matching als auch die pathologischen Verlangsamungen weiter unten. Das ist dieselbe Erkunden-und-Zurücknehmen-Logik wie bei einer rekursiven Suche ohne Memoisierung. Genau diese Art von Explosion behandelt Rekursion erklärt von der Seite der Funktionsaufrufe aus.

Grundlegende Regex-Syntax: Anker, Quantifizierer, Gruppen, Lookarounds

Anker und Zeichenklassen

^ und $ verankern eine Übereinstimmung am Anfang und Ende der Zeichenkette (oder der Zeile, mit dem Multiline-Flag). \d, \w und \s sind Kurzformen für die Zeichenklassen Ziffer, Wortzeichen und Leerzeichen, und [...] erlaubt es, eine Klasse direkt auszuschreiben.

1
2
3
4

import re

re.search(r"^\d{3}-\d{4}$", "555-0199")
# <re.Match object; span=(0, 8), match='555-0199'>

Ohne die Anker würde \d{3}-\d{4} auch innerhalb von "call 555-0199 now" matchen. Anker verwandeln “enthält” in “ist genau”.

Zeichenklassen arbeiten auf dem, was die Engine als ein Zeichen betrachtet, und außerhalb von reinem ASCII ist das nicht immer das, was man erwartet. \w matcht einen Buchstaben, eine Ziffer oder einen Unterstrich gemäß dem Zeichenbegriff der Engine, was dieselbe Code-Point-gegen-Byte-Unterscheidung ist, die was Unicode und die UTF-8-Kodierung wirklich tun behandelt. Führt man ein Muster gegen rohe UTF-8-Bytes statt gegen dekodierten Text aus, wird ein Mehrbyte-Zeichen in das aufgeteilt, was die Engine für getrennte Zeichen hält.

Greedy- und Lazy-Quantifizierer

+, * und {m,n} sind standardmäßig greedy: Sie nehmen so viel wie möglich und machen dann Backtracking, wenn das den Rest des Musters zerstört. Setzt man ein ? dahinter, wird der Quantifizierer lazy. Er nimmt so wenig wie möglich und erweitert sich nur, wenn er muss.

1
2
3

s = "<b>bold</b> and <i>italic</i>"
re.findall(r"<.+>", s)    # ['<b>bold</b> and <i>italic</i>']
re.findall(r"<.+?>", s)   # ['<b>', '</b>', '<i>', '</i>']

Ein Zeichen Unterschied, ein völlig anderes Ergebnis. Wenn Sie das Kürzeste wollen, das den Rest des Musters erfüllt, nutzen Sie die lazy Form. Wenn das, was Sie matchen, Markup ist, lesen Sie zuerst den letzten Abschnitt.

Capture-Gruppen, Non-Capture-Gruppen und Benannte Gruppen

(...) erfasst, was sie matcht, damit Sie es danach herausholen können. (?:...) gruppiert zur Strukturierung, etwa um einen Quantifizierer auf ein ganzes Teilmuster anzuwenden, ohne eine Capture zu erzeugen. (?P<name>...) in Python ((?<name>...) in JavaScript, Java und .NET) benennt eine Gruppe, damit Sie nicht Klammern zählen müssen, um sie später zu finden.

1
2
3

m = re.match(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", "2026-10-28")
m.groupdict()
# {'year': '2026', 'month': '10', 'day': '28'}

1
2
3

const m = "2026-10-28".match(/(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/);
m.groups;
// [Object: null prototype] { year: '2026', month: '10', day: '28' }

Sie lesen das Ergebnis über den Namen, mit groupdict() in Python oder .groups in JavaScript (benannte Gruppen kamen dort mit ES2018), statt über match[1], match[2]. Sobald ein Muster mehr als zwei Gruppen hat, zahlen sich die zusätzlichen Zeichen aus.

Lookahead und Lookbehind

Ein Lookaround prüft eine Position, keine Zeichen. Es prüft, ob etwas da ist (oder nicht da ist), ohne es zu konsumieren. (?=...) ist ein positiver Lookahead, (?!...) negativ; (?<=...) und (?<!...) sind die Lookbehind-Äquivalente.

1
2

"$40 bill".match(/(?<=\$)\d+/);
// [ '40', index: 1, ... ]   -- findet "40", nicht "$40"

Pythons re verlangt, dass Lookbehind feste Breite hat: (?<=\$) funktioniert, (?<=\$+) löst einen Fehler aus, weil die Engine genau wissen muss, wie weit sie zurückgehen muss, bevor sie prüft. JavaScript, das Lookbehind in ES2018 zusammen mit benannten Gruppen eingeführt hat, hat diese Einschränkung nicht, also funktioniert (?<=\$+) dort. In Python hebt das Drittanbieter-Paket regex auf PyPI die Einschränkung auf, falls ein variabel breites Lookbehind nötig ist.

Warum Manche Regex Hängen: Catastrophic Backtracking

Nehmen Sie die Backtracking-Regel vom Anfang und geben Sie ihr einen Fall, von dem sie sich nicht erholen kann. Verschachteln Sie zwei Quantifizierer, sodass die Engine viele Möglichkeiten hat, dieselbe Zeichenfolge zwischen ihnen aufzuteilen, und lassen Sie das Matching dann ganz am Ende fehlschlagen. Die Engine schlägt nicht schnell fehl. Sie probiert jede Aufteilung aus, bevor sie aufgibt.

1
2
3
4
5
6
7
8

import re, time

pattern = re.compile(r"(a+)+b")
for n in (20, 24, 26, 28):
    s = "a" * n  # kein abschließendes "b", also nie ein Match
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.1f} ms")

1
2
3
4

20 41.6 ms
24 525.8 ms
26 2083.6 ms
28 8369.3 ms

Jedes zusätzliche a verdoppelt ungefähr die Zeit: zwei Zeichen mehr, viermal langsamer. Das ist exponentielles Wachstum, die Kurve, die Big-O-Notation auf die andere Seite von O(n^2) setzt. (a+)+ kann eine Folge von 28 a auf 2^27 verschiedene Arten in Gruppen aufteilen, und ohne ein b in der Zeichenkette probiert die Engine sie eine nach der anderen, bevor sie “keine Übereinstimmung” melden kann. Verfolgt man dieselbe Kurve bis 40 Zeichen, wartet man etwa neun Stunden.

Wenn die Eingabe von einem Nutzer statt von Ihren Testfixtures kommt, ist das eine ausnutzbare Schwachstelle: ReDoS, regular expression denial of service. Der übliche Auslöser hat genau diese Form, zwei übereinandergestapelte Quantifizierer ohne irgendetwas dazwischen, das eine eindeutige Aufteilung erzwingt.

Drei Wege, es zu stoppen, vom billigsten an:

  1. Beseitigen Sie die Ambiguität. (a+)+b und a+b matchen hier dieselben erfolgreichen Zeichenketten; der äußere + bringt nichts. Die meisten katastrophalen Muster haben eine solche redundante Schicht, sobald man danach sucht.

  2. Machen Sie den inneren Quantifizierer possessiv oder packen Sie ihn in eine atomare Gruppe. Beides sagt der Engine “sobald dies matcht, kein Backtracking mehr hinein”. Das beseitigt die exponentielle Explosion, um den Preis, gelegentlich eine Zeichenkette abzulehnen, die die Backtracking-Version akzeptiert hätte. Pythons re unterstützt beides seit 3.11:

    1
2
3
4
5
6
7

    pattern = re.compile(r"(?>a+)+b")   # atomare Gruppe
# oder: re.compile(r"a++b")         # possessiver Quantifizierer, Python 3.11+
for n in (28, 1_000, 100_000):
    s = "a" * n
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.3f} ms")

    1
2
3

    28 0.002 ms
1000 0.001 ms
100000 0.026 ms

    Dasselbe fehlgeschlagene Matching auf 100.000 Zeichen dauert 26 Mikrosekunden. JavaScripts natives RegExp hat keine der beiden Funktionen. Das npm-Paket regex fügt atomare Gruppen und possessive Quantifizierer als erweiterte Syntax hinzu, falls man sie braucht, ohne die Engine zu wechseln.

  3. Begrenzen Sie unbegrenzte Quantifizierer. {1,50} statt + begrenzt, wie schlecht der schlechteste Fall werden kann, selbst ohne die Logik umzuschreiben.

Wenn die Zeichenkette von außerhalb Ihres Codes kommen kann, etwa aus einem Request-Body oder einem von jemand anderem geschriebenen Konfigurationswert, behandeln Sie verschachtelte Quantifizierer wie eine unbegrenzte Schleife über externe Eingaben. Testen Sie das Muster gegen eine lange Folge des Zeichens, das die Ambiguität auslöst, nicht nur gegen Ihre Happy-Path-Fixtures.

Wann Regex Nicht Verwenden

Ein Regex hat kein Gedächtnis dafür, wie tief es ist. Das ist in Ordnung für flachen Text mit fester Form wie ein Datum oder eine Logzeile mit bekannten Feldern. Deshalb kann <.+> auch nicht zuverlässig einen einzelnen HTML-Tag überspringen: Es hat kein Konzept von “dieses < öffnet einen Tag, den das nächste passende > schließt”, nur “nimm bis zum letzten >, das sich finden lässt”. Verschachtelte Strukturen wie HTML, JSON, Quellcode und ausgeglichene Klammern brauchen eine Grammatik, kein Muster. Der typische Fehlschlag ist ein Regex, der jeden Testfall besteht, den man geschrieben hat, und dann auf eine echte Datei mit einem Kommentar trifft, der ein > enthält, und stillschweigend den falschen Abschnitt matcht statt einen Fehler zu melden.

Verwenden Sie den Parser, der schon existiert: einen HTML-Parser für HTML, json.loads für JSON, das AST-Modul Ihrer Sprache für Code. Behalten Sie Regex für das Validieren oder Extrahieren von Text mit flacher Form, und wechseln Sie zu einem Parser, sobald “ausgeglichen” oder “verschachtelt” in der Beschreibung dessen auftaucht, was Sie matchen.

Verwandte Artikel