系统编程

Zig 解析器与编译器前端：词法分析、递归下降与 AST

Zig 的标签联合、编译期反射与无 GC 特性，使它成为手写编译器前端的理想语言。本文从零实现一个表达式语言的词法分析器、AST 定义、递归下降解析器与 Pratt 表达式解析，覆盖符号表、语义检查、错误恢复与错误报告，最后接一个树遍历解释器跑通端到端流程。

Plume 6 分钟阅读 2681 字

引言

编译器前端是练手 Zig 的最佳项目之一：它需要大量使用标签联合（union(enum)）、切片、错误联合类型、编译期反射与精细的内存管理——几乎覆盖了 Zig 语言的核心特性，同时又有清晰的正确性标准（能不能正确解析并求值）。

本文实现一个支持变量、算术、比较、函数调用的迷你语言，完整走通「源码 → Token → AST → 求值」四步。代码基于 Zig 0.13/0.14，可直接编译运行。

前置：标签联合与模式匹配、错误联合与 try/catch。

目录

1. 编译器前端全景

1.1 四个阶段

源码字符串
   ↓  词法分析 Lexer
Token 流
   ↓  语法分析 Parser
抽象语法树 AST
   ↓  语义分析 Analyzer
带类型标注的 AST / IR
   ↓  求值或代码生成
结果

词法分析负责把字符流切成有意义的 Token；语法分析负责把 Token 组织成树；语义分析负责解析名字、检查类型；后端负责执行或生成目标代码。

1.2 目标语言定义

本文实现的 Mini 语言支持：

let x = 10;
let y = x * 2 + 3;
if (y > 20) { print(y); }
fn add(a, b) { return a + b; }
print(add(x, y));

运算符优先级：= < ==/!=/</> < +/- < *// < 一元 - < 调用/分组。

2. 词法分析器设计

2.1 Token 类型

用标签联合表示 Token，这是 Zig 表达「带数据的不同类别」的惯用法：

const TokenTag = enum {
    number, string, ident,
    kw_let, kw_fn, kw_if, kw_else, kw_return, kw_print,
    plus, minus, star, slash,
    eq, eq_eq, bang_eq, lt, gt,
    lparen, rparen, lbrace, rbrace, comma, semicolon,
    eof,
};

const Token = struct {
    tag: TokenTag,
    lexeme: []const u8, // 指向源码缓冲区，零拷贝
    line: u32,
    column: u32,
};

2.2 关键字识别

用 std.StaticStringMap 在编译期建表，查表零运行时初始化成本：

const keywords = std.StaticStringMap(TokenTag).initComptime(.{
    .{ "let", .kw_let },
    .{ "fn", .kw_fn },
    .{ "if", .kw_if },
    .{ "print", .kw_print },
});

3. 手写词法分析实现

3.1 扫描器骨架

const Lexer = struct {
    src: []const u8,
    pos: usize = 0,
    line: u32 = 1,
    col: u32 = 1,

    fn peek(self: *Lexer) u8 {
        return if (self.pos < self.src.len) self.src[self.pos] else 0;
    }

    fn advance(self: *Lexer) u8 {
        const ch = self.src[self.pos];
        self.pos += 1;
        if (ch == '\n') {
            self.line += 1;
            self.col = 1;
        } else {
            self.col += 1;
        }
        return ch;
    }
};

3.2 主循环

fn next(self: *Lexer) !Token {
    self.skipWhitespace();
    if (self.pos >= self.src.len) return self.make(.eof, self.pos, self.pos);

    const start = self.pos;
    const ch = self.advance();

    if (std.ascii.isDigit(ch)) return self.number(start);
    if (std.ascii.isAlphabetic(ch) or ch == '_') return self.ident(start);

    return switch (ch) {
        '+' => self.make(.plus, start, self.pos),
        '-' => self.make(.minus, start, self.pos),
        '*' => self.make(.star, start, self.pos),
        '/' => self.make(.slash, start, self.pos),
        '(' => self.make(.lparen, start, self.pos),
        ')' => self.make(.rparen, start, self.pos),
        '{' => self.make(.lbrace, start, self.pos),
        '}' => self.make(.rbrace, start, self.pos),
        ',' => self.make(.comma, start, self.pos),
        ';' => self.make(.semicolon, start, self.pos),
        '=' => if (self.peek() == '=')
            self.twoChar(.eq_eq, start)
        else
            self.make(.eq, start, self.pos),
        '!' => if (self.peek() == '=')
            self.twoChar(.bang_eq, start)
        else
            return error.UnexpectedCharacter,
        '<' => self.make(.lt, start, self.pos),
        '>' => self.make(.gt, start, self.pos),
        else => error.UnexpectedCharacter,
    };
}

4. 抽象语法树设计

4.1 节点定义

AST 同样是标签联合。表达式与语句分开定义，避免巨型联合：

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

