Regular Expressions, in depth: from pattern to Thompson NFA, lockstep simulation, why backtracking explodes, and patterns that cannot hang

What a regular expression is, and what regex libraries add

Formally, a regular expression describes a set of strings using three operations on top of single characters: concatenation (ab: an a followed by a b), alternation (a|b: either) and the Kleene star (a*: zero or more). Everything else in the basic syntax is shorthand: a+ is aa*, a? is a| with an empty branch, and a class such as [a-c] is a|b|c. These operations describe the regular languages, exactly the sets a finite automaton can recognise.

Practical regex dialects add features that are not regular. A backreference such as (a+)b\1 must remember an unbounded substring, and matching with backreferences is NP-hard in general. That fact explains the split in engine design: support backreferences and you are pushed towards backtracking search; want a linear-time guarantee and you give them up.

Parsing the pattern into a tree

The first job is to turn the pattern string into a tree that respects precedence: repetition binds tightest, then concatenation, then alternation, so ab|c* means (ab)|(c*). A recursive-descent parser with one function per precedence level does this directly. The tree uses tuples: ("set", chars) for a literal or class, ("any",) for the dot, ("cat", items), ("alt", branches) and ("*", child) and its relatives.

class Parser:
    """alt := concat ('|' concat)* ; concat := repeat* ;
    repeat := atom ('*' | '+' | '?')* ; atom := char | '.' | '(' alt ')' | '[' class ']'"""
    def __init__(self, pattern):
        self.s, self.i = pattern, 0
    def peek(self):
        return self.s[self.i] if self.i < len(self.s) else None
    def take(self):
        ch = self.s[self.i]; self.i += 1
        return ch
    def parse(self):
        node = self.alt()
        if self.peek() is not None:
            raise ValueError(f"unexpected {self.peek()!r} at {self.i}")
        return node
    def alt(self):
        branches = [self.concat()]
        while self.peek() == "|":
            self.take(); branches.append(self.concat())
        return branches[0] if len(branches) == 1 else ("alt", branches)
    def concat(self):
        items = []
        while self.peek() not in (None, "|", ")"):
            items.append(self.repeat())
        return ("cat", items)
    def repeat(self):
        node = self.atom()
        while self.peek() in ("*", "+", "?"):
            node = (self.take(), node)
        return node
    def atom(self):
        ch = self.take()
        if ch == "(":
            node = self.alt()
            if self.peek() != ")":
                raise ValueError("missing )")
            self.take(); return node
        if ch == "[":
            chars = set()
            while self.peek() != "]":
                lo = self.take()
                if self.peek() == "-" and self.s[self.i + 1] != "]":
                    self.take(); hi = self.take()
                    chars.update(chr(c) for c in range(ord(lo), ord(hi) + 1))
                else:
                    chars.add(lo)
            self.take(); return ("set", frozenset(chars))
        if ch == ".":
            return ("any",)
        if ch == "\\":
            ch = self.take()
        if ch in "*+?)":
            raise ValueError(f"nothing to repeat at {self.i - 1}")
        return ("set", frozenset(ch))

Real parsers add counted repetition, anchors and escapes such as \d without changing the structure. One warning: a{1000} expands to a thousand copies of the sub-automaton, which is why engines cap compiled size.

Thompson's construction

Ken Thompson's 1968 construction turns the tree into a nondeterministic finite automaton (NFA) by structural recursion. Each node becomes a fragment with one start and one accept state. A character is two states joined by a labelled edge; concatenation chains fragments with empty (epsilon) edges; alternation fans out and back in; star adds a loop-back and a skip edge. Each rule adds a constant number of states, so a pattern of length m gives O(m) states.

class State:
    __slots__ = ("match", "out", "eps")
    def __init__(self, match=None):
        self.match = match   # ("set", chars) / ("any",) for a consuming state, None otherwise
        self.out = None      # next state after consuming one character
        self.eps = []        # epsilon edges

