13 分で読了
このページの目次

LR解析

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

概要

再帰下降とLLはトップダウン解析であり、文法から始めて入力を導出する。LR解析はボトムアップ解析であり、入力トークンから始めて、文法記号へと段階的に還元(reduce)し、最終的に入力が開始記号へと還元される。LRはLLよりも強力であり、LL(1)が扱える文法を厳密に超え、左再帰を除去する必要もない。LRの代償は、手書きでは不可能（複雑すぎる）であり、生成器(yacc/bison/lalrpop)を使って文法から構文解析表(parse table)を自動構築しなければならない点にある。ここでは、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はitemの集合
    I内の各item A→α·Bβに対して：
        Iにない場合、Bのすべての生成式 B→·γ をIに追加
    増加しなくなるまで繰り返す

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

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

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

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

SLRの改善点：item 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)のitemは、「点の位置」だけでなく、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)のコアが同じ（itemは同じだが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か

LLLR
記述手書き、直感的生成器必須
文法能力弱い、左再帰除去が必要強い、左再帰を自然に処理
エラーメッセージ優れている（手書きで文脈が豊富）劣っている（生成器の文脈では改善が難しい）
増分解析容易（関数レベル）困難（グローバルな状態スタック）
使用例Clang, Rustc, Goyacc/bison（伝統的コンパイラ）, lalrpop（Rust）

産業のトレンドは 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

関連ページ

© 2026 liz's doc