本文承接《Zig 中间表示》的内容，继续讨论 Zig 程序编译的下一步：从 ZIR 指令序列，经过语义分析的过程，生成 AIR 指令序列。

本文翻译自 Mitchell Hashimoto 关于 Zig 的系列博客第四篇：

• Zig Sema: ZIR => AIR (https://mitchellh.com/zig/sema)

语义分析是 Zig 程序编译的核心环节，且它包括了 Zig 语言独特的设计：编译时求值。不同于其他语言常常需要使用额外的语法来定义和计算类型（泛型），Zig 采用编译时求值的方式来完成类型计算。这使得很多原本需要宏或者模板的逻辑，现在可以使用跟主语言相同的语法来编写代码完成。

我在推特上发文讲过：

Zig 的泛型是用编译时类型计算来实现的。这有一个挺有趣的提示：如果 Zig 的编码体验提升，很多类型计算方法（类型论的实现）可以作为 Zig 库来提供，而不用像之前一样嵌入到编译器里作为编译器的内部实现。这可能是一个开放编译时计算的方向。

本文讨论了 AIR 制导生成的主要流程，但是没有深入讨论编译时求值的细节，也没有包括变量活性分析的内容，比较可惜。

以下原文。

AstGen 阶段之后是 Sema 阶段。这一编译阶段接收 AstGen 阶段输出的 ZIR 指令序列，并生成 AIR 指令序列。AIR 是“经过分析的中间表示（Analyzed Intermediate Representation）”的缩写，是一个完全类型化的中间表示。作为对比，ZIR 是一个无类型的中间表示。AIR 可以直接转换为机器代码。

正如 AstGen 一文中所指出的，ZIR 不完全类型化的一个原因，是完全类型化一个 Zig 程序需要进行编译时求值，才能完全实现泛型类型等功能。因此，Sema 阶段还会执行 Zig 程序的所有编译时求值。这就是魔法发生的地方！

AIR 是按函数而不是按文件生成的，就像 ZIR 或 AST 一样。本文将重点介绍如何将函数体从 ZIR 指令转换为 AIR 指令。

原注：有一些 AIR 指令是在文件范围内生成的，因此不能武断地说 AIR 是按函数生成的。然而，理解文件范围的 AIR 过程还需要更深入地讨论编译过程，本文将作为理解那些过程的重要基石。

AIR 是什么样的？

让我们看一个 AIR 的例子：

1
2
3

export fn add(a: u32, b: u32) u32 {
    return a + b;
}

1
2
3
4
5
6
7

# Begin Function AIR: add:
  %0 = arg("a", u32)
  %1 = arg("b", u32)
  %2!= dbg_stmt(2:5)
  %3 = add(%0!, %1!)
  %4!= ret(%3!)
# End Function AIR: add

你可以使用 zig build-obj --verbose-air <file.zig> 指令查看任意程序的 AIR 指令序列。这需要一个 DEBUG 模式构建的 Zig 编译器，可以查看 Zig 仓库的 Wiki 页面了解如何构建。

AIR 是按函数生成和打印的。上面的输出包含了以注释形式注明的 add 函数的 AIR 输出的行。请注意，只有导出或被引用的函数才会生成 AIR 指令，因为 AIR 是按需生成的。因此，为了调试目的，我通常会导出我想要查看 AIR 的函数。

如果你已经阅读了关于编译器先前阶段的内容，你会注意到 AIR 的打印形式跟 ZIR 非常相似。虽然如此，并且在许多情况下 ZIR 和 AIR 甚至有相同的指令标签名称，但是 AIR 是一个完全独立的中间表示。

%1 是指令的索引。当它后面跟着 ! 时，意味着该指令未被使用或未被任何其他已知部分的 Zig 程序引用。在上面的示例中，加法对应的指令 %0 和 %1 用于构造 %3 指令，而 %3 则被返回指令使用。但是，调试语句 %2 和返回结果 %4 都未被使用。在编译器后端将 AIR 转换为最终格式时，可以按需使用这些信息。

原注：如前所述，有一些 AIR 是在文件范围而不是函数范围内生成的。例如，文件范围的变量初始化、编译时块等。目前无法打印此类 AIR 的内容。文件范围的 AIR 通常只是一系列常量指令，因为它总是在编译时求值。

剖析 AIR 结构

在讨论 ZIR 如何转换成 AIR 之前，我将首先介绍 AIR 的格式并剖析单条 AIR 指令。理解 AIR 的结构有助于理解 AIR 是如何构造的。

AIR 的结构和 ZIR 非常相似，但也有一些细微的差别：

1
2
3
4
5

pub const AIR = struct {
    instructions: std.MultiArrayList(Inst).Slice,
    extra: []const u32,
    values: []const Value,
};

跟 ZIR 一样，AIR 在 instructions 字段中存储了一系列指令。再有，跟 ZIR 和 AST 一样，指令可能在 extra 字段存储相关的额外数据。这两个字段的工作方式跟 ZIR 和 AST 中的同名字段一样。如果你对这部分知识还不熟悉，我建议你回顾前几篇文章相关的内容，尤其是 AST 构造是如何填充 extra 字段的细节。

原注：我略过了对 MultiArrayList 的介绍，因为这部分信息在前面的文章里已经详细解释过了。

values 是 AIR 结构独有的新字段。它包含了从 ZIR 的编译时执行中获得的已知值。AIR 指令可以引用编译时已知的值。例如，如果源文件中有一个 const a = 42; 语句，那么值 42 将存储在 values 列表中，因为它是编译时已知的。我们稍后将看到更多关于编译期值的例子。

请注意，诸如字符串常量的字符串表等字段不存在。AIR 构建过程和使用 AIR 的代码生成过程仍然可以访问 ZIR 指令序列，也就可以访问 ZIR 的字符串表中的数据。

剖析单条 AIR 指令

Inst 代表了单条 AIR 指令的结构：

1
2
3
4

pub const Inst = struct {
    tag: Tag,
    data: Data,
};

这个结构跟 ZIR 的 Inst 结构是一致的：枚举类型的 tag 字段 + 标签对应的 data 字段。AIR 的标签和数据类型不同于 ZIR 的类型，但在功能上是相同的。

让我们看一个简单的例子。当语义分析确定一个值是常量时，它创建了 .constant 指令。常量标记指令的数据是 ty_pl 字段，其中包含常量的类型，而有效载荷是一个索引，指向值数组中的编译时已知值。

1

const c = 42;

1

%0 = constant(comptime_int, 42)

1
2
3
4
5
6
7
8
9

Inst{
    .tag = .constant,
    .data = .{
        .ty_pl = . {
            .ty = Type.initTag(.comptime_int),
            .pl = 7, // index into values
        },
    },
};

上面的代码块展示了一段 Zig 代码，它对应的 AIR 文本表示和内部结构表示。注意在 AIR 中不存在 c 标识符，因为用于产生 AIR 的 ZIR 只包括赋值语句的右值。

值、类型和带类型的值

Sema 阶段经常使用以下三种类型：值（Value）、类型（Type）和带类型的值（TypedValue）。

Value 表示编译时已知的值，例如整数、结构体等。Type 是编译时已知的类型，例如 u8 等（注意，所有类型都是编译时已知的）。而 TypedValue 是一个具有确切已知类型的值：例如将值 42 与类型 u16 配对。

可能看起来有些奇怪的是，类型在 Zig 中也是有效的值。类型是类型为 type 的值。例如，在 Zig 中，可以编写 const c = u8 语句，其中 c 是类型为 type 的值，u8 是 c 的值。我们将在下面展示许多这些情况的示例，以使其更加直观。

值

Value 结构定义如下所示：

1
2
3
4

pub const Value = extern union {
    tag_if_small_enough: Tag,
    ptr_otherwise: *Payload,
}

一个类型（type）的值具有描述其值类型（kind）的标签。我在这里故意使用 kind 而不是 type 是因为一个值是无类型的。尽管在某些情况下，类型可以从值中直接推断出来。某些标签值没有有效载荷，而其他情况下则需要有效载荷。ptr_otherwise 字段是指向有效载荷的指针，其中包含获取该值所需的更多信息。

Payload 类型是指向更具体有效载荷类型的 Payload-typed 字段的指针。这是 Zig 中使用多态类型的一种方式。然后，Zig 代码可以使用 @fieldParentPtr 指令确定完整类型。这是 Zig 中常见的模式，详细解释超出了本文的范围。请搜索 @fieldParentPtr 指南以了解其工作原理。

译注：这段相关代码有一个大重构，可以查阅 PR-15569 了解细节。

整数

接下来看一个整数值的例子，42 可以被表示成一个 Value 结构的实例：

1
2
3
4
5
6

Value{
    .ptr_otherwise = &Payload.U64{
        .tag = .int_u64,
        .data = 42,
    },
};

原注：这个值不是完全正确的。ptr_otherwise 字段指向 Payload 结构而不是完整的 Payload.U64 结构。不过，这种表现形式能更好的展示指针背后的内容，所以我会在本文中一致使用这种形式。

可以看到，42 对应到 int_u64 标签。这是因为 int_u64 被用于表示所有可以用 u64 表示的值。这并不意味着实际使用的 42 是 u64 类型，它可能是 u8 或者 u16 或者其他。不与 Type 关联的 Value 是无类型的。或者，如果你觉得我们这里总归是有一个类型标签，你可以认为这个值没有对应到一个准确的类型。

类型的值

Zig 的类型也是值。例如，语句 const c = u8 是完全有效的 Zig 代码：它将类型 u8 赋值到常量 c 上，而 c 本身是 type 类型的。这可能会非常令人困惑，随着类型的值在实际语义分析中的使用，它会变得更加令人困惑。因此，我将在这里提前解释。

作为一个值，常量 u8 可以用下面的 Value 表示：

1
2
3

Value{
    .tag_if_small_enough = .u8_type,
};

这个值没有 payload 内容，因为它可以被 .u8_type 完全清楚的表示：值是 u8 类型。

这个值本身仍然是无类型的。在这个场景里，我们可以简单的知道值的类型，因为 u8_type 的类型除了 type 没有别的可能。但是，从技术上说，u8 对应的 Value 实例仍然是无类型的。

原注：例如，这个事实允许 Zig 在未来定义一个 inttype 关键字来代表所有整数类型，此时 u8_type 就可能被解释成 type 或 inttype 之一。

我们来看一个更复杂的类型的例子，const c = [4]bool 对应的 Value 表示如下：

1
2
3
4
5
6
7
8
9

Value{
    .ptr_otherwise = &Payload.Ty{
        .tag = .ty,
        .data = Type{
            // .tag = .array
            // type data including element type (bool), length (4), etc.
        },
    },
};

这个值具有 .ty 标签（type 的缩写），这代表这个值是某种类型。值的有效载荷是一个 Type 结构，其值描述了一个由四个 bool 元素组成的数组。我们将在下一节讨论 Type 结构的细节。这里的关键点是，上述 Value 实例的值是一个数组类型，而不是一个数组值。

如果还有不明白的地方，你可以查看源代码中 Type 结构的 toValue 函数。Type 实例总是可以被转变成一个 Value 实例，因为类型在 Zig 中总是一个值，但是值不一定总是类型。

译注：原文解释了很多，反而把事情搞得有点复杂了。应该说，在绝大多数语言里，类型都不是值，它们需要各种特殊的语法来进行类型计算和泛型标记。Zig 把类型作为编译时已知的值，暴露了一系列操作类型的函数，使得泛型和函数重载可以使用编译时求值技术编写 Zig 代码完成，而不需要独特的语法。

类型

Type 结构的定义和 Value 结构是一样的，但是定义成一个新的类型以做区分：

1
2
3
4

pub const Type = extern union {
    tag_if_small_enough: Tag,
    ptr_otherwise: *Payload,
}

这里我们没有太多补充，因为大部分内容跟 Value 结构一样。让我们看一看 [4]bool 类型是怎么表示的，免得我们完全不介绍一个具体例子：

1
2
3
4
5
6
7
8
9

Type{
    .ptr_otherwise = &Payload.Array{
        .tag = .array,
        .data = .{
            .len = 4,
            .elem_type = Type{.tag_if_small_enough = .bool},
        },
    }
}

带类型的值

TypedValue 其实就是一个 Type 和一个 Value 组成的结构，从而将值绑定到一个确切的类型上。只有这样，值的类型才是准确已知的：

1
2
3
4

pub const TypedValue = struct {
    ty: Type,
    val: Value,
};

剖析 Sema 结构

在 AstGen 阶段之后，Zig 编译器将进行 Sema 阶段，Sema 是语义分析（Semantic Analysis）的缩写。Sema 也是主要负责此阶段的结构体的名称。Sema 的源代码位于 src/Sema.zig 文件内。这是一个非常大的文件（在编写本文时超过 18000 行），它的文档注释自称为 “Zig 编译器的核心”。

译注：0.11 版本上，Sema.zig 已经超过 36000 行。

Sema 有许多公共接口，但最重要的是 analyzeBody 函数。Sema 结构体有许多用于内部状态的字段。我们不会列举所有字段，但下面列出了一些主要的字段。为了便于解释类似的字段，这些字段的顺序与源代码中的顺序不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

pub const Sema = struct {
    mod: *Module,
    gpa: Allocator,
    arena: Allocator,
    perm_arena: Allocator,

    code: Zir,
    owner_decl: *Decl,
    func: ?*Module.Fn,
    fn_ret_ty: Type,

    air_instructions: std.MultiArrayList(Air.Inst) = .{},
    air_extra: std.ArrayListUnmanaged(u32) = .{},
    air_values: std.ArrayListUnmanaged(Value) = .{},
    inst_map: InstMap = .{},

    // other fields...
};

第一组字段是 Sema 过程的主要输入：

• gpa 用于分配在 Sema 过程和声明生命周期之后仍然存在的数据。
• arena 用于分配在 Sema 之后将被释放的临时数据。
• perm_arena 用于分配与正在进行语义分析的声明的生命周期相关联的数据。
• mod 是正在分析的模块。本文内容不涵盖模块，但模块封装了单个程序中的所有 Zig 代码。本文将忽略所有跟模块相关的接口。

第二组字段是 Sema 进行语义分析的输入：

• code 是包含正在分析的声明的文件的 ZIR 指令序列。
• owner_decl 通常是当前正在分析的声明，例如函数、comptime 块、测试等。

当分析函数时，func 和 fn_ret_ty 存储了可能得额外信息。

第三组字段是 Sema 过程的输出。这些输出主要是构建 Air 结构的字段。这些字段在整个 Sema 过程中被填充，并用于构建最终的 Air 结果。

其中，inst_map 字段最为重要。它是一个 ZIR 到 AIR 的映射，在整个 Sema 过程中都会使用。并非所有的 ZIR 指令都会产生 AIR 指令，但是 Sema 还是经常使用这个映射以使 AIR 指令可以引用稍后解析的特定 ZIR 指令：例如加法操作数、函数参数等。

分析函数体

Sema 结构上的核心接口是 analyzeBody 函数。这个函数用于分析函数体、循环体或代码块体等对应的 ZIR 指令序列，并产生对应的 AIR 指令序列。最简单的例子是函数体。下面是一个具体的例子：

1
2
3

export fn add() u32 {
    return 40 + 2;
}

1
2
3
4
5
6
7
8
9

# Begin Function AIR: add:
  %1 = constant(comptime_int, 40)
  %2 = constant(comptime_int, 2)
  %3 = constant(comptime_int, 42)
  %4 = constant(u32, 42)

  %0!= dbg_stmt(2:5)
  %5!= ret(%4!)
# End Function AIR: add

原注：可以使用 zig build-obj --verbose-air example.zig 指令打印导出函数的 AIR 指令序列。

从上述 AIR 指令序列中，我们可以直观地知道发生了什么事情。粗略地说，这些指令大致执行了以下步骤：

1. 我们看到一个无类型的整数常数 40 - 对应 %1 指令。
2. 我们看到一个无类型的整数常数 2 - 对应 %2 指令。
3. 我们执行了编译时求值，得到加法的结果：无类型的整数常数 42 - 对应 %3 指令。
4. 常量 42 关联到类型 u32 上（%4 指令）。这不需要任何转换，因为值 42 可以自动匹配到 u32 类型上。这个类型关联是必要的，因为返回类型被定义成 u32 类型。
5. 返回 %4 输出的值 - 对应 %5 指令。

太棒了！这里有一些冗长之处，但很明显可以看出 add 函数的编译过程。此外，可以看到在这个阶段进行了编译时求值：40 + 2 对应的加法操作已经完成，因此结果已经预先知道。当这段代码最终被转换为机器代码时，实际的加法结果已经预先计算好了。

译注：在新版 Zig 编译器中，所有中间 AIR 都能被优化，最终只产生一条 %4!= ret(<u32, 42>) 指令。

接下来，让我们逐步了解这个 AIR 是如何生成的。

逐步分析函数

函数体 AIR 主要通过 analyzeBodyInner 生成。这个函数会按顺序迭代分析每个 ZIR 指令，并为每条 ZIR 指令生成零或多条 AIR 指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const result = while (true) {
    const inst = body[i];
    const air_inst: Air.Inst.Ref = switch (tags[inst]) {
        .alloc                        => try sema.zirAlloc(block, inst),
        .alloc_inferred               => try sema.zirAllocInferred(block, inst, Type.initTag(.inferred_alloc_const)),
        .alloc_inferred_mut           => try sema.zirAllocInferred(block, inst, Type.initTag(.inferred_alloc_mut)),
        .alloc_inferred_comptime      => try sema.zirAllocInferredComptime(inst, Type.initTag(.inferred_alloc_const)),
        .alloc_inferred_comptime_mut  => try sema.zirAllocInferredComptime(inst, Type.initTag(.inferred_alloc_mut)),
        .alloc_mut                    => try sema.zirAllocMut(block, inst),
        // hundreds more...
    };

    try sema.inst_map.put(sema.gpa, inst, air_inst);
    i += 1;
}

这段代码清楚展示了 ZIR 翻译成 AIR 的过程。你可以打印 Zig 程序对应的 ZIR 指令序列并逐个分析每个指令如何生成对应的 AIR 指令。上述 add 函数的 ZIR 指令序列如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

%0 = extended(struct_decl(parent, Auto, {
  [25] export add line(6) hash(4ca8d4e33898374bdeee80480f698dad): %1 = block_inline({
    %10 = func(ret_ty={
      %2 = break_inline(%10, @Ref.u32_type)
    }, body={
      %3 = dbg_stmt(2, 5)
      %4 = extended(ret_type()) node_offset:8:5
      %5 = int(40)
      %6 = int(2)
      %7 = add(%5, %6) node_offset:8:15
      %8 = as_node(%4, %7) node_offset:8:15
      %9 = ret_node(%8) node_offset:8:5
    }) (lbrace=1:21,rbrace=3:1) node_offset:7:8
    %11 = break_inline(%1, %10)
  }) node_offset:7:8
}, {}, {})

其中，函数体从 %3 指令开始，到 %9 指令结束。因此，analyzeBodyInner 分析 add 函数体时，看到的第一条指令是 %3 指令。%2 和 %10 将会在早些时候被分析，我们会在后面讨论这个过程。

%3: dbg stmt

第一条分析的指令是一个 .dbg_stmt 指令。在 analyzeBodyInner 的主循环代码中，我们可以看到这将引导向 zirDbgStmt 分支。该分支的代码经简化后如下所示：

1
2
3
4
5
6
7
8
9
10

fn zirDbgStmt(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!void {
    const inst_data = sema.code.instructions.items(.data)[inst].dbg_stmt;
    _ = try block.addInst(.{
        .tag = .dbg_stmt,
        .data = .{ .dbg_stmt = .{
            .line = inst_data.line,
            .column = inst_data.column,
        } },
    });
}

这是一个很好的、简单的翻译 ZIR 到 AIR 的例子。没有比这更简单的了。在这种情况下，dbg_stmt ZIR 指令几乎一比一的被翻译成 dbg_stmt AIR 指令。这生成了之前显示的 %0 AIR 指令：

1

%0!= dbg_stmt(2:5)

%4: extended(ret type())

类似地，ZIR 指令 .extended 会引导调用 zirExtended 函数，其主循环分析子操作码（child opcode）并在遇到 .ret_type 时调用 zirRetType 函数。zirRetType 函数内容如下：

1
2
3
4
5
6
7
8
9

fn zirRetType(
    sema: *Sema,
    block: *Block,
    extended: Zir.Inst.Extended.InstData,
) CompileError!Air.Inst.Ref {
    const src: LazySrcLoc = .{ .node_offset = @bitCast(i32, extended.operand) };
    try sema.requireFunctionBlock(block, src);
    return sema.addType(sema.fn_ret_ty);
}

被分析函数中的返回类型可以在 Sema 的 fn_ret_ty 字段中找到。addType 函数将为类型定义添加一条指令。对于我们的函数，结果类型是 u32 类型。这是一个常用类型，因此不会生成额外的指令。

为了进行实验，如果您将返回值更改为一个不常用的类型 u9 那么 AIR 会生成以下指令：

1

%5 = const_ty(u9)

%5: int(40)

下一条指令是对应常数 40 的 %5 指令。它会引导调用 zirInt 函数。zirInt 函数读取整数值，并调用 addConstant 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fn zirInt(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
    const int = sema.code.instructions.items(.data)[inst].int;
    return sema.addConstant(ty, try Value.Tag.int_u64.create(sema.arena, int));
}

pub fn addConstant(sema: *Sema, ty: Type, val: Value) SemaError!Air.Inst.Ref {
    const gpa = sema.gpa;
    const ty_inst = try sema.addType(ty);
    try sema.air_values.append(gpa, val);
    try sema.air_instructions.append(gpa, .{
        .tag = .constant,
        .data = .{ .ty_pl = .{
            .ty = ty_inst,
            .payload = @intCast(u32, sema.air_values.items.len - 1),
        } },
    });
    return Air.indexToRef(@intCast(u32, sema.air_instructions.len - 1));
}

addConstant 函数在 Sema 阶段的很多地方都会被调用，用于加入一个编译时已知的常量。其内部逻辑首先通过 addType 添加对应到最后一条指令的类型。对于我们这里的例子，它是 comptime_int 类型。因为它是一个常用类型，所以没有额外的指令产生。紧接着，常量值被加入到 air_values 中。最后，constant AIR 指令被加入到 air_instructions 中。最终结果就是下述 AIR 指令：

1

%1 = constant(comptime_int, 40)

需要注意的一点是，.constant 指令的有效负载引用了 air_values 中的索引。所有在编译时已知的值都存储在 air_values 中，指令中的任何引用都存储为 air_values 切片中的索引。

指令 %6 不做讨论，因为它跟 %5 基本相同，只是有一个不同的常量值。

%7: add(%5, %6)

下一条指令是我们遇到的第一条有实际逻辑操作的指令：执行加法。.add 指令引导调用 zirArithmetic 函数。这个函数用于许多二元数学操作中，其函数体如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fn zirArithmetic(
    sema: *Sema,
    block: *Block,
    inst: Zir.Inst.Index,
    zir_tag: Zir.Inst.Tag,
) CompileError!Air.Inst.Ref {
    const inst_data = sema.code.instructions.items(.data)[inst].pl_node;
    sema.src = .{ .node_offset_bin_op = inst_data.src_node };
    const lhs_src: LazySrcLoc = .{ .node_offset_bin_lhs = inst_data.src_node };
    const rhs_src: LazySrcLoc = .{ .node_offset_bin_rhs = inst_data.src_node };
    const extra = sema.code.extraData(Zir.Inst.Bin, inst_data.payload_index).data;
    const lhs = sema.resolveInst(extra.lhs);
    const rhs = sema.resolveInst(extra.rhs);

    return sema.analyzeArithmetic(block, zir_tag, lhs, rhs, sema.src, lhs_src, rhs_src);
}

这段代码中，需要特别关注 lhs 和 rhs 的复制。resolveInst 函数用于查找给定 ZIR 指令的 AIR 指令索引。因此，对于给定的 %5 和 %6 这两条 ZIR 指令，分别将 lhs 和 rhs 设置为它们的结果 AIR 索引。这些 AIR 指令是在先前的循环迭代中创建 .constant 指令时设置的。

ZIR 到 AIR 的映射在 analyzeBodyInner 循环的 inst_map 字段中维护。虽然也有其他一些逻辑可以更新这个状态，但是 body 循环是主要的逻辑。

下一步，代码逻辑进到 analyzeArithmetic 函数里。这是一个很长的函数，几乎所有代码都用于确定是否能够对此算术操作进行编译时分析。下面是关键的代码行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const maybe_lhs_val = try sema.resolveMaybeUndefVal(block, lhs_src, casted_lhs);
const maybe_rhs_val = try sema.resolveMaybeUndefVal(block, rhs_src, casted_rhs);

if (maybe_lhs_val) |lhs_val| {
    if (maybe_rhs_val) |rhs_val| {
        if (is_int) {
            return sema.addConstant(
                scalar_type,
                try lhs_val.intAdd(rhs_val, sema.arena),
            );
        }
    }
}

return block.addBinOp(.add, casted_lhs, casted_rhs);

这段代码首先调用 resolveMaybeUndefVal 函数。它接受一个 AIR 指令的索引，并尝试加载其编译时已知的值。这个表达式返回一个可空值，因为如果该值不能在编译时确定，则返回 null 值。

接下来，我们尝试解包这些可空值。如果我们能够找到 lhs 和 rhs 的编译时已知值，并且它们都是整数类型，那么我们可以进行编译时加法，得到最终的常量。这就是我们的程序生成结果为 42 的 .constant AIR 指令的过程：

1

%3 = constant(comptime_int, 42)

我在代码中包含了 block.addBinOp 语句，以避免值不是编译时已知的情况。这个语句将添加一个 .add AIR 指令进行运行时计算（而不是编译时）。为了进行实验：我们将常量 2 更改为变量，例如 var b: u32 = 2 语句，并将其用于加法运算。这将产生一个 .add 操作，因为变量不能在编译时操作。

%8: as_node(%4, %7)

下一条指令实现了安全类型转换。从 ZIR 的角度来看，这将加法结果转换为返回类型的值。具体来说，根据已知信息，我们需要将编译时整数 42 转换为 u32 类型。

.as_node 指令引导调用 zirAsNode 函数，最终调用到 coerce 函数的核心逻辑。coerce 函数在 Sema 过程中被广泛用于执行从一种类型到另一种类型的安全类型转换。

我将让读者自行研究这个函数。逻辑相当直接，但由于需要处理许多类型转换情况，所以会比较冗长。对于 comptime_int 到 u32 的转换，他首先确定该值能被 u32 类型表示，并将该值原样返回。类型转换不需要进行额外的处理。

%9: ret_node(%8)

最后，返回指令在 ZIR 中被编码为 ret_node 指令。这将引导调用 zirRetNode 函数，它创建一个带有结果的 .ret AIR 指令。创建该指令的所有相关知识点前面都已经讲过。

zirRetNode 函数始终返回 always_noreturn 值。这个值强制 analyzeBodyInner 循环退出，从而完成函数体 AIR 生成。

原注：返回语句是否总是完成函数体 AIR 生成？如果多个返回语句，又该怎么办？

返回语句总是完成当前块的 AIR 生成。不可达代码是非法的，并在 AstGen 期间被捕获，这意味着多个返回语句的唯一方式是它们位于不同的块中。因此，在函数的上下文中，多个返回语句是可以的，因为它将递归进入多个 analyzeBodyInner 调用。

编译时不可知

上面第一个示例有点无聊，因为所有的逻辑都是编译时可知的。编译时可知仅适用于 const 值，而不适用于 var 值，因此我们可以通过使用 var 来查看运行时加法的 AIR 指令序列：

1
2
3
4

export fn add() u32 {
    var b: u32 = 2;
    return 40 + b;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Begin Function AIR: add:
  %2 = constant(comptime_int, 2)
  %3 = constant(u32, 2)
  %6 = constant(comptime_int, 40)
  %8 = constant(u32, 40)

  %0!= dbg_stmt(2:5)
  %1 = alloc(*u32)
  %4!= store(%1, %3!)
  %5!= dbg_stmt(3:5)
  %7 = load(u32, %1!)
  %9 = add(%8!, %7!)
  %10!= ret(%9!)
# End Function AIR: add

译注：新版 Zig 编译器会报错 var b: u32 = 2 应该是一个常量，需要其他手段来写一个真正的变量做这个实验。

将常量 2 更改为变量赋值的值 2 会产生更多的 AIR 指令！现在我们有了使用 .alloc 进行分配的指令、使用 .store 进行值存储的指令，还可以看到运行时的 .add 操作。

这是一个很好的程序，可以用来学习和追踪 AIR 指令的生成过程。由于它遵循了我们之前示例中的许多相同的代码路径，我将把这个函数编译过程的分析作为读者的练习。

编译时目标平台仿真

对于编译时计算的代码，Zig 编译器将在必要时模拟目标平台的特性。这是一个至关重要的功能，使得在 Zig 中进行编译时计算变得安全且可行。

在 @floatCast 的实现中可以看到这个功能的一个例子：

1
2
3
4
5
6
7
8

const target = sema.mod.getTarget();
const src_bits = operand_ty.floatBits(target);
const dst_bits = dest_ty.floatBits(target);
if (dst_bits >= src_bits) {
    return sema.coerce(block, dest_ty, operand, operand_src);
}

return block.addTyOp(.fptrunc, dest_ty, operand);

该函数通过 getTarget 获取有关目标平台的信息，然后确定目标平台上浮点数支持的位数。如果目标类型的位数多于源类型，可以安全地强制转换类型。否则，浮点数将被截断。

完成语义分析过程

Sema 过程为每个函数调用一次，且仅针对每个被引用的声明调用一次，而不是遍历每个声明。为了确定所有被引用的声明，Sema 从处理入口点函数开始查找。

这实现了 Zig 的延迟分析能力，意味着除非引用了声明，否则某些错误不会产生编译器错误。这个特性使 Zig 的编译过程非常快速，生成的代码更小，因为只编译了被引用的代码，但有时会导致令人困惑的行为。

译注：为了绕过这里的引用问题，Zig 有一个内部开洞的 std.testing.refAllDecls 函数。可以阅读 ISSUE-12838 了解更多细节。

基于本文介绍的基本知识，你现在应该能够跟踪任何 Zig 程序并确定它如何转换为 AIR 指令序列。请记住经常使用 zig ast-check 和 zig build-obj --verbose-air 命令来查看 Zig 编译器生成的内容。

语义分析完成后，AIR 指令序列将传递给 CodeGen 过程，并在该过程中被转换为最终格式。CodeGen 是编译器前端和多个后端之间的边界。后端可以是 LLVM 或诸如 WASM 之类的本机后端。

本文承接《Zig 词法分析和语法解析》的内容，继续讨论 Zig 程序编译的下一步：从抽象语法树（AST）中生成中间表示（IR）。

本文翻译自 Mitchell Hashimoto 关于 Zig 的系列博客第三篇：

• Zig AstGen: AST => ZIR (https://mitchellh.com/zig/astgen)

翻译本文的过程中，我越来越回想起自己使用 Perl 6 做编译实习作业的时候。通过 Perl 6 内嵌的 Grammar 语法，我基本把词法分析和语法分析的内容给快速解决了。余下的大部分时间都在完成从 AST 到课程定义的中间表示的翻译，数据流分析和生成 riscv 汇编代码的工作。应该说，北京大学仿照虎书内容做的编译实习课程还是很有含金量的。

感兴趣的读者可以查看我当时的代码仓库，其中包括一个完整的 PDF 报告。

以下原文。

构建出抽象语法树（AST）后，许多编译器的下一步是生成中间表示（IR）。AST 是一棵树，而 IR 通常开始为程序的各个块，例如文件、函数等，创建一系列指令。这种指令序列的格式更容易进行优化分析和转换为可执行的机器码。

Zig 编译器具有多个中间表示。AST 首先通过 AstGen 的阶段转换为 Zig 中间表示（ZIR）。ZIR 是一种无类型的 IR 形式。每个 Zig 文件对应一系列 ZIR 序列。

ZIR 是什么样的？

讨论 ZIR 的结构及其创建过程之前，我们先看一个简单的例子来初步建立对 ZIR 的印象。目前，你不需要理解下面展示的 ZIR 是什么含义。

给定一个简单的 Zig 源文件：

1
2
3
4
5

const result = 42;

export fn hello() u8 {
    return result;
}

其对应的 ZIR 指令序列打印如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

%0 = extended(struct_decl(parent, Auto, {
  [24] result line(0) hash(193c9ec04fd3f33e5e849a85f0c3b7fd): %1 = block_inline({
    %2 = int(42)
    %3 = break_inline(%1, %2)
  }) node_offset:1:1
  [32] export hello line(2) hash(322ad1340dd6faf97c80f152e26dfdd4): %4 = block_inline({
    %11 = func(ret_ty={
      %5 = break_inline(%11, @Ref.u8_type)
    }, body={
      %6 = dbg_stmt(2, 5)
      %7 = extended(ret_type()) node_offset:4:5
      %8 = decl_val("result") token_offset:4:12
      %9 = as_node(%7, %8) node_offset:4:12
      %10 = ret_node(%9) node_offset:4:5
    }) (lbrace=1:22,rbrace=3:1) node_offset:3:8
    %12 = break_inline(%4, %11)
  }) node_offset:3:8
}, {}, {})

ZIR 只是一个内部中间表示，并不需要是一个稳定的格式，因此今天的 Zig 编译器未必对上述源文件产生和这里展示的 ZIR 指令序列相同的输出。不过，对于 ZIR 的初见来说，上面展示的内容应该是足够接近的了。

需要注意的是，ZIR 将程序的实际逻辑分解为更细粒度的指令。ZIR 指令可以通过它们的索引进行引用。如上面所示，可以使用 % 符号来索引。例如，指令 9 将结果引用转换为 hello 函数的返回类型。

原注：如何打印 ZIR 指令序列？

如果你从源码中用 DEBUG 模式构建得到了 Zig 编译器，你可以通过 zig ast-check -t <file> 命令生成任意 Zig 源文件对应的 ZIR 指令序列。编写一些简单的 Zig 程序并使用这一技巧生成对应的 ZIR 指令序列，是学习 AstGen 步骤的一个很好的方法。

为什么 ZIR 是无类型的？

ZIR 是一种无类型的中间格式。这并不意味着 ZIR 不知道类型，而是类型没有被完全计算。Zig 有两个语言定义特性与此相关。其一是 Zig 将类型作为一等值，其二是 Zig 将编译时求值作为泛型类型的机制。因此，在 AST 和 ZIR 格式中，类型可能仍然是未知的。

这很容易 ZIR 输出示例中验证。首先，让我们看一个大部分已经确定类型的形式：

1

const result: u32 = 42;

1
2
3
4
5
6
7

%0 = extended(struct_decl(parent, Auto, {
  [10] a line(0) hash(63c8310741c228c128abf6692d07292d): %1 = block_inline({
    %2 = int(42)
    %3 = as_node(@Ref.u32_type, %2) node_offset:1:16
    %4 = break_inline(%1, %3)
  }) node_offset:1:1
}, {}, {})

指令 %3 将无类型的 42 转换为 u32 类型。在这个简单的例子里，ZIR 看起来是完全具备类型的。

不过，仍然有不具备类型的指令。例如，指令 %2 没有对应的类型。虽然它对应了一个值为 int(42) 的常量，但是这个常量仍然可以被解释成 u8/u16/u32 等类型。直到 Zig 代码将无类型常量分配给有类型常量时，ZIR 才会产生类型强制转换指令，即 as_node 指令。

接下来，我们看一个明确无类型的形式：

1
2

const t = bool;
const result: t = 42;

1
2
3
4
5
6
7
8
9
10
11
12

%0 = extended(struct_decl(parent, Auto, {
  [16] t line(0) hash(243086356f9a6b0669ba4a7bb4a990e4): %1 = block_inline({
    %2 = break_inline(%1, @Ref.bool_type)
  }) node_offset:1:1
  [24] result line(1) hash(8c4cc7d2e9f1310630b3af7c4e9162bd): %3 = block_inline({
    %4 = decl_val("t") token_offset:2:10
    %5 = as_node(@Ref.type_type, %4) node_offset:2:10
    %6 = int(42)
    %7 = as_node(%5, %6) node_offset:2:14
    %8 = break_inline(%3, %7)
  }) node_offset:2:1
}, {}, {})

result 的类型是常量 t 被赋予的值。这种情况下，常量 t 的值是显而易见的。但是 Zig 允许为 t 赋值为任何编译时表达式。只要所有值都是编译时已知的，那么这意味着 t 的值几乎可以是任意 Zig 代码执行的结果。这是 Zig 的一个非常强大的特性。

鉴于这种动态的可能性，你可以看到分配给 result 的 ZIR 更加复杂。指令 %4 和 %5 加载由 t 标识的值，并将其强制转换为类型 type 的值。type 是类型对应的类型，而不是值的类型。然后指令 %7 做 as_node 强制转换，但这次类型操作数引用的是 ZIR 指令 %5 的结果，而不是静态值。

最后，我们看一个极端的例子：

1
2

const std = @import("std");
const result: std.ArrayListUnmanaged(u8) = .{};

这里我们不展示这两行代码对应的 ZIR 指令序列，因为它将是一大段文本。在这个例子中，result 的类型是通过函数 ArrayListUnmanaged 编译时求值生成的泛型类型。ZIR 无法指向 result 的预定义类型，因为在编译时求值之前根本不知道它的类型。

这就是为什么 ZIR 是无类型的：ZIR 是用于编译时求值和进一步语义分析的预备中间形式。在编译时求值阶段后，所有的类型都将被确定，并且可以形成完全具备类型的中间表示（AIR）。

AstGen 过程的解析

AstGen 是一个把 AST 转换为 ZIR 的阶段，其源代码位于 src/AstGen.zig 文件中。AstGen 不是一个公开导出的结构体，它只用于管理 ZIR 生成过程的内部状态。外部调用方调用的是 generate 函数，该函数接受一个 AST 树并返回整个树的 ZIR 指令序列。

AstGen 结构体有许多用于内部状态的字段。我们不会列举所有的字段，但下面显示了一些重要的字段。以下结构体的字段顺序与源代码中的顺序不同：

1
2
3
4
5
6
7
8
9
10
11

const Astgen = struct {
    gpa: Allocator,
    arena: Allocator,
    tree: *const Ast,

    instructions: std.MultiArrayList(Zir.Inst) = .{},
    extra: ArrayListUnmanaged(u32) = .{},
    string_bytes: ArrayListUnmanaged(u8) = .{},

    // other fields, not covered...
};

第一组字段是 AstGen 过程的输入：

• gpa 用于分配在 AstGen 过程之外还需存活的数据
• arena 用于分配仅在 ZIR 生成期间使用的临时数据，这些数据在返回 ZIR 之前被释放
• tree 是要转换为 ZIR 的 AST 示例

原注：为什么 arena 叫这个名字？

Arena allocator 是一种内存分配器的分类，它一次性分配和释放整个内存区域，而不是逐个追踪和释放单个项。它通常用于具有共同生命周期的分配，因为相比于追踪单个项，释放整个内存块要更容易且性能更好。有关分配器和 Zig 的基础知识，可以参考 What’s a Memory Allocator Anyways? 主题演讲。

第二组字段是 AstGen 过程的输出。这一组字段非常重要，因为它是生成的 ZIR 的核心结构：

• instructions 存储 ZIR 指令序列，该序列中的每个条目对应一个单独的指令。例如，前文 ZIR 输出中，这一字段的第 9 个条目将是 as_node(%7, %8) 指令。
• extra 是 ZIR 指令可能需要存储的额外数据。这与 AST 节点及其 extra_data 字段遵循相同的模式。如果您不了解 AST 中 extra_data 的存储访问模式，请查看上一篇文章进行复习，因为在 AstGen 过程中到处都使用了这种模式！
• string_bytes 是用于标识符、字符串字面量、文档注释等的字符串池。所有静态字符串都作为 AstGen 的一部分进行了池化，并且 ZIR 指令引用了该字符串字节列表中的偏移量，而不是存储字符串本身的副本。

ZIR 指令结构的解析

在深入介绍 AST 转换为 ZIR 的过程之前，我将花费大量篇幅来讨论单个 ZIR 指令的格式。我建议仔细阅读和理解本节，因为这是理解 ZIR 构建的基本构件。

ZIR 实际上是一个指令列表。ZIR 指令的格式与 AST 节点使用的模式很相似，因此本文可能会忽略一些结构细节。在这些情况下，我将特别指出结构之间的相似之处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

pub const Inst = struct {
    tag: Tag,
    data: Data,

    pub const Tag = enum(u8) {
        add,
        addwrap,
        // many more...
    };

    pub const Data = union {
        // various fields that can be set depending on tag
    };
};

这个结构跟 AST 节点非常相似。tag 的存储访问模式与 AST 节点相同，但标签是完全不同的集合。例如，整数字面量的 AST 是 .integer_literal 而无论整数的大小如何。但在 ZIR 中，具体取决于整数是否在 u64 表示范围内，对应的 tag 将会是 .int 或 .int_big 等。

每个指令都与数据相关联，数据存储都 Data 联合字段上。Data 联合中的有效字段取决于标签值。数据可以直接存储在 Data 字段中，例如整数字面量值。也有可能 Data 字段是指向其他信息的位置的引用。

与 AST 节点类似，ZIR 也有一个 extra 字段。它的行为与 AST 节点的 extra_data 字段几乎相同：一些数据条目可能指向 extra 字段中的一个条目，从那里开始的一些字段将包含与 ZIR 指令相关的特定值。有关更多详细信息，请参阅 Zig 语法解析器源码以及下面的示例。

静态值

最简单的 ZIR 指令是存储静态值的指令，让我们看一个例子：

1

const x = 42;

1
2
3
4
5
6

%0 = extended(struct_decl(parent, Auto, {
  [7] x line(0) hash(5b108956afe84d38689dcd3f2d652f04): %1 = block_inline({
    %2 = int(42)
    %3 = break_inline(%1, %2)
  }) node_offset:1:1
}, {}, {})

静态值对应的是 %2 指令（int(42)）。如你所见，静态值 42 被直接内联到指令当中。这个指令对应的内部结构如下：

1
2
3
4
5
6

Zir.Inst{
    .tag = .int,
    .data = .{
        .int = 42,
    },
}

这是所有可能的 ZIR 指令中最简单形式：数据直接嵌入到指令中。在这种情况下，活跃数据的标签是 .int 标签，活跃数据是内联的静态整数值。

更常见的情况是数据是一个引用，或者标签包含更复杂的信息，无法直接适应 Inst 结构。下面是一些示例。

引用

许多 ZIR 指令包含对值的引用。例如，一元运算符 ! 可以是任何表达式的前缀，如静态值 !true 或变量 !myVar 或函数调用 !myFunc() 等。理解 ZIR 如何编码引用非常重要，因为它们非常常见。

ZIR 引用对应到 Zir.Inst.Ref 类型，这是一个未穷尽的枚举。类型定义的标签用于表示原始值或非常常见的值。否则，该值是对另一个 ZIR 指令索引的引用。

带标签的引用

让我们看一个具体的例子：

1

const x = !true;

1
2
3
4
5
6

%0 = extended(struct_decl(parent, Auto, {
  [7] result line(0) hash(0be0bb45d9cb29941abcc19d4176dde6): %1 = block_inline({
    %2 = bool_not(@Ref.bool_true) node_offset:1:16
    %3 = break_inline(%1, %2)
  }) node_offset:1:1
}, {}, {})

关注指令 %2 的内容，它包括一个对应 ! 运算符的 bool_not 指令，而 @Ref.bool_true 为其参数。bool_not 指令接受一个参数，它大致的内部表示如下（部分字段省略，它们跟本例关系不大）：

1
2
3
4
5
6

Zir.Inst{
    .tag = .bool_not,
    .data = .{
        .un_node = .{ .operand = Ref.bool_true },
    },
}

Ref.bool_true 是表示静态值 true 的一个 Ref 枚举的标签。Ref 枚举还有许多其他标签。例如，每种内置类型都有一个标签。一个具体地例子是，尽管下面的示例毫无意义，但它确实产生有效的 ZIR 指令（编译器稍后会报错）：

1

const x = !u8; // ZIR: bool_not(@Ref.u8_type)

对于常见的原始类型和值，ZIR 使用带标签的 Ref 来表示。

指令的引用

对于不常见的值，Ref 代表的是一个指令索引。下面是一个具体的例子：

1
2

const input = true;
const x = !input;

1
2
3
4
5
6
7
8
9
10
11

%0 = extended(struct_decl(parent, Auto, {
  [13] input line(0) hash(1af5eb6ed7d8836d8d54ff390bb38c7d): %1 = block_inline({
    %2 = break_inline(%1, @Ref.bool_true)
  }) node_offset:1:1
  [21] result line(1) hash(4ba2a2df9e05a2d7963b6c1eb80fdcea): %3 = block_inline({
    %4 = decl_val("input") token_offset:2:17
    %5 = as_node(@Ref.bool_type, %4) node_offset:2:17
    %6 = bool_not(%5) node_offset:2:16
    %7 = break_inline(%3, %6)
  }) node_offset:2:1
}, {}, {})

%6 是查找指令引用的关键指令。我们看到了熟悉的 bool_not 指令，但这一次它的参数是 %5 即另一条指令。通读所有的指令序列，你应该能凭直觉理解到这个参数对应从 input 变量中读到的值。

这段 ZIR 指令的内部表示大致表示如下：

1
2
3
4
5
6

Zir.Inst{
    .tag = .bool_not,
    .data = .{
        .un_node = .{ .operand = Ref.typed_value_map.len + 5 },
    },
}

要确定 Ref 值是标记还是指令索引，我们可以检查该值是否大于标记的数量。如果是，则值减去标记长度等于指令。这个操作非常常用，因此 Zig 内部定义了 indexToRef 和 refToIndex 两个辅助函数来执行对应操作。在上面的示例中，操作数 %5 对应的是 indexToRef(5) 的值。如果调用 refToIndex(operand) 则可以得到 5 作为返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

const ref_start_index: u32 = Inst.Ref.typed_value_map.len;

pub fn indexToRef(inst: Inst.Index) Inst.Ref {
    return @intToEnum(Inst.Ref, ref_start_index + inst);
}

pub fn refToIndex(inst: Inst.Ref) ?Inst.Index {
    const ref_int = @enumToInt(inst);
    if (ref_int >= ref_start_index) {
        return ref_int - ref_start_index;
    } else {
        return null;
    }
}

译注：这两个函数现在重构了，分别变成了 Zir.Inst.Index.toRef 和 Zir.Inst.Ref.toIndex 方法，如下所示：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

pub const Index = enum(u32) { // ... pub fn toRef(i: Index) Inst.Ref { return @enumFromInt(@intFromEnum(Index.ref_start_index) + @intFromEnum(i)); } } pub const Ref = enum(u32) { // ... pub fn toIndex(inst: Ref) ?Index { assert(inst != .none); const ref_int = @intFromEnum(inst); if (ref_int >= @intFromEnum(Index.ref_start_index)) { return @enumFromInt(ref_int - @intFromEnum(Index.ref_start_index)); } else { return null; } } }

额外数据

一些 ZIR 指令包含对额外字段的引用，有时也称为“尾部”数据。这与 AST 节点中的 extra_data 字段非常相似，因此在这里不会详细介绍其编解码过程。如果您对 AST 节点中的 extra_data 字段不熟悉或不理解，我建议您复习一下该部分。

我们来看一个额外数据的例子：

1

const x = 1 + 2;

1
2
3
4
5
6
7

%0 = extended(struct_decl(parent, Auto, {
  [10] x line(0) hash(48fa081b63af0a1c7f2d11a7bf9fbbc3): %1 = block_inline({
    %2 = int(2)
    %3 = add(@Ref.one, %2) node_offset:1:13
    %4 = break_inline(%1, %3)
  }) node_offset:1:1
}, {}, {})

这个输出的 ZIR 指令包括了我们在上面已经学到的一切：指令 %2 是一个静态值，指令 %3 中的 @Ref.one 是一个带标签的引用，指令 %3 中的 %2 引用了另一个指令。

二进制加法操作使用了额外字段。在 ZIR 指令的文本输出中，这并不明显，因为 ZIR 渲染器理解 add 指令并从额外字段（指令 %3）中以美化形式打印了数据。实际上，它的内部表示如下：

1
2
3
4
5
6
7
8
9
10

// Instruction
Zir.Inst{
    .tag = .add,
    .data = .{
        .pl_node = .{ .payload_index = 7 },
    },
}

// Exra data
[ ..., Ref.one, %2, ... ]

该指令使用了 pl_node 数据标签（pl_node 是 payload node 的缩写）。其中包含一个 payload_index 字段，它指向 extra 数组中附加数据的起始位置。通过查看 .add 标签的注释，可以了解到 extra 字段存储了一个 Zir.Inst.Bin 结构，该结构包含 lhs 和 rhs 字段。在这种情况下，我们有：

• lhs = Ref.one
• rhs = %2

跟 AST 节点类似，AstGen 源代码包含一个名为 addExtra 的辅助函数，以类型安全的方式编码结构化的额外数据。

额外数据本身可以包含静态值或其他 Zig.Inst.Ref 值等等。你需要查看每个标签的源代码才能理解它所编码的值。

其他数据类型

ZIR 还有许多其他的数据类型，但是我不会在本文中穷举其所有。我个人的感受是，上面这些类型囊括了编译器中编码 ZIR 指令的信息的绝大部分模式。

AstGen 的组件

AstGen 过程中有许多用于构建 ZIR 的共享组件。这些组件包含了通用的共享逻辑，了解这些逻辑对于理解 AstGen 的完整行为非常关键。

这些组件大多数是 AstGen 中函数的参数，下面介绍其中的一部分。我们不会介绍 AstGen 的所有功能，但是会强调一些关键要点。

作用域

AstGen 可以感知作用域，这使它可以引用父级作用域中的标识符，在使用未定义的标识符时抛出错误，或检测标识符被隐藏的问题。

AstGen.zig 文件中的 Scope 结构定义了作用域。作用域是多态的，可以是多个子类型之一。Zig 使用 @fieldParentPtr 模式来实现这一点。解释这个模式超出了本文的范围，但它 Zig 中很常见。

译注：以下材料可以帮助理解 @fieldParentPtr 模式。

• https://www.ryanliptak.com/blog/zig-fieldparentptr-for-dumbos/
• https://ziglang.org/documentation/master/#fieldParentPtr
• https://github.com/ziglang/zig/issues/7831

在撰写本文时，有七种作用域类型：

• Scope.Top 表示文件的最外层作用域。它始终是最顶层的作用域，没有父级作用域。该作用域不跟踪任何附加数据。
• GenZir 通常表示 Zig 中的一个块，但也用于跨 AST 节点进行大量的额外状态跟踪。它跟踪当前块标签（如果有）、指令列表、是否在编译时位置等。
• Scope.Namespace 该作用域包含一个无序的可以进行引用的声明集合。这里的关键词是“无序”。该作用域通常是结构体、联合等块的子作用域。例如：结构体变量可以引用文件中稍后定义的变量，而函数体则不行。因为结构体是命名空间，但函数体不是。
• Scope.LocalVal 和 Scope.LocalPtr 表示已定义的单个标识符，例如变量或常量。随着标识符的定义，这将创建一个新的该类型的子作用域，使其“在作用域内”。这与命名空间不同，因为它表示确切的一个声明，而不是一个无序列表。
• Scope.Defer 表示 defer 或 errdefer 周围的作用域。它用于跟踪 defer 的存在，以在所有的退出点生成指令。

作用域具有一个 parent 字段，可用于通过作用域向上遍历。这就是标识符解析的工作原理。

字符串内化

字符串（字节数组）不直接存储在 ZIR 指令中。字符串会被内化，并存储在一个连续的 string_bytes 数组中。字符串的起始索引存储在 ZIR 指令中。这意味着共享的字符串（例如标识符）只存储一次。

到目前为止，ZIR 是编译流水线上第一个存储字符串的结构。AST 节点存储 Token 索引，而 Token 存储其在源代码中的起始和结束偏移量。这要求 AST 和源代码保持可用。在 AstGen 之后，可以释放 AST 和源代码。这个设计使得编译器可以解析非常大的 Zig 程序，并且只在内存中存储所需的内容。

结果的位置

ResultLoc 结构用于跟踪表达式树的最终结果应该写入的位置。在遍历 AST 并生成 ZIR 时，某些写操作的值可能嵌套得很深，AstGen 需要知道最终值应该写入的位置。

考虑以下示例：

1
2
3
4
5
6

const x = blk1: {
  switch (someUnion) {
    .someTag => break :blk1 42,
    else => break :blk1 0,
  }
}

在最外层作用域中，常量 x 正在定义。在这段代码的 AST 树中，我们需要嵌套进入一个块，然后是一个 switch 语句，然后是一个 switch 的匹配，最后是一个带标签的 break 语句。在递归超过四个函数以后，AstGen 需要依靠 ResultLoc 结构来定位写入标记跳出值的位置。

ResultLoc 是一个带有许多可能结果类型的标记联合。它有很好的注释，我建议阅读源代码。这里将解释一些示例标记：

• .discard 表示赋值被丢弃，因为赋值左侧是 _ 标识符。在这种情况下，AstGen 知道不需要生成任何存储指令，我们可以直接丢弃该值。
• .ty 表示赋值是给某个类型化的值。这会生成一个 as_node 指令来强制转换返回之前的结果值。
• .ptr 表示赋值被写入某个内存位置。这会生成一个 store 指令，以便将结果写入该内存位置。

ZIR 的生成

现在让我们来了解一下 AstGen 是如何将 AST 转换为 ZIR 的。抽象地说，这个过程将遍历 AST 并为每个 AST 节点发出指令，从而将其转换为 ZIR 指令序列。AstGen 采用立即求值的模式将整个 AST 转换为 ZIR 指令序列，这意味着 AstGen 不会延迟求值（在后续编译阶段我们将看到延迟求值的例子）。

重要的是，AstGen 引入了我们第一个重要的语义验证过程。例如，AstGen 验证标识符是否被定义，是否不会遮蔽外部作用域，并且知道如何遍历父作用域。回想一下之前提到的 AST 构建引入了结构验证：它确保像 x pub == 7 这样的 Token 序列会抛出语法错误，但它并没有验证任何标识符 x 是否被定义。而词法分析本身只是逐个验证 Token 的有效性，例如 72 是一个有效的字面量，而 72a 不是一个有效的标识符。

学习 ZIR 的生成过程最简单的方式是查看 expr 函数。这个函数为 Zig 语言中任何有效的表达式生成对应的 ZIR 指令序列。我发现从语言的最简单组件开始，然后逐步构建起来是最容易理解这一过程的方式，因为 IR 生成是一个深度递归的过程。

整数字面量

让我们看一个简单的静态整数值的例子：

1

42

这将被解析成带有 .integer_literal 标签的 AST 节点，进而引导 expr 函数调用 integerLiteral 函数。integerLiteral 函数的内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

fn integerLiteral(gz: *GenZir, rl: ResultLoc, node: Ast.Node.Index) InnerError!Zir.Inst.Ref {
    const tree = astgen.tree;
    const main_tokens = tree.nodes.items(.main_token);
    const int_token = main_tokens[node];
    const prefixed_bytes = tree.tokenSlice(int_token);
    if (std.fmt.parseInt(u64, prefixed_bytes, 0)) |small_int| {
        const result: Zir.Inst.Ref = switch (small_int) {
            0 => .zero,
            1 => .one,
            else => try gz.addInt(small_int),
        };

        return rvalue(gz, rl, result, node);
    } else |err| switch (err) {
        error.InvalidCharacter => unreachable, // Caught by the parser.
        error.Overflow => {},
    }

    // ... other paths
}

这里有很多内容！这就是为什么我从最简单的事物开始。如果我从函数声明之类的东西开始，我会陷入太多细节中，学起来会很困难。即使看整数字面量，你可能仍然感到有些不知所措，但这已经是最简单的情况了，所以让我们深入了解一下。

首先，这个函数在 AST 中查找整数字面量对应的 Token 值。然后，我们可以使用 Token 的起始位置，通过 tree.tokenSlice 获取与 Token 关联的文本。这将得到 “42” 字符串，或者更具体地说，是 4 和 2 两个字节。

接下来，我们尝试将该字符数组解析为无符号 64 位整数。如果数字太大，代码就会走到 other parts 注释的逻辑，其中涉及存储“大整数”的复杂内容，我们在这里不进行探讨。在这个示例中，我们假设所有的整数常量都小于或等于无符号 64 位整数的最大值（18446744073709551615）。

原注：无符号？那负数怎么办？

负数前面的符号 - 会作为一个单独的 AST 节点存储，并在 ZIR 中单独生成一个一元操作。整数字面量始终为正数。

上述过程最终成功解析数字，因为 42 可以解析为有效的 u64 类型的值。接下来，我们处理特殊情况，即值为 0 或 1 的情形，因为它们具有特殊的标记引用。否则，我们生成一个 .int 标签的 ZIR 指令，并将指令索引存储在 result 中。

最后，我们调用 rvalue 函数，它将 ResultLoc 的语义应用于该值，以确定我们是否需要原样返回它，将其转换为已知类型，或将其存储在内存位置等等。在许多情况下，这将是一个空操作，并且只会简单地返回带 .int 标签的 ZIR 指令。

译注：翻译时，integerLiteral 函数已被重构为 numberLiteral 函数。

加法

理解静态值对应 ZIR 的生成过程，我们在进一步分析一个加法的生成过程：

1

42 + 1

这将被解析成带有 .add 标签的 AST 节点，并引导 expr 函数调用 simpleBinOp 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

fn simpleBinOp(
    gz: *GenZir,
    scope: *Scope,
    rl: ResultLoc,
    node: Ast.Node.Index,
    op_inst_tag: Zir.Inst.Tag,
) InnerError!Zir.Inst.Ref {
    const astgen = gz.astgen;
    const tree = astgen.tree;
    const node_datas = tree.nodes.items(.data);

    const result = try gz.addPlNode(op_inst_tag, node, Zir.Inst.Bin{
        .lhs = try reachableExpr(gz, scope, .none, node_datas[node].lhs, node),
        .rhs = try reachableExpr(gz, scope, .none, node_datas[node].rhs, node),
    });
    return rvalue(gz, rl, result, node);
}

这是我们第一个递归的例子。它通过递归构建左表达式和右表达式的 ZIR 指令序列，进而生成一个带有 lhs 和 rhs 数据的 .add ZIR 指令。其中 lhs 对应 42 字面量，rhs 对应 1 字面量，根据我们对整数字面量的探索，我们知道这将进一步转化为 .int 指令。

生成的 ZIR 大致如下：

1
2

%1 = int(42)
%2 = add(%1, @Ref.one)

赋值

接下来，我们把上面加法的值赋值给一个未标识类型的常量：

1

const x = 42 + 1;

expr 函数不会处理赋值，因为它不是一个表达式，而是一个语句。statement 函数也不处理赋值，因为 Zig 的变量赋值只能在容器（结构体）或块（函数体）内进行。因此，处理赋值的是 containerMembers 或 blockExprStmts 函数。前者用于结构体的主体，后者用于函数体。我认为首先看 blockExprStmts 会更容易，因为 containerMembers 比较复杂。

blockExprStmts 函数有一个 switch 语句，它在处理赋值时会跳转到 varDecl 函数处理变量或常量声明。varDecl 函数的代码量非常庞大！我不会在下面粘贴完整的函数，而只包括最关键的代码路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const type_node = var_decl.ast.type_node;
const result_loc: ResultLoc = if (type_node != 0) .{
    .ty = try typeExpr(gz, scope, type_node),
} else .none;
const init_inst = try reachableExpr(gz, scope, result_loc, var_decl.ast.init_node, node);

const sub_scope = try block_arena.create(Scope.LocalVal);
sub_scope.* = .{
    .parent = scope,
    .gen_zir = gz,
    .name = ident_name,
    .inst = init_inst,
    .token_src = name_token,
    .id_cat = .@"local constant",
};
return &sub_scope.base;

首先，代码递归地计算类型表达式（如果有的话）和初始化表达式。对于常量 const x: t = init 来说，t 是类型表达式，init 是初始化表达式。对于我们的示例，我们没有类型表达式，而初始化表达式是一个 .add 指令。

接下来，代码创建一个新的 LocalVal 作用域来表示这个值。这个作用域定义了标识符 x 和值指令 init_inst 并指向 varDecl 函数给出的父作用域。新定义的作用域是函数的返回值，调用者 blockExprStmts 将当前作用域从该语句起替换为这个新作用域，以便将来的语句和表达式可以引用这个赋值。

此前的示例返回 ZIR 指令索引，而这个示例返回了一个作用域。请注意，对 x 的命名赋值不会生成 ZIR 指令。如果你查看生成的 ZIR，你不会在任何地方看到 x 的命名：

1
2

%2 = int(42)
%3 = add(%2, @Ref.one)

x 被实现为一个作用域，而这个作用域被 inst 值指令追踪。如果 x 曾经被引用，我们知道它的值对应到前述值指令，并且可以通过值指令来引用 x 的值。具体地说，我们看到函数体中的后续 ZIR 指令序列：

1
2

const x = 42 + 1;
const y = x;

1
2
3

%2 = int(42)
%3 = add(%2, @Ref.one) // x assignment
%4 = ensure_result_non_error(%3) // y assignment

注意指令 %4 对应的对 y 的赋值直接引用了指令 %3 作为参数。ZIR 指令不需要进行显式的数据存储和加载，因为它可以直接引用指令的结果。

请注意，当生成机器代码时，后端可能会确定需要进行加载或存储数据，这取决于计算机体系结构。但中间表示不需要做出这个决定。

作为读者的练习：下一步，我建议研究 const y = x 语句的 ZIR 生成过程，并学习标识符引用的工作原理。这将解释上述的 ZIR 是如何生成的，并为应对更复杂的编译过程打下良好的基础。

完成 AstGen 流程

AstGen 进程为每个 Zig 文件各运行一次，并递归地构建整个文件的 ZIR 指令序列，最终在函数的末尾返回一个 Zir 值。

通过本文介绍的细节，你应该能够跟踪任何 Zig 语言结构并学习 ZIR 是如何生成的。你可以经常使用 zig ast-check 命令来查看 Zig 编译器实际生成的内容，并从中知道应该深入分析哪些函数。

Zig 语言是近几年来逐渐声名鹊起的一个新编程语言，也是数目稀少的系统编程语言家族中的一个新成员。它由 Andrew Kelley 于 2015 年开始创造，至今已经开发了八个年头，但是仍然还未发布 1.0 版本。

不过，已经有不少新锐项目选择使用 Zig 开发，例如 JavaScript 运行时和完整开发套件 bun 和分布式金融数据库 tigerbeetle 等。

Hashicorp 的创始人 Mitchell Hashimoto 也在前年卸任 CEO 成为 IC 后开始投入大量时间开发 Zig 程序，包括开源的 libxev 库和目前尚未公开的 Ghostty 等等。

Mitchell 在开发 Zig 程序的过程中，撰写了系列博客介绍 Zig 程序的编译过程。这些内容有助于理解 Zig 语言的设计，以及它如何在 LLVM 提供的抽象和系统开发者之间建立起一层抽象。

我在取得 Mitchell 的同意后对这些文章做一个翻译，以飨读者。

本文翻译自系列第一篇和第二篇博客：

• Zig Tokenizer https://mitchellh.com/zig/tokenizer
• Zig Parser https://mitchellh.com/zig/parser

这一部分属于编译器的前端，相对而言比较简单。

以下原文。

词法分析

词法分析是典型编译器流程中的第一步。词法分析是将字节流，即编程语言的语法，转换为 Token 流的过程。

例如，Zig 的 comptime {} 语法经过词法分析后，将得到 [.keyword_comptime, .l_brace, .r_brace] 的结果。词法分析通常不处理语义问题，也不关心分析得到的 Token 是否有实际意义。例如，comptime [] 不是有效的 Zig 语法，但是词法分析过程仍然会将其解释为合法的 [.keyword_comptime, .l_bracket, .r_bracket] 输出。解析 Token 流的语义以及在无效情况下失败推出，是下一章要介绍的语法解析的内容。

词法分析器的实现方式多种多样。本文主要介绍 Zig 的词法分析工作原理，并不会跟其他的方案做对比。

词法分析器

Zig 语言的词法分析器是标准库的一部分，代码位于 lib/std/zig/tokenizer.zig 文件内，对外暴露为 std.zig.Tokenizer 结构。

Zig 词法分析器接受一个字节数组切片作为参数，不断产生 Token 直到遇见结束符（EOF）。词法分析过程没有任何内存分配。

在深入讲解词法分析过程前，我们先看到它的一个基本使用方式：

1
2
3
4
5
6
7
8

const std = @import("std");
const expect = std.testing.expect;

const tok = std.zig.Tokenizer.init("comptime {}");
try expect(tok.next() == .keyword_comptime);
try expect(tok.next() == .l_brace);
try expect(tok.next() == .r_brace);
try expect(tok.next() == .eof);

Zig 的词法分析有两个重要特点：

1. 在字节数组切片上操作，而不是字节流。词法分析的参数类型是 [:0] const u8 而不是字节流。这意味着如果输入字符量巨大，调用方需要自己处理输入缓存和攒批处理的工作。实践当中，编程语言代码输入一般不会太大，所以整个源文件的词法分析可以一次性完成。这就是 Zig 当前的工作方式。
2. 没有内存分配。Zig 的词法分析器不做任何的堆上内存分配。对于系统编程语言，理解接口的内存使用和分配行为总是有意义的。Zig 的所有分配都是显式的，因此我们可以立即从词法分析器的参数列表中没有 Allocator 得到它不会做内存分配的结论。

如下所示，词法分析器结构的定义是相对简单的：

1
2
3
4
5
6
7

pub const Tokenizer = struct {
    buffer: [:0]const u8,
    index: usize,
    pending_invalid_token: ?Token,

    // ...
};

即使你对词法分析一无所知，从上面结构定义中你也应该能理解词法分析的工作原理。词法分析器逐个处理切片上的字节，同时前移索引并产生 Token 输出。

Token 的结构

理解了词法分析的高级接口之后，紧接着下一个问题就是：Token 结构如何定义？

Zig 当中 Token 的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

pub const Token = struct {
    tag: Tag,
    loc: Loc,

    pub const Loc = struct {
        start: usize,
        end: usize,
    };

    pub const Tag = enum {
        invalid,
        // ...
    };
};

其中，tag 保存了 Token 的类型，可能的取值包括 .keyword_comptime, .l_brace, .r_brace, .eof 等等。目前，Zig 大约定义了 120 个不同的 Token 类型。

此外，loc 字段定义了 Token 的位置。它由 start 和 end 两个索引组成。词法分析的调用者可以通过 source[tok.loc.start .. tok.loc.end] 来取得 Token 对应的文本内容。Token 结构中只保存两个索引是一种常见的效率优化手段。

Token 结构中只提供了最基本的信息：Token 的类型及其位置。不过，在不同的词法分析器中，Token 结构的定义可能有所不同。

例如，Golang 的词法分析器把 Token 定义成一系列整型常数。同时，对应到 next() 的函数返回代表 Token 类型的整数、代表偏移量的单一整数，以及对应 Token 文本内容的字符串。

1
2
3
4
5
6
7
8
9
10

func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string)

type Pos int
type Token int

const (
ILLEGAL Token = iota

    // ...
)

这与 Zig 大致相同。但是其中微妙的差异，对编译器的工效学和性能有重要影响。

查找下一个 Token

在词法分析器上每调用一次 next() 方法都将得到一个 Token 输出。

next() 函数从缓冲区的当前索引开始，逐个字节查看以构建 Token 输出。它使用一个状态变量来实现状态机，以跟踪可能出现的下一个状态。

在分析 Zig 词法分析器的实现细节之前，我们先从高层抽象上思考 next() 的工作流程。比如，输入包含空白符的语句 while 如何被分词。

首先，词法分析器会遇到 w 字符。此时，我们知道这个 Token 不会是数字，但它仍然可以是关键字或标识符。因此，我们不能确定 Token 的类型。词法分析器每次只看一个字符，所以我们接下来获取 h 字符。它仍然可以是标识符或关键字，所以我们继续读取字符，并依次读到 ile 三个字符。

现在，词法分析器得到了 while 输入，我们知道它是一个独立的关键字。但是，它仍然可以是标识符，因为可能还有更多字符，所以我们需要再向前看一个字符。

下一个输入是空格。我们现在明确知道它是 while 关键字，而不是标识符。于是，我们返回 .keyword_while Token 作为结果。反之，如果下一个字节是数字 1 这样的字符，我们会知道我们正在构建一个标识符，并且它绝不会是一个关键字，因为没有以 while1 开头的关键字。

这就是 Zig 词法分析器的工作原理。它维护当前状态，比如“正在构建一个标识符或关键字”，并逐个字符查看，直到明确确定了 Token 的类型和内容。

词法分析器只查看状态和当前字符：它不会向后查看，也不会向前查看。大多数词法分析器都是这样的。正如开头所提到的，词法分析器不关心语义，因此诸如 if while comptime x = 7 { else } 这样的无意义输入会产生一个有效的 Token 流。接下来，负责语法解析的解析器会分析 Token 流对应的语义含义。

词法分析的实现

next() 的实现基于嵌套的 while 和 switch 语句，其中一个代码片段如下：

1
2
3
4
5
6
7
8
9
10
11

while (true) : (self.index += 1) {
    const c = self.buffer[self.index];
    switch (state) {
        .start => switch (c) {
            'a'...'z', 'A'...'Z', '_' => {
                state = .identifier;
                result.tag = .identifier;
            },
        }
    }
}

外部的 while 是一个无限循环，每次处理缓冲区里的一个字符。循环体将在发现一个 Token 或字符耗尽时退出。

Zig 的一个好特性是缓冲区 buffer 具有 [:0] const u8 类型，其中的 :0 代表缓冲区以字节 0 结尾。因此，我们可以在发现 0 是退出循环。

接下来，词法分析器查看当前的 state 值。对于每个具体的 state 值，词法分析器再查看当前字符的值。结合这两者，词法分析器决定下一个动作应该是什么。

在上面的代码片段中，我们可以看到，如果词法分析器处于 .start 状态，下一个字符假设是 A 的话，词法分析器将进入到 .identifier 状态并试图得到一个标识符。

从 Token 到抽象语法树

词法分析完成后，下一个阶段是语法解析。语法解析器接收由词法分析器生成的 Token 流，并将其转换为更有意义的抽象语法树。

语法解析

语法解析是编译流程中紧随词法分析的下一步。语法解析负责从 Token 流构建抽象语法树。我之前已经写过关于 Zig 如何将字节流（源代码）转换为 Token 流的内容。

Zig 语法解析器的代码位于 lib/std/zig/parse.zig 文件中，对外暴露成标准库中的 std.zig.parse() 接口。语法解析器接受整个源代码文本，输出 std.zig.Ast 抽象语法树实例。Ast 结构定义在 lib/std/zig/Ast.zig 文件中。

译注：0.11 版本后，语法解析的接口有所变化，但是整体流程仍然是相似的。

MultiArrayList

从解析开始，Zig 编译器大量使用 MultiArrayList 结构。为了理解语法解析器的工作原理以及抽象语法树的结构，我们首先介绍 MultiArrayList 的设计。

在讲解 MultiArrayList 之前，我想先简要介绍一下常规的 ArrayList 的设计。ArrayList 是一个动态长度的值数组。当数组已满时，会分配一个更大的新数组，并将现有项复制到新数组中。这是一个典型的、动态分配的、可增长或缩小的项目列表。

例如，考虑如下一个 Zig 结构：

1
2
3
4

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

在 ArrayList 中，多个 Tree 结构会按如下形式存储：

1
2
3

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

每个 Tree 结构需要 8 字节内存存储，所以 4 个 Tree 值的数组需要 32 字节内存来存储。

原注：为什么是 8 字节？

一个 u32 值需要 4 字节存储，一个 bool 值需要 1 字节存储。但是结构体本身有一个 u32 字段，所以 bool 字段需要是 4 字节对齐的，也就占用了 4 字节的内存（其中 3 字节是浪费的）。总的就是 8 个字节。

MultiArrayList 同样是一个动态分配的值列表。然而，存储在数组列表中的类型的每个字段都存储在单独的连续数组中。这带来了两个主要优点：

1. 由于对齐而减少了浪费的字节
2. 具有更好的缓存局部性

这两个优点通常会带来更好的性能，以上面 Tree 结构为例，MultiArrayList(Tree) 的存储结构如下：

1
2
3
4
5
6

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

结构体的每个字段都存储在单独的连续数组中。一个包含四个树的数组使用了 20 字节，相比 ArrayList(Tree) 的方案减少 37.5% 的内存占用。这忽略了多个数组指针的开销，但是随着列表中项目数量的增长，这种开销会分摊到总共减少了 37.5% 的内存需求上。

原注：为什么是 20 字节？

由于结构体被拆分，age 字段需要 4 字节，上面数组有 4 个 Tree 实例，因此是 16 字节。alive 字段不再需要 4 字节对齐，因为它不再是结构体的一部分，所以只需要 1 字节（没有浪费的字节！）。上面数组有 4 个 Tree 实例，因此 alive 字段一共需要 4 字节。这两个字段加起来总共是 20 字节。

本文不会深入介绍 MultiArrayList 的实现细节。对于理解 Zig 编译器来说，只需要知道几乎每个结构都存储为 MultiArrayList 就足够了。编译一个真实世界的程序通常会生成数万个“节点”，因此这样做可以节省大量内存，并提高缓存的局部性。

语法解析器的结构

语法解析器使用 Parser 结构体来存储当前解析状态。这不是一个公开导出的结构体，只用于管理解析操作的内部状态。调用者会得到一个 Ast 作为解析操作的结果，这将在本文后面进行探讨。

以下是本文写作时解析器的结构，我在其中插入了换行符，以将状态分成功能组：

1
2
3
4
5
6
7
8
9
10
11
12
13

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 的不变式，Zig 只是将结构体字段放置在单独的连续内存块中。tok_i 值是解析器正在查看的当前 Token 的索引（从 0 开始计数）。

第三组状态是语法解析器的实际工作状态。这是 Ast 部分累积的结果。第三组非常重要，因为它是语法解析器构建的核心部分：

• errors 存储了语法解析器在进行解析过程中遇到的错误列表。大多数良定义的语法解析器在各种错误情况下都会尝试继续解析，Zig 的解析器也不例外。Zig 解析器会在这个字段中累积错误并尝试继续解析。
• nodes 是 AST 节点的列表。初始为空，在语法解析器继续进行时逐渐构建起来。理解 AST 节点的结构非常重要，这将在下一节中介绍。
• extra_data 是 AST 节点可能需要的附加信息的列表。例如，对于结构体，extra_data 包含了所有结构体成员的完整列表。这再次展示了面向数据的设计的例子；另一种方法是直接将额外数据放在一个节点上，但这会使整个解析器变慢，因为它会强制每个节点变得更大。
• scratch 是语法解析器共享的临时工作空间，通常用于为节点或额外数据构建信息。一旦语法解析器完成工作，这些空间就会被释放。

AST Node 的结构

语法解析的结果是一个 AST 节点的列表。请注意，AST 在抽象定义上是一棵树，但解析器返回的结果是包含树中节点的列表，也就是上面介绍的 MultiArrayList 内存表示方式。

AST 节点结构可能会令人困惑，因为数据本身存成 MultiArrayList 结构，其中包括许多间接引用。我建议反复阅读本节，确保理解 AST 节点的结构。在理解 Zig 编译器的内部工作原理时，对这种数据模式理解不透彻会导致许多问题，因为这个模式在编译器的每个后续阶段都被重复使用。

AST 结构可以在 lib/std/zig/Ast.zig 中找到，下面是其核心 Node 结构的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

pub const TokenIndex = u32;

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 对应调用内置函数，例如 @intFromEnum 等。

main_token 字段现在并不是非常重要。它存储跟当前 AST 节点密切相关的 Token 值。例如，对于函数声明，它可能是一个 fn Token 值。该值是一个索引，指向用于构建 AST 的 Token 列表。

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

AST Node 的数据

AST Node 的数据是关联到 AST Node 的关键数据。例如，函数声明具有函数名称、参数列表、返回类型和函数体等信息。Node 结构的定义没有立即解释这些信息存储的位置。

在我们深入了解语法解析器的具体工作方式之前，理解 AST Node 的数据存储模式非常重要。对于想要了解整个编译器流程的人来说，这是一个关键的细节，因为 AST 使用了一种贯穿整个编译流程的模式。

让我们来看看给定 Zig 代码的函数声明的 AST 结构会是怎样的：

1
2
3

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

函数声明

函数声明的根 AST 节点会被打上 fn_decl 标签。

对于 fn_decl 标签的节点，data 字段的 lhs 存储了函数原型在 NodeList 中的索引（名称、类型信息等），而 rhs 字段存储了函数体在 NodeList 中的索引。这些信息目前只能通过阅读 .fn_decl 标签上面的注释或源代码才能得知。

lhs 和 rhs 中的索引值是关联到 NodeList 上。因此，你可以通过 tree.nodes[lhs] 访问函数原型信息（伪代码，并非完全正确的写法）。

data 的两个字段都用于存储 NodeList 的索引。这是 data 的一种用法，用于存储与 AST 节点相关的信息。接下来，让我们看一下函数原型，了解 Zig 如何确定参数列表、返回类型和调用约定。

函数原型

通过 tree.nodes[lhs] 我们可以访问函数原型节点。函数原型节点对应的是 fn_proto 标签。这种类型的 AST 节点存储了有关参数、调用约定、返回类型等信息。

函数原型节点以不同的方式使用 lhs 和 rhs 字段。其中，rhs 字段的用法与函数声明相同，存储了返回类型表达式在 NodeList 中的索引。Zig 除了支持直接类型标识符，还支持使用各种表达式来在编译时计算返回类型。

然而，lhs 字段并不指向 AST 节点。相反，它是指向某个 extra_data 字段的索引。该索引是附加元数据的起始索引。附加元数据的长度根据 AST 节点类型事先已知。所以，lhs 字段对应的信息不是通过 tree.nodes[lhs] 来访问，而是通过 tree.extra_data[lhs] 来访问。

现在我们知道，lhs/rhs 可能指向一个 AST 节点，也可能指向一段额外数据。

此外，extra_data 具有 []Index 类型。这可能会让人误以为 tree.extra_data[lhs] 只是指向另一个索引。这是不正确的。这种情况下的 lhs 只是指向 extra_data 中的第一个索引。要读取的后续字段数量也取决于标签。例如，fn_proto 对应的 extra_data 有六个字段。要想知道 extra_data 的具体内容，当前只能通过阅读源代码及其注释来了解：

1
2
3
4
5
6
7
8
9
10
11
12

pub const FnProto = struct {
    params_start: Index,
    params_end: Index,
    /// Populated if align(A) is present.
    align_expr: Index,
    /// Populated if addrspace(A) is present.
    addrspace_expr: Index,
    /// Populated if linksection(A) is present.
    section_expr: Index,
    /// Populated if callconv(A) is present.
    callconv_expr: Index,
};

因此，fn_proto 的情形下，tree.extra_data[lhs] 指向的是一个 params_start 字段。对应地，tree.extra_data[lhs+1] 指向一个 params_end 字段。依此往下，直到 tree.extra_data[lhs+5] 指向 callconv_expr 字段。

Ast 结构提供了一个 extraData() 帮助函数来完成这些解码工作：传入一个 tree 实例，你可以简单的访问其 lhs/rhs 对应的数据：

1
2
3

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

其中，idx 是 NodeList 中 AST Node 的索引，该 AST Node 必须是 .fn_proto 标签的。

下一个问题是，params_start 和 params_end 等字段仍然是一些索引，那么它们所指向的数据是什么类型的呢？答案是，它们分别对应第一个参数、最后一个参数等的 AST 节点的 NodeList 索引。这是读取有关函数原型的所有额外信息的方法。

如前所述，这里存在很多间接索引。但是现在理解这一切非常重要，否则将来的阶段将更加混乱。

函数标识符

现在，我们只剩下 main_token 字段还未讲解，这也是某些数据可能被访问的最后一种方式。

在上面函数原型的例子中，tag 和 data 等字段都不存储函数名称。实际上，.fn_proto 类型的节点使用 main_token 字段来存储函数名称。fn_proto 的 main_token 存储了指向 Token 流中 fn 关键字的索引。Zig 函数的标识符总是紧随该关键字之后。因此，你可以通过查看索引 main_token + 1 的 Token 来提取函数标识符。这正是编译器后续阶段读取标识符的方式。

小结

如果你对了解 Zig 编译器的其余工作感兴趣，深刻理解上面介绍的信息存储模式非常重要。第一次阅读时，你可能会感到很难理解（甚至第二次或第三次也是如此）。本节再次回顾 AST 的数据布局方式。

AST 节点数据可能对应到以下三个位置的内容：

1. Token 流的数据，其中存储标识符或其他值。
2. NodeList 即节点列表，用于查找其他 AST 节点。
3. extra_data 列表，即额外数据列表，用于查找额外的数据结构。

后续的 AST 节点或额外数据结构通常包含额外的索引，这些索引可能指向其他节点、某个 Token 或额外的数据结构。例如，fn_decl 节点存在一个索引指向 fn_proto 节点，fn_proto 节点存在一个索引指向额外的 FnProto 数据结构，FnProto 结构存储了指向参数的一系列 AST 节点。

确定数据是否可用以及如何访问数据取决于节点标签。你必须阅读 lib/std/zig/Ast.zig 中的注释或语法解析器的源代码，才能了解数据的确切用法。

语法解析的工作原理

现在，我们对语法解析器的内部状态和 AST 构造有了坚实的理解，可以进一步讨论语法解析器实际解析 Token 流的过程了。

抽象地说，语法解析器检查 Token 流中当前 Token 的内容，并以此作为上下文来确定下一个 Token 可以是或应该是什么。例如，在解析 Token 流 fn foo 时，第一个 Token .keyword_fn 期望的下一个 Token 应该是一个标识符。如果不是标识符，则会出现语法错误。

不同于词法分析，语法解析关心 Token 的顺序是否合理。词法分析只是单纯的从文本中产生 Token 流，因此无效的语法，例如 fn pub var foo i32 } { 也能产生一个有效的 Token 流。但是，语法解析该 Token 流将产生一个错误，因为它是无意义的。

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

1
2
3
4
5

var x = 7;

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

解析一个 Zig 文件

语法解析器的主要入口是 parse 函数，它接受一个完整的 Zig 文件源代码。这个函数会初始化解析器状态，并调用 parseContainerMembers() 来解析 Zig 文件的成员。Zig 文件隐式地是一个结构体，因此解析器实际上是在解析一个结构体。

语法解析过程对应一个 while 循环，根据当前的 Token 确定下一个期望的内容。大致结构如下：

1
2
3
4
5

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

根据当前 Token 的值，上述代码确定下一个期望的内容。第一个 Token 是 .keyword_var 因为示例文件正在定义一个变量。这将进一步调用 parseVarDecl 来解析变量声明。此外，Zig 还有许多其他有效的 Token 如 comptime/fn/pub 等。

解析变量声明

示例文件中第一个被解析的对象是一个变量声明。Zig 语法解析器最终调用 parseVarDecl 方法来产生对应的 AST 节点。其代码概略如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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,
        },
   });
}

这个函数会“吞掉”一个 const 或 var 对应的 Token 值。“吞掉”意味着 Token 被消费：返回当前 Token 并使语法解析器的 tok_i 状态值递增。如果 Token 不是对应 const 或 var 关键字，那么函数将返回 null_node 以代表一个语法错误。因为变量定义必须以 const 或 var 开头。

接下来，语法解析器期望一个变量名的标识符。如果 Token 不是标识符，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 方法来创建节点。这将返回节点列表中的索引。在这种情况下，我们创建了一个带有 .simple_var_decl 标签的节点。

如果你查看 .simple_var_decl 的注释，其中写到其对应节点的 lhs 指向类型表达式 AST 节点的索引（如果没有类型表达式，则为零），而 rhs 指向初始化表达式 AST 节点的索引（如果没有初始化，则为零）。

parseVarDecl 函数返回 .simple_var_decl AST 节点的索引。最终，这个索引会一直返回到我们开始的 parseContainerMembers 函数，并存储在 scratch 状态中。我们将在后面解释 scratch 状态的用途。现在，while 循环继续解析下一个 Token 值，它将发现 .keyword_pub Token 并开始定义一个函数。

解析函数定义

语法解析器看到 .keyword_pub 之后，将调用 parseFnProto 和 parseBlock 方法继续解析。让我们重点关注 parseFnProto 的行为，因为它执行了我们尚未见过的操作。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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 中，然后返回 extra_data 中的起始索引。正如我们之前展示的那样，AST 节点的使用者将确切地知道 fn_proto_one 类型对应的额外数据有多少个字段以及如何读取这些信息。

完成 AST 构造

语法解析会递归地继续进行，为整个程序构建 AST 节点。在解析结束时，解析器会返回一个结构化的 Ast 结构，如下所示：

1
2
3
4
5
6
7

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

现在，我们已经理解了 Zig 的词法分析和语法解析过程，也清楚 AST 节点的结构，上面这些字段的意义也不难推断。

• source 存储了完整的源代码，可以用于确定标识符字符串的内容或提供错误消息
• tokens 是 Token 的列表
• nodes 是 AST 节点的列表
• extra_data 是 AST 节点的额外数据列表
• errors 存储了可能的错误累积结果

在后续文章中，我们将讨论如何从 AST 生成中间表示，以及如何进一步做语义分析。