Zig 토크나이저
이 글은 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);토크나이저의 중요한 특성 몇 가지를 짚고 넘어갈 만합니다.
- 스트림이 아니라 슬라이스에서 작동합니다 - 토크나이저는 리더가 아니라
[:0] const u8를 입력으로 받습니다. 따라서 입력이 충분히 크다면 토크나이저 호출을 버퍼링하고 일괄 처리하는 일은 호출자의 몫입니다. 실제로 프로그래밍 언어 입력은 충분히 클 일이 없으므로 소스 파일 전체를 한 번에 토큰화합니다. 현재 Zig도 이렇게 작동합니다. - 메모리를 할당하지 않습니다 - 토크나이저는 힙 할당을 전혀 수행하지 않습니다. 시스템 프로그래밍에서는 API의 메모리 사용량과 할당 특성을 파악하는 것이 언제나 유용합니다. 참고로 Zig에서는 Tokenizer가 어떤 작업에도
Allocator를 매개변수로 받지 않기 때문에 이 점이 곧바로 드러납니다.
토크나이저의 구조도 마찬가지로 간단합니다(아래와 같습니다). 토크나이저는 버퍼, 버퍼 내 현재 인덱스(0에서 시작), 그리고 잠재적인 잘못된 토큰을 저장합니다(잘못된 토큰은 이 글에서 다루지 않습니다).
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 필드는 가능한 모든 토큰 유형을 나타내는 열거형입니다. 태그의 예로는 .keyword_comptime, .l_brace, .r_brace, .eof가 있습니다. 이 글을 쓰는 시점에 Zig에는 서로 다른 태그가 약 120개 있습니다.
다음으로 토큰의 위치는 start와 end 인덱스로 구성된 loc 필드에 저장됩니다. 이 인덱스와 토크나이저를 초기화할 때 사용한 원본 소스 텍스트가 있으면 호출자는 source[tok.loc.start .. tok.loc.end]를 사용해 토큰의 텍스트를 추출할 수 있습니다. 시작과 끝만 저장하는 것은 흔히 쓰이는 효율화 기법입니다.
토큰에 제공되는 정보는 태그와 위치라는 본질적인 요소이지만, 구조는 토크나이저마다 다를 수 있습니다. 예를 들어 Go 토크나이저는 토큰을 정수 상수로 표현합니다. 또한 Go는 여러 반환값을 지원하므로 Go에서 next()에 해당하는 함수는 토큰 정수, 바이트 오프셋인 위치 정수, 토큰의 리터럴 문자열을 각각 별도의 반환값으로 돌려줍니다. 대체로 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 바이트로 끝난다는 것을 알 수 있다는 점입니다. 따라서 이 값을 찾아 루프를 종료할 수 있습니다.
그다음 토크나이저는 열거형인 현재 state를 기준으로 switch를 수행합니다. 그런 다음 상태에 따라 현재 문자를 기준으로 다시 switch를 수행해 다음에 무엇을 할지 결정합니다. 위 코드에서 A 같은 첫 문자를 보면 상태를 .identifier로 변경해 식별자를 만들어 가는 과정을 확인할 수 있습니다.
토큰에서 트리로
컴파일러의 다음 단계는 파서입니다. 파서는 토크나이저가 생성한 토큰 스트림을 받아 조금 더 의미 있는 추상 구문 트리로 변환합니다. Zig 파서에 관한 글도 계속해서 읽어 보세요.