quick AND (fox OR -lazy) into a clean stream of tokens, distinct from the document tokenizer we already had;Nodes;Index, Posting and tokenizer and pick the story up precisely where it left off;Learn Zig Series):I ended last episode by pointing at the last crack of naivety left in our little search engine. We had an index that could find (episode 125) and one that could rank (episode 126), and the two together already behave like a real search box -- feed it text, ask it a question, get back documents ordered by relevance. But look at how the question actually reaches the engine. A "query" is still just a bare string that we chop into a flat bag of words. searchRanked("quick fox") and searchRanked("fox quick") do the exact same thing, and there is no way on earth to say "quick but not lazy", or "cat OR dog", or "quick and (cat or fox)". Real users type structure. Today we teach the engine to read that structure.
This is a mini-project episode, so -- as with the two before it -- there are no separate exercises. The build is the exercise. By the end you will have a small query language with AND, OR, NOT and parentheses, a lexer that tokenizes it, a recursive-descent parser that turns it into a tree, and an evaluator that runs that tree against last episode's index. And here is the part that should make you smile: we have built every single piece of this machinery before, in other clothes. We wrote a tokenizer for the markdown project (episode 37). We wrote a recursive-descent parser and an AST for it (episode 38). We wrote sorted-list merges for the inverted index (episode 125). Today is mostly a matter of pointing tools we already own at a new target. Let's dive right in!
Before writing a line, let us be precise about the language, because a parser is only as good as the grammar it is built from. Users of a search box want four things, and only four to begin with: to require a word, to forbid a word, to offer alternatives, and to group those choices. In the classic search syntax that maps to implicit AND (typing two words means "I want both"), NOT (a leading - or the word NOT forbids a word), OR (alternatives), and parentheses for grouping. Written as a small grammar in the style we used for markdown, it looks like this:
query = or_expr
or_expr = and_expr ( "OR" and_expr )*
and_expr = unary ( ("AND")? unary )* # implicit AND: adjacency means AND
unary = ("NOT" | "-") unary | primary
primary = "(" or_expr ")" | TERM
The shape of that grammar is not arbitrary -- it encodes precedence. OR sits at the top because it binds the loosest: in a b OR c the a b clumps together and then the OR splits it from c, so it reads as (a AND b) OR c. AND sits in the middle. NOT sits near the bottom because it binds the tightest of the operators -- -lazy grabs only the single word next to it. And primary, the leaf, is where a bare word or a parenthesized sub-expression lives. Reading a grammar top-to-bottom is reading precedence loosest-to-tightest, and that is the single most important thing to internalize before we translate it into Zig. Nota bene: the grammar is recursive -- primary can contain a whole or_expr inside parentheses -- and that recursion is exactly what recursive descent handles so gracefully.
The document tokenizer from episode 125 lower-cased words and threw away everything else, because in a document punctuation is noise. But in a query, punctuation is meaning: (, ) and - are operators we must not discard. So the query needs its own, separate lexer that recognizes those symbols as tokens in their own right. We start with the token kinds and a tiny scanner:
const TokKind = enum { term, and_op, or_op, not_op, lparen, rparen, end };
const Token = struct {
kind: TokKind,
text: []const u8 = "", // slice into the original query, valid for term tokens
};
const Lexer = struct {
src: []const u8,
pos: usize = 0,
fn skipSpaces(self: *Lexer) void {
while (self.pos < self.src.len and self.src[self.pos] == ' ') : (self.pos += 1) {}
}
fn next(self: *Lexer) Token {
self.skipSpaces();
if (self.pos >= self.src.len) return .{ .kind = .end };
const c = self.src[self.pos];
if (c == '(') {
self.pos += 1;
return .{ .kind = .lparen };
}
if (c == ')') {
self.pos += 1;
return .{ .kind = .rparen };
}
if (c == '-') {
self.pos += 1;
return .{ .kind = .not_op };
}
// a run of term characters
const start = self.pos;
while (self.pos < self.src.len and isTermChar(self.src[self.pos])) : (self.pos += 1) {}
const word = self.src[start..self.pos];
if (word.len == 0) {
// an unrecognized punctuation char: skip it and retry
self.pos += 1;
return self.next();
}
if (std.mem.eql(u8, word, "AND")) return .{ .kind = .and_op };
if (std.mem.eql(u8, word, "OR")) return .{ .kind = .or_op };
if (std.mem.eql(u8, word, "NOT")) return .{ .kind = .not_op };
return .{ .kind = .term, .text = word };
}
};
Two design decisions deserve a word. First, the keyword check: after scanning a run of letters we compare it against AND, OR and NOT before deciding it is a plain term. This is the standard lexer trick of "scan an identifier, then look it up in a keyword table" -- cheaper and simpler than trying to special-case keywords in the scanner loop. (I keep the keywords upper-case so that searching for the literal word "and" as a search term still, mostly, works -- a real engine would be more careful here, but for us it keeps the demo honest.) Second, the Token.text for a term is a slice into the original query string, not a copy. No allocation, no ownership -- the token borrows the query, and as long as the query string outlives the tokens (which it does, we parse in one go) that is perfectly safe. That reuse of isTermChar from episode 125 is deliberate: a "word" means the same thing in a query as in a document.
Here is the lexer chewing through a query with every token type in it:
test "lexer splits words, operators, and parentheses" {
var lex = Lexer{ .src = "quick AND (fox OR -lazy)" };
try std.testing.expectEqual(TokKind.term, lex.next().kind);
try std.testing.expectEqual(TokKind.and_op, lex.next().kind);
try std.testing.expectEqual(TokKind.lparen, lex.next().kind);
try std.testing.expectEqual(TokKind.term, lex.next().kind);
try std.testing.expectEqual(TokKind.or_op, lex.next().kind);
try std.testing.expectEqual(TokKind.not_op, lex.next().kind);
try std.testing.expectEqual(TokKind.term, lex.next().kind);
try std.testing.expectEqual(TokKind.rparen, lex.next().kind);
try std.testing.expectEqual(TokKind.end, lex.next().kind);
}
The tree we parse into is a boolean expression tree. Every node is either a leaf term, or an internal node that combines children: and, or, or a single-child not. We spell it as a tagged struct with optional child pointers -- the same tagged-union-of-pointers shape we built for markdown in episode 38:
const NodeKind = enum { term, and_node, or_node, not_node };
const Node = struct {
kind: NodeKind,
text: []const u8 = "", // used only for term nodes
left: ?*Node = null,
right: ?*Node = null, // null for not_node (only `left` is used)
};
A not_node uses only left; the binary combiners use both left and right; a term uses neither pointer and carries text instead. Now, a tree of pointers means allocation, and allocation means the ownership question rears its head again -- who frees all these nodes, and when? We could dutifully write a recursive destroy that walks the tree freeing children before parents (and that is a fine exercise). But there is a much slicker answer for a short-lived parse tree, and it is one of my favourite Zig patterns: an arena. We allocate every node from a std.heap.ArenaAllocator, and when the query is done we throw the whole arena away in one call. No per-node bookkeeping, no chance of a missed child. Having said that, let us wire the parser to use exactly that.
Recursive descent is the most direct parsing technique there is: you write one function per grammar rule, and each function calls the functions for the rules it references. The grammar we wrote above practically transcribes itself into Zig. The parser holds the lexer, the current lookahead token, and the arena it allocates nodes from:
const ParseError = error{ UnexpectedToken, UnexpectedEnd, MissingParen } || std.mem.Allocator.Error;
const Parser = struct {
lex: Lexer,
cur: Token,
arena: *std.heap.ArenaAllocator,
fn init(arena: *std.heap.ArenaAllocator, query: []const u8) Parser {
var lex = Lexer{ .src = query };
const first = lex.next();
return .{ .lex = lex, .cur = first, .arena = arena };
}
fn advance(self: *Parser) void {
self.cur = self.lex.next();
}
fn make(self: *Parser, node: Node) ParseError!*Node {
const p = try self.arena.allocator().create(Node);
p.* = node;
return p;
}
// query = or_expr , then we must be at end
fn parse(self: *Parser) ParseError!*Node {
const n = try self.parseOr();
if (self.cur.kind != .end) return error.UnexpectedToken;
return n;
}
// or_expr = and_expr ( "OR" and_expr )*
fn parseOr(self: *Parser) ParseError!*Node {
var left = try self.parseAnd();
while (self.cur.kind == .or_op) {
self.advance();
const right = try self.parseAnd();
left = try self.make(.{ .kind = .or_node, .left = left, .right = right });
}
return left;
}
};
Look at parseOr. It parses a first and_expr into left, then while the next token is OR, it eats the OR and folds another and_expr in on the right. That left = make(or_node, left, right) loop builds a left-associative tree -- a OR b OR c becomes ((a OR b) OR c), which for a commutative operator like OR does not matter for results but does keep the tree shape predictable. The pattern -- parse-one, then loop-folding-while-the-operator-repeats -- is the beating heart of recursive descent, and you will see it again one level down for AND. The rest of the rules follow the same template:
// and_expr = unary ( ("AND")? unary )* -- adjacency implies AND
fn parseAnd(self: *Parser) ParseError!*Node {
var left = try self.parseUnary();
while (true) {
if (self.cur.kind == .and_op) {
self.advance(); // explicit AND
} else if (self.startsUnary()) {
// implicit AND: two operands with no operator between them
} else break;
const right = try self.parseUnary();
left = try self.make(.{ .kind = .and_node, .left = left, .right = right });
}
return left;
}
fn startsUnary(self: *const Parser) bool {
return switch (self.cur.kind) {
.term, .not_op, .lparen => true,
else => false,
};
}
// unary = ("NOT" | "-") unary | primary
fn parseUnary(self: *Parser) ParseError!*Node {
if (self.cur.kind == .not_op) {
self.advance();
const inner = try self.parseUnary(); // NOT NOT x is legal, hence recursion
return self.make(.{ .kind = .not_node, .left = inner });
}
return self.parsePrimary();
}
// primary = "(" or_expr ")" | TERM
fn parsePrimary(self: *Parser) ParseError!*Node {
switch (self.cur.kind) {
.term => {
const t = self.cur.text;
self.advance();
return self.make(.{ .kind = .term, .text = t });
},
.lparen => {
self.advance();
const inner = try self.parseOr(); // recurse back to the top rule
if (self.cur.kind != .rparen) return error.MissingParen;
self.advance();
return inner;
},
.end => return error.UnexpectedEnd,
else => return error.UnexpectedToken,
}
}
The clever bit is parseAnd's implicit AND. There is no AND token between quick and fox, yet we want them ANDed. So the loop continues not only when it sees an explicit and_op, but also whenever the next token could begin another operand -- that is what startsUnary checks. A term, a NOT, or an opening paren all mean "another operand is coming; glue it on with AND". Anything else (an OR, a closing paren, end of input) breaks the loop and hands control back up. This is how the parser knows that quick fox is two operands and quick OR is one operand followed by a different operator. And notice parsePrimary calling parseOr inside parentheses -- that is the recursion in "recursive descent", the mechanical reflection of primary referencing or_expr in the grammar. Error handling is pure idiomatic Zig: a missing ) is not a panic, it is return error.MissingParen, propagated up through every try until whoever called parse decides what to do about it.
We tie it off with a one-liner that owns the arena lifetime and hands back the root:
fn parseQuery(arena: *std.heap.ArenaAllocator, query: []const u8) ParseError!*Node {
var parser = Parser.init(arena, query);
return parser.parse();
}
A parsed tree is inert until we run it. Evaluation walks the AST and, at each node, produces the set of document ids that satisfy that sub-expression. A term node yields the docs in its postings list. An and node intersects its children's sets, an or node unites them, and a not node returns the complement against all documents. Because episode 125 stored postings in ascending doc-id order, every set we ever handle is sorted, which means intersect and union are the linear two-pointer merges we already wrote -- no hashing, no sorting, just a single walk down two lists:
const DocSet = std.ArrayList(u32);
fn termDocs(index: *const Index, gpa: std.mem.Allocator, term: []const u8) !DocSet {
var out: DocSet = .empty;
for (index.postingsFor(term)) |p| try out.append(gpa, p.doc);
return out; // postings are already ascending by doc id
}
fn intersect(gpa: std.mem.Allocator, a: []const u32, b: []const u32) !DocSet {
var out: DocSet = .empty;
var i: usize = 0;
var j: usize = 0;
while (i < a.len and j < b.len) {
if (a[i] == b[j]) {
try out.append(gpa, a[i]);
i += 1;
j += 1;
} else if (a[i] < b[j]) i += 1 else j += 1;
}
return out;
}
fn unite(gpa: std.mem.Allocator, a: []const u32, b: []const u32) !DocSet {
var out: DocSet = .empty;
var i: usize = 0;
var j: usize = 0;
while (i < a.len and j < b.len) {
if (a[i] == b[j]) {
try out.append(gpa, a[i]);
i += 1;
j += 1;
} else if (a[i] < b[j]) {
try out.append(gpa, a[i]);
i += 1;
} else {
try out.append(gpa, b[j]);
j += 1;
}
}
while (i < a.len) : (i += 1) try out.append(gpa, a[i]);
while (j < b.len) : (j += 1) try out.append(gpa, b[j]);
return out;
}
fn complement(gpa: std.mem.Allocator, a: []const u32, doc_count: u32) !DocSet {
var out: DocSet = .empty;
var i: usize = 0;
var doc: u32 = 0;
while (doc < doc_count) : (doc += 1) {
if (i < a.len and a[i] == doc) {
i += 1; // present in a -> excluded from the complement
} else {
try out.append(gpa, doc);
}
}
return out;
}
The complement deserves a caveat, because pure negation is genuinely dangerous in a search engine. Asking for NOT lazy on a corpus of a billion documents means materializing a billion-minus-a-few document ids -- a set so large it is useless. That is why real engines only allow NOT as a filter on an already-restricted set (fox AND NOT lazy), never as a standalone query. Our complement walks 0..doc_count, which is fine for a teaching corpus of a handful of documents but would be madness at scale; I keep it simple here and flag the danger loudly rather than hide it. The recursive evaluator itself is short and reads exactly like the grammar:
fn evaluate(node: *const Node, index: *const Index, gpa: std.mem.Allocator) !DocSet {
switch (node.kind) {
.term => return termDocs(index, gpa, node.text),
.and_node => {
var l = try evaluate(node.left.?, index, gpa);
defer l.deinit(gpa);
var r = try evaluate(node.right.?, index, gpa);
defer r.deinit(gpa);
return intersect(gpa, l.items, r.items);
},
.or_node => {
var l = try evaluate(node.left.?, index, gpa);
defer l.deinit(gpa);
var r = try evaluate(node.right.?, index, gpa);
defer r.deinit(gpa);
return unite(gpa, l.items, r.items);
},
.not_node => {
var inner = try evaluate(node.left.?, index, gpa);
defer inner.deinit(gpa);
return complement(gpa, inner.items, index.doc_count);
},
}
}
The memory choreography here is worth pausing on. Each internal node produces two child sets, uses them to build one result set, and frees the two children on the way out with defer. Only the freshly-built result survives up the call stack, where its parent will consume and free it in turn. Every intermediate DocSet is born and buried at exactly one level of the recursion -- no leaks, no double frees, and std.testing.allocator will scream if I got it wrong. That predictability is the whole reason Zig makes you name the allocator: the lifetime of every set is right there in the code, not hidden in a garbage collector's head.
The public entry point creates the arena, parses, evaluates, and tears the arena down -- the AST lives exactly as long as the evaluation that needs it:
fn runQuery(index: *const Index, gpa: std.mem.Allocator, query: []const u8) !DocSet {
var arena = std.heap.ArenaAllocator.init(gpa);
defer arena.deinit(); // frees the entire AST in one shot
const ast = try parseQuery(&arena, query);
return evaluate(ast, index, gpa);
}
And now the payoff -- the whole language, exercised against a four-document corpus. Watch each operator do precisely what the grammar promised:
test "the query language answers structured questions" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
_ = try index.addDocument("the quick brown fox"); // 0
_ = try index.addDocument("the lazy brown dog"); // 1
_ = try index.addDocument("a quick red cat"); // 2
_ = try index.addDocument("the sleepy fox and the lazy dog"); // 3
// implicit AND: only doc 0 has both "quick" and "fox"
var a = try runQuery(&index, gpa, "quick fox");
defer a.deinit(gpa);
try std.testing.expectEqual(@as(usize, 1), a.items.len);
try std.testing.expectEqual(@as(u32, 0), a.items[0]);
// OR: docs 1, 2 and 3 mention a cat or a dog
var b = try runQuery(&index, gpa, "cat OR dog");
defer b.deinit(gpa);
try std.testing.expectEqual(@as(usize, 3), b.items.len);
// NOT: doc 0 has fox and no lazy; doc 3 has fox AND lazy, so it is excluded
var c = try runQuery(&index, gpa, "fox -lazy");
defer c.deinit(gpa);
try std.testing.expectEqual(@as(usize, 1), c.items.len);
try std.testing.expectEqual(@as(u32, 0), c.items[0]);
// parentheses override precedence: quick AND (cat OR fox) -> docs 0 and 2
var d = try runQuery(&index, gpa, "quick (cat OR fox)");
defer d.deinit(gpa);
try std.testing.expectEqual(@as(usize, 2), d.items.len);
try std.testing.expectEqual(@as(u32, 0), d.items[0]);
try std.testing.expectEqual(@as(u32, 2), d.items[1]);
}
Every one of those passes clean, no leaks. That last query is the one I am proudest of -- quick (cat OR fox) correctly finds the quick fox (doc 0) and the quick cat (doc 2) while rejecting the lazy dog and the sleepy fox, because the parentheses forced the OR to resolve before the AND. Take the parentheses away and quick cat OR fox would parse as (quick AND cat) OR fox and let the sleepy fox back in. That difference -- invisible in a flat bag of words -- is the entire reason we built a parser.
A parser has two jobs: accept every valid input, and reject every invalid one without falling over. The second job is the one beginners forget, and it is where Zig's error unions shine, because a malformed query becomes a plain value you can assert on. We test that a dangling paren, a trailing operator, and a stray close-paren each produce the specific error we expect, not a crash and not a wrong answer:
test "malformed queries surface as errors, not crashes" {
const gpa = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(gpa);
defer arena.deinit();
try std.testing.expectError(error.MissingParen, parseQuery(&arena, "quick (fox"));
try std.testing.expectError(error.UnexpectedEnd, parseQuery(&arena, "quick OR"));
try std.testing.expectError(error.UnexpectedToken, parseQuery(&arena, "fox )"));
}
expectError is the mirror image of the try-based tests above: it asserts the call returns this error and nothing else. And there is a second class of "wrong" that should not be an error at all -- searching for a word that simply is not in the corpus. That is not malformed; it is a perfectly valid query that happens to match nothing, and the engine should return an empty set, calmly:
test "unknown words match nothing, without erroring" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
_ = try index.addDocument("the quick brown fox");
var docs = try runQuery(&index, gpa, "quick AND elephant");
defer docs.deinit(gpa);
try std.testing.expectEqual(@as(usize, 0), docs.items.len); // "elephant" is unknown -> AND empties it
}
Distinguishing "you typed nonsense" (an error) from "your valid query found nothing" (an empty result) is a real design line, and getting it right is what separates a toolbox from a tantrum. The unknown word elephant has empty postings, and intersecting anything with the empty set gives the empty set -- exactly the correct answer, delivered without drama.
Right now runQuery gives back an unordered set of matching doc ids. But last episode we learned to rank, and a structured query deserves ranking just as much as a flat one did. The clean way to combine them is a two-stage pipeline that mirrors how every production engine works: the boolean query decides which documents qualify (the candidate set), and TF-IDF decides in what order to show them. We reuse the tfWeight and idf from episode 126, but only score the survivors:
fn rankCandidates(
index: *const Index,
gpa: std.mem.Allocator,
candidates: []const u32,
terms: []const []const u8,
) !std.ArrayList(Result) {
var keep = std.AutoHashMap(u32, void).init(gpa);
defer keep.deinit();
for (candidates) |d| try keep.put(d, {});
var scores = std.AutoHashMap(u32, f64).init(gpa);
defer scores.deinit();
for (terms) |term| {
const w = index.idf(term);
if (w == 0) continue;
for (index.postingsFor(term)) |post| {
if (!keep.contains(post.doc)) continue; // ignore docs the boolean query rejected
const gop = try scores.getOrPut(post.doc);
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += tfWeight(post.tf) * w;
}
}
var results: std.ArrayList(Result) = .empty;
var it = scores.iterator();
while (it.next()) |e| {
try results.append(gpa, .{ .doc = e.key_ptr.*, .score = e.value_ptr.* });
}
std.mem.sort(Result, results.items, {}, struct {
fn less(_: void, a: Result, b: Result) bool {
return a.score > b.score;
}
}.less);
return results;
}
This is the whole architecture of real search in miniature: filter, then rank. The parser and evaluator answer "does this document qualify?" as a hard boolean -- it either satisfies the AND/OR/NOT structure or it does not -- and only the qualifying documents get sorted by the soft, continuous TF-IDF score. Keeping the two stages separate is not just tidy; it is what lets an engine apply cheap boolean filters to prune millions of documents down to thousands before paying for the expensive scoring pass. We have, almost by accident, arrived at the same shape Elasticsearch uses.
Everything we wrote today is a scaled-down version of production reality. Lucene -- the Java engine inside Elasticsearch and Solr -- ships a QueryParser that lexes exactly this kind of syntax (+required -forbidden "phrases" field:value AND OR), builds a tree of Query objects (BooleanQuery, TermQuery, MustNot clauses), and evaluates it against postings with the same set operations, just backed by compressed, skip-listed lists instead of our plain []u32. In Rust, the tantivy crate has a QueryParser that produces a boxed dyn Query tree and evaluates it with a BooleanWeight over its segments -- recursive descent into a trait-object AST, the Rust spelling of what our tagged Node does. In Go, Bleve parses its query syntax into a tree of Query interface values and walks them the same way. And C? The SQLite FTS5 extension hand-writes a recursive-descent parser for its MATCH query grammar in a single C file -- keyword scan, precedence climbing, an AST of Fts5ExprNode structs -- and it is startlingly close, line for line, to what we built here in Zig. Four ecosystems, one idea: lex the query, parse it into a tree by precedence, evaluate the tree against the index. Bam, jonguh! ;-)
The differences are all in the extensions we deliberately skipped: phrase queries ("quick fox" as adjacent words) need a positional index that stores where in each document a term occurs -- our postings only count how often, not where, so true phrase search is the one feature we cannot bolt on without going back to the index. Fielded search (title:zig), fuzzy matching, wildcards, and the top-k heap that keeps only the best results all layer on from here. But the spine -- lexer, precedence grammar, recursive-descent parser, tree-walking evaluator -- is done, and it is the same spine those giants stand on.
Look back at what these three episodes built together. Episode 125 gave us an index that could find. Episode 126 gave it the judgement to rank. Today gave it the ability to understand a structured question -- to read quick AND (cat OR fox) the way a human means it, not as a flat mush of words. Tokenizer, inverted index, TF-IDF scoring, and now a real query language with a parser and evaluator behind it: that is a small but genuinely honest search engine, and every gear in it -- the hash map from episode 22, the iterators from 23, the recursive-descent parsing from the markdown project, the sorted merges from 125, the ownership discipline from episode 7 -- is something we forged earlier in this series and simply pointed at a new problem.
That, more than any single algorithm, is the lesson I want you to take from this mini-project. A search engine sounds like a monolith, an intimidating thing you would download rather than write. But taken apart it is four small, comprehensible pieces you already knew how to build, wired together with care about ownership and correctness. Recursive descent in particular is a tool you will reach for again and again -- any time a program has to read a little language of its own, whether that is a query, a config format, an expression evaluator, or something bigger and more ambitious that turns text into structured meaning. We have practised the pattern twice now (markdown, and this), and it will come back. Go point our search engine at a folder of your own text files, type a real structured query, and watch the right documents float to the top in the right order.
Thanks for reading, and until the next one -- keep building the tools you use. De groeten! ;-)
@scipio