用 Zig 手写一个解释器（二）：语法分析

上一篇文章写完词法分析之后，我们拿到了一串token。接下来要做的，是把这串token变成一棵有层次结构的抽象语法树（AST）。这一步叫语法分析。

语法分析的方案不少，递归下降、LL、LR都是常见的。不过手写的话，Pratt解析是性价比很高的选择——代码量比递归下降略多，但处理表达式优先级极其干净，不需要为每一级优先级写一个函数。

先讲 AST 节点的定义，Pratt 解析器的实现，最后看怎么测试(测试用例抄的书, bushi)

AST 的定义

AST 节点怎么表示？先看根节点 Program，就是索引一组语句：

pub const Program = struct {
    statements: std.ArrayList(*Statement),

    pub fn tokenLiteral(self: Program) []const u8 {
        if (self.statements.items.len > 0) {
            return self.statements.items[0].tokenLiteral();
        } else {
            return "";
        }
    }
};

tokenLiteral() 返回这段程序的第一个 token 的原文，后面每个 AST 节点都会实现这个方法，主要给报错信息用。还有一个 string() 方法后面会细说。

往下是Statement和Expression的区分。这个语言里，let绑定和return是语句——它们不产生值；if、函数字面量、函数调用、各种运算都是表达式——它们求值后产生一个值。这两类节点都用 tagged union 表示：

pub const Statement = union(enum) {
    let_statement: *LetStatement,
    return_statement: *ReturnStatement,
    expression: *ExpressionStatement,
    block: *BlockStatement,
};

pub const Expression = union(enum) {
    identifier: *Identifier,
    boolean: *Boolean,
    integer: *IntegerLiteral,
    prefix: *PrefixExpression,
    infix: *InfixExpression,
    if_expr: *IfExpression,
    function: *FunctionLiteral,
    call: *CallExpression,
};

Zig 没有类继承，tagged union 就是表达”一组不同类型共用一个名字”的惯用方式。后面配合 switch 做模式匹配

每个具体的 AST 节点都是一个 struct，而且都带了一个 token: token.Token 字段。这是为了报错的时候能指出来这个节点对应的源码在哪里。

看一下LetStatement

pub const LetStatement = struct {
    token: token.Token,  // "let" 这个 token
    name: *Identifier,    // 变量名
    value: ?*Expression,  // 等号右边的表达式
};

value 是 optional 的（?*Expression），因为 let x没有初始值也是合法的（虽然当前测试里不会这么写）。Identifier 节点就更简单，就是 token 加上 value 字符串：

pub const Identifier = struct {
    token: token.Token,
    value: []const u8,
};

复杂一点的节点以 IfExpression 为例：

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

condition 是条件表达式，consequence 是 then 分支的代码块，alternative 是 else 分支。if 的整体是一个表达式而不是语句，意味着 let x = if (a > b) { a } else { b }; 这种写法是合法的。这是故意学的 Rust 和很多函数式语言的做法。

FunctionLiteral 存参数列表和函数体：

pub const FunctionLiteral = struct {
    token: token.Token,
    parameters: std.ArrayListUnmanaged(*Identifier),
    body: ?*BlockStatement,
};

CallExpression 存被调函数和实参：

pub const CallExpression = struct {
    token: token.Token,              // '(' token
    function: ?*Expression,          // 被调用的函数，是一个表达式
    arguments: std.ArrayListUnmanaged(*Expression),  // 实参列表
};

注意 function 是 ?*Expression 而不是 ?*Identifier。这是为了支持 fn(x) { return x; }(5) 这种匿名函数立即调用的写法。

每个 AST 节点除了 tokenLiteral()，还实现了 string() 方法。这个方法把 AST 节点还原成源码字符串的表示。拿 InfixExpression 来看：

