解析（Parsing）是编译流水线中紧随词法分析之后的下一步。解析负责从 token 流构建出抽象语法树。我之前写过 Zig 如何把字节流（源代码）转换成 token 流。

Zig 解析器位于 Zig 源码树中的 lib/std/zig/parser.zig，作为标准库的一部分可通过 std.zig.parse() 使用。解析器接收完整的源码文本，并返回一个 std.zig.Ast（定义在 lib/std/zig/Ast.zig 中）。

MultiArrayList

从解析阶段开始，Zig 编译器大量使用 MultiArrayList 结构。你必须理解 MultiArrayList，才能理解解析器的工作方式以及所生成的 AST 的结构。

在解释 MultiArrayList 之前，我先简单介绍一下普通的 ArrayList（没有 “Multi”）。ArrayList 是一个长度可动态变化的值数组。当数组满了时，会分配一个更大的新数组，并把现有元素复制过去。这是一种典型的、动态分配的、可增长（或收缩）的元素列表。

例如，考虑下面这个 Zig 结构体：

pub const Tree = struct {
    age: u32,       // trees can be very old, hence 32-bits
    alive: bool,    // is this tree still alive?
};

在一个 ArrayList 中，许多 Tree 结构体像这样存储：

       ┌──────────────┬──────────────┬──────────────┬──────────────┐
array: │     Tree     │     Tree     │     Tree     │     ...      │
       └──────────────┴──────────────┴──────────────┴──────────────┘

每个 Tree 需要 8 字节内存。四个树的数组占用 32 字节内存。

MultiArrayList 同样是一个动态分配的元素列表。不过，数组列表中所存类型的每个字段都存储在各自独立的连续数组中。这带来两个主要好处：(1) 减少因对齐而浪费的字节；(2) 更好的缓存局部性。这两个好处通常都会带来更好的性能。

对于我们的 Tree 结构体，MultiArrayList(Tree) 的存储方式如下：

          ┌──────┬──────┬──────┬──────┐
   age:   │ age  │ age  │ age  │ ...  │
          └──────┴──────┴──────┴──────┘
          ┌┬┬┬┬┐
 alive:   ││││││
          └┴┴┴┴┘

结构体的每个字段都存储在独立的连续数组中。四个树的数组只占用 20 字节，节省了 37.5% 的内存。这里忽略了多个数组指针的开销，但该开销是固定的，因此随着列表中元素数量的增长，本例最终摊销下来共节省 37.5% 的内存。

本页不会深入探讨 MultiArrayList 的实现细节。就理解 Zig 编译器而言，只需知道几乎每个结构（token、AST 节点、未来的 IR 节点等）都以 MultiArrayList 的形式存储即可。编译一个真实世界的程序通常会产生数以万计的“节点”，因此这能带来巨大的内存节省和缓存局部性的提升。

解析器的构造

解析器使用一个名为 Parser 的结构体来存储进行中的解析状态。这不是一个公开导出的结构体，仅用于管理解析操作的内部状态。调用方会得到一个 Ast 作为解析操作的结果，稍后会在本页详细探讨。

撰写本文时解析器的结构如下所示。我插入了换行符，将状态按功能分组。

const Parser = struct {
    gpa: Allocator,
    source: []const u8,

    token_tags: []const Token.Tag,
    token_starts: []const Ast.ByteOffset,
    tok_i: TokenIndex,

    errors: std.ArrayListUnmanaged(AstError),
    nodes: Ast.NodeList,
    extra_data: std.ArrayListUnmanaged(Node.Index),
    scratch: std.ArrayListUnmanaged(Node.Index),
};

第一组包含 gpa 和 source。这是分配器和单个 Zig 文件的完整原始源代码。

第二组中，token_tags 和 token_starts 是词法分析的拆解结果。如前所述，解析器采用面向数据的设计以获得更好的内存使用和缓存局部性。因此 token_tags.len == token_starts.len，它们只是被放入独立连续内存块的结构体字段。tok_i 值是解析器当前正在查看的 token 的索引（从 0 开始）。

第三组是解析器真正的工作状态。这里累积的结果将成为 Ast 的一部分。第三组非常重要，因为它是解析器所构建内容的核心。

• errors 是解析过程中产生的错误列表。大多数行为良好的解析器都会在各种错误场景下尝试继续解析，Zig 的解析器也不例外。Zig 解析器会把错误累积到该字段中，并尝试继续解析。
• nodes 是 AST 节点列表。它初始为空，随着解析的进行逐渐构建起来。理解 AST 节点的结构极其重要，下一节会讲到。
• extra_data 是 AST 节点可能需要的附加信息列表。例如对于一个 struct，extra_data 包含所有 struct 成员的完整列表。这也是面向数据设计的一个例子；另一种做法是把额外数据直接放在 Node 上，但这会使每个 Node 变得大得多，从而拖慢整个解析器。
• scratch 是解析器共享的临时工作空间，通常用于为节点或额外数据积累信息。解析完成后它会被释放。