def build(node):
    """Thompson construction: returns (start, accept) of a fragment."""
    kind = node[0]
    if kind in ("set", "any"):
        s, a = State(node), State()
        s.out = a
        return s, a
    if kind == "cat":
        start = acc = State()
        for item in node[1]:
            s, a = build(item)
            acc.eps.append(s)
            acc = a
        return start, acc
    if kind == "alt":
        start, acc = State(), State()
        for branch in node[1]:
            s, a = build(branch)
            start.eps.append(s); a.eps.append(acc)
        return start, acc
    s, a = build(node[1])
    start, acc = State(), State()
    start.eps.append(s); a.eps.append(acc)
    if kind in ("*", "?"):
        start.eps.append(acc)   # zero occurrences allowed
    if kind in ("*", "+"):
        a.eps.append(s)         # loop back for another occurrence
    return start, acc

Running the automaton in lockstep

An NFA can be in several states at once. Instead of guessing a branch and backing up when wrong, the simulation keeps the set of all states the automaton could be in. Start with the epsilon closure of the start state; for each character, advance every state whose label matches and take the closure again; accept if the accept state is in the final set.

def closure(states):
    stack, seen = list(states), set(states)
    while stack:
        for nxt in stack.pop().eps:
            if nxt not in seen:
                seen.add(nxt); stack.append(nxt)
    return seen

def step(states, ch):
    nxt = [st.out for st in states
           if st.match is not None and (st.match[0] == "any" or ch in st.match[1])]
    return closure(nxt)

def fullmatch(pattern, text):
    start, accept = build(Parser(pattern).parse())
    current = closure([start])
    for ch in text:
        current = step(current, ch)
        if not current:
            return False
    return accept in current

def search(pattern, text):
    """Unanchored: re-seed the start state at every position."""
    start, accept = build(Parser(pattern).parse())
    seed = closure([start])
    current = set(seed)
    if accept in current:
        return True
    for ch in text:
        current = step(current, ch) | seed
        if accept in current:
            return True
    return False

The active set never holds more than the O(m) states of the automaton, so matching costs O(m × n) time and O(m) memory for every pattern and input. Unanchored search costs nothing extra: re-adding the start closure at each step starts a match at every position simultaneously.

Worked example: (a|b)*abb on babb

Take the textbook pattern (a|b)*abb and the input babb. Running the code above, the start closure holds 9 states: our construction adds glue states for concatenation, so the count includes states that consume nothing. The table shows the measured set size and whether the accept state is present after each character.

No thread is ever retried: every possibility moves forward together and dies when its next label fails. On abab the run ends without the accept state and returns False.

Backtracking engines and catastrophic backtracking

A backtracking engine explores one path at a time. At an alternation it tries the first branch and, if the rest of the match fails, comes back and tries the second; at a star it tries one more repetition before trying to stop. This depth-first search is how Perl, PCRE, Java's java.util.regex, Python's re, .NET by default and JavaScript engines work; it handles backreferences naturally and is fast on typical patterns. The general search technique is covered in backtracking in depth.

def bt_match(node, text, i, k, counter):
    """k(j) continues the match after this node ended at position j."""
    counter[0] += 1
    kind = node[0]
    if kind in ("set", "any"):
        if i < len(text) and (kind == "any" or text[i] in node[1]):
            return k(i + 1)
        return False
    if kind == "cat":
        def run(idx, j):
            if idx == len(node[1]):
                return k(j)
            return bt_match(node[1][idx], text, j, lambda j2: run(idx + 1, j2), counter)
        return run(0, i)
    if kind == "alt":
        return any(bt_match(b, text, i, k, counter) for b in node[1])
    child = node[1]
    if kind == "?":
        return bt_match(child, text, i, k, counter) or k(i)
    def star(j):   # greedy: one more first; j2 > j stops empty loops
        return bt_match(child, text, j, lambda j2: j2 > j and star(j2), counter) or k(j)
    return star(i) if kind == "*" else bt_match(child, text, i, star, counter)

