Quantifiers: ? * +

Quantifiers turn an atom into "match this between N and M times":

By default they are greedy: match as many as possible, then backtrack. Append ? to make non-greedy: .*?.

The simplest implementation: backtracking recursive match.

This works but catastrophic backtracking is real: (a+)+b on aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! takes exponential time in backtracking engines. NFA simulation (next chapter) avoids this completely.

The NFA approach: at each text position, the engine maintains a set of possible NFA states. Each step transitions all states in parallel. Since the state count is bounded by the regex length, runtime is O(n*m) — never exponential.