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]。是否賦予語意並在無效情況下報錯，則取決於 Parser(剖析器)（Tokenization 之後的下一個步驟）。

撰寫 Tokenizer 的方法有很多。本頁將聚焦於 Zig 的 Tokenizer 如何運作，而不會嘗試將其與其他撰寫 Tokenizer 的方法進行比較。

Zig Tokenizer

Zig 語言的 Tokenizer 是 Zig 標準函式庫的一部分，位於 lib/std/zig/tokenizer.zig，並以 std.zig.Tokenizer 的形式公開。Tokenizer 以位元組的 slice 作為輸入，一次產生一個 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 值得一提的一些重要特性：

操作 slice，而非 stream - Tokenizer 以 [:0] const u8 作為輸入，而非 reader。這表示對於足夠大的輸入，由呼叫者負責緩衝並分批呼叫 Tokenizer。實務上，程式語言的輸入並不會「足夠大」，因此整個原始檔會一次性完成詞法分析；Zig 目前也是如此運作。
不會進行配置 - Tokenizer 不會執行任何堆積配置。在系統程式設計中，了解 API 的記憶體使用情況與配置特性總是很有用。附註：在 Zig 中，這一點一目了然，因為 Tokenizer 在任何參數中都不會接受 Allocator。

Tokenizer 的結構同樣簡單（如下所示）。Tokenizer 會儲存 buffer、指向 buffer 的目前索引（從零開始），以及一個潛在的無效 Token（本文將忽略此部分）。

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

    // ...
};

即使你對 Tokenizer 一無所知，也應該能從此狀態看出 Tokenizer 如何運作。Tokenizer 會在 buffer 中一次向前移動一個位元組的索引並建構 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 欄位是一個 enum，代表所有可能的 Token 類型。標籤的例子包括 .keyword_comptime, .l_brace, .r_brace, .eof。撰寫本文時，Zig 約有 120 種不同的 tag。

接著，Token 的位置儲存於 loc 欄位中，該欄位由 start 與 end 索引組成。有了這些索引與用於初始化 Tokenizer 的原始程式碼，呼叫者便可使用 source[tok.loc.start .. tok.loc.end] 擷取 Token 的文字。僅儲存起點與終點是一種常見的效率技巧。

Token 中提供的資訊非常基本——一個 tag、一個位置——但不同 Tokenizer 之間的結構可能有所不同。例如，Go Tokenizer 將 Token 建模為 int 常數，而 Go 中等同於 next() 的函式會將 Token int、作為 int 位元組偏移量的位置，以及 Token 的字面字串擷取，分別作為不同的回傳值回傳，因為 Go 支援多重回傳值。這與 Zig 的做法大致相同，但細微的差異確實會對編譯器的人體工學與效能產生重要影響。

尋找下一個 Token

Tokenizer 透過呼叫 next() 函式一次回傳一個 Token。

此函式從指向 buffer 的目前索引開始，一次查看一個位元組來建構 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 串流。由 Parser 負責接收 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 是一個無窮迴圈，會持續執行，並在 buffer 中一次迭代一個字元。迴圈主體預期在找到 Token 或 buffer 為空時 break。Zig 的一個優點是，buffer 的型別為 [:0] const u8，而 :0 表示 buffer 保證以 0 位元組結尾，因此我們可以藉由尋找該位元組來跳出迴圈。

接著，Tokenizer 會根據目前的 state（一個 enum）進行 switch。接著，根據該狀態，再對目前的字元進行 switch，以決定下一步該做什麼。在上面的片段中，你可以看到當看到像 A 這樣的第一個字元時，狀態會轉換為 .identifier 以開始建構識別字。

從 Token 到語法樹

編譯器的下一個階段是 Parser。Parser 會接收由 Tokenizer 產生的 Token 串流，並將其轉換為更具意義的抽象語法樹。請繼續閱讀關於 Zig Parser 的介紹。