字句解析器の設計

トークン表現からバッファ管理、Unicode 処理まで——実用的な字句解析器が考慮すべきことはオートマトン理論だけではありません。位置追跡とエラー回復の品質が、コンパイラのエラーメッセージにおけるユーザー体験を直接決定します。

概要

正規表現とオートマトンでは、字句解析の数学的基盤——正規表現→NFA→DFA→最小化——について解説しました。ここでは実装について扱います。実際の字句解析器では、トークンの種類をどのように設計し、キーワードと識別子の曖昧さをどのように解消し、ソースコードの位置をどのように追跡し、エラー回復をどのように行い、手書きとジェネレータのどちらを選ぶべきかといった点について説明します。これらは「お飾り」ではなく、位置追跡とエラー回復の品質が、その後のコンパイルエラーにおけるユーザー体験を直接決定します。これら2点は教科書ではしばしば省略されがちです。

トークンの種類設計

1つのトークンは少なくとも3つのフィールドが必要です。

Token {
    kind: TokenKind,       ← 列挙型: Number, Plus, Identifier, If, ...
    text: &str,            ← ソースコード内の実際のテキスト (例: "42", "+", "my_var")
    span: Span,            ← ソースコード内の位置 (開始行/列 → 終了行/列)
}

kind と text を分離することが重要な設計です。kind は構文解析器（パーサ）がトークンの種類に基づいて判断を行うために使用されます（例: If を見かけたら if 文の解析に進む）。text は意味解析やエラー報告に使用されます（例: 42 の数値は 42 であり、エラー発生時にはソースコード内の "my_var" という文字列をハイライトする）。

トークン種類の設計は、互いに牽制し合う2つの原則に従います。⁠パーサが必要とする粒度⁠（演算子每种に1つの kind が必要で、+ / - / * はそれぞれ別々の kind である必要がある。さもないとパーサは判断できない）と、⁠字句解析器の認識の一貫性⁠（1つの DFA 状態内でそのトークンの種類を確認できること）です。

キーワードは字句解析器の DFA ブランチを個別に通りません。字句解析器は「1つの識別子」（アルファベット始まり + 数字/アンダースコアの続き）だけを認識し、その後キーワードテーブルを参照します。

識別子 "if" を認識 → lookup_keyword("if") → TokenKind::If
識別子 "myvar" を認識 → lookup_keyword("myvar") → テーブルに存在しない → TokenKind::Identifier

キーワードテーブルは通常、コンパイル時に構築された完璧ハッシュまたはトライであり、lookup は O(1) または O(len) で実行されます。これは、DFA 内で各キーワードごとに個別の終端状態を作るよりもクリーンです。DFA の状態爆発は現実的なリスクです（すべてのキーワードの異なる接頭辞が異なる状態になってしまう）。

位置追跡: 行の世界

ソースコードは1次元のバイト列ですが、エラー報告時には人間が読みやすい行:列形式に変換する必要があります。字句解析器は以下の2つの量を追跡しなければなりません。

現在のオフセット:    ファイル先頭から現在文字までのバイトオフセット (span の起点/終点はオフセットで保存)
現在の行:      1-based
現在の列:    1-based (または 0-based。エディタの規約による)

改行文字 \n (または \r\n) を検出するたびに: line += 1, column = 1, offset += 改行文字の長さ。

Span は line/col ではなく offset を保存する⁠——offset は「ファイルからこの部分のソースコードを切り出す」（部分文字列）ために直接使用でき、改行位置を知る必要がありません。line/col はエラー発生時のみ、offset と行頭オフセットテーブル（行テーブル）から逆算されます。

line_table: Vec<offset>   ← 各行の先頭文字のファイル内オフセット

span_to_linecol(span):
    line = line_table.binary_search(span.start).unwrap() + 1
    col = span.start - line_table[line - 1] + 1

なぜ逆算するのか、直接保存しないのかというと、同じソースコードの位置は診断情報（diagnostics）の中で何度も問い合わされる可能性があるからです（例: 複数のパスで同じ行のエラーが報告される場合）。offset を保存することは安定しています（ファイル編集に伴って変化せず、IDE の増分再解析において重要）。line/col は offset と行テーブルから再計算可能です。

peek / consume / unget: 字句解析器の制御インターフェース

字句解析器が構文解析器（パーサ）に公開するインターフェースは、以下の数個の操作だけです。

• peek(): 現在のトークンを返すが消費しない（トークンを読み取っても進まない）。パーサはこれを使って分岐判断を行う——「次のトークンが + ならこの道、* ならあの道」。
• consume(): 現在のトークンを返し、次のトークンへ進む。
• consume(kind): 現在のトークンが kind であることをアサートし、そうでなければエラーとする——パーサが文法構造を既知の場合の読み取りに使用される（例: "( を消費した」後には必ず ) があるはず）。

peek は最も頻繁に呼び出されるパーサの操作（判断のたびに呼び出される）であり、O(1) でなければなりません。つまり、字句解析器は peek を実行する前に、次のトークンのスキャンを完了していなければなりません。実装上、字句解析器は常に「次のトークンを1つ先読み」してキャッシュしておき、peek はキャッシュを直接返し、consume はキャッシュを返して次のスキャンをトリガーします。

