パースは、コンパイルパイプラインにおいてトークナイズに続く次のステップである。パースは、トークンのストリームから抽象構文木を構築する役割を担う。以前、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     │     ...      │
       └──────────────┴──────────────┴──────────────┴──────────────┘

1つのTreeは8バイトのメモリを必要とする。Treeを4つ格納した配列は32バイトになる。

MultiArrayListも同様に、動的に確保される要素のリストである。ただし、配列リストに格納される型の各フィールドは、それぞれ別の連続した配列に格納される。これには主に2つの利点がある。(1) アライメントによる無駄なバイトが減ること、(2) キャッシュ局所性が向上することである。これら2つの利点は、しばしばパフォーマンスの向上につながる。

先ほどのTree構造体を例にすると、MultiArrayList(Tree)は次のように格納される。

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

構造体の各フィールドは、それぞれ別の連続した配列に格納される。Treeを4つ格納した配列は20バイトとなり、37.5%少ないメモリで済む。これは複数の配列ポインタのオーバーヘッドを無視した値だが、そのオーバーヘッドは固定であるため、リスト内の要素数が増えるにつれて償却され、この例では最終的に37.5%のメモリ削減となる。

本ページではMultiArrayListがどのように実装されているかまでは深入りしない。Zigコンパイラを理解する上では、ほぼすべての構造（トークン、ASTノード、将来のIRノードなど）がMultiArrayListとして格納されていることを知っておくことだけが重要である。実際のプログラムをコンパイルすると、通常数万もの「ノード」が生成されるため、これにより大幅なメモリ節約とキャッシュ局所性の向上がもたらされる。

パーサーの構造

パーサーはParserという構造体を使って、進行中のパース状態を保持する。これは公開されている構造体ではなく、パース処理の内部状態を管理するためだけに使われる。呼び出し元にはパース処理の結果として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ファイルの完全な元のソースコードである。

2つ目のグループでは、token_tagsとtoken_startsはトークナイズ結果を分解したものである。前述のとおり、パーサーはメモリ使用量とキャッシュ局所性を改善するためにデータ指向設計を採用している。そのためtoken_tags.len == token_starts.lenであり、これらは単に構造体のフィールドを別々の連続したメモリ領域に配置したものに過ぎない。tok_iはパーサーが現在見ているトークンのインデックス（0から始まる）である。

3つ目のグループがパーサーの実際の作業状態である。ここにAstの一部となる結果が蓄積されていく。この3つ目のグループは、パーサーが構築しているものの中核であるため、非常に重要である。

• errorsは、パースが進むにつれて発生したエラーのリストである。行儀の良いパーサーの多くは、さまざまなエラー状況でもパースを継続しようとするが、Zigのパーサーも同様である。Zigのパーサーはこのフィールドにエラーを蓄積しつつ、パースを継続しようとする。
• nodesはASTノードのリストである。最初は空で、パースが進むにつれて徐々に構築されていく。ASTノードの構造を理解することは極めて重要であり、次のセクションで解説する。
• extra_dataは、ASTノードが必要とする追加情報のリストである。例えば構造体の場合、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構造体の各フィールドが別々の連続したメモリブロックに格納されていることを意味する。概念的には、上記のようにノードを単一の構造体として考えることができるが、実際に使用される際にはフィールドは分割されている。

ノードのtagは、取りうるASTノードの種別を表すenumである。例えば、関数宣言を表すfn_decl、整数リテラルを表すinteger_literal、@enumToIntのようなビルトイン呼び出しを表すbuiltin_callなどがある。

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ノードのタグはfn_declである。

fn_declの場合、dataフィールドのlhsには関数プロトタイプ（名前、型情報など）へのインデックスが格納され、rhsフィールドには関数本体へのインデックスが格納される。これを知る唯一の方法は、.fn_declタグの上のコメントを読むか、ソースコードを読むか、あるいはその両方である。

この場合、lhsとrhsのインデックス値は、NodeList内のNodeの配列インデックスである。つまり、関数プロトタイプはtree.nodes[lhs]にあることになる（擬似コードであり、厳密には正しくない）。

つまりこの場合、dataの両方のフィールドはNodeListのインデックスを格納するために使われている。これがdataの一つの使い方であり、ASTノードに関する情報がどのように格納されるかの一例である。次に、関数プロトタイプを見て、パラメータリスト、戻り値の型、呼び出し規約をどのように特定するかを見てみよう。

関数プロトタイプ

関数プロトタイプはtree.nodes[lhs]のノードを読むことで取得できる。このノードのタグは、この場合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]として使うことが、単に別のインデックスを指しているだけのように見えるかもしれない。そうではない。.fn_protoの場合、lhsは単にextra_data内の最初のインデックスを指しているだけである。その後に読み取るフィールドの数も、タグによって決まる。fn_protoの場合は6つのフィールドである。なぜ6つだとわかるのか？ ソース内のコメント、あるいはエンコードされている構造体を読むことでわかる。

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コンパイラの残りの部分がどのように動作するかを知りたいのであれば、この情報格納パターンを深く理解することが極めて重要である。一度読んだだけでは理解が難しいかもしれない（2回、3回読んでも難しいかもしれない）。このセクションでは、ASTのデータがどのように配置されているかを復習する。

ASTノードのデータは、3つの場所に存在しうる。

1. トークンストリーム（識別子などの値）
2. 他のASTノードを探すためのノードリスト
3. 追加のデータ構造を探すための追加データリスト

後続のASTノードや追加データ構造は、通常、追加のノード、追加データ構造、またはトークンを指すさらなるインデックスを含んでいる。例えば、fn_declはfn_protoを指し、fn_protoは追加データのFnProto構造体を指し、それがパラメータごとに1つの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ファイルのパース

主要なエントリーポイントは、Zigファイルの完全なソースコードを受け取るparse()関数である。これはパーサーの状態を初期化し、ZigファイルのメンバーをパースするためにparseContainerMembers()を呼び出す。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がゼロに設定される。

次に、次のトークンがイコールであるかどうかをチェックする。そうであれば、変数の初期化式があることを期待する。今回の変数宣言にはそれがあるため、ここで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ループはパースを続行し、次のトークンを探す。それは関数定義の始まりである.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関数はすべての値を持つ構造体を受け取り、それを型安全な方法で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プロセスである。