Build a regex engine from scratch in about 130 lines of Python

Shipcode — Thu, 12 Nov 2026 17:16:24 +0000

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 match state 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!

DEV Community: Shipcode