解析是編譯流程中接在 tokenization(詞法分析) 之後的下一個步驟。解析負責從 token 串流建構出 abstract syntax tree(抽象語法樹)。我先前已撰寫過 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) 更好的 cache locality(快取區域性)。這兩個好處通常都能帶來更好的效能。

以我們的 Tree 結構為例，MultiArrayList(Tree) 的儲存方式如下：

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

結構的每個欄位都儲存在各自獨立的連續陣列中。包含四個 tree 的陣列僅使用 20 位元組，記憶體用量減少 37.5%。這尚未計入多個陣列指標的額外開銷，但該開銷是固定的，因此隨著列表中項目數量增加，平均下來在此範例中總共可節省 37.5% 的記憶體。

本頁不會深入探討 MultiArrayList 的實作方式。就理解 Zig 編譯器而言，只需知道幾乎所有結構（tokens、AST 節點、未來的 IR 節點等）都是以 MultiArrayList 儲存即可。編譯一個實際的程式通常會產生數萬個「節點」，因此這能帶來巨大的記憶體節省並改善 cache locality。

解析器的結構

解析器使用一個名為 Parser 的 struct 來儲存解析過程中的狀態。這不是一個公開匯出的 struct，僅用於管理解析作業的內部狀態。呼叫者會在解析作業完成後收到一個 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 是 tokenization 經過解構後的結果。如前所述，解析器採用 data-oriented design(資料導向設計) 以獲得更好的記憶體使用率與 cache locality。因此，token_tags.len == token_starts.len，它們只是被置於各自獨立連續記憶體區塊中的結構欄位。tok_i 的值是解析器目前檢視之 token 的索引（從 0 開始）。

第三個群組是解析器真正的工作狀態。將成為 Ast 一部分的結果會在此累積。這第三個群組非常重要，因為它是解析器正在建構的核心內容。

• errors 是解析過程中錯誤的列表。大多數行為良好的解析器會嘗試在各種錯誤情境下繼續解析，Zig 的解析器也不例外。Zig 解析器會在此欄位中累積錯誤，並嘗試繼續解析。
• nodes 是 AST 節點的列表。一開始為空，隨著解析器持續運作而逐漸建立。理解 AST 節點的結構極為重要，將在下一節說明。
• extra_data 是 AST 節點可能需要的額外資訊列表。例如，對於 struct，extra_data 包含所有 struct 成員的完整列表。這又是 data-oriented design 的一個範例；另一種做法是將額外資料直接放在 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 結構的每個欄位分別儲存在獨立的連續記憶體區塊中。在概念上，你可以將節點視為如上所示的單一 struct，但在實際使用時，這些欄位是被拆開儲存的。

節點的 tag 是所有可能 AST 節點型別的 enum。例如，用於函式宣告的 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 中的索引值是 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] 只是指向另一個索引。並非如此，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，而 fn_proto 又指向額外資料的 FnProto 結構，該結構則為每個參數指向一個 AST 節點。

可用的資料有哪些以及如何存取，取決於 tag。你必須閱讀 lib/std/zig/Ast.zig 中的註解或閱讀解析器的原始碼，才能確定究竟設定了哪些資料。

解析的運作方式

在紮實理解內部解析器狀態的資訊以及所產生 AST 的結構後，我們現在可以來了解解析器實際上如何解析 token 串流。

抽象來說，解析器透過檢視 token 串流中的目前 token，並以此作為上下文來判斷下一個 token 可以或應該是什麼。例如，在解析 fn foo 的 token 串流時，看到的第一個 token 是 .keyword_fn，而預期下一個 token 會是識別字。如果不是識別字，即為語法錯誤。

與 tokenizer(詞法分析器) 不同，解析器會在意 token 的順序是否合理。Tokenizer 只是盲目地產生 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 開頭）。

接下來，我們預期變數名稱為一個識別字。如果 token 不是識別字，expectToken 函式會回傳錯誤。例如，若我們寫了 var 32，解析器就是在此處建立並儲存錯誤，指出其預期為識別字，卻得到整數常值。

接下來，有幾種可能的情況。透過在 eatToken 周圍使用條件判斷，我們可以決定下一步該做什麼。如果下一個 token 是冒號，我們預期會找到一個型別運算式。例如 var x: u32。但型別運算式是選用的，而我們的實際範例並沒有，因此這會將 type_node 設為零。

接著我們檢查下一個 token 是否為等號 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,
};

至此，如果你已閱讀過 tokenization 頁面並完全理解解析器與 AST 節點的結構，這些欄位中的每一個都應該都能理解。AST 以 source 保存完整原始碼（用於判斷識別字字串、錯誤訊息等）、以 tokens 保存 token 列表、以 nodes 保存 AST 節點列表、以 extra_data 保存 AST 節點的額外資料，以及以 errors 保存可能累積的錯誤列表。

接下來是 AstGen 流程。