pub fn string(self: *InfixExpression, allocator: std.mem.Allocator) ![]const u8 {
    var buf: std.ArrayList(u8) = .empty;
    try buf.append(allocator, '(');
    // 递归还原左操作数
    if (self.left) |l| {
        const ls = try l.string(allocator);
        defer allocator.free(ls);
        try buf.appendSlice(allocator, ls);
    }
    try buf.append(allocator, ' ');
    try buf.appendSlice(allocator, self.operator);
    try buf.append(allocator, ' ');
    // 递归还原右操作数
    if (self.right) |r| {
        const rs = try r.string(allocator);
        defer allocator.free(rs);
        try buf.appendSlice(allocator, rs);
    }
    try buf.append(allocator, ')');
    return buf.toOwnedSlice(allocator);
}

这里给中缀表达式包了一层括号，所以 a + b * c 会变成 (a + (b * c))，运算符优先级直接体现在括号嵌套里。string() 不是华而不实的附加功能——它让测试验证变得极其简单。不用挨个 assert left 是什么

所有 AST 节点的内存都从 ArenaAllocator 分配。好处是不用追踪每个节点的生命周期，解析完一个程序，一把 arena.deinit() 全部释放。节点之间的引用全部用指针，因为 Arena 保证了所有节点存活时间一致。

Pratt 解析器

词法分析结束后，我们拿到一个 []token.Token 切片。Parser 的职责就是遍历这个切片，按语法规则构建 AST。

Parser 本身的定义：

pub const Parser = struct {
    tokenList: []token.Token,
    pos: usize,
    errors: std.ArrayListUnmanaged([]const u8),
    error_arena: std.heap.ArenaAllocator,
};

pos 是当前位置，errors 收集解析过程中遇到的所有，error_arena 专门给错误字符串用的 Arena，解析结束后一起释放。

先看主入口 parseProgram：

pub fn parseProgram(p: *Parser, arena: std.mem.Allocator) !*ast.Program {
    const program = try arena.create(ast.Program);
    program.statements = .empty;
    while (!p.curTokenIs(.eof)) {
        if (p.parseStatement(arena)) |stmt| {
            try program.statements.append(arena, stmt);
        }
        p.nextToken();
    }
    return program;
}

逻辑就是不停读 token，调用 parseStatement，直到碰到 EOF。parseStatement 返回 optional，如果解析失败（比如碰到不认识的 token），返回 null，外层跳过继续。这样设计是为了尽量多地收集错误。

parseStatement 根据当前 token 的类型做分发:

pub fn parseStatement(self: *Parser, arena: std.mem.Allocator) ?*ast.Statement {
    const tag = std.meta.activeTag(self.curToken().Type);
    switch (tag) {
        .let => return self.parseLetStatement(arena),
        .@"return" => return self.parseReturnStatement(arena),
        else => return self.parseExpressionStatement(arena),
    }
}

std.meta.activeTag 从 token 的 tagged union 里取出当前激活的标签。switch 覆盖了 let、return 和”其他”三种情况。其他情况都按表达式语句处理——因为大部分 token（标识符、数字、前缀运算符等等）都只能出现在表达式的开头位置。

优先级

先定义优先级。这个语言总共就几级：

const Precedence = enum(u8) {
    lowest,
    equals,       // == !=
    lessgreater,  // < >
    sum,          // + -
    product,      // * /
    prefix,       // -x  !x
    call,         // fn(x)
};

数字越大的枚举值越大——乘除比加减紧，函数调用比前缀运算符优先级就。tokenPrecedence 函数把 token 类型映射到优先级：

fn tokenPrecedence(t: std.meta.Tag(token.TokenType)) Precedence {
    return switch (t) {
        .eq, .not_eq => .equals,
        .lt, .gt => .lessgreater,
        .plus, .minus => .sum,
        .slash, .asterisk => .product,
        .lparen => .call,
        else => .lowest,
    };
}

