Learn Zig Series (#132) - Recursive Descent Parsing

scipio

Published: 08 Aug 2026 › Updated: 08 Aug 2026 Learn Zig Series (#132) - Recursive Descent Parsing

Learn Zig Series (#132) - Recursive Descent Parsing

What will I learn?

Why a recursive-descent parser is just one small function per grammar rule, and how that maps almost mechanically onto the language we started lexing last episode;
How to design a minimal AST (abstract syntax tree) that captures what a program means instead of just the flat characters it is made of;
The trick that makes 2 + 3 * 4 come out as 2 + (3 * 4) and not (2 + 3) * 4 -- precedence climbing, in about a dozen lines;
How Zig's tagged unions, error unions and an arena allocator turn a parser into something short, fast and impossible to leak;
Parsing statements -- let, return, if, while, blocks and function calls -- into a tree you can walk;
Turning malformed input into a typed error.UnexpectedToken the caller can point a line and column at, in stead of a crash;
How C, Rust and Go build the exact same shape at production scale;
Three exercises to push the parser further before the next episode.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
The lexer from episode 131 fresh in mind -- today we feed its tokens into a parser;
Tagged unions from episode 6, pointers and memory layout from episode 8, allocators from episode 7, and Zig's error handling from episode 4;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#132) - Recursive Descent Parsing

Last episode we built a lexer for our little language -- the one with let, fn, if, while, arithmetic, function calls and string literals -- and it gave us back a flat stream of typed tokens, each stamped with a line and column. let x = 42; came out as kw_let, identifier, assign, int, semicolon, eof, and that was as far as we got. A flat list. There is no notion in that list that x is being bound to 42, that 42 is the value half of an assignment, that the whole thing is one statement. The structure is still locked up inside the order of the tokens, implied but not expressed.

Today we express it. We take that flat stream and turn it into a tree -- a shape where let x = 42; becomes a let node with a name and a value, where 2 + 3 * 4 becomes a plus node whose right child is a times node, where fact(n - 1) becomes a call node with one argument that is itself a subtraction. That tree is the AST, the abstract syntax tree, and building it is the job of the parser. The technique we use is the one almost every hand-written compiler and interpreter reaches for first, because it is the one that reads most like the grammar it implements: recursive descent. Let's dive right in!

Solutions to Episode 131 Exercises

Before the new material, the three exercises from last episode. All of them extend the lexer, and all three compile against the Lexer struct exactly as we left it.

Exercise 1 -- Hexadecimal literals. The task was to make number recognise a 0x prefix and scan hex digits, keeping the token kind .int. The trick is to check for 0x (or 0X) before the normal decimal loop, and if we find it, run a separate hex-digit loop and return early -- so a bare 0 that is not followed by an x still falls through to the decimal path unchanged:

fn isHexDigit(c: u8) bool {
    return std.ascii.isDigit(c) or (c >= 'a' and c <= 'f') or (c >= 'A' and c <= 'F');
}

fn number(self: *Lexer, line: usize, col: usize) Token {
    const start = self.pos;
    if (self.peek() == '0' and (self.peekNext() == 'x' or self.peekNext() == 'X')) {
        _ = self.bump(); // '0'
        _ = self.bump(); // 'x'
        while (isHexDigit(self.peek())) {
            _ = self.bump();
        }
        return Token{ .kind = .int, .text = self.src[start..self.pos], .line = line, .col = col };
    }
    while (std.ascii.isDigit(self.peek())) {
        _ = self.bump();
    }
    var kind: TokenKind = .int;
    if (self.peek() == '.' and std.ascii.isDigit(self.peekNext())) {
        kind = .float;
        _ = self.bump(); // consume the '.'
        while (std.ascii.isDigit(self.peek())) {
            _ = self.bump();
        }
    }
    return Token{ .kind = kind, .text = self.src[start..self.pos], .line = line, .col = col };
}

The key insight is that the token's text still holds the raw slice "0xFF", prefix and all. We do not convert it to a number here -- the parser (or a later pass) can call std.fmt.parseInt(i64, "0xFF"[2..], 16) when it actually needs the value. The lexer's only job is to decide "these four characters are one integer token".

Exercise 2 -- Nesting block comments. The task was to add /* ... */ comments to skipTrivia, spanning multiple lines, and as a stretch to make them nest. Nesting is the interesting part: C famously does not nest block comments (the first */ ends everything), but Rust and Zig do, and a depth counter is all it takes. We count up on every /* and down on every */, and stop when depth returns to zero:

fn skipTrivia(self: *Lexer) void {
    while (self.pos < self.src.len) {
        const c = self.src[self.pos];
        if (std.ascii.isWhitespace(c)) {
            _ = self.bump();
        } else if (c == '/' and self.peekNext() == '/') {
            while (self.pos < self.src.len and self.src[self.pos] != '\n') {
                _ = self.bump();
            }
        } else if (c == '/' and self.peekNext() == '*') {
            _ = self.bump(); // '/'
            _ = self.bump(); // '*'
            var depth: usize = 1;
            while (self.pos < self.src.len and depth > 0) {
                if (self.peek() == '/' and self.peekNext() == '*') {
                    _ = self.bump();
                    _ = self.bump();
                    depth += 1;
                } else if (self.peek() == '*' and self.peekNext() == '/') {
                    _ = self.bump();
                    _ = self.bump();
                    depth -= 1;
                } else {
                    _ = self.bump();
                }
            }
        } else {
            break;
        }
    }
}

Because every character still goes through bump, a comment that spans three lines advances the line counter three times, so the token after the comment still reports its true position. That was the whole point of routing trivia through bump in the first place.

Exercise 3 -- A column-precise error. The task was to record the offending line and column on the struct before returning error.UnexpectedChar, so a caller can print a real diagnostic. We add two fields, err_line and err_col, and fill them in the else arm of the operator switch. The line and col passed into operator already point at the token's first character -- which, for an unrecognised character, is the offending character:

// added to the Lexer struct's fields:
//   err_line: usize = 0,
//   err_col: usize = 0,

fn operator(self: *Lexer, line: usize, col: usize) LexError!Token {
    const start = self.pos;
    const c = self.bump();
    const kind: TokenKind = switch (c) {
        '+' => .plus,
        '-' => .minus,
        // ... the rest of the operators, unchanged ...
        '<' => if (self.match('=')) .lte else .lt,
        '>' => if (self.match('=')) .gte else .gt,
        else => {
            self.err_line = line;
            self.err_col = col;
            return error.UnexpectedChar;
        },
    };
    return Token{ .kind = kind, .text = self.src[start..self.pos], .line = line, .col = col };
}

Now a test can assert not just that the lexer rejected @ but exactly where: feeding "let x = @;" and stepping past let x =, the failing next() leaves err_line == 1 and err_col == 9, the precise column of the @. That is the groundwork for the "error: unexpected character at 1:9" messages every good compiler prints -- and notice we get it for free from the position tracking we already built. On to the parser.

Recursive descent, in one sentence

Here is the whole idea, and it really is this simple: write one function for each rule in your grammar, and let the functions call each other the same way the rules refer to each other. A grammar rule like "a program is a list of statements" becomes a function parseProgram that loops calling parseStmt. "A statement is a let, or a return, or an expression followed by a semicolon" becomes a parseStmt that switches and delegates. "An expression can contain a smaller expression in parentheses" becomes a parseExpr that, in one of its branches, calls parseExpr again -- and that self-call is the recursion, the "descent" into a nested sub-expression. The structure of the code mirrors the structure of the language, one to one, which is exactly why it is the technique you can hold in your head.

The grammar of our little language, written informally, looks like this:

program    = statement*
statement  = "let" ident "=" expr ";"
           | "return" expr ";"
           | "if" expr block ("else" block)?
           | "while" expr block
           | block
           | expr ";"
block      = "{" statement* "}"
expr       = ... arithmetic, comparisons, calls, with precedence ...

Every one of those lines is about to become a function. But before we can write functions that build a tree, we need to decide what the tree is made of.

A tree worth building: the AST

The tokens are the raw material; the AST is the structure. An expression in our language is one of a handful of shapes -- a literal number, a name, a unary operation like -x, a binary operation like a + b, or a function call. That is a textbook case for a tagged union (episode 6): one type, several variants, the active variant known at runtime. The recursive shapes -- binary and unary and call -- hold pointers to child expressions, because a union cannot contain itself by value (it would have infinite size), so we box the children on the heap and point at them:

const Expr = union(enum) {
    int: i64,
    float: f64,
    boolean: bool,
    ident: []const u8,
    unary: struct { op: TokenKind, rhs: *Expr },
    binary: struct { op: TokenKind, lhs: *Expr, rhs: *Expr },
    call: struct { callee: []const u8, args: []const *Expr },
};

Statements get the same treatment. A statement is a let binding, a return, a bare expression, a { ... } block, an if, or a while. Blocks and bodies are slices of statements, because a block holds however many statements the programmer wrote:

const Stmt = union(enum) {
    let: struct { name: []const u8, value: *Expr },
    ret: *Expr,
    expr: *Expr,
    block: []const Stmt,
    if_: struct { cond: *Expr, then_body: []const Stmt, else_body: ?[]const Stmt },
    while_: struct { cond: *Expr, body: []const Stmt },
};

Notice else_body is an optional slice, ?[]const Stmt -- an if may or may not have an else, and Zig's optionals model "may or may not" exactly, so there is no sentinel and no ambiguity. This is a deliberately minimal AST -- just enough shape for the parser to fill in. The proper design of an AST, the traversal patterns you walk it with, and the choices around arenas versus indices, is a whole topic in its own right, and it is the very next brick in this arc. For now, keep it lean.

There is a memory question hiding in all those *Expr pointers: who frees them? The answer is the cleanest one Zig offers for this shape of problem -- an arena allocator (episode 7). Every node the parser creates comes from one arena, and when we are done with the whole tree we throw the entire arena away in a single deinit. No per-node frees, no walking the tree to tear it down, no chance of leaking a subtree. An AST is the perfect arena workload: many small allocations with exactly the same lifetime.

Tokenise first, then parse

There are two ways to feed a parser: pull one token at a time from the lexer as you go, or run the lexer to completion first and hand the parser a finished slice of tokens. We take the second route. It costs one array of tokens up front, and in return the parser becomes dramatically simpler: it can peek at the current token and the next as often as it likes, it never has to thread the lexer's LexError through every parsing function, and "look one token ahead" is a plain array index in stead of a stateful pull. So first, a small helper that drains the lexer into a slice:

fn tokenize(alloc: std.mem.Allocator, src: []const u8) !([]Token) {
    var lexer = Lexer{ .src = src };
    var toks: std.ArrayList(Token) = .empty;
    while (true) {
        const t = try lexer.next();
        try toks.append(alloc, t);
        if (t.kind == .eof) break;
    }
    return toks.toOwnedSlice(alloc);
}

We keep scanning until we append the eof token, then stop -- so eof is always the last element of the slice. That matters, because the parser leans on eof being present: it never walks off the end of the array, it just keeps seeing eof no matter how many times it peeks. Any LexError from a malformed source surfaces right here, at tokenise time, before parsing even begins.

The parser's skeleton and its cursor

The parser holds the token slice, a cursor position, and the arena allocator it builds nodes from. On top of those, a tiny vocabulary of cursor helpers -- and every parsing function is written in terms of these five, never touching pos directly, the same discipline that kept the lexer's position tracking honest last episode:

const ParseError = error{UnexpectedToken} || std.mem.Allocator.Error;

const Parser = struct {
    tokens: []const Token,
    pos: usize = 0,
    arena: std.mem.Allocator,

    fn peek(self: *Parser) Token {
        return self.tokens[self.pos];
    }

    fn advance(self: *Parser) Token {
        const t = self.tokens[self.pos];
        if (t.kind != .eof) self.pos += 1;
        return t;
    }

    fn check(self: *Parser, kind: TokenKind) bool {
        return self.peek().kind == kind;
    }

    fn match(self: *Parser, kind: TokenKind) bool {
        if (self.check(kind)) {
            _ = self.advance();
            return true;
        }
        return false;
    }

    fn expect(self: *Parser, kind: TokenKind) ParseError!Token {
        if (self.check(kind)) return self.advance();
        return error.UnexpectedToken;
    }

Look at ParseError. It has exactly one variant of its own -- UnexpectedToken -- unioned with std.mem.Allocator.Error, because any function that allocates a node can fail with OutOfMemory, and Zig makes us name that possibility in the type. That is the whole error surface of the parser: either we saw a token we did not expect, or we ran out of memory. Everything else is a valid parse.

The difference between advance, match and expect is worth pinning down, because the whole parser is built from them. advance unconditionally consumes and returns the current token (but refuses to step past eof, so a buggy caller loops on eof in stead of reading out of bounds). match consumes only if the current token is the kind you named, and reports whether it did -- perfect for optional syntax like a trailing comma. expect consumes a token that must be there and turns its absence into error.UnexpectedToken -- perfect for the required ; after a let, or the ) that has to close a (. Three verbs, and the entire grammar falls out of them.

The precedence problem, and how to climb out of it

Now the heart of it. Consider 2 + 3 * 4. A human reading left to right might be tempted to compute 2 + 3 = 5, then 5 * 4 = 20. Wrong -- multiplication binds tighter than addition, so the answer is 2 + 12 = 14, and the tree has to reflect that: a plus node whose children are 2 and the star node (3 * 4). The parser has to know that * outranks +, and it has to build the tree accordingly. The elegant way to teach it that, without writing a separate function for every precedence level, is called precedence climbing (you may also see it called Pratt parsing, its close cousin).

First, a table -- really just a function -- that assigns each binary operator a number. Higher number, tighter binding:

fn precedence(kind: TokenKind) u8 {
    return switch (kind) {
        .kw_or => 1,
        .kw_and => 2,
        .eq, .neq => 3,
        .lt, .lte, .gt, .gte => 4,
        .plus, .minus => 5,
        .star, .slash, .percent => 6,
        else => 0, // not a binary operator
    };
}

So or is loosest (level 1), then and, then equality, then comparisons, then +/-, and *///% bind tightest at level 6. Any token that is not a binary operator -- a semicolon, a closing paren, eof -- returns 0, which the parser reads as "stop, this is not part of the expression".

The climbing itself is one small loop. parseExpr takes a min_prec argument: "only fold in operators at least this tight". It parses a left-hand side, then keeps peeking at the next operator; if that operator's precedence is high enough, it consumes it, recursively parses a right-hand side, and folds the two into a binary node -- which becomes the new left-hand side. When it meets an operator too loose (or a non-operator), it stops and hands its subtree back up:

    fn parseExpr(self: *Parser, min_prec: u8) ParseError!*Expr {
        var lhs = try self.parseUnary();
        while (true) {
            const op = self.peek().kind;
            const prec = precedence(op);
            if (prec == 0 or prec < min_prec) break;
            _ = self.advance(); // consume the operator
            const rhs = try self.parseExpr(prec + 1); // left-associative
            const node = try self.makeExpr(.{ .binary = .{ .op = op, .lhs = lhs, .rhs = rhs } });
            lhs = node;
        }
        return lhs;
    }

The single most important line is self.parseExpr(prec + 1). By demanding the right-hand side be built from operators strictly tighter than the current one (prec + 1), we make the operator left-associative: 10 - 3 - 2 parses as (10 - 3) - 2, not 10 - (3 - 2), because when the loop meets the second -, the recursive call for the first -'s right side refused to swallow it. If you wanted a right-associative operator instead -- exponentiation, say, where 2 ^ 3 ^ 2 should be 2 ^ (3 ^ 2) -- you would recurse with prec in stead of prec + 1, and that one-character change is the entire difference. Trace 2 + 3 * 4: parseExpr(1) reads 2, sees + (prec 5), consumes it, and recurses with min_prec = 6; that inner call reads 3, sees * (prec 6), and since 6 is not less than 6 it folds 3 * 4; the inner call returns the star node, which becomes the right child of plus. Fourteen, not twenty. makeExpr, used above, is a one-liner that boxes an expression value onto the arena and hands back the pointer:

    fn makeExpr(self: *Parser, value: Expr) ParseError!*Expr {
        const node = try self.arena.create(Expr);
        node.* = value;
        return node;
    }

Unary operators, literals, calls: the leaves

parseExpr calls parseUnary for each operand, and parseUnary handles the prefix operators - and !. Because a unary operator can stack (- -x, !!flag), it recurses into itself; when there is no prefix operator left, it drops down to parsePrimary, the function that reads the actual leaves. Prefix binds tighter than any binary operator, which is why it lives below the precedence loop, not inside it:

    fn parseUnary(self: *Parser) ParseError!*Expr {
        if (self.check(.minus) or self.check(.bang)) {
            const op = self.advance().kind;
            const rhs = try self.parseUnary();
            return self.makeExpr(.{ .unary = .{ .op = op, .rhs = rhs } });
        }
        return self.parsePrimary();
    }

parsePrimary is where the token stream finally becomes values. It switches on the current token: an int becomes an int node (parsing the text with std.fmt.parseInt, exactly the deferred conversion we promised in the lexer), a float likewise, true/false become boolean nodes, an identifier becomes either a name or -- if a ( follows -- a function call, and a ( on its own opens a parenthesised sub-expression that recurses right back into parseExpr. Anything else is a token that has no business starting an expression, so it is a typed error:

    fn parsePrimary(self: *Parser) ParseError!*Expr {
        const tok = self.peek();
        switch (tok.kind) {
            .int => {
                _ = self.advance();
                const v = std.fmt.parseInt(i64, tok.text, 10) catch return error.UnexpectedToken;
                return self.makeExpr(.{ .int = v });
            },
            .float => {
                _ = self.advance();
                const v = std.fmt.parseFloat(f64, tok.text) catch return error.UnexpectedToken;
                return self.makeExpr(.{ .float = v });
            },
            .kw_true => {
                _ = self.advance();
                return self.makeExpr(.{ .boolean = true });
            },
            .kw_false => {
                _ = self.advance();
                return self.makeExpr(.{ .boolean = false });
            },
            .identifier => {
                _ = self.advance();
                if (self.check(.lparen)) return self.finishCall(tok.text);
                return self.makeExpr(.{ .ident = tok.text });
            },
            .lparen => {
                _ = self.advance();
                const inner = try self.parseExpr(1);
                _ = try self.expect(.rparen);
                return inner;
            },
            else => return error.UnexpectedToken,
        }
    }

The parenthesis case is a small marvel of recursive descent: (2 + 3) * 4 works because the ( branch calls parseExpr(1) -- resetting the precedence floor to the loosest level inside the parens -- parses 2 + 3 in full, then expects the closing ). The sub-expression comes back as a single node, and to the * waiting outside, that whole parenthesised group is just one operand. Grouping, precedence and recursion all cooperate through that one reset.

Function calls are the other branch. When an identifier is immediately followed by (, we peel off the argument list -- zero or more expressions separated by commas -- and each argument is a full expression, so we call parseExpr(1) for every one. The comma handling is where match earns its keep: parse an argument, then if the next token is a comma consume it and loop, otherwise stop:

    fn finishCall(self: *Parser, callee: []const u8) ParseError!*Expr {
        _ = try self.expect(.lparen);
        var args: std.ArrayList(*Expr) = .empty;
        if (!self.check(.rparen)) {
            while (true) {
                const arg = try self.parseExpr(1);
                try args.append(self.arena, arg);
                if (!self.match(.comma)) break;
            }
        }
        _ = try self.expect(.rparen);
        return self.makeExpr(.{ .call = .{ .callee = callee, .args = try args.toOwnedSlice(self.arena) } });
    }

Because each argument recurses through the full expression machinery, fact(n - 1, 2 * k) parses correctly: the first argument is a subtraction subtree, the second a multiplication subtree, both hanging off one call node. Recursion means we get arbitrarily complex arguments for free -- we did not write a single line of special-case code for "an argument that contains an operator".

Statements, blocks, and the top level

Expressions were the hard part; statements are a relief after them. parseStmt peeks at the first token and dispatches to a handler, falling through to "expression followed by a semicolon" for anything that is not a keyword-led statement. Note the labelled block blk: in the else arm -- Zig's way to run a few statements and then yield a value out of a switch prong:

    fn parseStmt(self: *Parser) ParseError!Stmt {
        return switch (self.peek().kind) {
            .kw_let => self.parseLet(),
            .kw_return => self.parseReturn(),
            .kw_if => self.parseIf(),
            .kw_while => self.parseWhile(),
            .lbrace => Stmt{ .block = try self.parseBlock() },
            else => blk: {
                const e = try self.parseExpr(1);
                _ = try self.expect(.semicolon);
                break :blk Stmt{ .expr = e };
            },
        };
    }

Each handler reads almost like the grammar line it implements. parseLet demands the keyword, a name, an =, an expression, and a ;, in that exact order, and every one of those expect calls is both a parse step and a validation -- a missing piece anywhere is an immediate typed error:

    fn parseLet(self: *Parser) ParseError!Stmt {
        _ = try self.expect(.kw_let);
        const name = try self.expect(.identifier);
        _ = try self.expect(.assign);
        const value = try self.parseExpr(1);
        _ = try self.expect(.semicolon);
        return Stmt{ .let = .{ .name = name.text, .value = value } };
    }

    fn parseReturn(self: *Parser) ParseError!Stmt {
        _ = try self.expect(.kw_return);
        const value = try self.parseExpr(1);
        _ = try self.expect(.semicolon);
        return Stmt{ .ret = value };
    }

A block is {, a run of statements, }. It gathers the statements into an ArrayList and hands back an owned slice -- the same collect-then-own pattern as the call arguments. if and while build straight on top of it: parse the keyword, parse a condition expression, parse a block body, and for if, optionally a second block after else:

    fn parseBlock(self: *Parser) ParseError![]const Stmt {
        _ = try self.expect(.lbrace);
        var stmts: std.ArrayList(Stmt) = .empty;
        while (!self.check(.rbrace) and !self.check(.eof)) {
            try stmts.append(self.arena, try self.parseStmt());
        }
        _ = try self.expect(.rbrace);
        return stmts.toOwnedSlice(self.arena);
    }

    fn parseIf(self: *Parser) ParseError!Stmt {
        _ = try self.expect(.kw_if);
        const cond = try self.parseExpr(1);
        const then_body = try self.parseBlock();
        var else_body: ?[]const Stmt = null;
        if (self.match(.kw_else)) {
            else_body = try self.parseBlock();
        }
        return Stmt{ .if_ = .{ .cond = cond, .then_body = then_body, .else_body = else_body } };
    }

    fn parseWhile(self: *Parser) ParseError!Stmt {
        _ = try self.expect(.kw_while);
        const cond = try self.parseExpr(1);
        const body = try self.parseBlock();
        return Stmt{ .while_ = .{ .cond = cond, .body = body } };
    }

The !self.check(.eof) guard in parseBlock is a small but important piece of defensive parsing: if the source has an unclosed {, the loop would otherwise run forever peeking at a } that never comes. By also stopping at eof, we fall through to the expect(.rbrace), which fails cleanly with error.UnexpectedToken in stead of hanging. And the top of the whole grammar, parseProgram, is the simplest function of all -- statements until eof:

    fn parseProgram(self: *Parser) ParseError![]const Stmt {
        var stmts: std.ArrayList(Stmt) = .empty;
        while (!self.check(.eof)) {
            try stmts.append(self.arena, try self.parseStmt());
        }
        return stmts.toOwnedSlice(self.arena);
    }
};

Seeing the tree

A parser you cannot inspect is a parser you cannot trust, so -- exactly as we printed the token stream last episode -- let us print the tree. A tiny recursive walker renders each expression in fully-parenthesised prefix form, so the shape is unambiguous on the page. This is the parser's counterpart to the lexer's token dump, and it is your first debugging tool the moment anything looks wrong:

fn printExpr(e: *const Expr) void {
    switch (e.*) {
        .int => |v| std.debug.print("{d}", .{v}),
        .float => |v| std.debug.print("{d}", .{v}),
        .boolean => |b| std.debug.print("{}", .{b}),
        .ident => |s| std.debug.print("{s}", .{s}),
        .unary => |u| {
            std.debug.print("({s} ", .{@tagName(u.op)});
            printExpr(u.rhs);
            std.debug.print(")", .{});
        },
        .binary => |b| {
            std.debug.print("({s} ", .{@tagName(b.op)});
            printExpr(b.lhs);
            std.debug.print(" ", .{});
            printExpr(b.rhs);
            std.debug.print(")", .{});
        },
        .call => |c| {
            std.debug.print("(call {s}", .{c.callee});
            for (c.args) |arg| {
                std.debug.print(" ", .{});
                printExpr(arg);
            }
            std.debug.print(")", .{});
        },
    }
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const a = arena.allocator();

    const source = "let x = 2 + 3 * 4;";
    const tokens = try tokenize(a, source);
    var parser = Parser{ .tokens = tokens, .arena = a };
    const program = try parser.parseProgram();

    for (program) |stmt| {
        switch (stmt) {
            .let => |l| {
                std.debug.print("let {s} = ", .{l.name});
                printExpr(l.value);
                std.debug.print(";\n", .{});
            },
            else => {},
        }
    }
}

Run that and it prints let x = (plus 2 (star 3 4));. There it is on the page: the multiplication nested inside the addition, the precedence made visible. Change the source to let x = (2 + 3) * 4; and it becomes let x = (star (plus 2 3) 4); -- the parentheses reshaped the tree, and the printer shows it. Also notice the arena: one init, one defer deinit, and every node of every expression in the whole program is freed in that single line. That is the payoff of arena allocation for tree-shaped data.

Proving it, subtree by subtree

As with the lexer, a test is worth more than my say-so. The first one nails down precedence -- that 2 + 3 * 4 really does put the star under the plus:

test "precedence: 2 + 3 * 4 parses as 2 + (3 * 4)" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const tokens = try tokenize(a, "2 + 3 * 4;");
    var p = Parser{ .tokens = tokens, .arena = a };
    const e = try p.parseExpr(1);
    try std.testing.expect(e.* == .binary);
    try std.testing.expectEqual(TokenKind.plus, e.binary.op);
    try std.testing.expect(e.binary.rhs.* == .binary);
    try std.testing.expectEqual(TokenKind.star, e.binary.rhs.binary.op);
}

The next proves left-associativity, the subtle consequence of that prec + 1 recursion -- 10 - 3 - 2 must nest to the left, so the top node's left child is itself a subtraction and its right child is the bare literal 2:

test "left-associativity: 10 - 3 - 2 parses as (10 - 3) - 2" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const tokens = try tokenize(a, "let y = 10 - 3 - 2;");
    var p = Parser{ .tokens = tokens, .arena = a };
    const prog = try p.parseProgram();
    try std.testing.expectEqual(@as(usize, 1), prog.len);
    try std.testing.expect(prog[0] == .let);
    const v = prog[0].let.value;
    try std.testing.expectEqual(TokenKind.minus, v.binary.op);
    try std.testing.expect(v.binary.lhs.* == .binary);
    try std.testing.expect(v.binary.rhs.* == .int);
    try std.testing.expectEqual(@as(i64, 2), v.binary.rhs.int);
}

Then a call, to prove the argument list is parsed and counted, and finally -- the part that separates a toy from a tool -- that malformed input produces a typed error rather than a crash. let z = 1 with no semicolon should fail at the missing ;, and expectError catches exactly that:

test "function call parses its arguments" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const tokens = try tokenize(a, "fact(n - 1, 2);");
    var p = Parser{ .tokens = tokens, .arena = a };
    const e = try p.parseExpr(1);
    try std.testing.expect(e.* == .call);
    try std.testing.expectEqualStrings("fact", e.call.callee);
    try std.testing.expectEqual(@as(usize, 2), e.call.args.len);
}

test "missing semicolon is a typed error, never a crash" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const tokens = try tokenize(a, "let z = 1");
    var p = Parser{ .tokens = tokens, .arena = a };
    try std.testing.expectError(error.UnexpectedToken, p.parseProgram());
}

That last test is the one I care about most. There is no input -- however garbled -- that turns this parser into undefined behaviour. Bad syntax becomes an error value the caller is forced to handle, the same guarantee the lexer gave us, now carried one layer up. Feed it random bytes and the worst that happens is error.UnexpectedToken.

Performance, and where the time actually goes

Recursive descent has a reputation for being slow because it is "just function calls". In practice that reputation is undeserved for a hand-written parser like ours. Every function is small, the recursion depth is bounded by how deeply the source nests (a program with expressions ten parentheses deep recurses ten frames, not a thousand), and modern compilers inline the trivial helpers -- peek, check, advance -- into nothing. The token borrow-slices mean we never copy identifier or string text; the only allocations are the AST nodes themselves, and those come from an arena, which is close to the fastest allocator there is (bump a pointer, hand back the address). Parsing is almost never the bottleneck in a compiler -- lexing touches every byte, and later passes touch every node many times, but parsing touches each token roughly once.

The one performance trap worth naming is pathological recursion depth on adversarial input. A malicious source that is nothing but ten thousand open parentheses would recurse ten thousand frames deep and could overflow the stack. Production parsers that accept untrusted input cap the nesting depth with a counter and return an error past some limit -- a one-line defense that our little language does not need but a real one would want. A part from that, the biggest real speedups come not from cleverness in the parse loop but from not doing work twice: interning identifiers so equal names share one slice, or building the AST into a flat array indexed by integers in stead of pointers (which improves cache locality and shrinks each node) -- a design the Zig compiler itself uses, and a natural thing to reach for once a tree gets large.

How C, Rust, and Go do it

The shape you just wrote is not a teaching simplification -- it is how production language front-ends are actually built. The book Crafting Interpreters builds its expression parser with this exact precedence-climbing loop (it calls the variant "Pratt parsing"), the same peek/advance/match/consume helpers, the same one-function-per-rule statement parser. If our parser feels familiar to anyone who has read that book, it is because we are walking the same well-trodden path.

The reference C implementation of Lua hand-writes its parser in lparser.c as recursive descent, with a subexpr function that takes a precedence limit -- precedence climbing, precisely our min_prec argument, in a language shipping on everything from game engines to routers. In Rust, the compiler's own parser (rustc_parse) is a large hand-written recursive-descent parser, and the popular syn crate parses Rust source for macros the same way; Rust's community leans on recursive descent so heavily that parser-combinator crates like nom are really just recursive descent wearing a functional coat. In Go, the compiler's cmd/compile/internal/syntax parser is hand-written recursive descent tracking source positions on every node, and Go's designers are famously allergic to parser generators -- they hand-write the whole front-end, lexer and parser both, for exactly the reasons we have seen: control over error messages and a codebase you can read.

Zig's own compiler, fittingly, parses with a hand-written recursive-descent parser in lib/std/zig/Parse.zig that builds a flat, index-based AST (the performance idea from the last section, at full scale). So across C, Rust, Go and Zig itself, recursive descent with a precedence-climbing expression parser is not a way to parse -- it is the way the languages you use every day are parsed, and generators are the exception reserved for grammars far larger and stranger than a hobby language. You have written the real thing, minus a few hundred more grammar rules.

Where this is heading

Step back and look at what we have. A flat token stream goes in; a typed tree comes out, with precedence and associativity baked into its shape, function calls and nested blocks and optional else branches all represented, and any malformed input turned into a typed error rather than a crash -- and the whole tree lives in one arena we free in a single line. That tree is the pivot of the entire language. Everything before it thinks in characters and tokens; everything after it thinks in expressions and statements.

But our AST is deliberately bare -- just enough structure to prove the parser works. Before we can do anything with a program, we need to design that tree properly and learn to walk it systematically: to visit every node, transform it, and answer questions about it, in stead of the one ad-hoc printExpr we hacked together for debugging. That is the next brick. After that, a parsed tree still is not a correct program -- let x = 1 + "hello"; parses perfectly and means nothing, and catching that kind of nonsense before we ever run the code is its own stage with its own techniques. Build the parser, dump a few trees over the factorial program from last episode until every parenthesis lands where you expect, and you will have the backbone the rest of this arc hangs off -- because every stage from here on reads the tree we just learned to build. ;-)

Exercises

Modulo and a right-associative power operator. Our precedence table already lists .percent at level 6, but the lexer has no ^ token. Add a caret token kind and lexer case for ^, give it a precedence higher than *, and make it right-associative by recursing with prec in stead of prec + 1 in parseExpr for that one operator. Write a test proving 2 ^ 3 ^ 2 parses as 2 ^ (3 ^ 2) (right-nested) while 2 * 3 * 2 still parses left-nested.
Better error messages. error.UnexpectedToken tells the caller that something went wrong but not what. Add two fields to Parser -- an expected TokenKind and the offending Token -- and have expect fill them in before returning the error. Then write a helper that prints expected ';' but found 'x' at line L, column C, using the line and column the lexer already stamped onto every token. Test it against let z = 1 and assert the reported position points at where the ; should have been.
A parenthesis-balance pre-check that fails fast. Before parsing, scan the token slice once and verify that every (, ), {, } is balanced, returning a typed error with the position of the first unmatched bracket if not. This catches the pathological "ten thousand open parens" case cheaply and gives a far clearer message than a deep parse failure. As a stretch, make it report which bracket is unmatched and where its partner was expected.

Bedankt voor het lezen, en tot de volgende keer! ;-)

@scipio

Leave Learn Zig Series (#132) - Recursive Descent Parsing to:

Written by scipio

Does it matter who's right, or who's left?

Best Posts From scipio

We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

Learn Zig Series (#132) - Recursive Descent Parsing