const Stmt = union(enum) {
    let: struct { name: []const u8, value: *Expr },
    assign: struct { name: []const u8, value: *Expr },
    print: *Expr,
    expr: *Expr,
    if_stmt: struct { cond: *Expr, then: *Stmt },
    func: struct { name: []const u8, params: [][]const u8, body: []*Stmt },
    return_stmt: ?*Expr,
};

const Program = struct { stmts: []*Stmt };

4.2 用 arena 分配节点

AST 节点数量多、生命周期统一（整个编译期），是 arena 分配器的典型场景：

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const a = arena.allocator();

const node = try a.create(Expr);
node.* = .{ .number = 42.0 };

一次 deinit 释放全部节点，无需逐个追踪。

5. 递归下降解析

5.1 解析器骨架

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

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

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

    fn match(self: *Parser, tag: TokenTag) bool {
        if (self.check(tag)) {
            self.pos += 1;
            return true;
        }
        return false;
    }

    fn expect(self: *Parser, tag: TokenTag) !Token {
        if (!self.check(tag)) {
            std.debug.print("第 {d} 行: 期望 {s}，实际 {s}\n", .{
                self.peek().line, @tagName(tag), @tagName(self.peek().tag),
            });
            return error.UnexpectedToken;
        }
        const t = self.peek();
        self.pos += 1;
        return t;
    }
};

5.2 语句解析

fn parseStmt(self: *Parser) anyerror!*Stmt {
    if (self.match(.kw_let)) {
        const name = try self.expect(.ident);
        _ = try self.expect(.eq);
        const value = try self.parseExpr(0);
        _ = try self.expect(.semicolon);
        const s = try self.alloc.create(Stmt);
        s.* = .{ .let = .{ .name = name.lexeme, .value = value } };
        return s;
    }
    if (self.match(.kw_print)) {
        _ = try self.expect(.lparen);
        const e = try self.parseExpr(0);
        _ = try self.expect(.rparen);
        _ = try self.expect(.semicolon);
        const s = try self.alloc.create(Stmt);
        s.* = .{ .print = e };
        return s;
    }
    if (self.match(.kw_if)) {
        _ = try self.expect(.lparen);
        const cond = try self.parseExpr(0);
        _ = try self.expect(.rparen);
        const then = try self.parseStmt();
        const s = try self.alloc.create(Stmt);
        s.* = .{ .if_stmt = .{ .cond = cond, .then = then } };
        return s;
    }
    const e = try self.parseExpr(0);
    _ = try self.expect(.semicolon);
    const s = try self.alloc.create(Stmt);
    s.* = .{ .expr = e };
    return s;
}

6. Pratt 表达式解析

6.1 优先级表

Pratt 解析（运算符优先级解析）用一张表统一处理二元运算的优先级与结合性：

fn bindingPower(tag: TokenTag) struct { left: u8, right: u8 } {
    return switch (tag) {
        .eq => .{ .left = 1, .right = 1 },       // 右结合
        .eq_eq, .bang_eq, .lt, .gt => .{ .left = 2, .right = 3 },
        .plus, .minus => .{ .left = 4, .right = 5 },
        .star, .slash => .{ .left = 6, .right = 7 },
        else => .{ .left = 0, .right = 0 },
    };
}

左结合运算符 left < right，右结合则 left == right。

6.2 核心循环

fn parseExpr(self: *Parser, min_bp: u8) anyerror!*Expr {
    var lhs = try self.parsePrefix();

    while (true) {
        const bp = bindingPower(self.peek().tag);
        if (bp.left <= min_bp) break;
        const op = self.peek().tag;
        self.pos += 1;
        const rhs = try self.parseExpr(bp.right);
        const node = try self.alloc.create(Expr);
        node.* = .{ .binary = .{ .op = op, .lhs = lhs, .rhs = rhs } };
        lhs = node;
    }
    return lhs;
}

6.3 前缀解析

fn parsePrefix(self: *Parser) anyerror!*Expr {
    if (self.match(.minus)) {
        const operand = try self.parseExpr(7); // 一元优先级最高
        const node = try self.alloc.create(Expr);
        node.* = .{ .unary = .{ .op = .minus, .operand = operand } };
        return node;
    }
    return self.parsePrimary();
}

fn parsePrimary(self: *Parser) anyerror!*Expr {
    const t = self.peek();
    switch (t.tag) {
        .number => {
            self.pos += 1;
            const node = try self.alloc.create(Expr);
            node.* = .{ .number = try std.fmt.parseFloat(f64, t.lexeme) };
            return node;
        },
        .ident => {
            self.pos += 1;
            if (self.match(.lparen)) {
                var args = std.ArrayList(*Expr).init(self.alloc);
                if (!self.check(.rparen)) {
                    while (true) {
                        try args.append(try self.parseExpr(0));
                        if (!self.match(.comma)) break;
                    }
                }
                _ = try self.expect(.rparen);
                const node = try self.alloc.create(Expr);
                node.* = .{ .call = .{ .callee = t.lexeme, .args = try args.toOwnedSlice() } };
                return node;
            }
            const node = try self.alloc.create(Expr);
            node.* = .{ .ident = t.lexeme };
            return node;
        },
        .lparen => {
            self.pos += 1;
            const e = try self.parseExpr(0);
            _ = try self.expect(.rparen);
            return e;
        },
        else => return error.ExpectedExpression,
    }
}

