↓ Skip to main content
  1. Books/
  2. From Interpreter To Compiler In Zig/
Chapter 2

Parsing

13 mins
On this page
Table of Contents

The parser takes tokens from the lexer and builds an Abstract Syntax Tree (AST). We use a Pratt parser (top-down operator precedence), which handles prefix and infix expressions with different precedence levels.

This chapter builds the parser across three files: ast.zig for AST node types, parser.zig for the Pratt parser itself, and parser_test.zig for tests.

AST (ast.zig)
#

Complete ast.zig
# 

const std = @import("std");

// Expression types.

pub const Identifier = struct { value: []const u8 };
pub const IntegerLiteral = struct { value: i64 };
pub const Boolean = struct { value: bool };
pub const StringLiteral = struct { value: []const u8 };
pub const ArrayLiteral = struct { elements: []const Expression };
pub const HashLiteral = struct { pairs: []const HashPair };

pub const IfExpression = struct {
    condition: *const Expression,
    consequence: BlockStatement,
    alternative: ?BlockStatement,
};

pub const InfixExpression = struct {
    left: *const Expression,
    operator: []const u8,
    right: *const Expression,
};

pub const PrefixExpression = struct {
    operator: []const u8,
    right: *const Expression,
};

pub const FunctionLiteral = struct {
    parameters: []const Identifier,
    body: BlockStatement,
};

pub const CallExpression = struct {
    function: *const Expression, // Identifier or Function Literal.
    arguments: []const Expression,
};


pub const IndexExpression = struct {
    left: *const Expression,
    index: *const Expression,
};

pub const HashPair = struct {
    key: Expression,
    value: Expression,
};


/// Every expression in Monkey Language is one of these variants.
pub const Expression = union(enum) {
    identifier: Identifier,
    integer_literal: IntegerLiteral,
    boolean: Boolean,
    string_literal: StringLiteral,
    prefix: PrefixExpression,
    infix: InfixExpression,
    if_expression: IfExpression,
    function_literal: FunctionLiteral,
    call: CallExpression,
    array_literal: ArrayLiteral,
    index_expression: IndexExpression,
    hash_literal: HashLiteral,

    /// Writes a human-readable string representation of the expression.
    /// Used for debugging and for testing operator precedence.
    pub fn writeTo(self: Expression, writer: anytype) !void {
        switch (self) {
            .identifier => |id| try writer.writeAll(id.value),
            .integer_literal => |il| try writer.print("{d}", .{il.value}),
            .boolean => |b| try writer.writeAll(if (b.value) "true" else "false"),
            .string_literal => |s| try writer.writeAll(s.value),
            .prefix => |p| {
                try writer.writeAll("(");
                try writer.writeAll(p.operator);
                try p.right.writeTo(writer);
                try writer.writeAll(")");
            },
            .infix => |i| {
                try writer.writeAll("(");
                try i.left.writeTo(writer);
                try writer.writeAll(" ");
                try writer.writeAll(i.operator);
                try writer.writeAll(" ");
                try i.right.writeTo(writer);
                try writer.writeAll(")");
            },
            .if_expression => |ie| {
                try writer.writeAll("if ");
                try ie.condition.writeTo(writer);
                try writer.writeAll(" { ... }");
                if (ie.alternative != null) {
                    try writer.writeAll(" else { ... }");
                }
            },
            .function_literal => |fl| {
                try writer.writeAll("fn(");
                for (fl.parameters, 0..) |param, idx| {
                    if (idx > 0) try writer.writeAll(", ");
                    try writer.writeAll(param.value);
                }
                try writer.writeAll(") { ... }");
            },
            .call => |c| {
                try c.function.writeTo(writer);
                try writer.writeAll("(");
                for (c.arguments, 0..) |arg, idx| {
                    if (idx > 0) try writer.writeAll(", ");
                    try arg.writeTo(writer);
                }
                try writer.writeAll(")");
            },
            .array_literal => |a| {
                try writer.writeAll("[");
                for (a.elements, 0..) |elem, idx| {
                    if (idx > 0) try writer.writeAll(", ");
                    try elem.writeTo(writer);
                }
                try writer.writeAll("]");
            },
            .index_expression => |ie| {
                try writer.writeAll("(");
                try ie.left.writeTo(writer);
                try writer.writeAll("[");
                try ie.index.writeTo(writer);
                try writer.writeAll("])");
            },
            .hash_literal => |h| {
                try writer.writeAll("{");
                for (h.pairs, 0..) |pair, idx| {
                    if (idx > 0) try writer.writeAll(", ");
                    try pair.key.writeTo(writer);
                    try writer.writeAll(": ");
                    try pair.value.writeTo(writer);
                }
                try writer.writeAll("}");
            },
        }
    }

    /// Returns a heap-allocated string representation.
    pub fn string(self: Expression, allocator: std.mem.Allocator) ![]const u8 {
        var buf: std.ArrayList(u8) = .empty;
        try self.writeTo(buf.writer(allocator));
        return buf.toOwnedSlice(allocator);
    }
};