The danger appears when the pattern offers many different ways to match the same text and the overall match then fails. For (a|a)* against n copies of a followed by a b, every one of the 2ⁿ ways to assign each a to a branch is tried before the engine concludes there is no match. The table shows calls to bt_match as written above, against the total size of the active sets in the NFA simulation on the same input.

Each extra character doubles the backtracking work and adds a constant to the automaton's. CPython's engine does no better on this shape: on one machine running CPython 3.13.5, re.fullmatch('(a|a)*', 'a' * n + 'b') took 0.008 s at n = 16, 0.12 s at n = 20 and 0.48 s at n = 22, quadrupling every two characters, while a* on the same input stayed under 0.0001 s. At n = 40 the same growth means days. This is catastrophic backtracking, and when an attacker controls the input it is called ReDoS, regular-expression denial of service.

What production engines do: DFAs, lazy DFAs and captures

If NFA simulation is always safe, why is it not the default everywhere? Updating a set of states costs more per character than a backtracker's tight loop on well-behaved patterns, and backreferences cannot be expressed in an automaton at all.

The classic speed fix is a DFA: precompute, for every set of NFA states and every character, the next set, so matching is one table lookup per character. But the number of sets can be exponential: (a|b)*a(a|b){k} (the character k+1 from the end is an a) needs 2^k+1 DFA states, because the machine must remember the last k+1 characters. RE2, Go's regexp and Rust's regex crate therefore build a lazy DFA: states are computed on demand, cached, and abandoned for NFA simulation if the cache thrashes. All three guarantee linear time and omit backreferences.

Captures need one more idea. The Pike VM gives each thread its own array of capture positions, and when two threads reach the same state the higher-priority one wins. Priority implements Perl's leftmost-first semantics, where a|ab on ab matches a; POSIX leftmost-longest would choose ab. Check which your engine implements before porting patterns.

Writing patterns that cannot hang

Most systems will keep a backtracking engine, so the practical skill is writing patterns that cannot explode. Catastrophic cases share one property: the engine can divide the same characters among sub-patterns in more than one way, and the match can still fail later.

• No nested quantifiers over the same characters. (a+)+ and (\w+\s?)* are the classic shapes; rewrite to one quantifier such as [\w\s]*.
• No overlapping alternation under repetition. (\w|\d)* offers two ways to consume every digit; merge the branches into one class.
• Make separators unambiguous. Use [^,]*(,[^,]*)* rather than .*(,.*)*: a negated class cannot consume the comma, so there is one way to split the input.
• Use atomic groups or possessive quantifiers. (?>a+) and a++ never give characters back. Java and PCRE support both, as does Python's re since 3.11.
• Anchor whole-string checks and cap input length. fullmatch stops retries at every start position, and a length limit bounds even an exponential worst case.

When users supply the pattern, as in search boxes or log filters, review cannot help: use a linear-time engine such as RE2 bindings or .NET's RegexOptions.NonBacktracking, or a match timeout. For plain substring or many-keyword search, a regex is the wrong tool entirely; Knuth-Morris-Pratt finds one literal in linear time and a trie underlies multi-keyword matching.

Trade-offs and failure modes

Failure modes worth knowing: a validation regex that hangs one request thread per malicious input until the pool is exhausted; a backtracking pattern wrapped in search that retries at every position; Unicode classes that compile into far larger automata than ASCII ones; . not matching newlines by default; and greedy .* captures that grab more than intended.

What to do next

1. Run the code from this article and compare it with your language's engine on random patterns over a two-letter alphabet.
2. Find every pattern applied to user input and rewrite nested quantifiers and overlapping alternations under repetition.
3. Time each flagged pattern on long runs of a repeated character plus one failing character, at lengths 10, 20 and 30; time that doubles per character is a ReDoS.
4. Cap input length before every regex on untrusted text, and use a linear-time engine wherever users supply the pattern.
5. Use atomic groups or possessive quantifiers where supported, and anchor whole-string validations.
6. Replace regexes that only search for literals with a substring or multi-keyword algorithm.