LR解析

ボトムアップのもう一つの道: LRはLLよりも多くの文法を処理でき、左再帰の除去は不要——その代償として生成器に依存しなければならない。LR(0)→SLR→LR(1)→LALRへの各段階のアップグレードを理解すれば、yacc/bisonの本質を理解したことになる。

概要

再帰下降とLLはトップダウンアプローチ: 文法から始めて入力を導出する。LRはボトムアップアプローチ: 入力トークンから始め、文法記号へと段階的に還元(reduce)し、最終的に入力が開始記号へと還元されるまで続ける。LRはLLよりも強力——処理できる文法はLL(1)の厳密なスーパーセットであり、左再帰の除去も不要である。LRの代償は: 手書きでは不可能(複雑すぎる)であり、生成器(yacc/bison/lalrpop)に依存して文法から構文解析テーブルを自動構築しなければならないことである。ここでは、LRがLR(0)からLALRへと段階的にアップグレードされる各ステップ——各ステップが前ステップの「少なすぎたり多すぎたりする」問題を解決していく様子——について解説する。

LR解析器の構造

LR解析器は3つの部品で構成され、入力とスタックによって駆動される:

入力: [id, +, id, *, id, $]         ← トークンストリーム、$は終了記号
スタック: [0, E, 1, +, 2, T, 5, ...]    ← 状態スタックと文法記号が交互に配置
                  ↑ スタックトップ

各ステップでテーブルを参照:
  action(state, next_token) → shift s / reduce A→β / accept / error
  goto(state, nonterminal)  → 次の状態

• shift: 次の入力トークンとactionテーブルで指定されたターゲット状態をスタックにプッシュする。
• reduce A→β: スタックトップから2×|β|個の要素をポップする(ここで|β|は還元規則の右辺に含まれる文法記数の数であり、各記号はスタック上で「記号+状態」のペアに対応する)。その後、Aをスタックにプッシュし、gotoテーブルを使って新しい状態を決定し、それをスタックにプッシュする。
• accept: 解析成功。
• error: 文法エラー。

構文解析テーブル(action + goto)はLR解析の知恵のすべてを含んでいる——コンパイラ生成器の中核的な作業は、このテーブルを構築することである。

LR(0)からLALRへ: 段階的なアップグレード

LR(0): 基礎的だが実用的ではない

項目⁠(item)はLR理論の中核概念である: A → α·β という形のドット付き規則で、ドットは「αはすでに認識済み、βはまだ認識していない」ことを示す。

LR(0)の構文解析テーブルの構築:

closure(I):   ← Iは項目の集合
    I内の各項目 A→α·Bβ について:
        Iにない場合、Bのすべての生成式 B→·γ をIに追加
    増加しなくなるまで繰り返す

goto(I, X):   ← Xは文法記号 (終端記号または非終端記号)
    I内の各項目 A→α·Xβ について、A→αX·β をJに追加
    return closure(J)

初期項目 S'→·S のclosureから始めて、可能な各記号Xに対してgotoを繰り返し計算し、新しい状態を生成し、すべての状態が飽和するまで続ける——これによりLR(0)の正規集合が得られる。

LR(0)の問題⁠: A→α·(ドットが末尾にあり、還元可能)の場合、あらゆる入力に対して還元を行う——現在のトークンを全く見ない。これは、多くの実用的な文法(else付きif、優先度付き式)がLR(0)においてshift/reduce衝突を発生させることを意味する。LR(0)が処理できる文法は非常に限られており、実際の言語のほとんどは少なくともSLR(1)の能力を必要とする。

SLR(1): FOLLOWを使って不要な還元を削減

SLRの改善点: 項目 A→α· (還元可能) に対して、現在のトークンがFOLLOW(A)に属する場合のみ還元を行う——つまり、「文法的にAの後にこのトークンが出現し得る場合」のみ還元を実行する。

LR(0) reduce:  あらゆる入力で A→α を還元
SLR reduce:    next_token ∈ FOLLOW(A) の場合のみ A→α を還元

SLRはLR(0)の大部分の無意味な還元を解決した。しかし、FOLLOWはグローバルな集合であり、Aが出現するすべての場所で同じであり、「この状態でAを還元する際に、次のトークンが何であるか」を区別しない。SLRは依然として、特定の文脈において不要な還元を行うことがある。

LR(1): 完全な精度だが、状態の爆発

LR(1)の項目は、「ドットの位置」だけでなく lookahead を記録する——この状態でこの規則を還元する際に、次のトークンがどの記号であるべきか。

LR(0) item:   A → α·β
LR(1) item:   [A → α·β, a]     ← a は lookahead トークン

LR(1)のclosureはLR(0)よりも複雑である:

closure(I):
    I内の [A→α·Bβ, a] について:
        Bの各生成式 B→γ について:
            b ∈ FIRST(βa) について:        ← β が導出し得る最初のトークン、または β→ε の場合は a
                [B→·γ, b] をIに追加 (Iにない場合)

LR(1)の構文解析テーブルはほとんど無駄な衝突を起こさず、処理できる文法の範囲は非常に広い。その代償は状態数の膨張である: 同一のLR(0)状態でも、lookaheadが異なるために複数のLR(1)状態に分裂する。実際のプログラミング言語の文法では、LR(1)の状態数はLR(0)の5〜10倍になる可能性がある。