// Statement types.

pub const ReturnStatement = struct { value: Expression };
pub const ExpressionStatement = struct { expression: Expression };
pub const BlockStatement = struct { statements: []const Statement };

pub const Statement = union(enum) {
    let_statement: LetStatement,
    return_statement: ReturnStatement,
    expression_statement: ExpressionStatement,
};

pub const LetStatement = struct {
    name: []const u8,
    value: Expression,
};

// Program (root node).

pub const Program = struct { statements: []const Statement };

Parser (parser.zig)
#

Precedence levels
#

To set precedence we use an enum backed by u8 where the integer value determines the precedence:

const Precedence = enum(u8) {
    lowest = 1,
    equals = 2,        // ==
    less_greater = 3,  // > or <
    sum = 4,           // +
    product = 5,       // *
    prefix = 6,        // -X or !X
    call = 7,          // myFunction(X)
    index = 8,         // array[index]
};

fn getPrecedence(token_type: token.TokenType) Precedence {
    return switch (token_type) {
        .eq, .not_eq => .equals,
        .lt, .gt => .less_greater,
        .plus, .minus => .sum,
        .slash, .asterisk => .product,
        .lparen => .call,
        .lbracket => .index,
        else => .lowest,
    };
}

Parser struct
#

Complete parser.zig
# 

const std = @import("std");
const token = @import("token.zig");
const ast = @import("ast.zig");
const Lexer = @import("lexer.zig").Lexer;

const Precedence = enum(u8) {
    lowest = 1,
    equals = 2,
    less_greater = 3,
    sum = 4,
    product = 5,
    prefix = 6,
    call = 7,
    index = 8,
};

fn getPrecedence(token_type: token.TokenType) Precedence {
    return switch (token_type) {
        .eq, .not_eq => .equals,
        .lt, .gt => .less_greater,
        .plus, .minus => .sum,
        .slash, .asterisk => .product,
        .lparen => .call,
        .lbracket => .index,
        else => .lowest,
    };
}