AST 节点的构造

解析的结果是一个 AST 节点列表。注意 AST 本身仍然是一棵树，但解析器返回的结果包含树中节点的列表，因为树在内存中就是这样表示的。

AST 节点结构可能让人困惑，因为在数据本身存储于 MultiArrayList 之上还有大量的间接引用。我建议反复重读本节，以确保你理解 AST 节点的结构。在学习 Zig 编译器内部机制的过程中，正是由于对这种数据模式缺乏完整的理解，我遇到了很多问题，因为这个模式在编译器的后续每个阶段都被复用。

AST 结构可以在 lib/std/zig/Ast.zig 中找到。主要结构是 Node：

pub const Node = struct {
    tag: Tag,
    main_token: TokenIndex,
    data: Data,

    pub const Data = struct {
        lhs: Index,
        rhs: Index,
    };

    pub const Index = u32;
};

注意，解析器本身将节点存储在 NodeList 中，它是一个 MultiArrayList(Node)，也就是说 Node 结构体的每个字段分别存储在独立的连续内存块中。概念上你可以把节点当作上面所示的单个结构体来思考，但具体使用时字段是被拆分的。

节点的 tag 是一个枚举，表示可能的 AST 节点类型。例如，函数声明用 fn_decl，整数字面量用 integer_literal，调用内建函数（如 @enumToInt）用 builtin_call。

main_token 字段现在不必过分深究。它是与该 AST 节点关联的主 token。例如对于函数声明，它可能是 fn。该值是指向用于构建 AST 的 token 列表的索引。

data 字段极其重要。它包含与 AST 节点关联的信息。例如，函数声明（.tag == .fn_decl）用 data 存储函数原型以及函数体。data 字段将在下一节详细介绍。

AST 节点数据

任何 AST 节点的关键部分都是与之关联的数据。例如，函数声明有函数名、参数列表、返回类型、函数体等等。看 Node 结构体，并不能立刻看出这些信息存在哪里。

在我们深入解析器如何工作之前，这是一个必须理解的极其重要的细节。 对于想了解整个编译流水线如何运作的人来说，这一点尤为关键，因为 AST 所使用的模式在整个编译流水线的其他中间形式中被反复复用。

让我们看看下面的 Zig 代码对应的函数声明的 AST 会如何组织：

fn add(a: u8, b: u8) callconv(.C) u8 {
    return a + b;
}

函数声明

函数声明的根 AST 节点的 tag 为 fn_decl。

对于 fn_decl，data 字段的 lhs 存储指向函数原型（名称、类型信息等）的索引，rhs 字段存储指向函数体的索引。你只有阅读 .fn_decl tag 上方的注释或阅读源码（或两者都读）才能知道这一点。

此例中 lhs 和 rhs 里的索引值就是 Node 在 NodeList 中的数组索引。所以你可以在 tree.nodes[lhs] 找到函数原型（伪代码，并不严格正确）。

所以在这个例子中，data 的两个字段都用来存储 NodeList 索引。这是 data 的一种用法，也是 AST 节点信息的存储方式之一。接下来让我们看看函数原型，弄清楚如何确定参数列表、返回类型和调用约定。

函数原型

我们可以通过读取 tree.nodes[lhs] 处的节点获得函数原型。此例中该节点的 tag 为 fn_proto。这种类型的 AST 节点存储参数、调用约定、返回类型等信息。

这种特定的 AST 节点类型对 lhs 和 rhs 的用法不同。rhs 字段的用法与函数声明相同，指向 NodeList 中返回类型表达式的索引（因为 Zig 支持各种表达式作为 comptime 计算出的返回类型，而不只是直接的类型标识符）。

然而，lhs 字段并不指向 AST 节点。相反，它是指向 extra_data 字段（见“解析器的构造”一节）的索引。这个索引是附加元数据的起始索引。附加元数据的长度可以根据 AST 节点类型预先得知。所以在这种情况下不是 tree.nodes[lhs]，而是 tree.extra_data[lhs]。要点：lhs/rhs 既可能指向节点，也可能指向额外数据。

提醒一下，extra_data 的类型是 []Index。这可能让人觉得 lhs 用作 tree.extra_data[lhs] 时只是指向另一个索引。不对，lhs（对于 .fn_proto）只是指向 extra_data 中的第一个索引。后续要读取多少个字段同样取决于 tag。对于 fn_proto 是六个字段。我们怎么知道是六个？通过源码中的注释或读取被编码的结构体：

pub const FnProto = struct {
    params_start: Index,
    params_end: Index,
    align_expr: Index,
    addrspace_expr: Index,
    section_expr: Index,
    callconv_expr: Index,
};

