Backtracking: een overzicht

When a greedy quantifier "overshoots", the engine performs backtracking: it steps back, tries another configuration, retries. On simple patterns it is invisible; on poorly written patterns it can become exponential and freeze the browser for seconds. It is the root of ReDoS (Regular expression Denial of Service).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consumes everything: "abc123def"
  2.  \d  fails (end of string).
  3.  Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
  4.  Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
  5.  ... and so on until \d finds a digit: match = "abc123" + "?"... actually
       the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
       backtrack continues and .* ends up being "abc12", \d=3.  Final match: "abc123".

The engine always gets there, but if a greedy quantifier contains another greedy quantifier (e.g. (a+)+), the number of configurations to try can explode.

Catastrophic patterns

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

No trailing b → the pattern fails, but to get there the engine tries every possible partition of the as. Exponential growth: with 30 as you can wait for hours.

Perils of backtracking and ReDoS

When a pattern contains overlapping or nested quantifiers (e.g. (a+)+), the engine evaluates an exponential number of paths before failing. Replacing generic wildcards with excluding character classes dramatically reduces backtracking paths.

Try it

Review exercise

Additional challenge