Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 61 ยท Projects

Project: A Regex Engine

Build a working regular expression engine in Python: parse patterns to a tree, compile to an NFA program, run Thompson simulation, and test it against re.

Earlier in this track you met regular expressions as a lexer tool, and you saw how a regex becomes an NFA and then a DFA. In this project you put that theory into one working program: a small regex engine with character classes, quantifiers, groups and alternation. It parses a pattern, compiles it into a tiny instruction list, and matches text with a Thompson simulation, which never backtracks and never takes exponential time.

A regex engine is a complete miniature compiler. The pattern is the source language, the parser produces an AST, the compiler produces a program for a very small virtual machine, and the matcher is that machine. Writing one is the best way to see that "compiler" is not only about programming languages. At the end you test your engine against Python's re module on hundreds of random patterns, and compare it with a backtracking matcher to see why the design matters.

What the engine supports

The engine handles the most useful part of the regex language:

Syntax Meaning
a, \. a literal character (escape a special one with a backslash)
. any character except a newline
[abc], [a-z0-9], [^x] a character class, ranges, negation
\d \w \s and \D \W \S digit, word character, whitespace, and their opposites (ASCII)
( ... ) grouping (no capturing, so it only changes precedence)
x|y alternation
* + ? zero or more, one or more, zero or one
{n,} {n,m} counted repetition

It answers two questions: fullmatch (does the whole text match?) and search (does a match start anywhere in the text?). It does not report where the match is or what the groups captured; that bookkeeping is a good exercise at the end.

flowchart LR
    P["Pattern text"] --> A["Parser<br/>recursive descent"]
    A --> T["AST<br/>set, cat, alt, star..."]
    T --> C["Compiler<br/>emits instructions"]
    C --> G["Program<br/>char, split, match"]
    G --> S["Simulator<br/>set of states per character"]
    S --> R["True or False"]

The same pipeline as every compiler in this track, only the target machine is tiny.

Step 1: parse the pattern into a tree

Regex syntax has three precedence levels, which is the same layering you saw in ambiguity and precedence: quantifiers bind tightest, then concatenation, then |. As a grammar:

TEXT
alternation = sequence ( "|" sequence )* ;
sequence    = quantified* ;
quantified  = atom ( "*" | "+" | "?" | "{n,m}" )? ;
atom        = "(" alternation ")" | "[" class "]" | "." | "\" escape | literal ;

That maps directly onto three methods. alternation calls sequence, which calls quantified, which calls atom; an opening parenthesis makes atom call alternation again, which is how nesting works. The tree uses a handful of node types: ("set", negated, ranges) for anything that matches one character, ("cat", [...]), ("alt", [...]), and the quantifier nodes star, plus, opt and rep.

Notice that every single-character matcher is a set of ranges. The literal a is the set [a-a], . is the negated set [^\n], and \d is [0-9]. One representation keeps the compiler and the matcher short.

Run the parser on a few patterns, and on several broken ones. A good engine reports a clear error instead of silently doing something odd.

Python Step 1: from pattern to AST

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree for a|bc is an alt of a single character and a cat, which shows the precedence rule: concatenation binds tighter than |, so the pattern means "a, or bc", not "a or b, then c". The error messages name the problem and the position, just like the parser errors in the JSON project.

Step 2: compile the tree to a small program