于是 tree.extra_data[lhs] 是 params_start，tree.extra_data[lhs+1] 是 params_end，依此类推直到 tree.extra_data[lhs+5] 是 callconv_expr。

Ast 结构体提供了辅助函数 extraData() 来解码这些数据。给定一棵 AST 树 tree，你可以用以下方法轻松访问。下面的例子中，idx 是 .fn_proto 节点所在节点列表中的索引。

const fnData = tree.extraData(idx, FnProto)
fnData.params_start
fnData.callconv_expr
// etc...

但 FnProto 结构体上的 param_start、param_end 等是什么？它们是表示第一个参数、最后一个参数等的 AST 节点在 NodeList 中的索引。这就是你读取函数原型全部附加信息的方式。

正如之前警告过的，这里有大量的间接引用。但现在彻底理解这一切极其重要，否则流水线的后续阶段会更加令人困惑。

函数标识符

main_token 字段是我们尚未使用的 Node 上唯一的字段，也是访问某些 AST 节点数据的最后一种方式。对于函数原型，你现在可以看到，标识符本身（函数名）无处可寻。

一些 AST 节点——比如 .fn_proto——就用 main_token 字段来做这件事。fn_proto 的 main_token 是 token 流中 “fn” 关键字的索引。在 Zig 中，函数标识符总是紧跟在这个关键字之后。因此，你可以通过查看索引 main_token + 1 处的 token 来提取函数标识符。编译器的后续阶段正是这样读取标识符的。

AST 数据布局回顾

如果你有兴趣了解 Zig 编译器的其余部分如何工作，那么深入理解这种信息存储模式极其重要。第一遍读可能很难理解（第二遍、第三遍或许也一样）。本节回顾一下 AST 数据是如何布局的。

AST 节点数据可以出现在三个位置：

1. token 流（用于标识符之类的值）
2. 节点列表，用于找到其他 AST 节点
3. 额外数据列表，用于找到额外的数据结构

后续的 AST 节点或额外数据结构通常还包含更多索引，可能指向更多节点、额外数据结构或 token。例如，一个 fn_decl 指向一个 fn_proto，后者指向一个额外的数据结构 FnProto，而它又为每个参数指向一个 AST 节点。

有哪些可用数据以及如何访问它们取决于 tag。你必须阅读 lib/std/zig/Ast.zig 中的注释或阅读解析器源码，才能确切知道设置了哪些数据。

解析是如何工作的

在对解析器的内部状态和生成的 AST 结构有了扎实的理解之后，我们现在可以学习解析器究竟是如何解析某个 token 流的了。

抽象地说，解析器的工作方式是检查 token 流中的当前 token，并以它为上下文来确定下一个 token 可以或应该是什么。例如，在解析 fn foo 的 token 流时，看到的第一个 token 是 .keyword_fn，期望的下一个 token 应该是一个标识符。如果不是标识符，那就是一个语法错误。