pub const Parser = struct {
    // Explicit error set needed because parse methods are recursive.
    // Zig cannot infer error sets across recursive call cycles.
    const Error = std.mem.Allocator.Error || error{ParseError};

    lexer: *Lexer,
    cur_token: token.Token,
    peek_token: token.Token,
    errors: std.ArrayList([]const u8),
    allocator: std.mem.Allocator,

    pub fn init(allocator: std.mem.Allocator, lexer: *Lexer) Parser {
        var p = Parser{
            .lexer = lexer,
            .cur_token = undefined,
            .peek_token = undefined,
            .errors = .empty,
            .allocator = allocator,
        };
        // Read two tokens to fill cur_token and peek_token
        p.nextToken();
        p.nextToken();
        return p;
    }

    fn nextToken(self: *Parser) void {
        self.cur_token = self.peek_token;
        self.peek_token = self.lexer.nextToken();
    }

    fn curPrecedence(self: *Parser) Precedence {
        return getPrecedence(self.cur_token.type);
    }

    fn peekPrecedence(self: *Parser) Precedence {
        return getPrecedence(self.peek_token.type);
    }

    /// Advances if peek_token matches the expected type. Returns false and records an error if not.
    fn expectPeek(self: *Parser, t: token.TokenType) Error!bool {
        if (self.peek_token.type == t) {
            self.nextToken();
            return true;
        }
        try self.peekError(t);
        return false;
    }

    fn peekError(self: *Parser, t: token.TokenType) Error!void {
        const msg = try std.fmt.allocPrint(
            self.allocator,
            "expected next token to be {}, got {} instead",
            .{ t, self.peek_token.type },
        );
        try self.errors.append(self.allocator, msg);
    }

    // Public API.

    /// Parses the entire program and returns the AST root.
    pub fn parseProgram(self: *Parser) Error!ast.Program {
        var statements: std.ArrayList(ast.Statement) = .empty;

        while (self.cur_token.type != .eof) {
            if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
            self.nextToken();
        }

        return .{ .statements = try statements.toOwnedSlice(self.allocator) };
    }

    // Statement parsing.

    fn parseStatement(self: *Parser) Error!?ast.Statement {
        return switch (self.cur_token.type) {
            .let_ => try self.parseLetStatement(),
            .return_ => try self.parseReturnStatement(),
            else => try self.parseExpressionStatement(),
        };
    }

    fn parseLetStatement(self: *Parser) Error!?ast.Statement {
        if (!try self.expectPeek(.ident)) return null;
        const name = self.cur_token.literal;

        if (!try self.expectPeek(.assign)) return null;
        self.nextToken();

        const value = try self.parseExpression(.lowest) orelse return null;

        if (self.peek_token.type == .semicolon) self.nextToken();

        return .{ .let_statement = .{ .name = name, .value = value } };
    }

    fn parseReturnStatement(self: *Parser) Error!ast.Statement {
        self.nextToken();

        const value = try self.parseExpression(.lowest) orelse
            return .{ .return_statement = .{ .value = .{ .integer_literal = .{ .value = 0 } } } };

        if (self.peek_token.type == .semicolon) self.nextToken();

        return .{ .return_statement = .{ .value = value } };
    }

    fn parseExpressionStatement(self: *Parser) Error!?ast.Statement {
        const expr = try self.parseExpression(.lowest) orelse return null;

        if (self.peek_token.type == .semicolon) self.nextToken();

        return .{ .expression_statement = .{ .expression = expr } };
    }

    fn parseBlockStatement(self: *Parser) Error!ast.BlockStatement {
        self.nextToken(); // skip the {

        var statements: std.ArrayList(ast.Statement) = .empty;

        while (self.cur_token.type != .rbrace and self.cur_token.type != .eof) {
            if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
            self.nextToken();
        }

        return .{ .statements = try statements.toOwnedSlice(self.allocator) };
    }

    // Expression parsing.

    /// The heart of the Pratt parser, there's a lot going on here.
    ///
    /// 1. Dispatch to a prefix parse function based on `cur_token`.
    /// 2. While `peek_token`` has higher precedence, dispatch to infix parse function.
    /// 3. Return the resulting expression.
    fn parseExpression(self: *Parser, precedence: Precedence) Error!?ast.Expression {

        // Step 1: Prefix dispatch.
        var left: ast.Expression = switch (self.cur_token.type) {
            .ident => .{ .identifier = .{ .value = self.cur_token.literal } },
            .int => blk: {
                const value = std.fmt.parseInt(i64, self.cur_token.literal, 10) catch {
                    try self.errors.append(self.allocator,
                        try std.fmt.allocPrint(self.allocator, "could not parse '{s}' as integer", .{self.cur_token.literal}),
                    );
                    return null;
                };
                break :blk .{ .integer_literal = .{ .value = value } };
            },
            .string => .{ .string_literal = .{ .value = self.cur_token.literal } },
            .true_ => .{ .boolean = .{ .value = true } },
            .false_ => .{ .boolean = .{ .value = false } },
            .bang, .minus => try self.parsePrefixExpression(),
            .lparen => try self.parseGroupedExpression() orelse return null,
            .if_ => try self.parseIfExpression(),
            .function => try self.parseFunctionLiteral(),
            .lbracket => try self.parseArrayLiteral(),
            .lbrace => try self.parseHashLiteral(),
            else => {
                try self.errors.append(self.allocator,
                    try std.fmt.allocPrint(self.allocator, "no prefix parse function for {}", .{self.cur_token.type}),
                );
                return null;
            },
        };

        // Step 2: Infix loop.
        while (self.peek_token.type != .semicolon and
            @intFromEnum(precedence) < @intFromEnum(self.peekPrecedence()))
        {
            switch (self.peek_token.type) {
                .plus, .minus, .slash, .asterisk, .eq, .not_eq, .lt, .gt => {
                    self.nextToken();
                    left = try self.parseInfixExpression(left);
                },
                .lparen => {
                    self.nextToken();
                    left = try self.parseCallExpression(left);
                },
                .lbracket => {
                    self.nextToken();
                    left = try self.parseIndexExpression(left);
                },
                else => return left,
            }
        }

        return left;
    }

    fn parsePrefixExpression(self: *Parser) Error!ast.Expression {
        const operator = self.cur_token.literal;
        self.nextToken();

        const right = try self.parseExpression(.prefix) orelse
            return error.ParseError;

        const right_ptr = try self.allocator.create(ast.Expression);
        right_ptr.* = right;
        return .{ .prefix = .{ .operator = operator, .right = right_ptr } };
    }

    fn parseInfixExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
        const operator = self.cur_token.literal;
        const prec = self.curPrecedence();
        self.nextToken();

        const right = try self.parseExpression(prec) orelse
            return error.ParseError;

        const left_ptr = try self.allocator.create(ast.Expression);
        left_ptr.* = left;
        const right_ptr = try self.allocator.create(ast.Expression);
        right_ptr.* = right;

        return .{ .infix = .{
            .left = left_ptr,
            .operator = operator,
            .right = right_ptr,
        } };
    }

    fn parseGroupedExpression(self: *Parser) Error!?ast.Expression {
        self.nextToken();
        const expr = try self.parseExpression(.lowest);
        if (!try self.expectPeek(.rparen)) return null;
        return expr;
    }

    fn parseIfExpression(self: *Parser) Error!ast.Expression {
        if (!try self.expectPeek(.lparen)) return error.ParseError;
        self.nextToken();

        const condition = try self.parseExpression(.lowest) orelse return error.ParseError;
        const condition_ptr = try self.allocator.create(ast.Expression);
        condition_ptr.* = condition;

        if (!try self.expectPeek(.rparen)) return error.ParseError;
        if (!try self.expectPeek(.lbrace)) return error.ParseError;

        const consequence = try self.parseBlockStatement();

        var alternative: ?ast.BlockStatement = null;
        if (self.peek_token.type == .else_) {
            self.nextToken();
            if (!try self.expectPeek(.lbrace)) return error.ParseError;
            alternative = try self.parseBlockStatement();
        }

        return .{ .if_expression = .{
            .condition = condition_ptr,
            .consequence = consequence,
            .alternative = alternative,
        } };
    }

    fn parseFunctionLiteral(self: *Parser) Error!ast.Expression {
        if (!try self.expectPeek(.lparen)) return error.ParseError;

        const parameters = try self.parseFunctionParameters();

        if (!try self.expectPeek(.lbrace)) return error.ParseError;

        const body = try self.parseBlockStatement();

        return .{ .function_literal = .{
            .parameters = parameters,
            .body = body,
        } };
    }

    fn parseFunctionParameters(self: *Parser) Error![]const ast.Identifier {
        var params: std.ArrayList(ast.Identifier) = .empty;

        if (self.peek_token.type == .rparen) {
            self.nextToken();
            return params.toOwnedSlice(self.allocator);
        }

        self.nextToken();
        try params.append(self.allocator, .{ .value = self.cur_token.literal });

        while (self.peek_token.type == .comma) {
            self.nextToken(); // skip comma
            self.nextToken(); // move to param
            try params.append(self.allocator, .{ .value = self.cur_token.literal });
        }

        if (!try self.expectPeek(.rparen)) return error.ParseError;

        return params.toOwnedSlice(self.allocator);
    }

    fn parseCallExpression(self: *Parser, function: ast.Expression) Error!ast.Expression {
        const func_ptr = try self.allocator.create(ast.Expression);
        func_ptr.* = function;
        const arguments = try self.parseExpressionList(.rparen);
        return .{ .call = .{
            .function = func_ptr,
            .arguments = arguments,
        } };
    }

    fn parseArrayLiteral(self: *Parser) Error!ast.Expression {
        const elements = try self.parseExpressionList(.rbracket);
        return .{ .array_literal = .{ .elements = elements } };
    }

    fn parseExpressionList(self: *Parser, end: token.TokenType) Error![]const ast.Expression {
        var list: std.ArrayList(ast.Expression) = .empty;

        if (self.peek_token.type == end) {
            self.nextToken();
            return list.toOwnedSlice(self.allocator);
        }

        self.nextToken();
        try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);

        while (self.peek_token.type == .comma) {
            self.nextToken(); // skip comma
            self.nextToken(); // move to expression
            try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);
        }

        if (!try self.expectPeek(end)) return error.ParseError;

        return list.toOwnedSlice(self.allocator);
    }

    fn parseIndexExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
        self.nextToken();
        const index = try self.parseExpression(.lowest) orelse return error.ParseError;

        if (!try self.expectPeek(.rbracket)) return error.ParseError;

        const left_ptr = try self.allocator.create(ast.Expression);
        left_ptr.* = left;
        const index_ptr = try self.allocator.create(ast.Expression);
        index_ptr.* = index;

        return .{ .index_expression = .{
            .left = left_ptr,
            .index = index_ptr,
        } };
    }

    fn parseHashLiteral(self: *Parser) Error!ast.Expression {
        var pairs: std.ArrayList(ast.HashPair) = .empty;

        while (self.peek_token.type != .rbrace) {
            self.nextToken();
            const key = try self.parseExpression(.lowest) orelse return error.ParseError;

            if (!try self.expectPeek(.colon)) return error.ParseError;
            self.nextToken();

            const value = try self.parseExpression(.lowest) orelse return error.ParseError;
            try pairs.append(self.allocator, .{ .key = key, .value = value });

            if (self.peek_token.type != .rbrace) {
                if (!try self.expectPeek(.comma)) return error.ParseError;
            }
        }

        if (!try self.expectPeek(.rbrace)) return error.ParseError;

        return .{ .hash_literal = .{ .pairs = try pairs.toOwnedSlice(self.allocator) } };
    }
};

