Regex is a tiny language with a beautiful implementation. You start with a matcher you can call on lesson one, then parse patterns into a tree, add the syntax real engines have, and build an NFA that never blows up - each step pinned by a concrete spec.
Over the next 34 lessons you'll build a regular-expression engine in the language of your choice, starting from a thirty-line matcher you can call on lesson one and growing it into a small library that mirrors a real `regexp` package. You'll parse patterns into a syntax tree; add groups, alternation, character classes, escapes, and `{n,m}` counts; then build a Thompson NFA that matches in linear time without the catastrophic backtracking that hangs naive engines.
By the end you'll have a teaching-grade regex library: compile a pattern once, then search text, pull out numbered and named capture groups, find every match, and replace. It deliberately stops short of lookaround, backreferences, and full Unicode - the features a production engine layers on top of exactly this core.
Today you turn a pattern string into a small syntax tree - the structure every later feature hangs off. Working from a tree instead of poking at the raw string is what will let you add stars, groups, and alternation cleanly.
Parse a pattern of plain characters into a Concat node holding one Literal per character.
A regex engine is really two machines glued together: a parser that reads the
pattern text into a tree, and a matcher that walks that tree against input.
Today is the parser’s first step. A pattern like abc is a concatenation of
three single-character matches, so it becomes a Concat node holding three
Literal nodes - one per byte.
It is tempting to skip the tree and match against the raw pattern string, and for
the very simplest features you could. But (ab|cd)* has structure a flat string
can’t express, and building the tree now means every feature you add later is just
one more node kind. Start with Literal and Concat; the rest of the syntax will
hang off this same shape.
// one node kind per pattern construct; today just twotype Literal struct{ Ch byte }type Concat struct{ Nodes []any }// walk the pattern left to right, one Literal per bytefunc parse(pat string) Concat { /* ... */ }
A solid teaching-grade ASCII regex library with two working engines and coherent capture semantics - not production-ready: no Unicode, no lookaround or backreferences, and capture correctness still degrades on deeply nested quantified constructs.
The essay that explains why backtracking blows up and how Thompson NFA simulation stays linear - the heart of this project's third chapter.
Companion piece extending the NFA into a bytecode VM with capture support - where to go after you finish.
The thirty-line backtracking matcher this project opens with, explained by its author.
The definitive guide to regex semantics and how engines actually behave across languages.
The "Dragon Book," with the formal treatment of Thompson construction and NFA simulation behind chapter three.