How a Regex Engine Actually Works: From Pattern to Automaton

A Regex Is Source Code; The Engine Is a Compiler

The word "regex" hides two different things. There's the regular expression — a formal object equivalent to a regular language, closed under union, concatenation, and Kleene star. And there's the engine — the program that turns that expression into something executable. The engine is a genuine compiler front-end plus a runtime, and it runs the classic phases:

• Lexing: scan the pattern string into tokens — literals, *, |, (, character classes [a-z], quantifiers {2,5}.
• Parsing: build an abstract syntax tree honoring precedence — star binds tighter than concatenation, which binds tighter than alternation. Most engines use a Pratt or recursive-descent parser.
• Lowering: compile the AST to an intermediate representation — either an NFA (a graph of states) or a linear bytecode program (Char, Split, Jmp, Match instructions).
• Execution: run the IR against input via automaton simulation, a VM loop, or recursive backtracking.

The single most consequential design decision is the last two phases. The Thompson NFA + simulation path guarantees linear-in-input time. The recursive backtracking path is easier to extend with features like backreferences but can explode exponentially. Everything else — the ReDoS headlines, RE2's existence, why Go's regexp is "slow but safe" — follows from that fork.

Thompson Construction: Compiling to an NFA in O(m)

Ken Thompson, in his 1968 CACM paper "Regular Expression Search Algorithm," gave the recipe still used today. Walk the AST bottom-up; each node becomes a small NFA fragment with exactly one entry and one exit, wired with ε-transitions (edges taken without consuming input). The fragments compose structurally:

• Literal c: two states with one edge labeled c.
• Concatenation AB: ε-edge from A's exit to B's entry.
• Alternation A|B: a new entry with ε-edges to both A and B; both exits ε-merge to a new exit.
• Kleene star A*: new state with ε-edges into A and past it; A's exit ε-loops back to the entry.

Each of the m characters in the pattern adds a constant number of states and edges, so the NFA has O(m) states, O(m) edges, and builds in O(m) time and space. No state has more than two outgoing edges — a key property Thompson exploited. In bytecode form the same construction is even cleaner:

a|b     →   0: Split 1, 3
            1: Char 'a'
            2: Jmp 4
            3: Char 'b'
            4: Match

a*      →   0: Split 1, 3
            1: Char 'a'
            2: Jmp 0
            3: Match

Split is the ε-branch; it forks the machine into two possible next instructions. This is the IR that Pike's VM interprets.

Simulating the NFA: Track a Set of States, Not a Tree of Guesses

An NFA is nondeterministic — at a Split, both branches are "live." The catastrophic idea is to try one branch, and on failure backtrack and try the other. The linear idea, from Thompson, is to keep all live states simultaneously in a set and advance them in lockstep.

The algorithm reads input character by character. At each step it holds a set S ⊆ states reachable so far, computes the ε-closure, then for the next input character c computes the set of states reachable on c:

S ← ε-closure({start})
for c in input:
    S ← ε-closure( ⋃_{q∈S} δ(q, c) )   // move then close
    if S = ∅: break
accept if any q∈S is a final state

The invariant is exact: after reading prefix input[0..i], S is precisely the set of NFA states the machine could occupy. Since |S| ≤ number of NFA states = O(m), and each of the n input characters triggers work proportional to |S| plus the edges out of those states, the total is O(nm) time and O(m) space — with no dependence on how the pattern nests. A duplicate state is simply never added twice to S, so the same "guess" is never explored redundantly. This is the entire secret: set membership replaces backtracking.

Subset Construction: From NFA to a DFA for O(n) Matching

The O(nm) NFA simulation still does O(m) work per character. A deterministic finite automaton (DFA) does O(1) work per character — one table lookup, one state transition — giving O(n) total, ~one instruction per byte. You get there with subset construction (Rabin–Scott, 1959): each DFA state is a set of NFA states.

• Start state = ε-closure({NFA start}).
• For each DFA state D and each input symbol c, the target is ε-closure(⋃ δ(q,c)) over q ∈ D — exactly the set the NFA simulation would compute.
• A DFA state is accepting iff its NFA-state set contains a final state.

The catch is the state count. A DFA over an m-state NFA can have up to 2^m states — an exponential blowup, real for patterns like .*a.{k}$, which needs states tracking the last k characters. Two defenses dominate practice:

• Lazy DFA (on-the-fly). RE2, PCRE2's DFA mode, and grep build DFA states only as input demands them and cache them in a hash table. Most inputs touch a tiny fraction of the 2^m states; when the cache fills, evict and rebuild. Match stays O(n) amortized while worst-case memory is bounded.
• DFA minimization (Hopcroft's algorithm, O(s log s)) collapses equivalent states when a full DFA is affordable — the standard lex/flex lexer path.

The Backtracking Fork and How ReDoS Happens

PCRE, Perl, Python's re, Java's java.util.regex, and JavaScript's RegExp take the other road. Their VM interprets the same bytecode but with recursion + a backtracking stack: at a Split, push the alternative and pursue the first branch; on Match failure, pop and retry. This makes backreferences ((a+)\1) and lookahead easy — features that are provably not regular and can't be expressed by a plain NFA/DFA. Deciding a match with backreferences is NP-hard in general.

The price is catastrophic backtracking. Consider (a+)+$ on "aaaa...aaa!". The nested quantifiers create exponentially many ways to partition the a's; every partition fails at !, and the engine tries them all — Θ(2ⁿ). That's ReDoS (regular-expression denial of service). A single request-supplied pattern or input has taken down production services (Cloudflare's 2019 global outage was a runaway regex).

Why do backtrackers survive? Two reasons: features (backrefs, lookaround, capture semantics with defined priority) and constants — for typical patterns they're fast and use only O(m + recursion depth) memory. Mitigations include converting to an automaton when the pattern is regular, imposing step/time limits, and memoizing (Davis's 2021 work makes backtracking polynomial via memoization).

Captures, Priority, and Pike's VM: The Best of Both

Pure NFA simulation answers "does it match?" but not "which substring did group 1 capture?" — and leftmost-greedy semantics require a defined priority among matches. Pike's VM (Rob Pike, from Thompson's ideas; the core of Russ Cox's articles and Go/RE2) extends the state-set simulation to carry capture slots per live thread while preserving linear time.

• Each thread is a program counter plus an array of saved input positions (Save n instructions record group boundaries).
• Threads are stored in a set keyed by PC, so at most O(m) run per character — the ordering of thread insertion encodes greedy/lazy priority, so the first thread to reach Match wins the right way.
• Total cost: O(nm) time, O(m) space, with full submatch extraction — no exponential blowup.

Real engines layer strategies. RE2 tries the lazy DFA first (fastest, O(n), no captures), falls back to the Pike/bitstate NFA only when captures are needed, and refuses backreferences entirely. Rust's regex, Go's regexp, and Google's search infra all descend from this design: guaranteed linear time is a hard contract, worth giving up backreferences for.

Optimizations, Pitfalls, and When Each Engine Wins

Production engines rarely run the naive loop. Key accelerations:

• Prefix/required-literal scan: if the regex must contain "error", run memchr/Boyer–Moore/SIMD to skip to candidate positions before touching the automaton — often the single biggest speedup on large inputs.
• Anchoring & unanchored search: an unanchored search is implicitly .*?(pattern); engines special-case it rather than prepending a real .*.
• Bit-parallel matching: for patterns under a machine word, Glushkov/bitap methods (Baeza-Yates–Gonnet's Shift-Or) run in O(n·⌈m/w⌉) with word size w — extremely fast constants.

Pitfalls that bite everyone:

• Nested quantifiers on a backtracker ((a*)*, (.*)*) are the classic ReDoS shape — audit them.
• Unicode multiplies the alphabet; DFA transition tables are keyed by byte ranges, not codepoints, to keep tables small.
• DFA cache thrash: pathological patterns can force constant DFA-state eviction, degrading toward the O(nm) NFA path — RE2 detects this and switches modes.

Choose an automaton engine (RE2, Rust regex, Go, grep) when inputs are attacker-controlled or throughput matters and you don't need backreferences. Choose a backtracker (PCRE2, Perl, JS) when you need backreferences/lookaround and control the input — but cap execution time. The standard references are Aho, Sethi & Ullman's Dragon Book (Ch. 3) and Russ Cox's "Regular Expression Matching Can Be Simple And Fast."

Two engine architectures for the same regex — the choice governs both speed and safety.

Property	Automaton (NFA/DFA)	Backtracking (PCRE, JS, Python re)
Match time	O(nm) worst, O(n) with DFA	O(n) typical, O(2ⁿ) adversarial
Compile	O(m) NFA; O(2^m) full DFA	O(m) to bytecode
ReDoS risk	None — bounded by construction	High — catastrophic backtracking
Backreferences \1	Not supported (not regular)	Supported (NP-hard in general)
Memory	O(m) NFA, O(states) DFA cache	O(m) + O(depth) call stack