How the Pratt parser works
#

Every token type has a precedence and can appear as a prefix (at the start of an expression) or infix (between two expressions). The algorithm looks at cur_token and dispatches to the appropriate prefix handler, then loops while the peek token’s precedence is higher, dispatching to the infix handler each time. The precedence parameter controls how “greedy” parsing is: lower precedence means more tokens get consumed.

So 5 + 3 * 4 parses as (5 + (3 * 4)) because * has higher precedence than +.

Every parse method returns Error!T instead of just !T. This is required because the parse methods are mutually recursive. parseExpression calls parsePrefixExpression, which calls parseExpression again. Zig cannot infer error sets across recursive call cycles, so we define an explicit one.

Tests
#

The parser tests import lexer.zig, so they go in a separate file. Create src/parser_test.zig.

const std = @import("std");
const Parser = @import("parser.zig").Parser;

// Verify that the parser groups expressions correctly by comparing the `string()` output.
test "operator precedence parsing" {
    const allocator = std.testing.allocator;

    const tests = [_]struct { input: []const u8, expected: []const u8 }{
        .{ .input = "-a * b", .expected = "((-a) * b)" },
        .{ .input = "!-a", .expected = "(!(-a))" },
        .{ .input = "a + b + c", .expected = "((a + b) + c)" },
        .{ .input = "a + b - c", .expected = "((a + b) - c)" },
        .{ .input = "a * b * c", .expected = "((a * b) * c)" },
        .{ .input = "a * b / c", .expected = "((a * b) / c)" },
        .{ .input = "a + b / c", .expected = "(a + (b / c))" },
        .{ .input = "a + b * c + d / e - f", .expected = "(((a + (b * c)) + (d / e)) - f)" },
        .{ .input = "5 > 4 == 3 < 4", .expected = "((5 > 4) == (3 < 4))" },
        .{ .input = "true", .expected = "true" },
        .{ .input = "false", .expected = "false" },
        .{ .input = "3 > 5 == false", .expected = "((3 > 5) == false)" },
        .{ .input = "3 < 5 == true", .expected = "((3 < 5) == true)" },
        .{ .input = "1 + (2 + 3) + 4", .expected = "((1 + (2 + 3)) + 4)" },
        .{ .input = "(5 + 5) * 2", .expected = "((5 + 5) * 2)" },
        .{ .input = "2 / (5 + 5)", .expected = "(2 / (5 + 5))" },
        .{ .input = "-(5 + 5)", .expected = "(-(5 + 5))" },
        .{ .input = "a * [1, 2, 3, 4][b * c] * d", .expected = "((a * ([1, 2, 3, 4][(b * c)])) * d)" },
        .{ .input = "add(a * b[2], b[1], 2 * [1, 2][1])", .expected = "add((a * (b[2])), (b[1]), (2 * ([1, 2][1])))" },
    };

    for (tests) |tt| {
        var arena = std.heap.ArenaAllocator.init(allocator);
        defer arena.deinit();

        var l = @import("lexer.zig").Lexer.init(tt.input);
        var p = Parser.init(arena.allocator(), &l);
        const program = try p.parseProgram();

        try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
        try std.testing.expectEqual(@as(usize, 1), program.statements.len);

        const expr = program.statements[0].expression_statement.expression;
        const result = try expr.string(arena.allocator());
        try std.testing.expectEqualStrings(tt.expected, result);
    }
}

