이 글은 Zig 컴파일러 내부 구조 시리즈의 일부입니다.

토큰화는 일반적인 컴파일러 파이프라인의 첫 단계이다. 토큰화는 바이트 스트림(프로그래밍 언어 문법)을 토큰 스트림으로 변환하는 과정이다.

Zig를 예로 들면, comptime {} 구문은 [.keyword_comptime, .l_brace, .r_brace]로 토큰화된다. 토크나이저는 보통 의미나 토큰 집합이 유의미한지 여부를 다루지 않는다. 예를 들어 comptime []는 유의미한 Zig 문법이 아니지만, 토크나이저는 이를 기꺼이 [.keyword_comptime, .l_bracket, .r_bracket]로 변환한다. 의미 부여와 잘못된 경우의 오류 처리는 토큰화 다음 단계인 파서의 몫이다.

토크나이저를 작성하는 방법은 여러 가지가 있다. 이 글에서는 Zig 토크나이저가 어떻게 동작하는지에 집중하며, 다른 토크나이저 작성 방식과의 비교는 다루지 않는다.

Zig 토크나이저

Zig 언어의 토크나이저는 Zig 표준 라이브러리의 일부로, lib/std/zig/tokenizer.zig에 있으며 std.zig.Tokenizer로 노출된다. 토크나이저는 바이트 슬라이스를 입력으로 받아 EOF에 도달할 때까지 한 번에 하나의 토큰을 생성한다. 토크나이저는 할당을 수행하지 않는다.

어떻게 동작하는지 자세히 살펴보기 전에, 기본적인 사용법을 먼저 살펴보자:

const std = @import("std");
const expect = std.testing.expect;

const tok = std.zig.Tokenizer.init("comptime {}");
try expect(tok.next() == .keyword_comptime);
try expect(tok.next() == .l_brace);
try expect(tok.next() == .r_brace);
try expect(tok.next() == .eof);

언급할 만한 토크나이저의 중요한 특성 몇 가지는 다음과 같다:

• 슬라이스에서 동작하며, 스트림이 아니다 - 토크나이저는 reader가 아니라 [:0] const u8을 입력으로 받는다. 따라서 입력이 충분히 큰 경우, 버퍼링하고 토크나이저 호출을 배치로 나누는 것은 호출자의 책임이다. 실제로 프로그래밍 언어 입력은 “충분히 크지” 않기 때문에 전체 소스 파일을 한 번에 토큰화한다. 현재 Zig도 같은 방식으로 동작한다.
• 할당을 하지 않는다 - 토크나이저는 힙 할당을 전혀 수행하지 않는다. 시스템 프로그래밍에서는 API의 메모리 사용량과 할당 특성을 이해하는 것이 항상 유용하다. 참고로 Zig에서는 Tokenizer가 어떤 경우에도 Allocator를 파라미터로 받지 않으므로 이 점이 바로 드러난다.

토크나이저의 구조 역시 마찬가지로 단순하다(아래 참조). 토크나이저는 버퍼와 버퍼 내 현재 인덱스(0부터 시작), 그리고 잠재적인 invalid 토큰(이 글에서는 다루지 않는다)을 저장한다.

pub const Tokenizer = struct {
    buffer: [:0]const u8,
    index: usize,
    pending_invalid_token: ?Token,

    // ...
};

토크나이저에 대해 아무것도 몰라도, 이 상태만으로 토크나이저가 어떻게 동작하는지 짐작할 수 있을 것이다. 토크나이저는 버퍼에서 인덱스를 한 바이트씩 앞으로 이동시키며 토큰을 만들어낸다.

토큰의 구조

토크나이저의 상위 수준 API를 이해했으니, 다음 질문은 토큰의 구조가 어떻게 생겼는가이다. Zig에서 토큰은 다음과 같은 구조체이다:

pub const Token = struct {
    tag: Tag,
    loc: Loc,

    pub const Loc = struct {
        start: usize,
        end: usize,
    };

    pub const Tag = enum {
        invalid,
        // ...
    };
};

tag 필드는 가능한 모든 토큰 타입을 나타내는 enum이다. 태그의 예로는 .keyword_comptime, .l_brace, .r_brace, .eof가 있다. 이 글을 쓰는 시점에서 Zig에는 약 120개의 서로 다른 태그가 있다.

다음으로, 토큰의 위치는 start와 end 인덱스로 이루어진 loc 필드에 저장된다. 이 인덱스와 토크나이저를 초기화하는 데 사용된 원본 소스 텍스트가 있으면, 호출자는 source[tok.loc.start .. tok.loc.end]를 이용해 토큰의 텍스트를 추출할 수 있다. 시작과 끝만 저장하는 것은 흔히 쓰이는 효율화 기법이다.

