How the Regex Engine Actually Works

What's running when you type a pattern

You type a(b|c)*d. Behind the curtain, the regex engine compiles your pattern into a state machine and walks the input string one character at a time, tracking which states are active.

Two big families of engines exist:

NFA (Non-deterministic Finite Automaton) — used by Python, JavaScript, Java, .NET, PCRE, Perl. Powerful: supports backreferences, lookaround, recursion. Cost: can suffer catastrophic backtracking on certain patterns (entire Track 8 lessons devoted to this).

DFA (Deterministic Finite Automaton) — used by grep's default mode, ripgrep (RE2 family), Go's regexp. Restricted: no backreferences, no lookaround. Trade-off: linear time guaranteed, never blows up.

Backtracking, in slow motion

NFA engines try one path; if it fails, they roll back and try another. Pattern a(b|c)d against input abd:

Engine at position 0, state "expecting a". Match a. Advance to position 1.
State "inside group, try b". Match b. Advance to position 2.
State "after group, expecting d". Match d. Done.

Now imagine abd wasn't there and the engine had to backtrack. With (a|ab)c against abc: try a, then c — fail. Backtrack to start of group, try ab, then c — match.

That's the whole mechanism. Most of the time it's invisible. When it goes wrong (Track 3 greedy/lazy, Track 8 ReDoS), this picture is what you debug from.

Code

Watch backtracking with Python's re.DEBUG·python

import re
pattern = re.compile(r'(a|ab)c', re.DEBUG)
# Prints the compiled state machine — try it once and read the output.

DFA vs NFA in practice·bash

# RE2/ripgrep — DFA, can't backtrack, can't ReDoS, no backrefs
rg '(a|ab)c' file.txt   # works
rg '(\w+)\1' file.txt    # ERROR: backreferences not supported

# Python re — NFA, backrefs work, but vulnerable to ReDoS
python -c "import re; print(re.findall(r'(\w+)\1', 'abab xyz'))"  # ['ab']

How the Regex Engine Actually Works

What's running when you type a pattern

Backtracking, in slow motion

Code

External links

Exercise

Progress

Comments 0