파싱은 토크나이제이션 다음에 이어지는 컴파일 파이프라인의 다음 단계입니다. 파싱은 토큰 스트림으로부터 추상 구문 트리를 구성하는 역할을 합니다. 이전에 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라는 구조체를 사용해 진행 중인 파싱 상태를 저장합니다. 이는 공개적으로 export되는 구조체가 아니며 파싱 작업의 내부 상태를 관리하는 데만 사용됩니다. 호출자에게는 파싱 작업의 결과로 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는 토크나이제이션 결과를 분해한 것입니다. 앞서 언급했듯이 파서는 더 나은 메모리 사용량과 캐시 지역성을 위해 데이터 지향 설계를 적용합니다. 따라서 token_tags.len == token_starts.len이며, 이는 단순히 구조체 필드를 별도의 연속된 메모리 덩어리에 배치한 것입니다. tok_i 값은 파서가 현재 보고 있는 토큰의 인덱스(0부터 시작)입니다.

세 번째 그룹은 파서의 실제 작업 상태입니다. Ast의 일부가 될 결과들이 이곳에 누적됩니다. 이 세 번째 그룹은 파서가 구축하는 핵심이므로 매우 중요합니다.

• errors는 파서가 진행됨에 따라 발생하는 오류 목록입니다. 잘 동작하는 대부분의 파서는 다양한 오류 상황에서도 파싱을 계속 시도하며, Zig 파서 역시 마찬가지입니다. Zig 파서는 이 필드에 오류를 누적하고 파싱을 계속 시도합니다.
• nodes는 AST 노드 목록입니다. 빈 상태에서 시작해 파서가 진행됨에 따라 점차 채워집니다. AST 노드의 구조를 이해하는 것은 매우 중요하며 다음 섹션에서 다룹니다.
• extra_data는 AST 노드가 필요로 할 수 있는 추가 정보 목록입니다. 예를 들어 struct의 경우 extra_data는 모든 struct 멤버의 전체 목록을 포함합니다. 이는 다시 데이터 지향 설계의 예시입니다. 대안적인 접근법은 추가 데이터를 Node에 직접 넣는 것이겠지만, 이는 각 Node를 훨씬 크게 만들어 전체 파서를 느리게 합니다.
• scratch는 파서가 공유하는 임시 작업 공간으로, 보통 노드나 extra_data를 위한 정보를 구축하는 데 사용됩니다. 파서 작업이 끝나면 해제됩니다.

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 중 하나를 가리킬 수 있습니다.

다시 상기하자면 extra_data의 타입은 []Index입니다. lhs가 tree.extra_data[lhs]로 사용되는 것이 단순히 또 다른 인덱스를 가리키는 것처럼 보일 수 있습니다. 그렇지 않습니다. lhs(.fn_proto의 경우)는 단지 extra_data에서 첫 번째 인덱스를 가리킬 뿐입니다. 이후에 읽어야 할 필드 수도 태그에 따라 달라집니다. 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. 추가 데이터 구조를 찾기 위한 extra data 리스트

이후의 AST 노드나 extra data 구조는 일반적으로 추가 노드, 추가 데이터 구조 또는 토큰을 가리킬 수 있는 추가 인덱스를 포함합니다. 예를 들어 fn_decl은 fn_proto를 가리키고, fn_proto는 각 매개변수당 하나의 AST 노드를 가리키는 extra data FnProto 구조를 가리킵니다.

어떤 데이터를 사용할 수 있고 어떻게 접근하는지는 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는 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에 대한 인덱스입니다. 이는 extra_data가 어떻게 작성되는지를 보여줍니다. addExtra 함수는 모든 값을 담은 구조체를 받아 타입 안전한 방식으로 extra_data에 인코딩한 뒤 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 과정입니다.