Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 59 ยท Projects

Project: A Regular Expression Engine

Build a regular expression matcher from scratch in Python: parse a regex, build an NFA with Thompson's construction, simulate it in linear time and test it against Python's re module.

Regular expressions and finite automata are two names for the same thing: Kleene's theorem says that a language is described by a regular expression exactly when some finite automaton accepts it. In this project you will turn that theorem into a working program. You will write a parser for a small regex language, a compiler that converts the parsed expression into an NFA (Thompson's construction), and a matcher that simulates the NFA.

The result is a tiny regex engine that runs in time proportional to |regex| ร— |text|, with no exponential blow-up. You will also see why some famous regex engines, which use backtracking instead, can take exponential time on innocent-looking patterns.

Our regex language

We support these operators, from tightest to loosest binding:

Syntax Meaning
a a literal character
. any single character
r* zero or more repetitions of r
r+ one or more
r? zero or one
rs concatenation (r followed by s)
r|s alternation (r or s)
( r ) grouping

The matcher answers whether the whole input string matches (a full match), which is what formal language theory means by "the string is in L(r)".

The pipeline

flowchart LR
    R["Regex text<br/>(a|b)*abb"] --> P["Parser<br/>recursive descent"]
    P --> T["Syntax tree"]
    T --> C["Thompson<br/>construction"]
    C --> N["NFA with<br/>ฮต-moves"]
    N --> M["State-set<br/>simulation"]
    M --> A["match / no match"]

From text to an answer in four stages.

Step 1: parsing with a grammar

Parsing regexes is a nice use of context-free grammars. The grammar encodes the binding strength of the operators:

TEXT
expr   -> term ( '|' term )*
term   -> factor factor*
factor -> atom ( '*' | '+' | '?' )*
atom   -> CHAR | '.' | '(' expr ')'

Each rule becomes one function (recursive descent). The parser returns a tuple tree such as ('cat', ('lit', 'a'), ('star', ('lit', 'b'))).

Step 2: Thompson's construction

Every operator corresponds to a small NFA fragment with one start state and one accepting state, glued together with ฮต-moves:

  • Literal a: start --a--> accept.
  • Concatenation r s: ฮต from r's accept to s's start.
  • Alternation r | s: a new start with ฮต-moves into both, and both accepts ฮต-move to a new accept.
  • Star r*: a new start and accept; ฮต-moves allow skipping r or looping back to r's start.
  • Plus and question mark are variations on star.

A regex of length m produces an NFA with O(m) states (our version creates two per syntax-tree node), so the conversion is linear.

Python Parser and Thompson construction

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.

Step 3: simulating the NFA

We do not convert to a DFA. Instead we simulate the NFA by tracking the set of states we could be in, which is the subset construction performed on the fly. For each input character we move every state in the set along matching edges and then expand with ฮต-moves. If the accept state is in the set at the end, we have a match. Each character costs at most O(number of states), so matching takes O(m ยท n) for a regex of size m and a text of length n.

Python The matcher, tested against Python's re module

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.

All pairs agree with Python's own engine. Testing a new implementation against a trusted one on every short string is a powerful technique called differential testing.

Why backtracking engines can explode

Most built-in engines (Python, Java, JavaScript, Perl) do not simulate the NFA with state sets. They try one path and backtrack when it fails, which also lets them support features like back-references. The cost is that some patterns take exponential time. For example (a*)*b against a long string of as tries every way to split the run of as. The state-set simulation we just built is immune: it never revisits the same state twice per character. Several modern engines (RE2 in Go and Rust's regex crate, for example) use exactly this approach to guarantee linear time.

Backtracking regex engines can be used to attack servers ("ReDoS"). If you accept regexes or run regexes on untrusted input, prefer a linear-time engine or put strict limits on input size and execution time.

Extension ideas

  • Add character classes [a-z] and escapes like \..
  • Add counted repetition a{2,4} by expanding it into concatenations.
  • Convert the NFA to a DFA with the subset construction from the previous project and cache the DFA states lazily; this is how fast production engines work.
  • Add search (find a match anywhere) by prefixing the pattern with .*.
  • Print the NFA as a Mermaid diagram, then compare with the textbook pictures.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Thompson's construction produce for the regex r|s?

    The new start state has ฮต-moves into both alternatives and each alternative's accept state has an ฮต-move to the new accept state.
  2. 2. Why does the state-set simulation run in O(m * n) time?

    The NFA has O(m) states for a regex of length m, and each input character needs one pass over the set of current states.
  3. 3. In the grammar term -> factor factor*, what does this rule describe?

    A term is a sequence of factors placed one after another, which is concatenation.
  4. 4. Why can backtracking regex engines be exponentially slow on some patterns?

    Nested repetition such as (a*)*b on a long run of a's lets the engine split the input in exponentially many ways before giving up.

Summary

  • A regex engine is a pipeline: parser (recursive descent), Thompson construction (NFA), simulation (state sets).
  • Thompson's construction builds an NFA with O(m) states for a regex of size m.
  • Simulating the set of states gives linear-time matching with no backtracking.
  • Differential testing against a trusted implementation on all short strings catches bugs quickly.
  • Backtracking engines add features at the price of possible exponential slowdowns.

Next: Project: A Grammar Toolkit with CNF Conversion and a CYK Parser