Learn Zig Series (#146) - Mini Project: Calculator - Lexer/Parser

scipio(71)

Published in

StemSocial

Words

3978

Reading

18 min

Listen

Play

21d

Learn Zig Series (#146) - Mini Project: Calculator - Lexer/Parser

Part of a multi-episode project

What will I learn?

How to start a real mini project -- a working four-function-plus calculator -- by building its front end: the lexer and the parser;
How a lexer (tokenizer) turns a flat string like -2 * (3 + x) into a clean stream of tokens, skipping whitespace and catching illegal characters as it goes;
How to design an AST for arithmetic with a Zig tagged union -- numbers, identifiers, unary negation, binary operators, and function calls;
Precedence climbing (a compact form of Pratt parsing) -- one small function and a binding-power table that gets * binding tighter than +, makes - right-associative for powers, and handles parentheses for free;
How to get left- versus right-associativity exactly right (why 10 - 3 - 2 groups left but 2 ^ 3 ^ 2 groups right), controlled by a single asymmetry in the table;
How to parse function calls and constants like sqrt(2 + 7), max(1, 2, 3) and pi with the same machinery;
How Zig's error unions make a parser that reports precise, typed failures (UnexpectedEof, ExpectedRParen) instead of crashing or guessing;
How an arena allocator turns messy AST-node ownership into a single deinit, and why that is the right tool for a tree you build then throw away.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org) -- the code here is written and tested against Zig 0.16;
The lexer, recursive-descent parser and AST from episodes 131, 132 and 133 fresh in mind -- this mini project is where those three ideas finally earn their keep together;
Tagged unions from episode 6, allocators (and arenas) from episode 7, and slices from episode 5;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#146) - Mini Project: Calculator - Lexer/Parser

For the last handful of episodes we have been deep in the machine room of a compiler -- lexing, recursive-descent parsing, ASTs, a type checker, bytecode, a stack VM, garbage collection, a JIT, code generation, and last time the register allocator that finally made our generated code fast. That was a big arc, and I promised at the end of episode 145 that we would start putting the pieces to work on something you can actually run and play with. Here we go! Over the next few episodes we build a calculator -- and before you roll your eyes, this is not the four-liner every tutorial starts with. It is a proper little language: it will lex, parse, evaluate, and then (later on) compile to bytecode and run on a VM with a debugger. Today is the front end -- the lexer and the parser that turn a raw string like -2 * (3 + x) into a structured tree we can do real work on.

Solutions to Episode 145 Exercises

Register allocation left you three exercises, and all three build directly on that episode's Program, Interval, linearScan, run and evalAst, so paste these alongside episode 145's file.

Exercise 1 -- a naive "spill everything" allocator. The whole point of register allocation is speed, not correctness -- so the fastest way to feel how much work it saves is to write the dumbest allocator imaginable and prove it still computes the right answers. This one uses zero registers and gives every virtual register its own memory slot:

fn spillAll(gpa: std.mem.Allocator, p: *const Program) !Allocation {
    const loc = try gpa.alloc(Location, p.nvregs);
    for (0..p.nvregs) |v| loc[v] = .{ .spill = v };
    return .{ .loc = loc, .num_spills = p.nvregs, .gpa = gpa };
}

Because our run interpreter already dispatches on Location, this needs no other changes -- pass num_regs = 0 and every value lives in memory. The test drives it home: identical results to the AST oracle, but a spill count equal to the entire program where linear scan spills nothing at all.

test "spill-everything is correct but wasteful vs linear scan" {
    const gpa = std.testing.allocator;

    const xv = Expr{ .var_x = {} };
    const a = Expr{ .bin = .{ .op = .mul, .lhs = &xv, .rhs = &xv } };
    const b = Expr{ .bin = .{ .op = .add, .lhs = &xv, .rhs = &a } };
    const c = Expr{ .bin = .{ .op = .sub, .lhs = &b, .rhs = &a } };
    const root = Expr{ .bin = .{ .op = .mul, .lhs = &c, .rhs = &b } };

    var prog = try buildProgram(gpa, &root);
    defer prog.deinit();

    var dumb = try spillAll(gpa, &prog);
    defer dumb.deinit();
    var smart = try linearScan(gpa, &prog, 8);
    defer smart.deinit();

    var x: i64 = -20;
    while (x <= 20) : (x += 1) {
        try std.testing.expectEqual(evalAst(&root, x), try run(gpa, &prog, &dumb, 0, x));
    }
    try std.testing.expect(dumb.num_spills > smart.num_spills);
    try std.testing.expectEqual(@as(usize, 0), smart.num_spills);
}

That gap between dumb.num_spills and zero is exactly the value of the pass we wrote. Correct-but-slow and correct-and-fast are seperated by precisely this.

Exercise 2 -- register coalescing. When the IR contains a move dst <- src, and dst and src never interfere, you can give them the same register and delete the move entirely. The interference-graph view from episode 145 makes this natural: two values can share a home when their live intervals do not overlap. I use a tiny union-find to merge coalescable pairs and count how many moves vanish:

fn overlaps(a: Interval, b: Interval) bool {
    return a.start <= b.end and b.start <= a.end;
}

const MovePair = struct { a: VReg, b: VReg };

fn findRoot(parent: []VReg, v: VReg) VReg {
    var r = v;
    while (parent[r] != r) r = parent[r];
    return r;
}

fn coalesce(gpa: std.mem.Allocator, p: *const Program, moves: []const MovePair) !usize {
    const intervals = try computeIntervals(gpa, p);
    defer gpa.free(intervals);

    const parent = try gpa.alloc(VReg, p.nvregs);
    defer gpa.free(parent);
    for (0..p.nvregs) |v| parent[v] = v;

    var removed: usize = 0;
    for (moves) |m| {
        const ra = findRoot(parent, m.a);
        const rb = findRoot(parent, m.b);
        if (ra == rb) {
            removed += 1; // already share a home
            continue;
        }
        if (!overlaps(intervals[m.a], intervals[m.b])) {
            parent[ra] = rb; // merge into one register
            removed += 1;
        }
    }
    return removed;
}

The subtle part -- and the thing that trips people up -- is that a value's last use and another value's definition at the same instruction still counts as interference under an inclusive-interval test. So a move between two operands of the same add cannot coalesce, but a move between a value that already died and one born later can:

test "coalescing removes a move when its ends do not interfere" {
    const gpa = std.testing.allocator;

    // (x + x) * 5 lowers to: v0=x v1=x v2=v0+v1 v3=5 v4=v2*5
    const xv = Expr{ .var_x = {} };
    const five = Expr{ .num = 5 };
    const sum = Expr{ .bin = .{ .op = .add, .lhs = &xv, .rhs = &xv } };
    const root = Expr{ .bin = .{ .op = .mul, .lhs = &sum, .rhs = &five } };
    var prog = try buildProgram(gpa, &root);
    defer prog.deinit();

    const good = [_]MovePair{.{ .a = 0, .b = 3 }};
    const bad = [_]MovePair{.{ .a = 0, .b = 1 }};
    try std.testing.expectEqual(@as(usize, 1), try coalesce(gpa, &prog, &good));
    try std.testing.expectEqual(@as(usize, 0), try coalesce(gpa, &prog, &bad));
}

Coalescing is one of the biggest real-world wins in production allocators -- every move you delete is an instruction that never executes.

Exercise 3 -- model a hardware constraint. Real chips are not the clean "any value in any register" world we modelled. Remember x86's idiv? It demands its result in a fixed register and clobbers another. So this allocator pins every division result to physical register 0 and treats register 1 as always-clobbered (never handed out). When a division needs register 0 and someone else is sitting there, we evict them to memory:

fn allocConstrained(
    gpa: std.mem.Allocator,
    p: *const Program,
    num_regs: usize,
    pinned: []const bool, // pinned[v] => vreg v must live in register 0
) !Allocation {
    const intervals = try computeIntervals(gpa, p);
    defer gpa.free(intervals);
    std.sort.pdq(Interval, intervals, {}, startLess);

    const loc = try gpa.alloc(Location, p.nvregs);
    errdefer gpa.free(loc);

    // General pool excludes reg 0 (reserved) and reg 1 (clobbered).
    var free = std.ArrayList(usize).empty;
    defer free.deinit(gpa);
    var r: usize = num_regs;
    while (r > 2) {
        r -= 1;
        try free.append(gpa, r);
    }

    var active = std.ArrayList(Interval).empty;
    defer active.deinit(gpa);
    var active_reg = std.ArrayList(usize).empty;
    defer active_reg.deinit(gpa);

    var reg0_holder: ?usize = null; // index into active holding reg 0
    var next_slot: usize = 0;
    var spills: usize = 0;

    for (intervals) |cur| {
        var i: usize = 0;
        while (i < active.items.len) {
            if (active.items[i].end < cur.start) {
                const rr = active_reg.items[i];
                if (rr == 0) reg0_holder = null else try free.append(gpa, rr);
                _ = active.orderedRemove(i);
                _ = active_reg.orderedRemove(i);
                if (reg0_holder) |h| if (h > i) {
                    reg0_holder = h - 1;
                };
            } else i += 1;
        }

        if (pinned[cur.vreg]) {
            if (reg0_holder) |h| { // evict whoever holds reg 0
                loc[active.items[h].vreg] = .{ .spill = next_slot };
                next_slot += 1;
                spills += 1;
                _ = active.orderedRemove(h);
                _ = active_reg.orderedRemove(h);
            }
            loc[cur.vreg] = .{ .reg = 0 };
            try active.append(gpa, cur);
            try active_reg.append(gpa, 0);
            reg0_holder = active.items.len - 1;
        } else if (free.items.len > 0) {
            const rr = free.pop().?;
            loc[cur.vreg] = .{ .reg = rr };
            try active.append(gpa, cur);
            try active_reg.append(gpa, rr);
        } else {
            loc[cur.vreg] = .{ .spill = next_slot };
            next_slot += 1;
            spills += 1;
        }
    }
    return .{ .loc = loc, .num_spills = spills, .gpa = gpa };
}

The differential test confirms two things at once: the pinned result really lands in register 0, and the constrained program still computes exactly what the AST means:

test "constrained allocation still matches the AST" {
    const gpa = std.testing.allocator;

    const xv = Expr{ .var_x = {} };
    const three = Expr{ .num = 3 };
    const one = Expr{ .num = 1 };
    const dv = Expr{ .bin = .{ .op = .div, .lhs = &xv, .rhs = &three } };
    const sub = Expr{ .bin = .{ .op = .sub, .lhs = &xv, .rhs = &one } };
    const root = Expr{ .bin = .{ .op = .add, .lhs = &dv, .rhs = &sub } };

    var prog = try buildProgram(gpa, &root);
    defer prog.deinit();

    const pinned = try gpa.alloc(bool, prog.nvregs);
    defer gpa.free(pinned);
    @memset(pinned, false);
    for (prog.code.items) |ins| switch (ins) {
        .bin => |b| if (b.op == .div) {
            pinned[b.dst] = true;
        },
        else => {},
    };

    var alloc = try allocConstrained(gpa, &prog, 6, pinned);
    defer alloc.deinit();

    for (prog.code.items) |ins| switch (ins) {
        .bin => |b| if (b.op == .div) {
            try std.testing.expectEqual(Location{ .reg = 0 }, alloc.loc[b.dst]);
        },
        else => {},
    };

    var x: i64 = -30;
    while (x <= 30) : (x += 1) {
        if (x == 0) continue;
        try std.testing.expectEqual(evalAst(&root, x), try run(gpa, &prog, &alloc, 6, x));
    }
}

That wrinkle -- pre-colored results and clobbered registers -- is precisely what seperates a textbook allocator from one that can target a real chip. And now, on to something you can play with.

What we are building

The plan for this mini project is a calculator that grows across several episodes. Today: a lexer and a parser that together read a string and hand back an AST. Next time we breathe life into that tree by evaluating it, and after that we take it further still. Keeping the front end (text to tree) strictly seperate from the back end (tree to answer) is not busywork -- it is the architectural decision that lets a language grow. The parser does not care how you evaluate; the evaluator does not care how you parsed. Each side can be tested, rewritten and optimized on its own. That is the same lesson from the markdown tool back in episodes 37 to 39, now applied to something numeric.

Our calculator understands: integer and decimal numbers, the operators + - * / % and ^ (power), parentheses, unary minus (-x), identifiers for constants (pi, e), and function calls with any number of arguments (sqrt(2), max(1, 2, 3)). That is a genuinely useful expression language -- and every piece of it flows through the two stages we write today.

Step one: the tokens

A token is the smallest meaningful chunk of the input -- a number, an operator, a parenthesis, a name. The lexer's entire job is to walk the raw bytes and emit these, throwing away whitespace and rejecting anything nonsensical. We start by naming every kind of token in an enum, and giving the token itself a little payload:

const std = @import("std");

const TokenKind = enum {
    number, plus, minus, star, slash, percent, caret,
    lparen, rparen, comma, ident, eof,
};

const Token = struct {
    kind: TokenKind,
    text: []const u8,
    value: f64 = 0,
    pos: usize,
};

Two design decisions worth calling out. First, text is a slice into the original source, not a copy -- the lexer allocates nothing per token for the spelling, it just remembers where each token starts and ends. That is a very Zig way to think: no hidden allocation, and the caller keeps the source string alive. Second, I carry an explicit .eof token rather than signalling end-of-input with a null or an error. A real end-of-file token makes the parser dramatically simpler -- it can always peek() at something, and "did we reach the end?" becomes an ordinary kind == .eof check instead of a special case.

Step two: the lexer

The lexer is a tiny state machine over a cursor pos. Each call to next skips whitespace, looks at the current byte, and decides what to do: digits (or a leading dot) start a number, a letter starts an identifier, and everything else is a single-character operator or an error. Having said that, let us look at the core:

const LexError = error{ UnexpectedChar, BadNumber } || std.mem.Allocator.Error;

const Lexer = struct {
    src: []const u8,
    pos: usize = 0,

    fn isSpace(c: u8) bool {
        return c == ' ' or c == '\t' or c == '\r' or c == '\n';
    }
    fn isDigit(c: u8) bool {
        return c >= '0' and c <= '9';
    }
    fn isIdentStart(c: u8) bool {
        return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or c == '_';
    }
    fn isIdentPart(c: u8) bool {
        return isIdentStart(c) or isDigit(c);
    }

    fn next(self: *Lexer) LexError!Token {
        while (self.pos < self.src.len and isSpace(self.src[self.pos])) self.pos += 1;
        if (self.pos >= self.src.len) return .{ .kind = .eof, .text = "", .pos = self.pos };

        const start = self.pos;
        const c = self.src[self.pos];

        if (isDigit(c) or c == '.') return self.lexNumber();
        if (isIdentStart(c)) return self.lexIdent();

        self.pos += 1;
        const kind: TokenKind = switch (c) {
            '+' => .plus,
            '-' => .minus,
            '*' => .star,
            '/' => .slash,
            '%' => .percent,
            '^' => .caret,
            '(' => .lparen,
            ')' => .rparen,
            ',' => .comma,
            else => return error.UnexpectedChar,
        };
        return .{ .kind = kind, .text = self.src[start..self.pos], .pos = start };
    }

Notice the else => return error.UnexpectedChar arm. An unknown byte is not a token, and it is not the parser's problem either -- it is caught the moment it is seen, with a pos we could point at in a nice error message. This is Zig's error-union philosophy in miniature: the only way to get a Token out of next is to have a real one, because failure is a distinct, typed value the caller cannot ignore.

Numbers and identifiers each scan a run of characters. The number scanner allows a single decimal point and then leans on the standard library to parse the actual value -- no hand-rolled float arithmetic, and a malformed number becomes a typed BadNumber error:

    fn lexNumber(self: *Lexer) LexError!Token {
        const start = self.pos;
        var seen_dot = false;
        while (self.pos < self.src.len) {
            const c = self.src[self.pos];
            if (isDigit(c)) {
                self.pos += 1;
            } else if (c == '.' and !seen_dot) {
                seen_dot = true;
                self.pos += 1;
            } else break;
        }
        const text = self.src[start..self.pos];
        const value = std.fmt.parseFloat(f64, text) catch return error.BadNumber;
        return .{ .kind = .number, .text = text, .value = value, .pos = start };
    }

    fn lexIdent(self: *Lexer) LexError!Token {
        const start = self.pos;
        while (self.pos < self.src.len and isIdentPart(self.src[self.pos])) self.pos += 1;
        return .{ .kind = .ident, .text = self.src[start..self.pos], .pos = start };
    }
};

For convenience (and for testing the lexer in isolation) we can also drain the whole input into a slice of tokens, ending with the .eof sentinel:

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

The errdefer there is the ownership discipline we have practised all series: if an append fails mid-stream, the partial list is freed and nothing leaks. And a quick test pins the behaviour down -- the right kinds, the parsed value, the identifier text, and a clean rejection of garbage:

test "lexer produces the right token stream" {
    const gpa = std.testing.allocator;
    const toks = try tokenize(gpa, "3.14 + x * (2)");
    defer gpa.free(toks);
    const kinds = [_]TokenKind{ .number, .plus, .ident, .star, .lparen, .number, .rparen, .eof };
    try std.testing.expectEqual(kinds.len, toks.len);
    for (kinds, 0..) |k, i| try std.testing.expectEqual(k, toks[i].kind);
    try std.testing.expectEqual(@as(f64, 3.14), toks[0].value);
    try std.testing.expectEqualStrings("x", toks[2].text);
}

test "lexer rejects an unknown character" {
    const gpa = std.testing.allocator;
    try std.testing.expectError(error.UnexpectedChar, tokenize(gpa, "1 @ 2"));
}

Step three: the AST

With tokens in hand, we need a shape to parse into. An arithmetic expression is naturally a tree, and Zig's tagged union is the perfect tool -- it says, exhaustively, "an expression is exactly one of these five things":

const BinOp = enum { add, sub, mul, div, mod, pow };

fn opName(op: BinOp) []const u8 {
    return switch (op) {
        .add => "+", .sub => "-", .mul => "*",
        .div => "/", .mod => "%", .pow => "^",
    };
}

const Expr = union(enum) {
    number: f64,
    ident: []const u8,
    unary: struct { op: enum { neg }, operand: *Expr },
    binary: struct { op: BinOp, lhs: *Expr, rhs: *Expr },
    call: struct { name: []const u8, args: []*Expr },
};

Because it is a union(enum), every part of the calculator that walks a tree -- the evaluator we write next time, the printer we write in a minute -- must handle all five cases or the compiler complains. That exhaustiveness is not bureaucracy; it is the reason adding a new node type later is safe: the compiler shows you every place that needs updating. The child pointers (*Expr) are where the tree branches, and managing their memory is the one genuinely fiddly part -- which is exactly where an arena earns its place, as we will see.

Step four: precedence, the heart of it

Here is the problem every expression parser must solve: given 1 + 2 * 3, how do we know it means 1 + (2 * 3) and not (1 + 2) * 3? The answer is precedence -- * binds tighter than + -- and the elegant way to encode it is a technique called precedence climbing (the compact cousin of Pratt parsing). Every infix operator gets a pair of binding powers, a left and a right, and the whole parser is one small recursive function driven by that table:

const Bp = struct { left: u8, right: u8 };

fn infixBp(k: TokenKind) ?Bp {
    return switch (k) {
        .plus, .minus => .{ .left = 1, .right = 2 },
        .star, .slash, .percent => .{ .left = 3, .right = 4 },
        .caret => .{ .left = 7, .right = 6 }, // right-associative: left > right
        else => null,
    };
}

fn binOpOf(k: TokenKind) BinOp {
    return switch (k) {
        .plus => .add, .minus => .sub, .star => .mul,
        .slash => .div, .percent => .mod, .caret => .pow,
        else => unreachable,
    };
}

Look closely at the asymmetry, because it is doing something clever. For + the pair is (1, 2) -- left lower than right -- and that makes it left-associative. For ^ the pair is (7, 6) -- left higher than right -- and that flips it to right-associative. One number, and 10 - 3 - 2 groups as (10 - 3) - 2 while 2 ^ 3 ^ 2 groups as 2 ^ (3 ^ 2), exactly as mathematicians expect. I find that genuinely beautiful: associativity, which sounds like a deep property, is a single inequality in a lookup table.

Step five: the parser

Now the engine. parseExpr(min_bp) parses an expression whose operators all bind at least as tightly as min_bp. It grabs a prefix (a number, a parenthesised group, a unary minus), then loops: while the next operator's left binding power is high enough, it consumes that operator and recursively parses the right side at the operator's right binding power. That single recursion, with the right binding power passed down, is what produces correct trees:

const ParseError = error{
    UnexpectedToken,
    UnexpectedEof,
    ExpectedRParen,
} || LexError;

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

    fn peek(self: *Parser) Token {
        return self.toks[self.pos];
    }
    fn advance(self: *Parser) Token {
        const t = self.toks[self.pos];
        if (self.pos + 1 < self.toks.len) self.pos += 1;
        return t;
    }
    fn make(self: *Parser, e: Expr) ParseError!*Expr {
        const p = try self.arena.create(Expr);
        p.* = e;
        return p;
    }

    fn parseExpr(self: *Parser, min_bp: u8) ParseError!*Expr {
        var lhs = try self.parsePrefix();
        while (true) {
            const t = self.peek();
            const bp = infixBp(t.kind) orelse break;
            if (bp.left < min_bp) break;
            _ = self.advance();
            const rhs = try self.parseExpr(bp.right);
            lhs = try self.make(.{ .binary = .{ .op = binOpOf(t.kind), .lhs = lhs, .rhs = rhs } });
        }
        return lhs;
    }

The prefix parser handles everything that can start an expression. A number becomes a leaf. A ( opens a fresh parseExpr(0) -- precedence resets inside parentheses, which is the whole reason they work -- and demands a matching ). A leading - becomes a unary negation, parsing its operand at a binding power (6) chosen so that -2 ^ 2 correctly means -(2 ^ 2). And an identifier is either a bare constant or, if a ( follows, a function call whose arguments are comma-separated expressions:

    fn parsePrefix(self: *Parser) ParseError!*Expr {
        const t = self.advance();
        switch (t.kind) {
            .number => return self.make(.{ .number = t.value }),
            .ident => {
                if (self.peek().kind == .lparen) {
                    _ = self.advance(); // consume '('
                    var args = std.ArrayList(*Expr).empty;
                    if (self.peek().kind != .rparen) {
                        while (true) {
                            const a = try self.parseExpr(0);
                            try args.append(self.arena, a);
                            if (self.peek().kind == .comma) {
                                _ = self.advance();
                                continue;
                            }
                            break;
                        }
                    }
                    if (self.peek().kind != .rparen) return error.ExpectedRParen;
                    _ = self.advance(); // consume ')'
                    const slice = try args.toOwnedSlice(self.arena);
                    return self.make(.{ .call = .{ .name = t.text, .args = slice } });
                }
                return self.make(.{ .ident = t.text });
            },
            .minus => {
                const operand = try self.parseExpr(6);
                return self.make(.{ .unary = .{ .op = .neg, .operand = operand } });
            },
            .plus => return self.parseExpr(6),
            .lparen => {
                const e = try self.parseExpr(0);
                if (self.peek().kind != .rparen) return error.ExpectedRParen;
                _ = self.advance();
                return e;
            },
            .eof => return error.UnexpectedEof,
            else => return error.UnexpectedToken,
        }
    }
};

The top-level entry point ties it together: tokenize, parse one expression at binding power zero, and insist that nothing is left over except .eof -- so 1 2 is a clean error, not a silently-ignored 2:

fn parse(arena: std.mem.Allocator, src: []const u8) ParseError!*Expr {
    const toks = try tokenize(arena, src);
    var p = Parser{ .toks = toks, .arena = arena };
    const e = try p.parseExpr(0);
    if (p.peek().kind != .eof) return error.UnexpectedToken;
    return e;
}

Notice parse takes an arena allocator. Every Expr node, and the args slices, and the token buffer, all come from that one arena. The caller creates an arena, parses into it, uses the tree, and calls arena.deinit() once -- and every node, no matter how deep the tree, is freed in a single stroke. This is the textbook use case for an arena (episode 7): a batch of allocations with a common, well-defined lifetime. We could hand-write a recursive freeExpr that walks the tree freeing children, but why? The tree lives exactly as long as the arena, and there is no shorter-lived subset we ever need to free early. Arenas turn a whole category of use-after-free and double-free bugs into a non-issue.

Step six: proving the tree is right

An AST is invisible -- so to see what we parsed (and to test it), I render each tree as a Lisp-style S-expression: 1 + 2 * 3 becomes (+ 1 (* 2 3)). The structure of the parentheses is the structure of the tree, which makes it a perfect, unambiguous thing to assert against:

fn sexpr(arena: std.mem.Allocator, e: *const Expr) ![]const u8 {
    return switch (e.*) {
        .number => |v| std.fmt.allocPrint(arena, "{d}", .{v}),
        .ident => |name| std.fmt.allocPrint(arena, "{s}", .{name}),
        .unary => |u| blk: {
            const inner = try sexpr(arena, u.operand);
            break :blk std.fmt.allocPrint(arena, "(neg {s})", .{inner});
        },
        .binary => |b| blk: {
            const l = try sexpr(arena, b.lhs);
            const r = try sexpr(arena, b.rhs);
            break :blk std.fmt.allocPrint(arena, "({s} {s} {s})", .{ opName(b.op), l, r });
        },
        .call => |c| blk: {
            var buf = std.ArrayList(u8).empty;
            try buf.appendSlice(arena, "(call ");
            try buf.appendSlice(arena, c.name);
            for (c.args) |a| {
                try buf.append(arena, ' ');
                const s = try sexpr(arena, a);
                try buf.appendSlice(arena, s);
            }
            try buf.append(arena, ')');
            break :blk try buf.toOwnedSlice(arena);
        },
    };
}

And here is where it all pays off. This helper parses a string and returns its S-expression, then the tests assert precedence, associativity, unary minus, parentheses, function calls and errors -- one readable line per property:

fn parseToSexpr(gpa: std.mem.Allocator, src: []const u8) ![]const u8 {
    var arena = std.heap.ArenaAllocator.init(gpa);
    defer arena.deinit();
    const a = arena.allocator();
    const tree = try parse(a, src);
    const s = try sexpr(a, tree);
    return gpa.dupe(u8, s); // copy out of the arena so the caller owns it
}

test "precedence, associativity, unary minus, parens" {
    const gpa = std.testing.allocator;
    const cases = [_]struct { in: []const u8, out: []const u8 }{
        .{ .in = "1 + 2 * 3", .out = "(+ 1 (* 2 3))" },
        .{ .in = "10 - 3 - 2", .out = "(- (- 10 3) 2)" },
        .{ .in = "2 ^ 3 ^ 2", .out = "(^ 2 (^ 3 2))" },
        .{ .in = "-2 ^ 2", .out = "(neg (^ 2 2))" },
        .{ .in = "(1 + 2) * 3", .out = "(* (+ 1 2) 3)" },
    };
    for (cases) |c| {
        const got = try parseToSexpr(gpa, c.in);
        defer gpa.free(got);
        try std.testing.expectEqualStrings(c.out, got);
    }
}

test "function calls and constants" {
    const gpa = std.testing.allocator;
    const s1 = try parseToSexpr(gpa, "sqrt(2 + 7)");
    defer gpa.free(s1);
    try std.testing.expectEqualStrings("(call sqrt (+ 2 7))", s1);
    const s2 = try parseToSexpr(gpa, "max(1, 2, 3)");
    defer gpa.free(s2);
    try std.testing.expectEqualStrings("(call max 1 2 3)", s2);
}

test "parser reports precise, typed errors" {
    const gpa = std.testing.allocator;
    var arena = std.heap.ArenaAllocator.init(gpa);
    defer arena.deinit();
    const a = arena.allocator();
    try std.testing.expectError(error.UnexpectedEof, parse(a, "1 +"));
    try std.testing.expectError(error.ExpectedRParen, parse(a, "(1 + 2"));
    try std.testing.expectError(error.UnexpectedToken, parse(a, "1 2"));
}

Look at that last test especially. A parser that crashes on bad input is useless; a parser that returns a wrong-but-plausible tree is worse. Ours returns a specific, typed error for each kind of mistake, and the catch-free call sites (try) mean we physically cannot forget to handle them. That is the Zig bargain paying off: errors are values, the type system tracks them, and "did this fail?" is never a guess.

How this compares elsewhere

If you have written a calculator in C, you know the pain points our version quietly avoids. In C you would hand-manage the AST nodes with malloc/free (or reach for a garbage collector), you would signal lex errors with sentinel return values or a global errno-style variable that is easy to ignore, and a tagged union would be a struct with an enum tag plus a bare union that the compiler does not force you to destructure correctly -- read the wrong arm and you get undefined behaviour, not a compile error. Our Zig union(enum) makes that mistake impossible, and the arena makes the memory management a one-liner.

Rust would give you much of the same safety -- enum for the AST, Result for errors, an arena crate if you want one -- and the borrow checker where Zig gives you explicit allocators. Go would lean on its garbage collector for the tree and on multiple return values (value, err) for errors, which is ergonomic but pays a runtime GC cost we never incur. The precedence-climbing algorithm itself is identical in every language -- it is a beautiful, language-agnostic idea -- but Zig lets us express it with no hidden control flow, no hidden allocation, and exhaustiveness the compiler actually enforces. For a front end, where correctness is everything, that combination is hard to beat.

That is the calculator's front end, done and tested: a lexer that turns text into tokens, an AST that captures the shape of an expression, and a precedence-climbing parser that gets * over +, right-associative powers, unary minus, parentheses and function calls all correct -- with typed errors and single-deinit memory. Right now we can read an expression and print its tree, but we cannot yet get an answer out of it. That is the obvious next step: walking this tree and actually computing what it means, constants and functions included. We have the whole compiler toolbox behind us and a clean tree in front of us -- next time we make it compute. Thanks for reading, and happy hacking! ;-)

@scipio