与词法分析器不同，解析器关心 token 的顺序是否合理。词法分析器只是盲目地生成 token，因此诸如 fn pub var foo i32 } { 这样的无效语法也会产生一个合法的 token 流。但解析器看到这个 token 流后会产生错误，因为它毫无意义。

接下来，让我们具体看看解析器如何解析下面这个简单的 Zig 文件。

var x = 7;

pub fn inc() callconv(.C) void {
  x += 1;
}

解析 Zig 文件

主入口是 parse() 函数，它接收一个 Zig 文件的完整源代码。它会初始化解析器状态，然后调用 parseContainerMembers() 来解析 Zig 文件的成员。Zig 文件隐式地就是一个 struct，所以解析器实际上是在解析一个 struct。

随后进入一个 while 循环，查看当前 token 以确定接下来期望什么。其结构大致如下：

while (true) {
    switch (p.token_tags[p.tok_i]) {
        .keyword_var => ...
    }
}

根据当前 token，它决定接下来期望什么。我们的第一个 token 是 .keyword_var，因为示例文件定义了一个变量。这最终会走到 parseVarDecl 来解析变量声明。此时还有很多其他合法的 token：comptime、fn、pub 等。

解析变量声明

我们在 Zig 文件中遇到的第一个成员是变量声明。调用链最终到达 parseVarDecl，我们将在这里看到第一个 AST 节点的创建。下面是一个简化版本。

fn parseVarDecl(p: *Parser) !Node.Index {
    const mut_token = p.eatToken(.keyword_const) orelse
        p.eatToken(.keyword_var) orelse
        return null_node;

    _ = try p.expectToken(.identifier);
    const type_node: Node.Index = if (p.eatToken(.colon) == null) 0 else try p.expectTypeExpr();
    const init_node: Node.Index = if (p.eatToken(.equal) == null) 0 else try p.expectExpr();

    return p.addNode(.{
        .tag = .simple_var_decl,
        .main_token = mut_token,
        .data = .{
            .lhs = type_node,
            .rhs = init_node,
        },
   });
}

这段代码“吃掉”第一个 token：要么是 const 要么是 var（这个解析函数两者都处理）。“吃掉”token 意味着它被消费：返回当前 token，并且解析器状态中的 tok_i 索引递增。如果既不是 const 也不是 var，则返回 null_node 值，沿调用链向上产生错误（变量声明必须以 const 或 var 开头）。

接着，我们期望变量名是一个 identifier。如果 token 不是 identifier，expectToken 函数会返回错误。例如，如果我们写 var 32，解析器就会在这里创建并存储“期望标识符但得到整数字面量”的错误。

再接着，有几种可能的情形。通过对 eatToken 使用条件判断，我们可以决定下一步做什么。如果下一个 token 是冒号，我们就期望找到一个类型表达式。例如 var x: u32。但类型表达式是可选的，我们的实际示例中没有，所以这里会把 type_node 设为零。

然后我们检查下一个 token 是否是等号。如果是，我们就期望找到一个变量初始化表达式。我们的变量声明确实有，所以这里会创建一个 AST 节点并返回其在节点列表中的索引。我们不会深入看 expectExpr。

注意，这产生了多种合法的变量声明语法，例如 var x、var x: i32 和 var x: i32 = 42。但也要注意什么是不合法的，例如 var : i32 x 或 var = 32。

最后，我们调用 addNode 来创建 Node。它返回节点列表中的索引。在这里，我们创建了一个 .simple_var_decl。如果你查看 .simple_var_decl 的注释，它会说明 lhs 指向类型表达式 AST 节点的索引（如果没有类型表达式则为零），rhs 指向初始化表达式 AST 节点的索引（如果没有初始化则为零）。

parseVarDecl 函数返回 .simple_var_decl AST 节点的索引。它最终一路返回到我们最初所在的 parseContainerMembers 函数，并被存入 scratch 状态。稍后我们会解释这个 scratch 状态如何使用。目前，while 循环继续解析并寻找下一个 token，也就是开启我们函数定义的 .keyword_pub。

解析函数定义

一旦找到 .keyword_pub，调用链最终会到达 parseFnProto 和 parseBlock，分别解析我们的函数原型和函数体。让我们聚焦于 parseFnProto，因为它做了一件我们还没见过的事情。

下面是 parseFnProto 的简化且不完整的版本：

fn parseFnProto(p: *Parser) !Node.Index {
    const fn_token = p.eatToken(.keyword_fn) orelse return null_node;

    // We want the fn proto node to be before its children in the array.
    const fn_proto_index = try p.reserveNode();

    _ = p.eatToken(.identifier);
    const params = try p.parseParamDeclList();
    const callconv_expr = try p.parseCallconv();
    _ = p.eatToken(.bang);

    const return_type_expr = try p.parseTypeExpr();
    if (return_type_expr == 0) {
        try p.warn(.expected_return_type);
    }

    return p.setNode(fn_proto_index, .{
        .tag = .fn_proto_one,
        .main_token = fn_token,
        .data = .{
            .lhs = try p.addExtra(Node.FnProtoOne{
                .param = params.zero_or_one,
                .callconv_expr = callconv_expr,
            }),
            .rhs = return_type_expr,
         },
    })
}

这与解析变量声明类似。这里出现了几个新模式。首先，可以看到如果没有设置返回类型，会存储一条警告而不是中止整个解析。解析器常常会在出错的情况下尝试继续解析，这就是其中一种场景。

其次，fn_proto_one tag 的 lhs 值是指向 extra_data 的索引。这展示了额外数据是如何写入的。addExtra 函数接收一个包含所有值的结构体，以类型安全的方式将其编码进 extra_data，然后返回额外数据中起始位置的索引。正如前面所示，该 AST 节点的使用者会确切知道 fn_proto_one tag 有多少个字段，并能读取这些信息。

完成 AST

解析会对整个程序递归进行，不断构建 AST 节点。解析结束时，解析器返回一个 Ast 结构体，其结构如下所示：

pub const Ast = struct {
    source: [:0]const u8,
    tokens: TokenList.Slice,
    nodes: NodeList.Slice,
    extra_data: []Node.Index,
    errors: []const Error,
};

到了这一步，如果你读过词法分析那一页，并完全理解了解析器和 AST 节点的构造，那么这些字段的含义应该都很清楚了。AST 包含完整源码 source（用于确定标识符字符串、错误消息等）、token 列表 tokens、AST 节点列表 nodes、AST 节点的额外数据 extra_data，以及可能累积的错误列表 errors。

接下来是 AstGen 过程。