10 分で読了 #compilers #syntax-analysis
このページの目次

再帰下降と 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

関連ページ

© 2026 liz's doc