Zig Tokenizer

2022-02-10

Zig 分词器

Tokenization(分词)是典型编译器流水线中的第一步。Tokenization是将字节流（编程语言语法）转换为 Token(词元)流的过程。

以 Zig 为例，语法 comptime {} 会被分词为 [.keyword_comptime, .l_brace, .r_brace]。Tokenizer(分词器)通常不处理语义，也不判断一组 Token 是否有意义。例如，comptime [] 并非有意义的 Zig 语法，但 Tokenizer 仍会将其转换为 [.keyword_comptime, .l_bracket, .r_bracket]。由解析器（分词之后的下一步）来赋予语义并在无效情况下报错。

编写 Tokenizer 的方法有很多。本文将重点介绍 Zig 的 Tokenizer 是如何工作的，并不打算将其与其他编写 Tokenizer 的方法进行比较。

Zig 分词器

Zig 语言的 Tokenizer 是 Zig 标准库的一部分，位于 lib/std/zig/tokenizer.zig，并以 std.zig.Tokenizer 对外暴露。Tokenizer 以字节切片作为输入，一次产生一个 Token，直至 EOF。Tokenizer 不会进行任何分配。

在深入了解其工作原理之前，先看一下基本用法：

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

Tokenizer 的一些值得一提的重要特性：

操作切片而非流 - Tokenizer 接受 [:0] const u8 作为输入，而非 reader。这意味着对于足够大的输入，由调用者负责缓冲并分批调用 Tokenizer。在实践中，编程语言的输入并不会“足够大”，因此整个源文件会一次性完成分词；如今的 Zig 也是这样工作的。
不分配内存 - Tokenizer 不执行任何堆分配。在系统编程中，了解 API 的内存使用和分配特性总是很有用的。顺带一提：在 Zig 中，这一点一目了然，因为 Tokenizer 在任何地方都不会将 Allocator 作为参数。

Tokenizer 的结构同样简单（如下所示）。Tokenizer 存储缓冲区、缓冲区中的当前位置索引（从零开始）以及一个潜在的无效 Token（本文将忽略它）。

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

    // ...
};

即使你对 Tokenizer 一无所知，有了这些状态，Tokenizer 的工作原理也应该很清楚了。Tokenizer 在缓冲区中一次向前移动一个字节的索引并构造 Token。

Token 的构成

在了解了 Tokenizer 的高层 API 之后，下一个问题是：Token 的构成是什么？在 Zig 中，Token 是如下结构：

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 字段中，该字段由 start 和 end 索引组成。给定这些索引和原始源文本（用于初始化 Tokenizer），调用者可以使用 source[tok.loc.start .. tok.loc.end] 提取 Token 的文本。仅存储起点和终点是一种常见的效率技巧。

Token 中给出的信息是基础的——一个标签、一个位置——但不同 Tokenizer 之间的结构可能有所不同。例如，Go 分词器将 Token 建模为 int 常量，而 Go 中与 next() 等效的函数会将 Token 的 int 值、作为 int 字节偏移的位置以及 Token 的字面量字符串捕获作为不同的返回值返回，因为 Go 支持多返回值。这与 Zig 大同小异，但细微的差异确实会对编译器的人体工程学乃至性能产生重要影响。

查找下一个 Token

Tokenizer 通过调用 next() 函数一次返回一个 Token。

该函数从缓冲区中的当前索引开始，一次查看一个字节来构造 Token。它使用单个 state 变量来实现状态机，以跟踪接下来可能出现的内容。

在了解 Zig Tokenizer 的实际状态之前，我们先从高层面来考虑这种方法。让我们看看输入 while（包括空格）将如何被分词。

首先，Tokenizer 会看到字符 w。此时，我们知道它不可能是数字，但它仍然可能是关键字或标识符，因此我们还没有得到一个完整的 Token。我们一次只看一个字符，所以我们获取下一个字符：h。这仍然可能是标识符或关键字，所以我们继续。i、l、e。现在，我们得到了 while，我们知道它本身是一个关键字，但它仍然可能是标识符，因为后面可能还有更多字符，所以我们必须再向前看一个字符。下一个输入是空白字符。现在我们确切地知道它是 while 关键字，而不是标识符，并且可以返回一个 Token。如果下一个字节是诸如 1 之类的字符，我们就会知道我们正在构造一个标识符（尚未完成），并且它永远不可能是关键字（没有关键字以 while1 开头）。

这就是 Zig Tokenizer 的工作原理。它维护一个当前状态（例如“我们知道正在构建一个标识符或关键字”），并一次查看一个字符，直到明确地确定 Token。

Tokenizer 只查看状态和当前字符；它不会向后看，也不会向前窥视。大多数 Tokenizer 都不会。如开头所述，Tokenizer 不关心语义，因此诸如 if while comptime x = 7 { else } 之类无意义的输入也会产生有效的 Token 流。由解析器来接收 Token 流并为其赋予语义。

Zig 实现

next() 的实现是通过嵌套的 while 和 switch 完成的。片段如下所示。

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 或缓冲区为空时 break。Zig 的一个很好的特性是，buffer 的类型是 [:0] const u8，而 :0 告诉我们缓冲区保证以 0 字节结尾，因此我们可以寻找它来跳出循环。

接下来，Tokenizer 会根据当前的 state（一个枚举）进行 switch。然后，给定一个状态，我们再对当前字符进行 switch，以确定下一步该做什么。在上面的片段中，你可以看到看到像 A 这样的首字符会如何将状态转移到 .identifier 以构建标识符。

从 Token 到树

编译器的下一阶段是解析器。解析器接收由 Tokenizer 生成的 Token 流，并将其转换为稍微更有意义的抽象语法树。请继续阅读关于Zig 解析器的内容。