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に達するまで一度に1つずつトークンを生成します。アロケーションは一切行いません。
基本的な使い方は次のとおりです。仕組みを詳しく見ていく前に、まず確認しておきましょう。
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から始まります）、そして起こりうる無効なトークン（本記事では触れません）のみです。
pub const Tokenizer = struct {
buffer: [:0]const u8,
index: usize,
pending_invalid_token: ?Token,
// ...
};この状態があれば、トークナイザについて何も知らなくても、その動作はおおよそ想像できるでしょう。トークナイザはバッファ内でインデックスを1バイトずつ進めながらトークンを構築していきます。
トークンの構造
トークナイザの高レベルな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種類の異なるタグが存在します。
次に、トークンの位置情報がlocフィールドに格納されます。これはstartとendのインデックスから成ります。これらのインデックスと、トークナイザの初期化に使った元のソーステキストがあれば、呼び出し側はsource[tok.loc.start .. tok.loc.end]としてトークンのテキストを抽出できます。開始位置と終了位置だけを保持するのは、よく使われる効率化のテクニックです。
トークンに含まれる情報は、タグと位置という基本的なものですが、その構造はトークナイザによって異なります。たとえばGoのトークナイザでは、トークンは整数定数としてモデル化されており、Goでnext()に相当する関数は、Goが多値を返せることを活かして、トークンの整数値、バイトオフセットとしての位置、そしてトークンのリテラル文字列をそれぞれ別の戻り値として返します。これはZigと本質的には同じですが、こうした微妙な違いがコンパイラの使いやすさや、時にはパフォーマンスに大きな影響を与えます。
次のトークンを見つける
トークナイザはnext()関数を呼び出すことで、一度に1つずつトークンを返します。
この関数はバッファ内の現在のインデックスから開始し、トークンを構築するために1バイトずつ読み進めます。次に何が来る可能性があるかを追跡するために、単一のstate変数で状態機械を実装しています。
実際のZigトークナイザの状態を追う前に、このアプローチを高レベルで考えてみましょう。入力while（末尾の空白を含みます）がどのようにトークン化されるかを見てみます。
まず、トークナイザは文字wを読み取ります。この時点では数値ではないことはわかりますが、キーワードか識別子のどちらでもあり得るため、まだ完全なトークンとは言えません。一度に1文字ずつしか見ないので、次の一文字hを取得します。これもまだ識別子かキーワードの可能性がありますから、処理を続けます。i、l、eと続きます。ここでwhileが揃い、これだけならキーワードであることはわかりますが、さらに文字が続く可能性があるため、まだ識別子である可能性も残ります。そのため、もう一文字先を読まなければなりません。次の入力は空白です。これで、識別子ではなくwhileというキーワードであることが確定し、トークンを返すことができます。もし次のバイトが1のような文字だった場合は、識別子を構築中（まだ未完成）であり、キーワードになることはないとわかります（while1で始まるキーワードは存在しないためです）。
これがZigのトークナイザの動作そのものです。現在の状態（たとえば「識別子かキーワードを構築中であることがわかっている」といった状態）を保持し、トークンが一意に確定するまで1文字ずつ読み進めていきます。
トークナイザが参照するのは状態と現在の文字だけで、後方を振り返ることも、前方を先読みすることもありません。ほとんどのトークナイザがそうです。冒頭で述べたとおり、トークナイザはセマンティクスを気にしません。そのため、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は無限ループで、バッファを1文字ずつ進めながら永遠に続きます。ループ本体は、トークンを見つけたときやバッファが空になったときにbreakすることを想定しています。Zigのうれしい特性として、bufferの型が[:0] const u8であることが挙げられます。:0はバッファが必ず0バイトで終わることを保証するため、これを検出してループを抜けることができます。
次に、トークナイザは現在のstate（enumです）でswitchします。そして、状態ごとに現在の文字でさらにswitchして次に何をすべきかを判断します。上のスニペットを見ると、Aのような最初の文字を見たときに、状態が.identifierへ遷移して識別子の構築が始まる様子がわかります。
トークンから木構造へ
コンパイラの次のフェーズはパーサーです。パーサーはトークナイザが生成したトークン列を受け取り、より意味のある抽象構文木へと変換します。Zigのパーサーについての解説をぜひ続けてお読みください。