Part of a multi-episode project
., grouping (), alternation |, and the three repetition operators *, +, ? -- and how operator precedence falls out of a recursive-descent parser;switch cannot forget a case;?u32 optional lets us say "this state has no outgoing edge" without a magic sentinel value, and how error unions carry parse failures back to the caller;Learn Zig Series):We closed the Lisp project last episode with a promise: turn away from parsing and evaluating for a while, and point ourselves back at the machine -- the kind of from-scratch engine work where you build one data structure that does one focused thing, and does it fast. A regular expression engine is exactly that. Almost every program you use runs regexes constantly -- your editor's find box, grep, the input validation on a signup form, the lexer of every compiler -- and yet most working programmers treat the regex engine as a magic black box. Over the next two episodes we are going to open the box and build one, and by the end you will understand not only how it works but why the good ones cannot be tricked into hanging for thirty seconds on a fourty-character pattern. That last part is not a footnote; it is the whole reason to do it the way we are about to.
Here is the single idea that organises everything. A regex engine is two machines stacked. The first is a parser that reads the pattern -- a flat string of characters like a(b|c)*d where some characters are literals and some are operators -- and produces a tree that captures the structure the flat string only implied. The second is a compiler that walks that tree and builds a state machine, a little graph of states and transitions that, when you feed it text, either accepts or rejects. Today we build both of those halves and stop just short of running the machine; next episode we feed it input and watch it match. Splitting the work this way is not busywork -- it is the same parse-then-compile shape we used for the calculator (episodes 146 to 149) and the Lisp (150 to 153), and seeing it a third time in a completely different domain is exactly how the pattern sinks in. Here we go!
Let us be precise about the little language we are going to support, because a regex dialect is itself a small language with a grammar. We support: literal characters (a matches an a), the wildcard . (matches any single character), grouping with parentheses, alternation a|b (match a or b), and the three repetition operators -- * (zero or more), + (one or more) and ? (zero or one). That is a genuinely useful subset; it is enough to write (ab)* or a.c or gr(a|e)y. What it deliberately leaves out -- character classes like [a-z], anchors, backreferences -- we can layer on later, but this core is where all the interesting machinery lives.
The reason we need a tree and not just the string is precedence. In ab|c, does the | split b and c, or ab and c? Regex convention (and ours) says repetition binds tightest, then concatenation, then alternation binds loosest -- so ab|c means (ab)|(c), not a(b|c)... wait, no, it means "the string ab, or the single c". The flat string cannot express that grouping; a tree can. So our first job is to turn the string into an abstract syntax tree, and in Zig the natural home for an AST node is a tagged union:
const std = @import("std");
const NodeKind = enum { char, any, concat, alt, star, plus, opt };
const Node = union(NodeKind) {
char: u8, // a literal byte
any: void, // the wildcard '.'
concat: [2]*Node, // left then right
alt: [2]*Node, // left OR right
star: *Node, // zero or more
plus: *Node, // one or more
opt: *Node, // zero or one
};
This is the same trick from episode 133, and it is worth savouring how much the type is doing for us. A Node is exactly one of these seven shapes -- never two, never none -- and the union(NodeKind) pairing means Zig will force any switch over a Node to handle all seven cases or refuse to compile. A whole category of "oops, forgot to handle alternation" bug is deleted at the type level, before we have written a line of logic. The binary operators (concat, alt) hold [2]*Node -- two child pointers -- and the repetition operators hold a single child. Pointers, because a tree of unknown depth has to live on the heap; we will hand out those pointers from an arena, so there is nothing to free by hand.
Recursive descent is the right tool here, and the structure of the parser mirrors the precedence table directly: one function per precedence level, each calling down into the tighter-binding level. parseAlt sits at the top (loosest), calls parseConcat, which calls parseRepeat, which calls parseAtom (tightest). Read them top-down and the grammar reads right off the code. First the scaffolding and the alternation level:
const ParseError = error{ UnexpectedEnd, UnbalancedParen, TrailingInput, OutOfMemory };
const Parser = struct {
src: []const u8,
pos: usize,
arena: std.mem.Allocator,
fn init(arena: std.mem.Allocator, src: []const u8) Parser {
return .{ .src = src, .pos = 0, .arena = arena };
}
fn peek(self: *Parser) ?u8 {
if (self.pos >= self.src.len) return null;
return self.src[self.pos];
}
fn make(self: *Parser, value: Node) ParseError!*Node {
const n = try self.arena.create(Node);
n.* = value;
return n;
}
fn parseAlt(self: *Parser) ParseError!*Node {
var left = try self.parseConcat();
while (true) {
const c = self.peek() orelse break;
if (c != '|') break;
self.pos += 1; // consume the '|'
const right = try self.parseConcat();
left = try self.make(.{ .alt = .{ left, right } });
}
return left;
}
};
Notice peek returns ?u8 -- an optional -- so "we are at the end of input" is a first-class value (null), not some sentinel byte we have to remember never appears in a real pattern. That orelse break idiom shows up all over the parser: try to read a character, and if there is none, stop. parseAlt reads one concatenation, then keeps swallowing | concat as long as it sees a pipe, folding each into a left-leaning alt node. Concatenation is the next level down, and it is subtle in one nice way -- there is no operator character for "concatenate"; juxtaposition is the operator:
fn parseConcat(self: *Parser) ParseError!*Node {
var left: ?*Node = null;
while (self.peek()) |c| {
if (c == '|' or c == ')') break; // these end a concatenation
const piece = try self.parseRepeat();
if (left) |l| {
left = try self.make(.{ .concat = .{ l, piece } });
} else {
left = piece;
}
}
return left orelse error.UnexpectedEnd;
}
We keep gluing pieces together until we hit something that ends the run -- a |, a closing ), or end of input. The left orelse error.UnexpectedEnd at the bottom is where an empty pattern (or an empty alternation branch like a|) turns into a clean error in stead of a crash. Now the two tightest levels, repetition and atoms:
fn parseRepeat(self: *Parser) ParseError!*Node {
var atom = try self.parseAtom();
while (self.peek()) |c| {
switch (c) {
'*' => {
self.pos += 1;
atom = try self.make(.{ .star = atom });
},
'+' => {
self.pos += 1;
atom = try self.make(.{ .plus = atom });
},
'?' => {
self.pos += 1;
atom = try self.make(.{ .opt = atom });
},
else => break,
}
}
return atom;
}
fn parseAtom(self: *Parser) ParseError!*Node {
const c = self.peek() orelse return error.UnexpectedEnd;
switch (c) {
'(' => {
self.pos += 1;
const inner = try self.parseAlt(); // recurse to the top!
const close = self.peek() orelse return error.UnbalancedParen;
if (close != ')') return error.UnbalancedParen;
self.pos += 1;
return inner;
},
'.' => {
self.pos += 1;
return self.make(.{ .any = {} });
},
'\\' => {
self.pos += 1; // escape: next char is a literal
const esc = self.peek() orelse return error.UnexpectedEnd;
self.pos += 1;
return self.make(.{ .char = esc });
},
else => {
self.pos += 1;
return self.make(.{ .char = c });
},
}
}
parseRepeat loops so that a** is legal (harmless, matches the same as a*), and parseAtom is where the recursion closes the loop: an opening ( calls parseAlt again, which is how nesting to any depth works with no explicit stack -- the Zig call stack is the stack. The \\ case gives us an escape hatch so a pattern can match a literal * or ( by writing \* or \(. This is roughly forty lines of code and it is a complete, correct recursive-descent parser for our dialect. If you followed the calculator and Lisp parsers, none of this is new -- and that is the point.
Now the machine. The tree tells us what the pattern means; we need something that can actually be run against text. That something is a nondeterministic finite automaton, an NFA -- a graph of states connected by transitions. Some transitions are labelled with a character ("if the next input byte is a, you may follow this edge"), and some are epsilon transitions, labelled with nothing at all -- you may follow them for free, consuming no input. Those free edges are the entire reason the construction is so clean, and they are worth understanding before we build anything.
The problem with wiring an NFA directly is that when you glue two pieces together -- say the machine for a followed by the machine for b -- you need the "exit" of the first to become the "entrance" of the second. If states could only have labelled edges, gluing would mean rewriting the first machine's exit transitions to point into the second. Epsilon edges make gluing trivial: you just drop a free edge from the first machine's accept state to the second machine's start state, and you are done. Nothing gets rewritten. This is Thompson's construction (Ken Thompson, 1968, the same Thompson who later co-created Unix and Go), and its genius is that every regex operator becomes a tiny, local rewiring using epsilon edges. Here are the Zig types:
const Symbol = union(enum) { literal: u8, any };
const State = struct {
symbol: ?Symbol = null, // a labelled (input-consuming) edge, or null for none
symbol_target: u32 = 0, // where that labelled edge goes
eps: [2]?u32 = .{ null, null }, // up to two free (epsilon) edges
accept: bool = false,
};
const Nfa = struct {
states: []State,
start: u32,
};
const Fragment = struct { start: u32, accept: u32 };
Look closely at the choices, because they are where Zig's type system quietly does work. A state's labelled edge is ?Symbol -- optional -- so "this state consumes no input, it only has epsilon edges" is represented honestly by null, not by some reserved character code that we would have to pray never collides with real data. The two epsilon slots are [2]?u32, an array of optionals: a state can have zero, one or two free edges, and an empty slot is null. Thompson's construction guarantees every state needs at most two epsilon edges -- I will show you why in a moment -- so a fixed [2] array is not a limitation, it is a proof encoded in the type. States are referred to by u32 index in stead of pointer, which makes the whole NFA a flat, relocatable []State we can allocate in one shot. A Fragment is a sub-machine mid-construction: just its start state and its single dangling accept state.
Here is the compiler that walks the AST and emits states. Every case follows the same recipe: recursively compile the children into fragments, then wire a few epsilon edges to combine them, and return a new fragment. Because we allocate states up front (more on that next), the construction itself never fails -- a pleasant separation, all the fallible work happened in the parser:
const Compiler = struct {
states: []State,
count: u32,
fn newState(self: *Compiler) u32 {
const id = self.count;
self.states[id] = .{}; // all defaults: no edges, not accepting
self.count += 1;
return id;
}
fn addEps(self: *Compiler, from: u32, to: u32) void {
const s = &self.states[from];
if (s.eps[0] == null) s.eps[0] = to else s.eps[1] = to;
}
fn atom(self: *Compiler, sym: Symbol) Fragment {
const s = self.newState();
const a = self.newState();
self.states[s].symbol = sym;
self.states[s].symbol_target = a;
return .{ .start = s, .accept = a };
}
fn compile(self: *Compiler, node: *const Node) Fragment {
return switch (node.*) {
.char => |c| self.atom(.{ .literal = c }),
.any => self.atom(.any),
.concat => |pair| blk: {
const f1 = self.compile(pair[0]);
const f2 = self.compile(pair[1]);
self.addEps(f1.accept, f2.start); // glue: f1 -> f2
break :blk .{ .start = f1.start, .accept = f2.accept };
},
.alt => |pair| blk: {
const f1 = self.compile(pair[0]);
const f2 = self.compile(pair[1]);
const s = self.newState(); // split
const a = self.newState(); // join
self.addEps(s, f1.start);
self.addEps(s, f2.start);
self.addEps(f1.accept, a);
self.addEps(f2.accept, a);
break :blk .{ .start = s, .accept = a };
},
.star => |inner| blk: {
const f = self.compile(inner);
const s = self.newState();
const a = self.newState();
self.addEps(s, f.start); // enter the loop body
self.addEps(s, a); // ...or skip it entirely (zero matches)
self.addEps(f.accept, f.start); // loop back for another match
self.addEps(f.accept, a); // ...or exit
break :blk .{ .start = s, .accept = a };
},
.plus => |inner| blk: {
const f = self.compile(inner);
const a = self.newState();
self.addEps(f.accept, f.start); // loop back (one match already done)
self.addEps(f.accept, a);
break :blk .{ .start = f.start, .accept = a };
},
.opt => |inner| blk: {
const f = self.compile(inner);
const s = self.newState();
self.addEps(s, f.start); // take it...
self.addEps(s, f.accept); // ...or skip it (zero matches)
break :blk .{ .start = s, .accept = f.accept };
},
};
}
};
Trace star and you can see the machine breathe. A new split state s has two epsilon edges: one into the loop body and one straight to the accept a, which is how a* matches the empty string. The body's own accept loops back to the body start (another repetition) or forward to a (done). That is four epsilon edges touching two states -- and here is the promise I made, kept: the split state s gets exactly two, and the body's accept state f.accept gets exactly two. No state in any of these cases ever needs a third epsilon edge, which is precisely why [2]?u32 is enough and not a corner cut. alt is the classic diamond -- split to both branches, both branches join back -- and plus is star minus the skip-edge, so it demands at least one match. Concatenation, the most common operation, is the cheapest: a single glue edge and zero new states.
One question remains: how big a []State do we allocate? With most data structures you would reach for a growable list and let it resize. But Thompson's construction has a property worth exploiting -- the number of states is bounded by the length of the pattern. Every pattern character contributes at most two states (a literal is two; an operator adds at most two; parentheses add none). So 2 * pattern.len + 2 is a hard upper bound, and we can allocate the whole thing once, from the arena, with no resizing ever. This is a very Zig way to think: you often know more about your sizes than a general-purpose container assumes, and when you do, you can trade a dynamic allocation for a single static one.
fn build(arena: std.mem.Allocator, pattern: []const u8) !Nfa {
var parser = Parser.init(arena, pattern);
const ast = try parser.parseAlt();
if (parser.pos != pattern.len) return error.TrailingInput; // e.g. a stray ')'
const states = try arena.alloc(State, pattern.len * 2 + 2);
var comp = Compiler{ .states = states, .count = 0 };
const frag = comp.compile(ast);
comp.states[frag.accept].accept = true; // the top fragment's exit is THE accept
return Nfa{ .states = comp.states[0..comp.count], .start = frag.start };
}
The parser.pos != pattern.len check is a small gem: after parsing a valid expression, if we have not consumed the entire string, something is wrong -- most commonly a ) with no matching (, which parseConcat stopped at but nobody consumed. That becomes a clean error.TrailingInput rather than a silently truncated match. We slice comp.states down to comp.count so the returned NFA reports its actual size, not the generous upper bound we reserved. Everything lives in the arena, so freeing the entire regex -- AST, states, all of it -- is one arena.deinit() at the call site. This is the allocator discipline from episode 7 paying off yet again: match the allocator's lifetime to the data's lifetime and manual cleanup disappears.
We will not have matching until next episode, so how do we test today's work? We test structure. The claims we can check without feeding input are surprisingly strong: that a compiles to a two-state machine with a labelled a edge into an accept state; that alternation produces a split start with two epsilon edges; that a stray ( is rejected. And there is one behavioural claim we can verify -- that a* can accept the empty string -- because "accept the empty string" means "the accept state is reachable from the start using only epsilon edges." That is a tiny graph walk:
fn epsAdd(nfa: Nfa, id: u32, visited: []bool) void {
if (visited[id]) return;
visited[id] = true;
for (nfa.states[id].eps) |maybe| {
if (maybe) |t| epsAdd(nfa, t, visited);
}
}
That epsAdd is not throwaway test scaffolding -- it is the epsilon-closure, the single most important operation in NFA simulation, and next episode it becomes the beating heart of the matcher. Here it earns its first paycheck validating the construction:
test "single char builds two states with a labelled edge" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const nfa = try build(arena.allocator(), "a");
try std.testing.expectEqual(@as(usize, 2), nfa.states.len);
const start = nfa.states[nfa.start];
try std.testing.expectEqual(@as(u8, 'a'), start.symbol.?.literal);
try std.testing.expect(nfa.states[start.symbol_target].accept);
}
test "star lets the accept state be reached with no input" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const nfa = try build(arena.allocator(), "a*");
const visited = try arena.allocator().alloc(bool, nfa.states.len);
@memset(visited, false);
epsAdd(nfa, nfa.start, visited);
var reached = false;
for (nfa.states, 0..) |st, i| {
if (st.accept and visited[i]) reached = true;
}
try std.testing.expect(reached);
}
test "unbalanced parenthesis is an error" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
try std.testing.expectError(error.UnbalancedParen, build(arena.allocator(), "(ab"));
}
On my machine zig test runs these green against Zig 0.16, alongside two more that check alternation's split shape and that (ab)+c stays inside its state budget. Testing structure before behaviour is a genuinely useful habit for machine-building code: if the graph is wired wrong, you want to know it here, from a five-line assertion, not three hundred lines later when a match mysteriously fails and you cannot tell whether the bug is in construction or simulation.
Here is the payoff I promised at the top, and it is the real reason to build the engine this way. You may have read about "catastrophic backtracking" or "ReDoS" -- a regex like (a+)+b that takes exponential time on an input of a's followed by no b, hanging a server on a forty-character string. That disaster is a property of backtracking engines (the kind in Perl, Python's re, JavaScript, PCRE), which try one path, and when it fails, back up and try another, and on a pathological pattern the number of paths explodes. Our NFA has a completely different performance character. When we simulate it next episode, we will track the set of states the machine could be in, all at once, advancing every state by one input character in lockstep. There are at most 2n states for a pattern of length n, so the state set can never be bigger than that, and each input character does at most O(n) work. Total: O(n * m) for a pattern of length n and text of length m -- linear in the text, always, with no pathological input. Thompson's 1968 construction plus set-based simulation is immune to the backtracking blow-up by design. The preallocated []State, the u32 indices instead of chased pointers, the cache-friendly flat array -- those are the constant-factor speedups; the guaranteed linear time is the algorithmic one, and it is the difference between an engine you can safely run on untrusted input and one you cannot.
Building this makes you see other engines' choices clearly. C is where Thompson's construction was born, and the canonical modern writeup is Russ Cox's regex series, whose C implementation uses exactly this shape -- State structs with an out and out1 pointer, epsilon edges as states with a special Split opcode. The difference from ours is memory management: Cox's C code hands you raw malloc'd states and a manual free, and the "dangling arrow" patching is done with pointer-to-pointer lists because C has no arena to lean on. Our arena erases that whole category of bookkeeping. Go's standard regexp package is the production heir to that lineage -- Russ Cox wrote it too -- and it guarantees the same linear-time worst case precisely because it refuses to backtrack; when you use Go's regexp you are running an industrial-strength version of what we just built, which is why Go is a safe choice for regexes over user input. Rust's regex crate is arguably the fastest of all, and it is the same core idea taken further: it compiles to an NFA, then often to a DFA (the subject of episode 142), and adds SIMD-accelerated literal prefiltering -- but it, too, stakes its reputation on never exhibiting catastrophic backtracking, and its author (Andrew Gallant) has written at length defending that guarantee. Zig sits comfortably in this company: our tagged-union AST, our ?Symbol optionals and our arena give us the same clarity as the C original with far less manual memory choreography, and nothing about the design gives up the linear-time promise.
Step back and look at what we have. A recursive-descent parser turns a(b|c)*d into a tree; Thompson's construction walks that tree and wires up an NFA of states and epsilon edges, allocated in a single arena slice whose size we could prove in advance; and an epsilon-closure walk already lets us test structural truths about the machine before it can run a single match. Every operator -- concat, alternation, and the three repetitions -- turned out to be a handful of free edges and at most two new states, which is why the construction is short enough to hold in your head. That is a real, non-trivial engine, and we built it from nothing.
What is missing is the fun part: actually running it. Next time we take an input string and this NFA and simulate the machine -- tracking that set of simultaneously-active states, advancing them character by character using the very epsAdd closure we wrote for testing today, and reporting a match when an accept state is live. That is where the linear-time guarantee stops being a promise and starts being code you can benchmark against a pathological input that would hang a backtracking engine for a minute. Bring the epsilon-closure idea with you -- it is the whole game. That is the machine built; next time we make it run. Thanks for reading, and I will see you in the next one! ;-)
@scipio