--- title: 字句解析器の設計 url: https://doc.liz6.com/ja/compilers/01-lexical-analysis/02-lexer-design locale: ja area: compilers tags: - compilers - lexical-analysis date: 2026-06-30 modified: 2026-07-16 description: トークン表現からバッファ管理、Unicode 処理まで——実用的な字句解析器が考慮すべきことはオートマトン理論だけではありません。位置追跡とエラー回復の品質が、コンパイラのエラーメッセージにおけるユーザー体験を直接決定します。 --- # 字句解析器の設計 > トークン表現からバッファ管理、Unicode 処理まで——実用的な字句解析器が考慮すべきことはオートマトン理論だけではありません。位置追跡とエラー回復の品質が、コンパイラのエラーメッセージにおけるユーザー体験を直接決定します。 ## 概要 [正規表現とオートマトン](/compilers/01-lexical-analysis/01-regular-expressions-and-automata.md)では、字句解析の数学的基盤——正規表現→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 ← 各行の先頭文字のファイル内オフセット 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` に事前にデコードする必要はありません——マルチバイトシーケンスを検出した際にのみ現在の文字をデコードすればよく、メモリ効率を維持できます。 ## エラー回復: 字句解析器はクラッシュしてはならない 字句解析器は不正な文字（C 言語での `@`、閉じられていない文字列リテラル）に出会うと、クラッシュしてはいけません。以下のことを実行しなければなりません。 1. **エラーを報告する**（どの行のどの列か、不正な文字は何か）。 2. **その文字をスキップしてスキャンを続ける**——パーサのその後の作業を中断しない（ユーザーが一度のコンパイルで全ての字句エラーを見られるようにするためであり、1つ修正するたびに1つ報告されるようにするため）。 文字列の未闭合は最も一般的な字句エラーです。 ``` "hello world ← 閉じ括弧が欠落 ``` 処理: `"` の後に行末または EOF までスキャンしても閉じられていない場合 → 「未完了の文字列リテラル、閉じ `"` が必要です」と報告し、**現在位置で閉じられたとみなす**（または行全体をスキップ）して、スキャンを継続する。 ## 手書き vs ジェネレータ: 業界での実際の選択 | | 手書き lexer | ジェネレータ (flex, re2c, lex) | |---|---|---| | 例 | Clang, Rustc, V8, CPython | Bash, awk, 各 DSL | | 方式 | 手動で状態管理 + DFA テーブル、または直接記述 | 正規表現入力 → DFA/テーブルを自動生成 | | 利点 | エラーメッセージが非常に良い、カスタマイズ可能、インライン化が積極的、ジェネレータ依存なし | 正規表現がトークンに直接対応、トークン変更が容易 | | 欠点 | トークンが多いと状態管理が繁重、新人はコードを学ぶ必要がある | 生成されたコードの可読性が悪い、エラーメッセージの調整が困難 | 業界のコンパイラの大多数は**手書き**です——なぜなら、コンパイルエラーメッセージの品質は製品の顔であり、ジェネレータはこの点で手書きと競争できないからです。ジェネレータの最大の価値は「正規表現から 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*