Build your own regex engine, and see why some regexes hang forever

Everyone uses regular expressions and almost no one knows what happens when they run. You type ab*c, hand it a string, and get back yes or no. It feels like a spell. It is not. A regex is a small machine, and once you build the machine you will understand two things at once: how tools like grep match millions of lines a second, and why a single innocent-looking pattern can pin a CPU at 100 percent and take a website down.

We will build an engine for the core of regex, concatenation, alternation with |, and the star *, that matches without ever backtracking.

The one idea

A backtracking engine tries one path, and if it fails, it rewinds and tries another. That rewinding is where the danger lives. Our engine will do something different: it keeps a set of states alive at the same time. At each character, every live state takes a step, and we collect where they all land. There is never a wrong path to undo, because we walk all paths at once. That single decision is why the running time stays proportional to pattern size times text length, and never explodes.

The classic way to get there is Thompson's construction: compile the pattern into a graph of tiny states connected by character-labeled and empty (epsilon) arrows.

Compile the pattern to a state machine

First we rewrite the pattern into postfix so precedence is explicit (star binds tighter than concatenation, which binds tighter than |), inserting an explicit . wherever two things are concatenated. That is a standard shunting-yard pass; call it to_postfix. Then we fold the postfix into an NFA, where each state is a list of (char, target) arrows and None means an epsilon arrow.

def thompson(postfix):
    trans, stack = [], []
    def new(): trans.append([]); return len(trans) - 1
    for c in postfix:
        if c == '.':                                  # concatenate a then b
            (s2, o2), (s1, o1) = stack.pop(), stack.pop()
            for st in o1: trans[st].append((None, s2))
            stack.append((s1, o2))
        elif c == '|':                                # a or b
            (s2, o2), (s1, o1) = stack.pop(), stack.pop()
            s = new(); trans[s] = [(None, s1), (None, s2)]
            stack.append((s, o1 + o2))
        elif c == '*':                                # zero or more
            (s1, o1) = stack.pop(); s = new()
            trans[s].append((None, s1))
            for st in o1: trans[st].append((None, s))
            stack.append((s, [s]))
        else:                                         # a single character
            s, a = new(), new(); trans[s].append((c, a))
            stack.append((s, [a]))
    start, outs = stack.pop(); accept = new()
    for st in outs: trans[st].append((None, accept))
    return trans, start, accept

Three details that matter:

• Each fragment is tracked as (start, dangling_arrows). Operators wire fragments together by pointing the dangling arrows at the next piece.
• * adds one state that can either enter the loop or skip it, and routes the loop body back to itself. That is the whole meaning of "zero or more".
• Epsilon arrows (None) cost nothing to take. They exist only to connect pieces, so the shape of the pattern becomes the shape of the graph.

Match by walking every path at once

To match, we track the set of states reachable right now. closure adds every state you can reach by following free epsilon arrows. Then each input character advances the whole set.

def closure(trans, states):
    stack, seen = list(states), set(states)
    while stack:
        for ch, t in trans[stack.pop()]:
            if ch is None and t not in seen:
                seen.add(t); stack.append(t)
    return seen

def match(rx, text):
    trans, start, accept = thompson(to_postfix(rx))
    cur = closure(trans, {start})
    for ch in text:
        cur = closure(trans, {t for s in cur for c, t in trans[s] if c == ch})
    return accept in cur

The whole matcher is those two functions. There is no recursion into alternatives, no saving a position to jump back to. At every character the state set can only grow to the number of states in the pattern, so one pass over the text finishes the job.

Proof: it agrees with Python, and it never bombs

Check it against Python's own re on a spread of patterns:

import re
for rx, cases in [("ab*c", ["ac","abc","abbbc","ab"]), ("a|b", ["a","c"]), ("(ab)*", ["abab","aba"])]:
    for t in cases:
        assert match(rx, t) == (re.fullmatch(rx, t) is not None)
print("agrees with re on every case")
print(match("a*a*a*a*a*", "aaaaaaaaaa"))   # instant, no matter how many stars

Both pass. The last line is the point. Stack up quantifiers and feed a long string, and a backtracking engine can try an exponential number of ways to divide the input, the failure mode behind real "regex denial of service" incidents where one request hangs a server. Our engine cannot do that, because it never divides the input into cases at all. It just moves a set of states forward.

Where this shows up

This is not a toy detour. It is the design behind grep, and behind Google's RE2 and Rust's regex crate, which use exactly this guarantee to promise linear-time matching and refuse to ship the catastrophic-backtracking feature. Understanding it is also how you spot a dangerous pattern in a code review before it reaches production.

If you want to keep going, adding +, ?, character classes, and capture groups, that is what the compilers track on IWTLP builds next, one small machine at a time.