Backtracking: Grundlagen

Wenn ein gieriger Quantifizierer es „übertreibt“, macht die Engine einen Rückzieher: Gehen Sie einen Schritt zurück, versuchen Sie es mit einer anderen Konfiguration und versuchen Sie es erneut. Komm schon einfache Muster sind unsichtbar; Bei schlecht geschriebenen Mustern kann es passieren exponentiell und den Browser für Sekunden blockieren. Es ist die Wurzel von ReDoS (Regular Expression Denial of Service).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consuma tutto: "abc123def"
  2.  \d  fallisce (fine stringa).
  3.  Backtrack: .* lascia 'f' -> "abc123de", \d fallisce su 'f'.
  4.  Backtrack: .* lascia 'ef' -> "abc123d", \d fallisce su 'e'.
  5.  ... e cosi' via finche' \d trova una cifra: match = "abc123" + "?"... in realta'
       il pattern matcha "abc123" perche' .* lascia "def" e \d cerca su '3'? No: il backtrack
       continua e .* finisce per essere "abc12", \d=3.  Match finale: "abc123".

Die Engine kommt immer dorthin, aber wenn der gierige Quantifizierer es in sich hat ein anderer gieriger Quantor (z. B. (a+)+), die Anzahl von Konfigurationen zum Ausprobieren können explodieren.

Katastrophale Muster

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Nichts Endgültiges b → Das Muster schlägt fehl, aber die Engine versucht, dorthin zu gelangen alle möglichen Partitionen von a. exponentielles Wachstum: mit 30 a Sie können stundenlang warten.

Gefahren von Backtracking und ReDoS

Wenn ein Muster überlappende oder verschachtelte Quantoren enthält (z. B. (a+)+), wertet die Engine eine exponentielle Anzahl von Kombinationen aus, bevor sie fehlschlägt. Durch das Ersetzen allgemeiner Platzhalter durch ausschließende Zeichenklassen werden die Backtracking-Pfade drastisch reduziert.

Probieren Sie es selbst aus

Wiederholungsübung

Zusätzliche Herausforderung