Instead of building NFA fragments and patching their edges, this engine compiles the tree into a flat list of instructions. The idea comes from Rob Pike's virtual-machine regex matchers. There are only three instructions:

  • char: if the next input character belongs to this set, consume it and go to instruction next.
  • split a, b: go to both a and b (an NFA's choice, or an epsilon edge pair).
  • match: the pattern is satisfied.

The compiler works backwards: every node is compiled with the address of the instruction that should run after it (nxt), and returns its own entry address. That removes all patching except for loops:

  • A set emits one char instruction that continues at nxt.
  • A cat compiles its items from last to first, feeding each entry point to the previous item.
  • An alt compiles every branch to continue at the same nxt, then chains split instructions that choose between the branches.
  • A star reserves a split first, because the loop body must jump back to it; then it compiles the body with the split as its continuation and fills in the split to choose "body or nxt". A plus uses the same loop but enters at the body, so it runs at least once.
  • opt is a split between the body and nxt.
  • rep is expanded before compiling: x{2,4} becomes x x (x (x)?)? and x{2,} becomes x x x*.

For example, (a|b)*c becomes a program of six instructions in which one split is the loop head and another chooses between a and b. Each instruction has at most two successors, which is exactly what Thompson's construction guarantees.

Step 3: simulate all paths at once

To match a string, keep the set of instructions the machine could be at after each character:

  1. Start with the closure of the entry point: follow every split until only char and match instructions remain. That set is the machine's "current states".
  2. For each input character, collect the next of every char instruction in the set that accepts that character. Take the closure of those targets.
  3. After the last character, the text matches if the set contains match.

This is the same loop as nfa_matches in the earlier lesson, with split playing the part of epsilon edges. Because the set contains each instruction at most once, its size is bounded by the size of the program, so matching takes time proportional to text length times pattern size, no matter how nasty the pattern.

A search (match anywhere) needs one change: before each step also add the program's entry point to the set, which means "a new match attempt starts here". If match ever appears in the set, return true immediately.

flowchart TD
    S0["Start: closure of entry"] --> C1{"next character"}
    C1 -->|"char instructions accept it"| S1["New set: their targets, then closure"]
    S1 --> C1
    C1 -->|"end of text"| E{"match in the set?"}
    E -->|"yes"| Y["True"]
    E -->|"no"| N["False"]

The simulator's whole job: a set of states in, one character, a set of states out.

Step 4: test it against re

The complete engine is about 150 lines. The run below puts it all together and checks it three ways:

  1. A table of hand-picked patterns and texts, compared with re.fullmatch (using the re.ASCII flag so that \d and \w mean the same as in our engine).
  2. A few search calls.
  3. Random patterns. A seeded generator builds 150 random patterns over the letters a and b from atoms, character classes, groups, alternation and quantifiers. Every pattern is compared with re on all 63 strings of up to five letters. Any disagreement is printed.
Python Step 2 to 4: compile, simulate and test against re

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you see mismatches: 0 the engine agrees with Python on about 9,500 comparisons. When you extend the engine, keep this harness: a random generator plus a trusted reference finds bugs far faster than hand-written cases, and the same technique appears again in Testing and Debugging a Compiler.

Why simulate instead of backtrack?

Python's re, Perl, Java and JavaScript use backtracking: they try one path, and when it fails they go back and try the next. That makes features like backreferences possible, and for typical patterns it is fast. But the number of paths can grow exponentially. The pattern (a|a)*b against a string of a characters can reach the end of the text in two different ways at every position, so a backtracking matcher explores about 2^n paths before it gives up.

The next run builds a deliberately naive backtracking matcher over the same AST (using continuations: "after this node, what must still match?") and counts its calls. It compares them with the number of state visits in the Thompson simulation.

Python Backtracking versus Thompson simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The backtracking column roughly doubles with every extra letter, while the simulation column grows by a constant amount per letter. At n = 30 the first would need billions of calls and the second still needs only about a hundred visits. Real engines soften the problem with memoization and clever optimizations, but the underlying risk is real: carefully chosen input can freeze a service that uses a backtracking engine. This attack has a name, ReDoS (regular-expression denial of service). Engines that guarantee linear time, such as RE2 and Rust's regex crate, use the approach you just built (usually with a lazily built DFA on top for speed).

The Thompson approach cannot support backreferences such as (a+)\1. Matching them is NP-hard in general, so engines that offer them must backtrack. That is the trade-off: expressive power versus a guaranteed running time.

Exercises

  • Capturing groups. Add a save instruction and track which positions each simulated thread passed through. This is Pike's full algorithm, with one thread per state.
  • Anchors. Add ^ and $ as zero-width instructions that only succeed at the start or end of the text.
  • Lazy quantifiers. Support *? by changing the order of the two branches in the split. (In the boolean simulation the result does not change; it matters once you report match positions.)
  • A DFA backend. Apply the subset construction from From Regex to NFA to DFA to the program, caching DFA states as you meet them. Matching then costs one lookup per character.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In this engine, how is the pattern ab|c parsed?

    Concatenation binds tighter than alternation, so the pattern means either the string ab or the string c.
  2. 2. What does a split instruction do during simulation?

    A split is the NFA's choice (an epsilon edge pair). The closure step follows both targets, so both paths are explored in parallel.
  3. 3. Why is the Thompson simulation immune to exponential blowup?

    Many paths can lead to the same instruction, but the set remembers it once. Work per character is at most the program size.
  4. 4. Which regex feature cannot be implemented with a pure NFA or DFA simulation?

    A backreference makes the engine remember an arbitrary earlier substring, which is more than a finite automaton can do. Engines with backreferences use backtracking.
  5. 5. How does the engine turn a fullmatch into a search?

    Adding the entry point at every position means a new match attempt can begin there, and the machine stops as soon as match appears in the set.

Summary

  • A regex engine is a small compiler: parser, AST, code generation for a three-instruction machine (char, split, match), and a simulator.
  • Precedence is quantifier, then concatenation, then alternation; one recursive-descent method per level.
  • Compiling backwards (each node receives the address of what comes next) removes almost all jump patching.
  • Simulating the whole set of states per character gives time proportional to text length times pattern size.
  • Backtracking engines can take exponential time on patterns like (a|a)*b; Thompson-style engines cannot.
  • A seeded random pattern generator compared with re is a cheap and powerful test.

Next: Project: A Transpiler to Python