LL・LR・LALR 構文解析アルゴリズムの違い

解析の向きという根本の分岐

構文解析は、トークン列が文法から導出できるかを判定し、導出の構造（構文木）を復元する処理です。文法の開始記号から葉のトークンへ向かう導出を、どちらの端から再現するかで二大戦略が分かれます。

• トップダウン（LL） — 開始記号から始め、規則を選んで非終端記号を展開し、入力に一致させていきます。左端導出（leftmost derivation）をそのままの順で再現する戦略です。
• ボトムアップ（LR 系） — 入力のトークンから始め、規則の右辺にまとまった並びを左辺へ畳み込みながら開始記号へ向かいます。右端導出を逆順に（rightmost derivation in reverse）復元する戦略です。

名前の L は入力を左から右へ読むこと、2文字目（L か R）は再現する導出が左端か右端かを表します。続く数字は先読みするトークン数で、LL(1) や LR(1) のように書きます。

トップダウン：LL の動き方

LL 解析は、現在展開中の非終端記号と次の k トークンの先読みだけで、適用する規則を一意に決められる必要があります。これを表で持つのが**表駆動（table-driven）**の LL パーサで、行に非終端記号、列に先読みトークンを取り、セルに「適用する規則」を1つだけ書きます。

parse():
  スタックに開始記号を積む
  while スタックが空でない:
    X = スタックの先頭
    a = 入力の先頭トークン
    if X が終端記号:
      X と a が一致すれば両方を消費、違えばエラー
    else:
      規則 = table[X][a]        # 先読み1で規則を一意に選ぶ
      X をポップし、規則の右辺を逆順にプッシュ

この一意決定が崩れる代表が左再帰です。A → A α のような規則は、A を展開しようとすると再び A が先頭に来て無限ループに陥ります。LL では左再帰を除去し、共通接頭辞は左くくり出しで分離してから表を作る前処理が要ります。手書きの再帰下降パーサは LL を関数呼び出しで素直に表現したもので、各非終端記号が1つの関数に対応します。再帰下降は再帰の典型的な応用例です。

ボトムアップ：LR のシフト還元

LR 解析は**シフト還元（shift-reduce）**という2種類の操作で進みます。状態を載せたスタックを使い、各ステップで解析表を引いて次の動作を決めます。

• シフト — 入力トークンを1つスタックへ移し、表が指す次の状態へ遷移します。
• 還元（reduce） — スタック上端が、ある規則の右辺と一致したとき、その並びを左辺の非終端記号へ畳み込みます。

parse():
  状態スタックに初期状態を積む
  loop:
    s = スタック上端の状態
    a = 入力の先頭トークン
    action = ACTION[s][a]
    if action == shift t:    push(a, t)、入力を1つ進める
    if action == reduce r:   右辺の長さ分ポップし、GOTO で左辺へ遷移
    if action == accept:     受理して終了
    if action == error:      構文エラー

LR が LL より広い文法を扱えるのは、規則の選択を右辺を読み終えるまで遅らせられるからです。LL は非終端記号を展開する瞬間に規則を1つに決めねばなりませんが、LR は右辺全体がスタックに揃ってから還元するため、共通接頭辞や左再帰をそのまま受け入れられます。

LR の3変種：SLR・LALR・正準 LR

LR 系の解析表はオートマトンの状態（LR 項の集合）から作りますが、「いつ還元してよいか」を判断する先読みの精度と、状態数のバランスで3つに枝分かれします。すべて先読み1（(1)）を前提に並べます。

ポイントは状態数の出方です。正準 LR(1) は先読み情報まで含めて状態を区別するため、状態数が爆発的に増えます。SLR(1) は先読みを FOLLOW 集合で粗く近似することで状態を減らしますが、文脈を無視するためシフト還元衝突を解けない文法が出ます。LALR(1) は、先読みを無視した「核（core）」が同じ状態どうしを併合します。これにより状態数は SLR と同じまで圧縮されつつ、併合後も状態固有の先読み集合を保つため、SLR より多くの文法を曖昧なく解析できます。

包含関係は次の通りで、左ほど扱える文法が広く、状態数も多くなります。

正準 LR(1)  ⊇  LALR(1)  ⊇  SLR(1)
（広い・大表）              （狭い・小表）

なぜ yacc/bison は LALR なのか

ここまでの整理が、古典的なパーサ生成系 yacc とその後継 bison が LALR(1) を既定に据える理由を説明します。1970年代に yacc が設計された当時、正準 LR(1) の解析表は当時のメモリ事情では実用的でないほど大きく、SLR(1) は現実の言語文法に対して衝突が出やすいものでした。

LALR の弱点は、状態の併合に由来する reduce/reduce 衝突がまれに生じることです。核が同じ2状態を1つに併せた結果、本来は別々だった先読み集合が混ざり、どちらの規則で還元すべきか決まらなくなる場合があります。正準 LR(1) なら状態を分けたまま保てるので、この衝突は起きません。実務では衝突が出た箇所だけ文法を書き換えて回避するのが定石です。

LL と LR の使い分け

両者は表現力と実装のしやすさで対照的です。文法をどう持つか、エラーをどう報告するかで選びます。

観点	LL（トップダウン）	LR 系（ボトムアップ）
再現する導出	左端導出（そのままの順）	右端導出（逆順）
規則を決める時点	展開する瞬間（早い）	右辺が揃ってから（遅い）
左再帰	不可（除去が必要）	そのまま扱える
扱える文法の広さ	狭い	広い
手書きのしやすさ	易しい（再帰下降）	難しい（生成系が前提）
代表的な実装	再帰下降、ANTLR、JavaCC	yacc/bison、各言語の LALR 生成系

近年は LL を強化した ANTLR（任意長の先読みを扱う ALL(*)）のように、トップダウンでも広い文法を扱う処理系が普及しています。とはいえ、コンパクトな表で広い文法を正確に解析する LALR(1) は今も主力で、構文解析がコンパイルのどの段階に当たるかを押さえると、生成系の選択基準が見えてきます。なお、状態数や FOLLOW 集合の計算量を見積もるには計算量（ビッグオー）の感覚が役立ちます。

まとめ

LL と LR の違いは、導出をどちらの端から再現するかという解析の向きに根ざします。LL はトップダウンで左端導出を再現し、展開の瞬間に規則を一意に決める必要があるため左再帰を扱えません。LR 系はボトムアップでシフトと還元を繰り返し、右辺が揃うまで規則の決定を遅らせられるぶん広い文法を扱えます。その LR 系は SLR・LALR・正準 LR の順に先読みの精度と状態数が増え、LALR(1) は正準 LR(1) に近い表現力を SLR(1) 並みの小さな表で実現する位置にあります。yacc/bison がこれを採るのは、まさにその費用対効果のためです。