test "let statements" {
    const allocator = std.testing.allocator;
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();

    const input = "let x = 5; let y = true; let foobar = y;";
    var l = @import("lexer.zig").Lexer.init(input);
    var p = Parser.init(arena.allocator(), &l);
    const program = try p.parseProgram();

    try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
    try std.testing.expectEqual(@as(usize, 3), program.statements.len);

    const expected_names = [_][]const u8{ "x", "y", "foobar" };
    for (expected_names, 0..) |name, i| {
        const stmt = program.statements[i];
        try std.testing.expectEqualStrings(name, stmt.let_statement.name);
    }
}

test "function literal parsing" {
    const allocator = std.testing.allocator;
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();

    const input = "fn(x, y) { x + y; }";
    var l = @import("lexer.zig").Lexer.init(input);
    var p = Parser.init(arena.allocator(), &l);
    const program = try p.parseProgram();

    try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
    try std.testing.expectEqual(@as(usize, 1), program.statements.len);

    const func = program.statements[0].expression_statement.expression.function_literal;
    try std.testing.expectEqual(@as(usize, 2), func.parameters.len);
    try std.testing.expectEqualStrings("x", func.parameters[0].value);
    try std.testing.expectEqualStrings("y", func.parameters[1].value);
    try std.testing.expectEqual(@as(usize, 1), func.body.statements.len);
}

Verify it works
#

Make sure you’ve uncommented "src/parser_test.zig" in build.zig, then run zig build test. No output means all tests passed.

In chapter 3 we build the evaluator, a tree-walking interpreter that traverses the AST and produces values.