---
title: 再帰下降と LL 解析
url: https://doc.liz6.com/ja/compilers/02-syntax-analysis/01-recursive-descent-and-ll-analysis
locale: ja
area: compilers
tags:
- compilers
- syntax-analysis
date: 2026-06-30
modified: 2026-07-16
description: '最も広く使用されているパーサの記述方法: 手書きの再帰下降パーサは直感的で制御可能、エラーメッセージも良好——背景には LL(1) の FIRST/FOLLOW 理論と Pratt parser の優先度駆動があり、これら一連の組み合わせで実用的な文法の大多数をカバーします。'
---

# 再帰下降と LL 解析

> 最も広く使用されているパーサの記述方法: 手書きの再帰下降パーサは直感的で制御可能、エラーメッセージも良好——背景には LL(1) の FIRST/FOLLOW 理論と Pratt parser の優先度駆動があり、これら一連の組み合わせで実用的な文法の大多数をカバーします。

## 概要

構文解析（パーシング）はコンパイラの第2工程です：字句解析が生成したトークン列を**抽象構文木（AST）**に変換します。主に2つのアプローチがあります：**LL**（トップダウン、文法から入力を導出）と **LR**（ボトムアップ、入力から文法へ帰約）。ここでは LL アプローチ——再帰下降（recursive descent）とその背後にある理論（LL(1)、FIRST/FOLLOW、左再帰の除去）——について解説します。手書きの再帰下降パーサは依然として業界の主流です（Clang、Rust、Go のコンパイラはいずれも手書きの再帰下降を採用）。その理由は**直感的で読みやすく、エラーメッセージの制御が容易**であるためです。これらは、パーサジェネレータが未だに苦手としている部分です。

## 再帰下降：1つの関数が1つの文法規則に対応

核心となる考え方は極めて素朴です。各非終端記号（文法の左辺の記号、例えば `expression` や `statement`）に対して1つの関数を書き、関数本体ではその規則の右辺に従って**探索**を行います。簡単な算術式の文法を見てみましょう。

```
expr    → term (('+' | '-') term)*
term    → factor (('*' | '/') factor)*
factor  → NUMBER | '(' expr ')'
```

これを再帰下降に変換すると：

```
def expr():
    left = term()
    while peek() in ('+', '-'):    ← 反復探索であり、再帰ではない
        op = consume()
        right = term()
        left = BinOp(op, left, right)
    return left

def term():
    left = factor()
    while peek() in ('*', '/'):
        op = consume()
        right = factor()
        left = BinOp(op, left, right)
    return left

def factor():
    if peek() == '(':
        consume('(')
        node = expr()              ← ここで再帰的に expr() に戻る
        consume(')')
        return node
    else:
        return Number(consume(NUMBER))
```

重要なメカニズム：
- **各関数は現在のトークンから開始**し、処理できる正確な数のトークンを消費し、ASTの部分木を返します。
- **peek()** は現在のトークンを確認しますが消費しません。**consume()** はトークンを消費して進めます。
- 左再帰（`expr → expr + term`）は無限再帰を引き起こします——`expr()` の最初の行で再び `expr()` を呼び出してしまうためです。**左再帰を除去する必要があります**：`A → Aα | β` を `A → β A'`、`A' → α A' | ε` に書き換えます。この除去は**直接左再帰**を対象としています。間接左再帰（`A → B → A`）の場合は、まず代入によって除去する必要があります。

## 左再帰の除去：アルゴリズムと代償

即時左再帰（規則の右辺の最初の記号が自分自身である場合）は機械的に除去できます。

```
元の文法:  expr → expr + term | term
           term → term * factor | factor

除去後: expr  → term expr'
        expr' → + term expr' | ε
        term  → factor term'
        term' → * factor term' | ε
```

代償として、ASTの構造が変化します——元の文法における `expr + term` は直接左結合の部分木に対応していましたが、除去後は `expr'` が右結合を累積します。演算順序を保持するためには、ASTの構築時に手動で左結合化を行う必要があります。Pratt parser は別の方法（優先度に基づいて逐次的に沈み込む）を用い、明示的な左再帰の除去を回避します。

## FIRST と FOLLOW：LL の理論的基盤

再帰下降の本質は、**現在のトークンを見てどの分岐に進むかを決定する**ことです。この意思決定の理論的根拠が FIRST と FOLLOW 集合です。

- **FIRST(X)**：X から導出可能なすべての文字列の**最初のトークンの集合**。X が ε（空）を導出できる場合、ε も FIRST(X) に含まれます。
- **FOLLOW(X)**：すべての導出において、X の直後に続くトークンの集合。

