Zig Parser

2022-02-11

Zig 파서

파싱은 토큰화 다음에 이어지는 컴파일 파이프라인의 다음 단계입니다. 파싱은 토큰 스트림으로부터 추상 구문 트리를 구성하는 역할을 합니다. 이전에 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바이트의 메모리를 필요로 합니다. 4개의 트리로 이루어진 배열은 32바이트의 메모리입니다.

왜 8바이트일까요? u32는 4바이트가 필요합니다. bool은 1바이트만 필요하지만 u32와 함께 구조체 안에 있기 때문에 4바이트 정렬을 맞춰야 하므로 역시 4바이트를 차지합니다(3바이트 낭비). 총합은 8바이트입니다.

MultiArrayList 역시 동적으로 할당되는 항목 리스트라는 점에서는 동일합니다. 다만 배열 리스트에 저장되는 타입의 각 필드가 별도의 연속된 배열에 저장된다는 차이가 있습니다. 이는 두 가지 주요 이점이 있습니다. (1) 정렬로 인한 바이트 낭비가 적고, (2) 캐시 지역성이 더 좋습니다. 이러한 이점들은 종종 더 나은 성능으로 이어집니다.

앞서 본 Tree 구조체를 예로 들면, MultiArrayList(Tree)는 다음과 같이 저장됩니다:

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

구조체의 각 필드는 별도의 연속된 배열에 저장됩니다. 4개의 트리를 담은 배열은 20바이트를 사용하며, 이는 37.5% 적은 메모리입니다. 이는 여러 배열 포인터의 오버헤드를 제외한 수치이지만, 해당 오버헤드는 고정되어 있으므로 리스트의 항목 수가 늘어날수록 결국 이 예시에서는 총 37.5% 적은 메모리가 필요하도록 상쇄됩니다.

왜 20바이트일까요? 구조체가 분해되었기 때문에 age 필드는 4바이트가 필요하고, 예시에서는 트리가 4개이므로 16바이트가 됩니다. alive 필드는 더 이상 구조체의 일부가 아니므로 4바이트 정렬이 필요하지 않아 1바이트만 필요합니다(낭비되는 바이트 없음!). 예시에서는 트리가 4개이므로 alive에 4바이트가 필요합니다. 두 필드를 합치면 총 20바이트가 됩니다.

이 페이지에서는 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 파일의 전체 원본 소스 코드와 할당자(allocator)입니다.

두 번째 그룹에서 token_tags와 token_starts는 토큰화 결과를 분해한 것입니다. 앞서 언급했듯이 파서는 메모리 사용량과 캐시 지역성을 개선하기 위해 데이터 지향 설계를 적용합니다. 따라서 token_tags.len == token_starts.len이며, 이는 단순히 구조체 필드들을 별도의 연속된 메모리 덩어리로 나눈 것입니다. tok_i 값은 파서가 현재 바라보고 있는 토큰의 인덱스(0부터 시작)입니다.

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

errors는 파싱이 진행됨에 따라 발생하는 오류 목록입니다. 대부분의 잘 동작하는 파서는 다양한 오류 상황에서도 파싱을 계속 시도하며, Zig 파서도 마찬가지입니다. Zig 파서는 이 필드에 오류를 누적하고 파싱을 계속 시도합니다.
nodes는 AST 노드 목록입니다. 빈 상태에서 시작해 파서가 진행됨에 따라 점차 채워집니다. AST 노드의 구조를 이해하는 것은 매우 중요하며, 다음 섹션에서 다룹니다.
extra_data는 AST 노드가 필요로 할 수 있는 추가 정보 목록입니다. 예를 들어 구조체의 경우 extra_data에는 구조체의 모든 멤버 전체 목록이 들어 있습니다. 이 역시 데이터 지향 설계의 한 예입니다. 대안으로 추가 데이터를 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의 경우 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 노드의 일부 데이터에 접근하는 마지막 방법입니다. 함수 프로토타입의 경우 식별자 자체(함수 이름)가 어디에도 보이지 않는다는 것을 알 수 있습니다.

.fn_proto와 같은 일부 AST 노드는 이를 위해 main_token 필드를 사용합니다. fn_proto의 main_token은 토큰 스트림에서 “fn” 키워드에 대한 인덱스입니다. Zig에서는 함수 식별자가 항상 이 키워드 바로 뒤에 옵니다. 따라서 main_token + 1 인덱스에 있는 토큰을 보면 함수 식별자를 추출할 수 있습니다. 이는 컴파일러의 이후 단계에서 식별자를 읽는 정확한 방식입니다.

AST 데이터 레이아웃 정리

Zig 컴파일러의 나머지 부분이 어떻게 동작하는지 알고 싶다면, 이 정보 저장 패턴을 깊이 이해하는 것이 매우 중요합니다. 처음 읽을 때(그리고 두세 번째에도) 이해하기 어려울 수 있습니다. 이 섹션에서는 AST를 위한 데이터가 어떻게 배치되는지 정리합니다.

AST 노드 데이터는 세 곳에서 찾을 수 있습니다:

토큰 스트림(식별자 같은 값들)
다른 AST 노드를 찾기 위한 노드 리스트
추가 데이터 구조를 찾기 위한 extra_data 리스트

후속 AST 노드나 extra_data 구조는 보통 추가 노드, extra_data 구조 또는 토큰을 가리킬 수 있는 추가 인덱스를 포함합니다. 예를 들어 fn_decl은 fn_proto를 가리키고, fn_proto는 extra_data의 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 파일 파싱하기

주요 진입점은 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,
        },
   });
}

이는 첫 번째 토큰을 “먹습니다(eat)”: const 또는 var 중 하나입니다(이 파싱 함수는 둘 다에 사용됩니다). 토큰을 “먹는다”는 것은 토큰이 소비된다는 의미입니다. 현재 토큰이 반환되고 파서 상태의 tok_i 인덱스가 증가합니다. const나 var가 아니라면 null_node 값이 반환되어 호출 체인 상위로 오류가 전파됩니다(변수 선언은 반드시 const 또는 var로 시작해야 합니다).

다음으로 변수 이름에 대한 식별자를 기대합니다. expectToken 함수는 토큰이 식별자가 아니면 오류를 반환합니다. 예를 들어 var 32라고 작성했다면, 파서는 식별자를 기대했지만 정수 리터럴을 받았다는 오류를 바로 이 지점에서 생성해 저장합니다.

다음으로는 몇 가지 가능한 경우가 있습니다. eatToken을 조건문으로 감싸서 다음에 무엇을 할지 결정합니다. 다음 토큰이 콜론이라면 타입 표현식을 기대합니다. 예를 들어 var x: u32 같은 경우입니다. 하지만 타입 표현식은 선택 사항이며 실제 예시에는 없으므로 type_node는 0으로 설정됩니다.

그 다음 다음 토큰이 equal 토큰인지 확인합니다. 그렇다면 변수 초기화 표현식을 기대합니다. 예시의 변수 선언에는 초기화가 있으므로, 이는 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로, AST 노드 목록을 nodes로, AST 노드를 위한 추가 데이터를 extra_data로, 그리고 누적된 오류들의 잠재적 목록을 errors로 가지고 있습니다.

다음은 AstGen 과정입니다.