Lesson 1 of 9 · 22m

How Regex Engines Actually Match

Backtracking versus automata engines, what a choice point costs, and the mental model that lets you predict a pattern's behavior before you run it.

Every regex you write is a tiny program, and the engine is its interpreter. Most developers treat a pattern as a declarative spec — "strings shaped like this" — and get blindsided the first time a one-line validator pins a CPU core at 100%. The day you understand how the engine walks a string is the day regex stops being incantation and becomes a tool you can reason about.

Two families of engines

There are two fundamentally different ways to execute a regex, and your tool picked one for you:

Family	Who uses it	Guarantee	What it gives up
Backtracking	Perl, PCRE, Python `re`, Java, JavaScript (V8 Irregexp), .NET, Ruby	Rich features: backreferences, lookarounds, lazy and possessive quantifiers	Worst case is exponential in input length
Automata (Thompson NFA / DFA)	RE2, Go `regexp`, Rust `regex`, GNU grep, mawk	Linear time in input length, always	Backreferences and (mostly) lookarounds

A backtracking engine is a depth-first search. At every choice point — a quantifier that could take one more character, an alternation with another branch — it pushes a bookmark and tries the first option. When the path fails, it pops back to the most recent bookmark and tries the next one. An automata engine instead tracks every possible position in the pattern simultaneously, so each input character is examined once.

Watch a backtracker think

Greedy backtracking trace

pattern:  ".*"
input:    say "hi" and "bye"

1. scan forward to the first "               -> index 4
2. .* is greedy: it eats to end of input     -> hi" and "bye"
3. need a closing " but input is exhausted   -> FAIL, backtrack one char
4. give back e, y, b ... none is a "         -> keep backing off
5. give back the final "                     -> closing " matches
result:   "hi" and "bye"      (not "hi")

Run it and compare three ways of saying "a quoted string":

const line = 'say "hi" and "bye"';
console.log(line.match(/".*"/)[0]);    // "hi" and "bye"  greedy: overshoot, back off
console.log(line.match(/".*?"/)[0]);   // "hi"            lazy: creep forward one char at a time
console.log(line.match(/"[^"]*"/)[0]); // "hi"            no ambiguity, no backtracking needed

The third version is the professional answer. It doesn't rely on the engine's search strategy at all — [^"]* can never consume a quote, so there is exactly one way to match.

Why automata engines refuse some features

A backreference like (\w+) \1 requires remembering what was matched, which is not a regular language; matching with backreferences is NP-hard in general. RE2-family engines drop the feature rather than the guarantee. In Go, compiling a pattern containing \1 panics with invalid escape sequence. That's not a bug — it's the price of never hanging.

Field notes

Know which engine your tool uses before you ship a pattern that sees untrusted input. "It's just a regex" is how ReDoS tickets start (lesson 7).
Backtracking cost scales with ambiguity: the more ways a pattern can match the same characters, the more paths the engine explores.
The expensive case is the failed match. A benchmark on inputs that match tells you almost nothing — test the near-misses.
When you catch yourself relying on greedy-versus-lazy to get the right answer, rewrite the pattern so only one answer is possible.