注意 ( 被映射到 call 优先级。因为在这个语言里，左括号出现的位置要么是分组 (1+2)——这种情况在前缀解析里处理；要么是函数调用 add(1,2)——这种情况在中缀解析里处理。中缀的 ( 需要 call 级优先级来保证它比任何二元运算符都高。

Pratt 的核心循环

parseExpression 是 Pratt 的心脏。它接收一个参数 precedence

pub fn parseExpression(self: *Parser, arena: std.mem.Allocator, precedence: Precedence) ?*ast.Expression {
    var left_exp = self.parsePrefix(arena) orelse return null;

    while (!self.peekTokenIs(.semicolon) and @intFromEnum(precedence) < @intFromEnum(self.peekPrecedence())) {
        const peek_tag = std.meta.activeTag(self.peekToken().Type);
        const infix_exp = switch (peek_tag) {
            .plus, .minus, .slash, .asterisk, .eq, .not_eq, .lt, .gt => blk: {
                self.nextToken();
                break :blk self.parseInfixExpression(arena, left_exp);
            },
            .lparen => blk: {
                self.nextToken();
                break :blk self.parseCallExpression(arena, left_exp);
            },
            else => null,
        };
        if (infix_exp) |exp| {
            left_exp = exp;
        } else return left_exp;
    }
    return left_exp;
}

前缀分发

parsePrefix 的职责是根据当前 token 的类型，把控制权交给对应的解析函数：

pub fn parsePrefix(self: *Parser, arena: std.mem.Allocator) ?*ast.Expression {
    const tag = std.meta.activeTag(self.curToken().Type);
    switch (tag) {
        .ident => return self.parseIdentifier(arena),
        .int => return self.parseIntegerLiteral(arena),
        .bang, .minus => return self.parsePrefixExpression(arena),
        .true, .false => return self.parseBoolean(arena),
        .lparen => return self.parseGroupedExpression(arena),
        .@"if" => return self.parseIfExpression(arena),
        .function => return self.parseFunctionLiteral(arena),
        else => {
            self.noPrefixParseFnError(self.curToken().Type);
            return null;
        },
    }
}

8 个分支，覆盖了所有能作为表达式开头的 token 类型.

几个前缀解析的例子。PrefixExpression 处理 -x 和 !x：

pub fn parsePrefixExpression(self: *Parser, arena: std.mem.Allocator) ?*ast.Expression {
    const expr = arena.create(ast.PrefixExpression) catch return null;
    expr.token = self.curToken();
    expr.operator = self.curToken().Literal;
    self.nextToken();
    expr.right = self.parseExpression(arena, .prefix);
    const exp = arena.create(ast.Expression) catch return null;
    exp.* = .{ .prefix = expr };
    return exp;
}

值得注意的是递归调用 parseExpression(arena, .prefix) 传的是 .prefix 优先级。这意味着 -x 里的 x 后面也不能再跟中缀运算符了——除非右边有括号或者更高优先级的东西。实际上 prefix 是这个优先级表里仅次于 call 的最高级，所以 -a + b 会正确解析为 ((-a) + b) 而不是 -(a + b)。

If 表达式的解析展示了 Pratt 解析器怎么处理关键字前缀：

pub fn parseIfExpression(self: *Parser, arena: std.mem.Allocator) ?*ast.Expression {
    const expr = arena.create(ast.IfExpression) catch return null;
    expr.token = self.curToken();
    if (!self.expectpeek(.lparen)) return null;
    self.nextToken();
    expr.condition = self.parseExpression(arena, .lowest);
    if (!self.expectpeek(.rparen)) return null;
    if (!self.expectpeek(.lbrace)) return null;
    expr.consequence = self.parseBlockStatement(arena);
    if (self.peekTokenIs(.@"else")) {
        self.nextToken();
        if (!self.expectpeek(.lbrace)) return null;
        expr.alternative = self.parseBlockStatement(arena);
    }
}

expectpeek 是一个辅助方法：如果下一个 token 是期望的类型，就前进并返回 true；不是就记录错误返回 false。条件部分递归 parseExpression(arena, .lowest)——条件里当然允许任何优先级的表达式。

中缀分发

回到 parseExpression 的 while 循环，中缀分发只处理两类情况：

const infix_exp = switch (peek_tag) {
    .plus, .minus, .slash, .asterisk, .eq, .not_eq, .lt, .gt => blk: {
        self.nextToken();
        break :blk self.parseInfixExpression(arena, left_exp);
    },
    .lparen => blk: {
        self.nextToken();
        break :blk self.parseCallExpression(arena, left_exp);
    },
    else => null,
};

这里用了 Zig 的 labeled block（blk: { break :blk expr })

pub fn parseInfixExpression(self: *Parser, arena: std.mem.Allocator, left: *ast.Expression) ?*ast.Expression {
    const expr = arena.create(ast.InfixExpression) catch return null;
    expr.token = self.curToken();
    expr.operator = self.curToken().Literal;
    expr.left = left;
    const prec = self.curPrecedence();
    self.nextToken();
    expr.right = self.parseExpression(arena, prec);
}

pub fn parseCallExpression(self: *Parser, arena: std.mem.Allocator, function: *ast.Expression) ?*ast.Expression {
    const expr = arena.create(ast.CallExpression) catch return null;
    expr.token = self.curToken();
    expr.function = function;
    expr.arguments = .empty;
    // 循环解析实参，逗号分隔，直到 )
    if (self.peekTokenIs(.rparen)) {
        self.nextToken();
    } else {
        self.nextToken();
        while (true) {
            if (self.parseExpression(arena, .lowest)) |arg| {
                expr.arguments.append(arena, arg) catch return null;
            }
            if (!self.peekTokenIs(.comma)) break;
            self.nextToken();
            self.nextToken();
        }
        if (!self.expectpeek(.rparen)) return null;
    }
}

参数列表中每个实参都是独立的表达式，传入的优先级是 lowest，意味着 add(a + b, c * d) 里，a + b 和 c * d 都能正确解析各自的运算符。

错误收集

这个 parser 不会在第一个语法错误就 panic 或返回 error。expectpeek 的核心逻辑：

pub fn expectpeek(self: *Parser, t: std.meta.Tag(token.TokenType)) bool {
    if (self.peekTokenIs(t)) {
        self.nextToken();
        return true;
    } else {
        self.peekError(t);
        return false;
    }
}
fn peekError(self: *Parser, t: std.meta.Tag(token.TokenType)) void {
    const msg = std.fmt.allocPrint(
        self.error_arena.child_allocator,
        "expected next token to be {s}, got {s} instead",
        .{ @tagName(t), @tagName((std.meta.activeTag(self.peekToken().Type))) }
    ) catch "error formatting error";
    self.errors.append(self.error_arena.allocator(), msg) catch {};
}

测试设计

Parser 的测试分了几个层次。每个核心 AST 节点类型一个独立测试：let 语句、return 语句、标识符表达式、整数字面量、前缀表达式、中缀表达式、if 表达式、if-else 表达式、函数字面量、调用表达式。每个测试的流程一致：

test "let statements" {
    const allocator = std.testing.allocator;
    const tests = [_]struct { input: []const u8, expected_ident: []const u8, expected_value: []const u8 }{
        .{ .input = "let x = 5;", .expected_ident = "x", .expected_value = "5" },
        .{ .input = "let y = true;", .expected_ident = "y", .expected_value = "true" },
        .{ .input = "let foobar = y;", .expected_ident = "foobar", .expected_value = "y" },
    };
    for (tests) |tt| {
        var my_lexer = lexer.Lexer.init(tt.input);
        const tokens = try my_lexer.nextToken(allocator);
        defer allocator.free(tokens);

        var parser = Parser.init(tokens, allocator);
        defer parser.deinit();

        var ast_arena = std.heap.ArenaAllocator.init(allocator);
        defer ast_arena.deinit();

        const program = try parser.parseProgram(ast_arena.allocator());

        try std.testing.expectEqual(0, parser.errors.items.len);
        try std.testing.expectEqual(1, program.statements.items.len);
        const stmt = program.statements.items[0].*;
        try std.testing.expect(stmt == .let_statement);
        try std.testing.expectEqualStrings(tt.expected_ident, stmt.let_statement.name.value);
    }
}

最核心的测试是 operator precedence，一张大表覆盖了 21 组输入：

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 = "5 > 4 == 3 < 4", .expected = "((5 > 4) == (3 < 4))" },
    .{ .input = "1 + (2 + 3) + 4", .expected = "((1 + (2 + 3)) + 4)" },
    .{ .input = "a + add(b * c) + d", .expected = "((a + add((b * c))) + d)" },
    .{ .input = "add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))",
       .expected = "add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))" },

    太长了
};