```
文法:  E → T E'
       E'→ + T E' | ε
       T → id

FIRST(T) = {id}
FIRST(E')= {+, ε}
FIRST(E) = FIRST(T) = {id}
FOLLOW(E')= FOLLOW(E) = {$}   ← $ は入力の終了記号
```

LL(1) の工学的意味：規則 `A → α | β` において、**FIRST(α) と FIRST(β) が交差してはなりません**——現在のトークンを見たときに選択できないためです。`LL(1)` の `1` は「1つのトークンを見て決定する」ことを意味します。

したがって、手書きの再帰下降パーサは LL(1) で決定できない場合に以下を行います：
- **演算子の場合**：Pratt/precedence climbing（優先度テーブルに依存し、左再帰の除去を不要とする）を用いて式を処理できます。これは従来の `expr→term→factor` の階層よりも平坦であり、演算子の追加はテーブルの変更だけで済みます。もちろん、左再帰を除去した後に `expr → term expr'` / `expr' → + term expr' | ε` という再帰下降として記述することも完全に可能であり、教科書的な標準的な書き方です。
- **キーワードの場合**：`if` / `while` / `return` は本質的に FIRST が互いに排他的であるため、現在のトークンに応じて直接ルーティングできます。

## Pratt parser：文法の階層を優先度テーブルで置き換える

式（算術、比較、論理）において、再帰下降の階層（`expr→term→factor`）は演算子のネストを非常に深い呼び出しスタックとして表現し、演算子を追加する際に文法の階層を再構築する必要があります。Pratt parser は優先度テーブルを用いてこれを置き換えます。

```
precedence = {
    '+': 10, '-': 10,
    '*': 20, '/': 20,
    '(': 0,                 ← 最低優先度、prefix 処理でのみ使用
}

def expr(min_prec=0):
    left = prefix(peek())   ← 前置演算子（例：-x）
    while prec(peek()) >= min_prec:    ← 核心：優先度の比較
        op = consume()
        right = expr(prec(op) + (1 if left_associative else 0))
        left = BinOp(op, left, right)
    return left
```

核心的なルール：**現在の演算子の優先度が最小優先度以上の場合、右結合を継続**（より大きな式を形成）します。それ以外の場合は返します。`+1` は左結合を処理します（左結合の場合、`min_prec` を上げて同優先度の演算子を先に消費させます）。右結合（例：`=`）の場合、1 は加算されません。

これは「expr/term/factor」の階層よりも平坦であり、新しい演算子を追加する際に優先度テーブルに行を追加するだけで済み、文法や呼び出しスタックを変更する必要がありません。

## LL の問題と対応策

- **左再帰**：除去すると AST の構造が変化する → Pratt で回避（式の場合）、または AST 構築時に結合性を手動で反転させる。
- **共通接頭辞**：`if (cond) { ... } if (cond) { ... } else { ... }` の LL(1) 競合——`if` を見た後に `if` を選ぶか `if-else` を選ぶか決定できない → 解決策：dangling else は常に直近の `if` にマッチする（再帰下降では、`parse_if` 内で `else` を見たら貪欲に消費する）。
- **エラー回復**：再帰下降の最大の利点——各関数内で「余分なトークンをスキップして同期マーク（例：`;` や `}`）まで進む）までスキップする」ことをその場で決定でき、LR パーサよりもはるかに優れたエラーメッセージを生成できる。

## テーブル駆動 LL：再帰下降が不十分な場合

文法がユーザーによって提供される場合や、文法が非常に大きく手書きに適さない場合など、いくつかのシナリオではテーブル駆動 LL が用いられます。文法から FIRST/FOLLOW を計算し、予測分析表を構築します。

```
規則 A → α に対して:
  FIRST(α) の各トークン t について:
    table[A][t] = α
  もし ε ∈ FIRST(α) なら:
    FOLLOW(A) の各トークン t について:
      table[A][t] = α
```

実行時は `table[現在の非終端記号][現在のトークン]` に基づいて規則を選択します——これは再帰下降と同等ですが、分岐がコードにハードコードされるのではなくテーブルに格納されている点が異なります。ただし、テーブル駆動ではエラーメッセージを適切に作成するのは困難です（手書きの関数内の意味論的コンテキストが存在しないため）。

## 参考文献

- **Dragon Book**: Chapter 4, Syntax Analysis — LL(1)、FIRST/FOLLOW の完全な導出
- **Pratt (1973)**: "Top Down Operator Precedence" — Pratt parser の原論文
- **Nystrom**: "Crafting Interpreters", Chapter 6 (Pratt parser の優れた実装解説)

*Keywords: recursive descent, LL(1), FIRST, FOLLOW, predictive parsing, left recursion, left recursion elimination, Pratt parser, precedence climbing, top-down operator precedence, table-driven LL, dangling else, synchronizing token, error recovery*