この記事は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);

トークナイザの特筆すべき重要な特性をいくつか挙げます。

• スライスで動作し、ストリームではない - トークナイザはリーダーではなく [: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のトークナイザではトークンをint定数としてモデル化し、Goにおける next() 相当の関数は、Goが多重戻り値をサポートしているため、トークンを表すint、位置を表すintのバイトオフセット、そしてトークンのリテラル文字列をそれぞれ別の戻り値として返します。これは多かれ少なかれZigと同じですが、微妙な違いがコンパイラの使いやすさや、場合によってはパフォーマンスに重要な影響を与えることもあります。

次のトークンを見つける

トークナイザは next() 関数を呼び出すことで、一度に1つずつトークンを返します。

この関数はバッファ内の現在のインデックスから開始し、一度に1バイトずつ見ながらトークンを構築します。次に何が来る可能性があるかを追跡するために、単一の state 変数を使ってステートマシンを実装しています。

Zigのトークナイザの実際の状態を順に見ていく前に、このアプローチを高い視点から考えてみましょう。入力 while （空白を含む）がどのようにトークン化されるかを見てみます。

まず、トークナイザは文字 w を見ます。この時点では数値ではないことはわかりますが、キーワードか識別子のどちらかである可能性はまだあるため、完全なトークンは得られていません。一度に1文字ずつしか見ないので、次の1文字を取得します。h です。これもまだ識別子かキーワードの可能性があるので、続行します。i、l、e と続きます。ここで while となりましたが、これは単独ではキーワードであることがわかります。しかし、さらに文字が続く可能性があるため、まだ識別子である可能性もあり、もう1文字先を見る必要があります。次の入力は空白です。これで、それが識別子ではなく 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のパーサについての続きをお読みください。