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

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

MultiArrayList

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

在解释 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 字节内存。包含四个 Tree 的数组占用 32 字节内存。

MultiArrayList 同样是一个动态分配的列表。但其中存储类型的每个字段都存放在各自独立的连续数组中。这带来了两个主要好处：（1）因对齐而浪费的字节更少；（2）缓存局部性更好。这两点通常都能带来更好的性能。

以我们的 Tree 结构体为例，MultiArrayList(Tree) 的存储方式如下：

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

结构体的每个字段都存储在各自独立的连续数组中。包含四个 Tree 的数组仅使用 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 节点可能需要的额外信息列表。例如，对于结构体，extra_data 包含其所有成员的完整列表。这同样是面向数据设计的体现；另一种做法是将额外数据直接放在 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 表示整数字面量，builtin_call 表示对 @enumToInt 这类内置函数的调用。

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 标签上方的注释，或阅读源码，或两者结合。

在这种情况下，lhs 和 rhs 中的索引值是 NodeList 中 Node 的数组索引。因此，你会在 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] 只是指向了另一个索引。并非如此，对于 .fn_proto 来说，lhs 指向的只是 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，因此解析器实际上是在解析一个结构体。

这会进入一个 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 开头）。

接下来，我们期待一个作为变量名的标识符。如果 token 不是标识符，expectToken 函数会返回错误。例如，如果我们写了 var 32，那么解析器就会在此处创建并存储一个错误，提示它期待的是标识符，却得到了一个整数字面量。

接下来有几种可能的情况。通过在 eatToken 外层使用条件判断，我们可以决定下一步做什么。如果下一个 token 是冒号，我们就期待找到一个类型表达式。例如 var x: u32。但类型表达式是可选的，而我们的实际示例中并没有，因此会将 type_node 设为 0。

然后我们检查下一个 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 节点的索引（如果没有类型表达式则为 0），rhs 指向初始化表达式 AST 节点的索引（如果没有初始化则为 0）。

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 标签的 lhs 值是 extra_data 的索引。这展示了额外数据是如何写入的。addExtra 函数接收一个包含所有值的结构体，并以类型安全的方式将其编码到 extra_data 中，然后返回其在额外数据中的起始索引。如前所述，该 AST 节点的使用者会确切知道对于 fn_proto_one 标签应该期待多少个字段，并据此读取这些信息。

最终确定 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 是完整源代码（用于确定标识符字符串、错误信息等），tokens 是 token 列表，nodes 是 AST 节点列表，extra_data 是 AST 节点的额外数据，errors 则是可能累积的错误列表。

接下来是AstGen 流程。