注意⁠: consume(kind) という API は、実装によって役割が異なります。一部の字句解析器では、字句解析層で consume(kind) を提供してアサート付きの消費を行います。より一般的には、これはパーサの責任です——パーサはまず peek() を呼び出してトークンを取得し、token.kind == expected を比較し、その後 consume() を呼び出すかどうかを決定します。いずれの場合でも、意味は一致します。

バッファ管理: 大ファイルとストリーミング入力

ファイル全体を String に読み込んでから字句解析を行うことはできません——大ファイルではメモリが溢れます。字句解析器はリングバッファまたはダブルバッファを使用します。

リングバッファ (ring buffer):
  固定サイズのウィンドウ（例: 4KB）を維持し、現在のスキャン位置を指す
  消費されたデータは破棄される
  ウィンドウの末尾に近づくと、ファイルから次のブロックをバッファの先頭部分に読み込む

  ただし、トークンはバッファの境界を跨ぐことはできない → 字句解析器は、遡視が必要ない場合にバッファを進める

ダブルバッファ（交互に埋められる2つのバッファ）は flex の古典的な手法です——YY_BUFFER_SIZE のデフォルトは 16KB で、現在のバッファが消費されると、すでに埋められた別のバッファに切り替わり、I/O とスキャンが並列で行われます。

現代の環境ではメモリが一般的に豊富であり、多くの実装ではファイル全体を仮想アドレス空間に mmap しています——OS がページを必要に応じて読み込むため、コンパイラは独自のバッファロジックを必要としません。ただし、字句解析器は span の構築をサポートするためにオフセットを追跡し続ける必要があります。

Unicode: 単語のアルファベットはもはや ASCII 128 文字ではない

C 時代の字句解析器は ASCII だけを扱っていました——128 文字、それぞれ1バイト。現代の言語（Rust、Go、Swift）はソースコードレベルで Unicode をサポートしています。

• 識別子には Unicode 文字を含めることができる（の、蛇、é、α）。
• 文字クラス \w はもはや [a-zA-Z0-9_] と同等ではない——Rust の識別子文字クラスは XID_Start + XID_Continue（Unicode 標準で定義された「プログラミング言語の識別子として安全な文字」）である。

字句解析器が Unicode を処理する戦略は、⁠トークナイザがバイトレベルで動作し続け、UTF-8 の規則に従ってマルチバイトシーケンスを認識することです。

識別子を認識する際:
  バイト単位でスキャン
  ASCII の文字/数字/アンダースコアの場合 → 1 バイト消費、継続
  UTF-8 のマルチバイトの先頭バイトの場合（ビットパターンで高速判断: 110xxxxx=2バイト, 1110xxxx=3バイト, 11110xxx=4バイト）
    → 規則に従って完全なシーケンスを消費し、符号点をデコード
  Unicode テーブルを参照し、その符号点が XID_Start/XID_Continue 内にあるか確認
  それ以外の場合: 識別子の終了

ファイル全体を Vec<char> に事前にデコードする必要はありません——マルチバイトシーケンスを検出した際にのみ現在の文字をデコードすればよく、メモリ効率を維持できます。

エラー回復: 字句解析器はクラッシュしてはならない

字句解析器は不正な文字（C 言語での @、閉じられていない文字列リテラル）に出会うと、クラッシュしてはいけません。以下のことを実行しなければなりません。

1. エラーを報告する⁠（どの行のどの列か、不正な文字は何か）。
2. その文字をスキップしてスキャンを続ける⁠——パーサのその後の作業を中断しない（ユーザーが一度のコンパイルで全ての字句エラーを見られるようにするためであり、1つ修正するたびに1つ報告されるようにするため）。

文字列の未闭合は最も一般的な字句エラーです。

"hello world          ← 閉じ括弧が欠落

処理: " の後に行末または EOF までスキャンしても閉じられていない場合 → 「未完了の文字列リテラル、閉じ " が必要です」と報告し、⁠現在位置で閉じられたとみなす⁠（または行全体をスキップ）して、スキャンを継続する。

手書き vs ジェネレータ: 業界での実際の選択

業界のコンパイラの大多数は手書きです——なぜなら、コンパイルエラーメッセージの品質は製品の顔であり、ジェネレータはこの点で手書きと競争できないからです。ジェネレータの最大の価値は「正規表現から DFA へ」の自動変換（手動での部分集合構築が不要）にありますが、生成された DFA と手書きのエラー回復が混在すると保守性が低下します。

Clang の字句解析器は手書きの模範です。各トークン種類の消費ロジックは明確で読みやすく、各文字クラスやトークンの先頭に対して分岐を行い、エラー回復戦略は各トークンの処理ロジックに組み込まれています。

参考文献

• flex マニュアル⁠: The Fast Lexical Analyzer — ジェネレータの完全な使用法、バッファ管理、YY_CURRENT_BUFFER
• re2c: http://re2c.org — もう一つのジェネレータの路線。完全な DFA テーブルではなく、埋め込みコードを出力
• Clang: lib/Lex/Lexer.cpp — 手書き字句解析器の業界標準。行番号/バッファ/エラー回復

Keywords: lexer design, token kind, span, line/column tracking, line table, peek, consume, unget, ring buffer, double buffer, mmap, Unicode, XID_Start, XID_Continue, UTF-8, identifier, keyword table, error recovery, invalid character, unterminated string, hand-written lexer, lexer generator, flex, re2c