字句解析と構文解析の原理（オートマトンと文法）

2段階に分ける理由

ソースコードから構文木を得る処理は、字句解析（lexing / トークナイズ）と構文解析（parsing）の2段階に分かれます。これは実装上の都合ではなく、扱う言語クラスの違いに根ざした必然です。チョムスキー階層では、トークンの形（識別子・数値・記号など）は正規言語で書け、文の構造（式の入れ子や括弧の対応）は正規言語では書けず**文脈自由言語（CFL）**が必要になります。

なぜ正規言語では足りないのか。正規言語を認識する有限オートマトンは状態が有限で、過去にいくつ括弧を開いたかという「任意に大きい数」を覚えられません。a^n b^n（同数の対応）が正規言語でないことは**反復補題（pumping lemma）**で証明でき、括弧の対応や式の入れ子はまさにこの形です。そこで、有限オートマトンで安価に処理できる字句を先に切り出し、残る入れ子構造だけを表現力の高い文脈自由文法に任せる、という役割分担が生まれます。

字句解析：正規表現からDFAへ

字句解析器は、各トークン種別を正規表現で定義し、それを有限オートマトンとして実行します。理論的な流れは次の通りです。

正規表現
  → トンプソン構成法 → ε遷移つきNFA
  → 部分集合構成法   → DFA（決定性有限オートマトン）
  → 状態最小化       → 最小DFA

非決定性有限オートマトン（NFA）は1つの入力に複数の遷移先を許しますが、認識できる言語はDFAと等価です。部分集合構成法（subset construction）はNFAの「同時に取りうる状態の集合」を1つのDFA状態へ写し、決定化します。DFAは各状態で次の1文字を見るだけで遷移先が一意に決まるため、入力長 n に対して O(n) で走査できます。これが字句解析が高速である数理的な根拠です。

実際のトークン分割では2つの規則が要になります。**最長一致（maximal munch）**は、可能な限り長く一致するトークンを採るという原則で、>= を > と = に割らないために必要です。複数の正規表現が同じ最長一致を持つ場合は、定義順の優先度で曖昧さを解きます（予約語を識別子より先に並べる、など）。

文脈自由文法と導出

構文解析が扱う**文脈自由文法（CFG）**は、非終端記号 → 記号列 という生成規則の集合です。たとえば四則演算の一部は次のように書けます（縦棒は選択肢を表します）。

E → E + T | T
T → T * F | F
F → ( E ) | num

E（式）が E + T を含むように、規則の右辺に自分自身が現れる再帰こそが、正規言語にない「無限の入れ子」を有限の規則で表せる源です。文を作る過程を導出、その木構造を**構文木（解析木）と呼びます。同じ文に2通り以上の構文木が付くとき、その文法は曖昧（ambiguous）**です。a + b * c を * 優先で読むか左から読むかが定まらないのが典型で、上の文法のように演算子ごとに非終端記号を層にして優先順位と結合方向を文法へ埋め込むことで曖昧さを除きます。右辺に自分自身が現れる構造の扱いは再帰の考え方とも通じます。

トップダウン：LL構文解析

LL構文解析は、根（開始記号）から葉へ向かって構文木を作るトップダウン方式です。名称の「LL」は、入力を**左から（Left to right）**読み、最左導出（Leftmost derivation）を再現することを意味します。LL(1) なら先読み1記号で次に適用すべき規則を一意に決めます。

そのために2つの集合を計算します。FIRST集合は各非終端記号から始まりうる終端記号、FOLLOW集合はその直後に来うる終端記号です。これらから構築した予測テーブルに「同じ升目へ2つの規則」が入らなければ、その文法は LL(1) です。手書きの再帰下降パーサはこのLLを素直にコード化したものです。

ボトムアップ：LR構文解析

LR構文解析は、葉（入力トークン列）から根へ向かって木を組み立てるボトムアップ方式です。スタックに記号を積むシフトと、規則の右辺がスタック頂上に揃った時点でそれを左辺へ畳む還元（reduce）を繰り返します。状態は LR(0)項（規則中のどこまで読んだかを示すドット付き規則）から作るオートマトンで管理し、この遷移表をDFAのように引きながら進みます。

LR系はLLが扱える文法を真に包含し、左再帰もそのまま受理できるため表現力が高いのが特徴です。代表的な変種は次のように先読みと表サイズで段階があります。

実用では、表を抑えつつ多くの言語を解ける LALR(1) が長く使われてきました。判断が割れる競合には2種があり、シフトと還元のどちらを採るか定まらないシフト・還元競合（ぶら下がりelse問題が典型）と、複数の規則のどちらへ畳むか定まらない還元・還元競合です。前者は多くのツールが「シフト優先」で機械的に解消します。

まとめ

字句解析と構文解析を分けるのは、トークンが正規言語、文の入れ子が文脈自由言語という言語クラスの差に由来します。字句解析は正規表現をNFA経由でDFAへ変換し、状態遷移で O(n) にトークンを切り出します。構文解析は文脈自由文法を扱い、先読みで予測するトップダウンのLLと、シフト・還元で組み上げるボトムアップのLRが二大潮流です。LRはLLを包含し左再帰も扱える反面、表が大きく実装は複雑になります。この原理は、コンパイラの前段だけでなく、正規表現エンジンや設定ファイルの読み取り、コンパイルとインタプリタにおける処理系の入口まで広く共通する基盤です。計算量の見積もりは計算量と Big-O 記法も参照してください。