解析（Parsing）是詞法分析之後，編譯流程中的下一個步驟。解析負責從詞彙串流中建構出抽象語法樹。我先前已經寫過 Zig 如何將位元組串流（原始碼）轉換為詞彙串流。

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 編譯器而言，重要的是知道幾乎所有結構（詞彙、AST 節點、未來的 IR 節點等）都是以 MultiArrayList 的形式儲存。編譯一個實際的程式通常會產生數以萬計的「節點」，因此這種設計能大幅節省記憶體並提升快取局部性。

解析器的結構

解析器使用一個名為 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 檔案的配置器（allocator）與完整的原始碼。

第二組中的 token_tags 和 token_starts 是詞法分析結果經拆解後的資料。如前所述，解析器採用資料導向設計（data-oriented design）以獲得更好的記憶體使用率與快取局部性。因此，token_tags.len == token_starts.len，它們只是將 struct 的欄位分別存放在獨立的連續記憶體區塊中。tok_i 則是解析器目前正在檢視的詞彙索引（從 0 開始）。

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

• errors 是解析過程中累積的錯誤清單。大多數行為良好的解析器會嘗試在各種錯誤情境下繼續解析，Zig 的解析器也是如此。Zig 解析器會將錯誤累積在此欄位中，並嘗試繼續解析。
• nodes 是 AST 節點的清單。一開始是空的，隨著解析的進行會逐步建構。理解 AST 節點的結構極為重要，下一節將詳細說明。
• extra_data 是一份 AST 節點可能需要的額外資訊清單。例如，對於 struct，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 結構的每個欄位都儲存在各自獨立的連續記憶體區塊中。概念上，你可以將節點視為如上所示的單一 struct，但在實際使用時，這些欄位是被拆開儲存的。

節點的 tag 是所有可能 AST 節點類型的列舉。例如，fn_decl 代表函式宣告，integer_literal 代表整數字面值，builtin_call 代表對 @enumToInt 這類內建函式的呼叫。

main_token 欄位目前不需要深入理解。它是與 AST 節點相關的主要詞彙。舉例來說，對於函式宣告，它可能是 fn。這個值是指向用來建構 AST 的詞彙清單中的索引。

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 除了直接的型別識別符之外，也支援各種用於在編譯期計算回傳型別的運算式）。

然而，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 是詞彙串流中「fn」關鍵字的索引。在 Zig 中，函式識別符永遠緊接在這個關鍵字之後。因此，你可以透過查看索引為 main_token + 1 的詞彙來取得函式識別符。這正是編譯器後續階段讀取識別符的方式。

AST 資料佈局回顧

如果你想了解 Zig 編譯器其餘部分如何運作，深入理解這種資訊儲存模式極為重要。第一次閱讀時可能難以理解（或許第二、第三次也是）。本節將回顧 AST 的資料佈局方式。

AST 節點的資料可以在三個位置找到：

1. 詞彙串流（用於識別符等值）
2. 節點清單，用於尋找其他 AST 節點
3. 額外資料清單，用於尋找額外的資料結構

後續的 AST 節點或額外資料結構通常還包含額外的索引，可能指向更多的節點、額外資料結構或詞彙。例如，一個 fn_decl 指向一個 fn_proto，fn_proto 再指向一個額外的 FnProto 結構，而該結構則為每個參數各指向一個 AST 節點。

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

解析如何運作

在已經扎實理解了解析器內部狀態與最終 AST 結構的資訊如何組織之後，現在我們可以來了解解析器實際上如何解析詞彙串流。

抽象來說，解析器的工作方式是檢查詞彙串流中的當前詞彙，並以此作為上下文來判斷下一個詞彙可以或應該是什麼。舉例來說，在解析 fn foo 的詞彙串流時，看到的第一個詞彙是 .keyword_fn，而預期中的下一個詞彙應該是識別符。如果不是識別符，那就是語法錯誤。

與詞法分析器不同，解析器會在意詞彙的順序是否合理。詞法分析器只是盲目地產生詞彙，因此像 fn pub var foo i32 } { 這樣無效的語法也會產生一個有效的詞彙串流。但解析器看到該串流後，會因為其毫無意義而產生錯誤。

接下來，讓我們具體看看解析器如何解析如下所示的簡單 Zig 檔案。

var x = 7;

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

解析一個 Zig 檔案

主要的進入點是 parse() 函式，它接收一個 Zig 檔案的完整原始碼。它會初始化解析器狀態，並呼叫 parseContainerMembers() 來解析 Zig 檔案中的成員。一個 Zig 檔案隱含地就是一個 struct，因此解析器實際上是在解析一個 struct。

這會進入一個 while 迴圈，透過檢視當前詞彙來決定接下來預期什麼。其結構大致如下：

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

根據當前的詞彙，它會決定接下來預期什麼。我們的範例檔案第一個詞彙是 .keyword_var，因為它定義了一個變數。這最終會導向 parseVarDecl 來解析變數宣告。在這個位置還有許多其他有效的詞彙：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,
        },
   });
}

這會「吃掉」第一個詞彙：const 或 var（二者皆由這個解析函式處理）。「吃掉」詞彙意味著將其消耗：回傳當前詞彙，並將解析器狀態中的 tok_i 索引遞增。如果既不是 const 也不是 var，就會回傳 null_node 值，並在呼叫鏈上層產生錯誤（變數宣告必須以 const 或 var 開頭）。

接著，我們預期變數名稱是一個識別符。如果該詞彙不是識別符，expectToken 函式會回傳錯誤。例如，如果我們寫 var 32，解析器就會在此處建立並儲存一個錯誤，指出它預期的是識別符，卻得到了一個整數字面值。

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

接著我們檢查下一個詞彙是否為等號。如果是，我們就預期會找到一個變數初始化運算式。我們的變數宣告確實有這個部分，因此這會建立一個 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 迴圈會繼續解析並尋找下一個詞彙，也就是作為函式定義開頭的 .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 函式接收一個包含所有值的 struct，並以型別安全的方式將其編碼到 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 的詞彙清單、作為 nodes 的 AST 節點清單、作為 extra_data 的 AST 節點額外資料，以及作為 errors 的已累積錯誤清單。

接下來是 AstGen 流程。