構文解析器（パーサ）徹底解説：字句解析からASTまで、LL/LR・ツールと実装の実践
エバープレイ編集部構文解析器（パーサ）とは何か
構文解析器（パーサ、parser）は、入力されたトークン列を受け取り、与えられた文法に従ってその構造を判定し、構文木（parse tree）や抽象構文木（AST: Abstract Syntax Tree）を生成するソフトウェアコンポーネントです。主にコンパイラやインタプリタの前半部分で用いられ、字句解析（lexer / tokenizer）が切り出したトークン列を受け取り、文法的に正しいかどうかを検査すると同時に意味解析やコード生成のための中間表現を組み立てます。
字句解析と構文解析の役割の違い
- 字句解析（Lexical analysis）: 文字列をトークン（キーワード、識別子、数値、記号など）に分割し、各トークンに属性（lexeme）を付与する。
- 構文解析（Syntactic analysis）: トークン列が文法（通常は文脈自由文法：CFG）に従っているか検査し、構造（木構造）を構築する。
文法の表現（BNF / CFG）
構文は通常、BNF（Backus–Naur Form）やその拡張であるEBNFで記述される。これらは文脈自由文法（CFG）として形式化され、非終端記号、終端記号、生成規則、開始記号を用いて記述されます。CFGはプログラミング言語の多くの構造を自然に表現できますが、名前解決や型チェックなどの意味的検査は別段階で扱われることが一般的です。
構文木と抽象構文木の違い
構文木は文法規則に忠実な木構造で、すべての終端・非終端が現れることがあります。対して抽象構文木（AST）は不要な中間ノードや構文糖（syntactic sugar）を省いた簡潔な表現で、セマンティック解析や最適化、コード生成に適した形に整えられます。
パーサの分類（概観）
パーサは大きく「トップダウン解析（Top-down）」と「ボトムアップ解析（Bottom-up）」に分けられます。それぞれさらに細かいクラスがあります。
トップダウン解析
- 再帰下降パーサ（Recursive Descent）: 各文法規則ごとに再帰的な関数を用いる実装が多く、可読性が高い。左再帰を含む文法にはそのままでは対応できない。
- LL(k)パーサ: 左から右へ入力を読み、左端導出（leftmost derivation）を構築する。kは先読みトークン数を表す。LL(1)は文法の設計が容易で手動実装がしやすい。
ボトムアップ解析
- LRパーサ（LR(k)）: 左から右へ入力を読み、右端導出を逆順で構築する。一般に扱える文法の範囲が広い。例：SLR, LALR, Canonical LR。
- LALR: yacc/bisonでよく使われる手法で、テーブルサイズを小さくした実用的なLRの変種。
- GLR（Generalized LR）: 曖昧文法や非決定的文法にも対応する汎用的なLRの拡張。
その他のアルゴリズム
- Earleyアルゴリズム: 任意のCFGを扱える汎用アルゴリズムで、平均的には効率的、最悪計算量はO(n^3)。
- CYKアルゴリズム: 文法をチャムスキー正規形（CNF）にして動的計画法で解析する。最悪O(n^3)だが理論的に重要。
- PEG（Parsing Expression Grammar） / Packrat: 優先選択を持つ記述法で、バックトラッキングをメモ化するPackratパーサにより線形時間を実現するが、メモリ使用量が多くなることがある。PEGは曖昧性（ambiguous grammars）を許さない決定的な文法モデル。
- パーサコンビネータ: 関数型言語でよく使われる技法で、小さなパーサを組み合わせて大きなパーサを構築する。可読性やモジュール性に優れる。
実装上の注意点とテクニック
- 左再帰の除去: 再帰下降型では左再帰（A → A α）が無限再帰を招くため、変換（右再帰化やループへの変換）が必要。
- 左ファクタリング（Left-factoring）: LL(1)などで選択が必要な場合、共通接頭辞を外に出すことで先読み1トークンで決定できるようにする。
- エラーハンドリングと回復: 構文エラーを検出した際に単に停止するのではなく、同期トークン（セミコロンなど）までスキップして複数のエラー報告を行う戦略がよく使われる。
- 優先順位と結合性: 演算子の優先度・結合性を文法に組み込むか、生成後にASTで処理するかを設計時に決める。
- セマンティックアクション: パーザ生成器（Yacc/Bison, ANTLRなど）では、文法規則に紐づけたアクションでAST構築や型情報の付与を行える。
代表的なツールとライブラリ
- Lex/Flex + Yacc/Bison: C系で長年使われる組み合わせ。LALRパーサを生成する。
- ANTLR: LL(*) ベースで強力な文法記述とツリー操作機能を提供。複数言語へのコード生成対応。
- JavaCC, CUP: Java環境でのパーサ生成器。
- Boost.Spirit: C++のパーサコンビネータライブラリ（テンプレートメタプログラミングを利用）。
- PEG.js, parsimonious, peg (各言語実装): PEGベースの実装で記述が直感的。
性能と実用上の考慮点
パーサは入力長nに対する計算量やメモリ使用が重要です。LR系やLL(1)系は一般に線形時間で動作しますが、文法の性質やエラーハンドリングの実装によって実効速度は変わります。Packratは理論上線形だがメモリを多く使う一方、EarleyやCYKは汎用性が高いが最悪計算量は高めです。実用では「扱いたい文法の表現力」と「実行時性能・メモリ制約」のバランスで方式を選びます。
現実のユースケース
- コンパイラやインタプリタのフロントエンド（例：C/C++, Java, Rustなど）
- ドメイン固有言語（DSL）の実装
- データフォーマットの解析（JSON, XML, CSV など）
- IDEの構文解析・インクリメンタル解析（リアルタイムの構文ハイライトや補完）
- 自然言語処理における構文解析（確率的パーサや依存構造解析などはまた別分野）
設計上のベストプラクティス
- まず文法を簡潔に定義し、ASTをどのように表現するかを先に設計する。
- 手作業で実装するなら再帰下降（LL）で始め、必要ならボトムアップやGLRに切り替える。
- テスト用の文法テストケース（良い入力・悪い入力）を充実させる。ファジングでエラー耐性を検査するのも有効。
- エラーメッセージは利用者視点でわかりやすく。位置情報（行・列）を確実に伝搬する。
- 複雑な文法はモジュール化し、可能なら文法工学ツール（ANTLR等）を活用する。
まとめ
構文解析器は、プログラミング言語やデータフォーマットを扱う上で中心的な役割を担うコンポーネントです。文法の性質に応じてトップダウン／ボトムアップ、LL／LR、PEGやEarleyなど適切なアルゴリズムやツールを選ぶことが重要です。性能、可読性、メンテナンス性、エラーハンドリングのしやすさといった現実的な要件を踏まえ、AST設計と合わせてパーサを設計・実装すると良いでしょう。
参考文献
- Parser (computing) — Wikipedia
- Parsing techniques — Wikipedia
- Parsing expression grammar (PEG) — Wikipedia
- Earley parser — Wikipedia
- CYK algorithm — Wikipedia
- ANTLR — Official Site
- GNU Bison Manual
- Boost.Spirit — Boost C++ Libraries
- Compilers: Principles, Techniques, and Tools — (Dragon Book) — Wikipedia
投稿者プロフィール
