Most of us use regular expressions every day and treat the engine as a black box. It turns out the core idea fits in one sitting: parse the pattern, turn it into a state machine, and walk that machine over the input. That is the approach Ken Thompson described in 1968, and it still powers engines like RE2 and Rust's regex crate.
In this post we will build a small engine that supports literals, ., *, +, ?, | and parentheses. Along the way you will see why some regex engines can hang on a 30 character string and why this one cannot.
The plan
- Parse the pattern into a tree (an AST).
- Compile the tree into an NFA (a nondeterministic finite automaton) using Thompson's construction.
- Simulate the NFA by tracking the set of states we could be in after each character.
Step 1: Parsing
Regex syntax has precedence, just like arithmetic. From loosest to tightest:
- alternation:
a|b - concatenation:
ab - repetition:
a*,a+,a? - atoms: a character,
., or a parenthesized group
A recursive descent parser mirrors that list with one function per level. alternation calls concat, which calls repeat, which calls atom. The result is a nested tuple like ("cat", ("char", "a"), ("*", ("char", "b"))) for ab*.
The nice part: once precedence is encoded in the call structure, things like ab|cd meaning (ab)|(cd) fall out for free.
Step 2: Thompson's construction
Every AST node becomes a small NFA fragment with one entry and one exit. Fragments snap together:
- char / any: one state that consumes a character and moves to the exit.
- cat: connect the exit of the left fragment to the entry of the right one.
- alt: a new entry that splits into both branches, and both branches flow into a new exit.
- star: a split that either enters the fragment or skips it, and the fragment loops back to that choice.
- plus: like star, but you must enter the fragment at least once.
- question: a split that enters the fragment once or skips it.
The "split" states are epsilon transitions: you can follow them without consuming input. That is where the nondeterminism lives.
Step 3: Simulating a set of states
A backtracking engine picks one path, and if it fails, rewinds and tries another. With patterns like (a|aa)*b the number of paths grows exponentially with the input length.
Thompson's trick is to never choose. Instead we keep every state we could be in at once:
- Start with the entry state and follow all epsilon edges (the closure).
- For each input character, move every state that accepts it one step forward, then take the closure again.
- At the end, we matched if the
matchstate is in the set.
Each step touches each NFA state at most once, so the total work is O(pattern length x text length). Linear in the input, always.
The code
# Tiny regex engine: parse -> NFA (Thompson) -> simulate a set of states.
# Supports literals, '.', '*', '+', '?', '|' and parentheses.
class Parser:
def __init__(self, pattern):
self.p = pattern
self.i = 0
def peek(self):
return self.p[self.i] if self.i < len(self.p) else None
def eat(self):
c = self.p[self.i]
self.i += 1
return c
def parse(self):
node = self.alternation()
if self.peek() is not None:
raise ValueError(f"unexpected {self.peek()!r} at {self.i}")
return node
def alternation(self):
node = self.concat()
while self.peek() == "|":
self.eat()
node = ("alt", node, self.concat())
return node
def concat(self):
parts = []
while self.peek() not in (None, "|", ")"):
parts.append(self.repeat())
node = ("empty",)
for part in parts:
node = part if node == ("empty",) else ("cat", node, part)
return node
def repeat(self):
node = self.atom()
while self.peek() in ("*", "+", "?"):
node = (self.eat(), node)
return node
def atom(self):
c = self.eat()
if c == "(":
node = self.alternation()
if self.peek() != ")":
raise ValueError("missing )")
self.eat()
return node
if c == ".":
return ("any",)
if c == "\\":
return ("char", self.eat())
return ("char", c)
class State:
def __init__(self, kind, char=None):
self.kind = kind # "char", "any", "split", "match"
self.char = char
self.out = [] # next states
def build(node):
"""Return (start, end) states for a fragment. end is a 'split' with no outs yet."""
kind = node[0]
if kind in ("char", "any"):
s, e = State(kind, node[1] if kind == "char" else None), State("split")
s.out.append(e)
return s, e
if kind == "empty":
s = State("split")
return s, s
if kind == "cat":
s1, e1 = build(node[1])
s2, e2 = build(node[2])
e1.out.append(s2)
return s1, e2
if kind == "alt":
s1, e1 = build(node[1])
s2, e2 = build(node[2])
s, e = State("split"), State("split")
s.out += [s1, s2]
e1.out.append(e)
e2.out.append(e)
return s, e
s1, e1 = build(node[1])
s, e = State("split"), State("split")
if kind == "*":
s.out += [s1, e]
e1.out += [s1, e]
elif kind == "+":
s.out.append(s1)
e1.out += [s1, e]
elif kind == "?":
s.out += [s1, e]
e1.out.append(e)
return s, e
def compile_regex(pattern):
start, end = build(Parser(pattern).parse())
end.out.append(State("match"))
return start
def closure(states):
"""Follow every epsilon (split) edge and return the real states we can be in."""
seen, stack, result = set(), list(states), []
while stack:
s = stack.pop()
if id(s) in seen:
continue
seen.add(id(s))
if s.kind == "split":
stack.extend(s.out)
else:
result.append(s)
return result
def fullmatch(pattern, text):
current = closure([compile_regex(pattern)])
for ch in text:
nxt = [s.out[0] for s in current
if s.kind == "any" or (s.kind == "char" and s.char == ch)]
current = closure(nxt)
if not current:
return False
return any(s.kind == "match" for s in current)
A few quick checks:
assert fullmatch("colou?r", "color")
assert fullmatch("(ab)+", "ababab")
assert not fullmatch("(ab)+", "aba")
assert fullmatch("(a|b)*c", "ababbc")
assert fullmatch("a\\.b", "a.b")
The payoff: no catastrophic backtracking
Here is (a|aa)*b against a string of only as (so it can never match), on my laptop:
- 25 characters: this engine ~0.07 ms, Python
re~9 ms - 30 characters: this engine ~0.07 ms, Python
re~110 ms - 34 characters: this engine ~0.14 ms, Python
re~716 ms
Every few extra characters, the backtracking engine gets several times slower. That is the root of ReDoS bugs, where a crafted input freezes a server. The state set simulation just keeps going in a straight line.
To be fair, backtracking exists for a reason: features like backreferences ((a+)\\1) cannot be expressed as a plain finite automaton. Real engines either pick a side or combine both.
Where to go next
If you want to keep going, good next steps are:
-
Search instead of fullmatch: add a new start state at every position, and support
^and$. -
Character classes:
[a-z],[^0-9]. - Captures: record where each group starts and ends (Pike VM style).
-
Lazy quantifiers like
*?and replacement with$1. - Caching the state sets into a DFA for even faster matching.
Russ Cox's article Regular Expression Matching Can Be Simple And Fast is the classic deep dive on all of this.
If you would rather build it stage by stage in your own editor and language, with tests that check each step, we turned exactly this path (literals, anchors, quantifiers, alternation, classes, captures, lazy quantifiers and replacement) into a guided project: Build your own regex engine on Shipcode.
Happy hacking!
Top comments (1)
Nice walkthrough. One test I'd add to the quick checks: a pattern like (a*)* or (a?)*. The inner fragment can match empty, so the star's loop becomes an epsilon cycle, and a closure that follows epsilon edges without a visited set never terminates. It's the one input where the linear guarantee depends on a detail of the closure code rather than the construction.
Does your closure keep a visited set per step, or does the construction avoid that cycle another way?