7. 符号表与语义分析

7.1 作用域链

const Scope = struct {
    alloc: std.mem.Allocator,
    vars: std.StringHashMapUnmanaged(Value) = .{},
    parent: ?*Scope = null,

    fn lookup(self: *Scope, name: []const u8) ?*Value {
        if (self.vars.getPtr(name)) |v| return v;
        if (self.parent) |p| return p.lookup(name);
        return null;
    }
};

7.2 静态检查

求值前遍历 AST 做一轮检查，能在运行前捕获大部分错误：变量是否已声明、函数调用参数个数是否匹配、return 是否在函数体内。

把能静态发现的错误提前，能显著改善使用体验——这也正是 Zig 本身「尽可能在编译期发现问题」理念的延伸。

8. 错误报告与错误恢复

8.1 恐慌模式恢复

遇到语法错误时，不要立即放弃整个文件，而是跳到下一个同步点（; 或 }）继续解析，一次报告多个错误：

fn synchronize(self: *Parser) void {
    while (!self.check(.eof)) {
        if (self.tokens[self.pos - 1].tag == .semicolon) return;
        switch (self.peek().tag) {
            .kw_let, .kw_fn, .kw_if, .kw_print => return,
            else => self.pos += 1,
        }
    }
}

好的错误信息包含三点：在哪出错、期望什么、实际看到什么。加上源码片段与插入符，用户几乎不需要思考就能定位问题。

9. 树遍历解释器

9.1 值类型与表达式求值

const Value = union(enum) {
    nil,
    number: f64,
    string: []const u8,
    boolean: bool,
};

fn evalExpr(e: *Expr, scope: *Scope) anyerror!Value {
    return switch (e.*) {
        .number => |n| .{ .number = n },
        .string => |s| .{ .string = s },
        .ident => |name| (scope.lookup(name) orelse return error.UndefinedVariable).*,
        .unary => |u| .{ .number = -(try evalExpr(u.operand, scope)).number },
        .binary => |b| blk: {
            const l = try evalExpr(b.lhs, scope);
            const r = try evalExpr(b.rhs, scope);
            break :blk switch (b.op) {
                .plus => .{ .number = l.number + r.number },
                .minus => .{ .number = l.number - r.number },
                .star => .{ .number = l.number * r.number },
                .slash => .{ .number = l.number / r.number },
                .gt => .{ .boolean = l.number > r.number },
                .lt => .{ .boolean = l.number < r.number },
                .eq_eq => .{ .boolean = l.number == r.number },
                else => error.UnsupportedOperator,
            };
        },
        .call => error.NotImplemented,
    };
}

9.2 语句执行

fn exec(stmt: *Stmt, scope: *Scope) anyerror!void {
    switch (stmt.*) {
        .let => |l| {
            const v = try evalExpr(l.value, scope);
            try scope.vars.put(scope.alloc, l.name, v);
        },
        .print => |e| {
            const v = try evalExpr(e, scope);
            switch (v) {
                .number => |n| std.debug.print("{d}\n", .{n}),
                .string => |s| std.debug.print("{s}\n", .{s}),
                .boolean => |b| std.debug.print("{}\n", .{b}),
                .nil => std.debug.print("nil\n", .{}),
            }
        },
        .if_stmt => |i| {
            const cond = try evalExpr(i.cond, scope);
            if (cond.boolean) try exec(i.then, scope);
        },
        else => {},
    }
}

速查表

阶段关键结构Zig 特性
词法分析Token（tag + lexeme + 位置）enum、切片、StaticStringMap
语法分析Expr / Stmt（标签联合）union(enum)、*T 间接层
表达式Pratt 优先级表switch 穷尽匹配
语义分析作用域链 ScopeStringHashMap、可选指针
内存节点统一 arena 分配ArenaAllocator
错误带行列的错误结构error{} 集合、try
求值树遍历解释器标签联合的模式匹配

一句话记忆

前端四步：Lexer 把字符切成 Token（保留位置切片）、Parser 用递归下降 + Pratt 把 Token 组成 AST（节点用 arena 分配、递归处用指针）、Analyzer 查符号表、后端遍历 AST 求值；错误要带行列并做恐慌恢复。

相关阅读

延伸阅读

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「系统编程」更多文章

  1. Zig 算法与数据结构实战：哈希表、树、图与排序
  2. Zig 游戏开发实战：raylib、ECS 架构与游戏循环
  3. Zig 文本处理：Unicode、正则与高性能字符串