LALR(1): 「魂が同じ状態」をマージし、実世界での選択

LALR(Look-Ahead LR) はLR(1)の簡略化版であり、すべての実用的なLR生成器(yacc/bison/lalrpop)のデフォルトアルゴリズムである:

LR(1)の状態集合を取り、LR(0)のコアが同じ (項目は同じだがlookaheadが異なる) 状態をすべてマージ
  マージ後、各状態のlookahead = 元の複数の状態のlookaheadの和集合
  マージ後の状態集合を使って構文解析テーブルを構築

• LALRの状態数 = LR(0)の状態数⁠(LR(1)より大幅に少ない)、しかし解析能力はLR(1)に非常に近い。
• 代償: マージにより新しいreduce/reduce衝突が発生する可能性がある——しかし実際には非常に稀であり、ほぼ常に文法自体に問題があることを意味する。

なぜLALRが産業標準なのか: 状態数が少ない → 構文解析テーブルが小さい → コンパイラのメモリ使用量が低く、構文解析テーブルの構築時間が許容範囲内である。ほとんどのプログラミング言語(LRルート)のパーサ生成器はLALR(1)を使用している。

Shift/Reduce および Reduce/Reduce 衝突

LRテーブルの生成時に、以下の2種類の衝突が発生する可能性がある:

• Shift/Reduce: actionテーブルのあるセルにshiftとreduceの両方が存在する。最も古典的な例は dangling else——if...if...else を見たとき、else は shift(直近のifとマッチさせる)すべきか、reduce(外側のifを終了させる)すべきか？ ほとんどの生成器はデフォルトでshiftを優先する(直近のifとマッチさせる)ため、これはプログラミングの直感に正好符合する。
• Reduce/Reduce: 同じセル内で2つの異なる還元が衝突する。これは常に文法問題のシグナルである——文法に真の曖昧さがあり、文法を変更するか、優先度規則を追加する必要がある。

yacc/bisonでは、トークンと規則に優先度を設定できる:%left '+' '-' → expr + expr が同じ状態で shift+ と reduce の両方に直面している場合、優先度が動作を決定する。これは文法を変更して左再帰や曖昧さを除去するよりも実用的だが、使いすぎると文法の意味が優先度設定によって微妙に変化してしまう。

lalrpop: LRの現代的な代替

lalrpopはRustのLR(1)/LALR(1)パーサジェネレーター——文法はRustのソースコードに直接記述され、生成されるコードもRustである。yacc/bisonとの核心的な違いは: lalrpopがパラメータ化された文法⁠(Rust型のセマンティックアクション付き)を処理するのに対し、yacc/bisonは無型文法⁠(セマンティックアクションがCコードブロック)を処理することである。

lalrpop 文法の例:

Expr: i32 = {
    <l:Expr> "+" <r:Term> => l + r,       ← 右オペランドは Term 型を使用 (Expr に自動昇格)
    Term,
};

Term: i32 = {
    <l:Term> "*" <r:Factor> => l * r,
    Factor,
};

生成されたLRテーブルは、Rustのコンパイル時に生成されるコードに埋め込まれる——本質的にはyacc/bisonが生成するCのテーブルと同じLALRアルゴリズムである。lalrpopでは Term は Expr に自動昇格する(Expr が Term バリアントを含むため)。

LR解析のエラー回復

LRパーサはエラーのあるトークン(現在の状態でactionテーブルが空)に出会った場合、回復を試みる。標準的な戦略:

• panic mode: スタックトップから下に状態をポップし、ある状態が特定のトークンに対して合法的なshiftを持つまで続ける——途中のトークンをスキップして解析を継続する。スキップされたトークンは「エラーに飲み込まれた部分」である。
• error productions: 文法に明示的に Stmt → error ';' を書き、パーサ生成器が error を「あらゆるトークンにマッチするワイルドカード」として特別扱いする——パーサはエラー発生後、「同期マークに遭遇するまでゴミを消費する」。

これはLLのエラー回復よりも難しい⁠——LRは現在どのセマンティック構造を解析しているかを知らない(「ボトムアップ」であり、上位が何を期待しているか分からない)ため、エラーメッセージは通常、手書きの再帰下降よりも劣る。これが産業用コンパイラがLLルートを好む重要な理由の一つである。

LLかLRか

産業のトレンドは LL手書き⁠(エラーメッセージ + インクリメンタル) > LR生成器⁠(新規プロジェクトでの使用は減少)。LRの価値は主に、既存システム(Bash/awkのパーサ、yacc時代の多くのレガシーコード)の理解や、DSLパーサを迅速に構築する必要がある場面に限定される。

参考文献

• Dragon Book: 第4章、4.5〜4.7節 — LR(0)/SLR/LR(1)/LALRの完全な数学的導出
• Knuth (1965): "On the Translation of Languages from Left to Right" — LR解析の原論文
• lalrpop: https://github.com/lalrpop/lalrpop — Rust用 LALR(1) パーサジェネレーター

Keywords: LR, LR(0), SLR, LR(1), LALR, shift, reduce, shift/reduce conflict, reduce/reduce conflict, item, closure, goto, parse table, yacc, bison, lalrpop, dangling else, precedence, associativity, panic mode, error productions