토큰에 담긴 정보는 태그와 위치라는 기본적인 것이지만, 구조는 토크나이저마다 다를 수 있다. 예를 들어 Go 토크나이저는 토큰을 int 상수로 모델링하고, Go에서 next()에 해당하는 함수는 Go가 다중 반환값을 지원하므로 토큰 int, int 바이트 오프셋 형태의 위치, 그리고 토큰의 리터럴 문자열 캡처를 각각 별개의 반환값으로 돌려준다. 이는 Zig와 대체로 동일하지만, 미묘한 차이가 컴파일러 사용성과 때로는 성능에 중요한 영향을 미치기도 한다.

다음 토큰 찾기

토크나이저는 next() 함수를 호출해 한 번에 하나의 토큰을 반환한다.

이 함수는 버퍼의 현재 인덱스에서 시작해 한 번에 한 바이트씩 살펴보며 토큰을 만든다. 다음에 올 수 있는 것을 추적하기 위해 단일 state 변수를 사용해 상태 머신을 구현한다.

Zig 토크나이저의 실제 상태들을 살펴보기 전에, 이 접근 방식을 큰 그림에서 생각해 보자. 입력 while(공백 포함)이 어떻게 토큰화되는지 살펴보자.

먼저 토크나이저는 문자 w를 본다. 이 시점에서는 숫자일 수는 없다는 것을 알지만, 여전히 키워드일 수도 식별자일 수도 있으므로 아직 완전한 토큰이 아니다. 한 번에 한 문자씩만 보기 때문에 다음 문자인 h를 가져온다. 이 역시 식별자나 키워드일 수 있으므로 계속 진행한다. i, l, e가 이어진다. 이제 while이 되었고, 이는 그 자체로 키워드임을 알지만 뒤에 문자가 더 올 수 있으므로 여전히 식별자일 가능성이 있어 한 문자 더 앞서 살펴봐야 한다. 다음 입력은 공백이다. 이제 비로소 이것이 식별자가 아니라 while 키워드임을 확실히 알게 되었고, 토큰을 반환할 수 있다. 만약 다음 바이트가 1 같은 문자였다면, 식별자를 만들고 있는 중이며(아직 미완성) 절대 키워드가 될 수 없다는 것을 알 수 있다(while1로 시작하는 키워드는 없으므로).

Zig 토크나이저도 바로 이렇게 동작한다. 현재 상태(예: “식별자나 키워드를 만들고 있다는 것을 안다”)를 유지하며, 토큰을 모호하지 않게 결정할 때까지 한 번에 한 문자씩 살펴본다.

토크나이저는 상태와 현재 문자만 보고, 뒤를 돌아보거나 앞을 미리 들여다보지 않는다. 대부분의 토크나이저가 그렇다. 앞에서 언급했듯이 토크나이저는 의미를 따지지 않으므로, if while comptime x = 7 { else } 같은 무의미한 입력도 유효한 토큰 스트림을 만들어낸다. 토큰 스트림에 의미를 부여하는 것은 파서의 역할이다.

Zig 구현

next()의 구현은 중첩된 while과 switch를 사용해 이루어진다. 아래에 일부를 발췌했다.

while (true) : (self.index += 1) {
    const c = self.buffer[self.index];
        switch (state) {
        .start => switch (c) {
            'a'...'z', 'A'...'Z', '_' => {
                state = .identifier;
                result.tag = .identifier;
            },
        }
    }
}

첫 번째 while은 버퍼를 한 문자씩 순회하며 영원히 계속되는 무한 루프이다. 루프 본문은 토큰을 찾거나 버퍼가 비었을 때 break할 것으로 기대된다. Zig의 좋은 점 중 하나는 buffer의 타입이 [:0] const u8이며, :0이 버퍼가 반드시 0 바이트로 끝난다는 것을 보장한다는 점이므로, 이를 확인해 루프를 탈출할 수 있다.

다음으로 토크나이저는 enum인 현재 state에 대해 switch한다. 그리고 주어진 상태에서 현재 문자에 대해 switch하며 다음에 무엇을 할지 결정한다. 위 코드 조각에서 A 같은 첫 문자를 보면 상태가 .identifier로 바뀌어 식별자를 만들어 가는 것을 볼 수 있다.

토큰에서 트리로

컴파일러의 다음 단계는 파서이다. 파서는 토크나이저가 생성한 토큰 스트림을 받아 좀 더 의미 있는 추상 구문 트리로 변환한다. Zig 파서에 대해 계속 읽어 보라.