[コンパイラ] 06. 構文解析 (1) - Top-DownパーシングとLLパーサ

構文解析 (1) - Top-DownパーシングとLLパーサ

構文解析（Syntax Analysis）はトークンストリームがプログラミング言語の文法に合致するか検証し、構文木を生成する段階です。この記事ではTop-Down方式の構文解析を扱います。

1. パーサの役割

  トークンストリーム
       |
       v
  +---------+
  |  パーサ  | <---> シンボルテーブル
  +---------+
       |
       v
  構文木 / AST

パーサの主な役割は以下の通りです。

構文検証: トークンストリームが文法に合致するか確認します。
構文木生成: 以降の意味解析とコード生成で使用されます。
エラー報告: 構文エラーの位置と種類を報告します。
エラー回復: エラー後も解析を継続して追加エラーを発見します。

2. 文脈自由文法（CFG）の復習

文脈自由文法Gは4-タプル (V, T, P, S) で定義されます。

V: 非終端記号の集合
T: 終端記号の集合
P: 生成規則の集合
S: 開始記号（Vの要素）

記法の慣例

大文字:     非終端記号 (A, B, S, E, T, F, ...)
小文字:     終端記号 (a, b, c, +, *, (, ), ...)
ギリシャ文字: 文法記号の列 (alpha, beta, gamma, ...)

導出の形式的定義

A -> gamma が生成規則であれば、alpha A beta から alpha gamma beta を導出できます。

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

最左導出の例: id + id * id
  E => E + T => T + T => F + T => id + T
    => id + T * F => id + F * F => id + id * F => id + id * id

3. 文法の修正

Top-Downパーシングのために文法を変換する必要がある場合があります。

3.1 曖昧性の除去

曖昧な文法の代表的な例は**ぶら下がりelse（dangling else）**問題です。

// 曖昧な文法
stmt -> if expr then stmt
      | if expr then stmt else stmt
      | other

if E1 then if E2 then S1 else S2 で else がどの if にマッチするか曖昧です。

// 曖昧性解消: elseは最も近いifにマッチ
matched_stmt   -> if expr then matched_stmt else matched_stmt
                | other
unmatched_stmt -> if expr then stmt
                | if expr then matched_stmt else unmatched_stmt
stmt           -> matched_stmt | unmatched_stmt

3.2 左再帰の除去（Left Recursion Elimination）

**左再帰（left recursion）**があると再帰下降パーサが無限ループに陥ります。

// 左再帰のある文法
A -> A alpha | beta

// 左再帰除去後
A  -> beta A'
A' -> alpha A' | epsilon

実際の例を見てみましょう。

// 左再帰のある算術式文法
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

// 左再帰除去後
E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

間接左再帰

// 間接左再帰
S -> A a | b
A -> S c | d

// S -> A a -> S c a（間接的に左再帰）

間接左再帰も体系的に除去できます。非終端記号に順序を付け、順番に代入して直接左再帰に変換した後除去します。

3.3 左括り出し（Left Factoring）

2つの生成規則が同じ接頭辞を共有する場合、どの規則を選ぶか決めにくくなります。

// 共通接頭辞のある文法
A -> alpha beta1 | alpha beta2

// 左括り出し後
A  -> alpha A'
A' -> beta1 | beta2

実際の例を見てみましょう。

// if-else文法
stmt -> if expr then stmt else stmt
      | if expr then stmt

// 左括り出し後
stmt       -> if expr then stmt else_part
else_part  -> else stmt | epsilon

4. 再帰下降パーサ（Recursive Descent Parser）

再帰下降パーサは各非終端記号に対して1つの関数を記述するTop-Downパーシング方法です。

実装例

文法: E -> T E', E' -> + T E' | epsilon, T -> F T', T' -> * F T' | epsilon, F -> ( E ) | id

public class RecursiveDescentParser {
    private Token lookahead;
    private Lexer lexer;

    public RecursiveDescentParser(Lexer lexer) {
        this.lexer = lexer;
        this.lookahead = lexer.nextToken();
    }

    // E -> T E'
    void E() {
        T();
        Eprime();
    }

    // E' -> + T E' | epsilon
    void Eprime() {
        if (lookahead.type == TokenType.PLUS) {
            match(TokenType.PLUS);
            T();
            Eprime();
        }
        // else: epsilon（何もしない）
    }

    // T -> F T'
    void T() {
        F();
        Tprime();
    }

    // T' -> * F T' | epsilon
    void Tprime() {
        if (lookahead.type == TokenType.STAR) {
            match(TokenType.STAR);
            F();
            Tprime();
        }
        // else: epsilon
    }

    // F -> ( E ) | id
    void F() {
        if (lookahead.type == TokenType.LPAREN) {
            match(TokenType.LPAREN);
            E();
            match(TokenType.RPAREN);
        } else if (lookahead.type == TokenType.ID) {
            match(TokenType.ID);
        } else {
            throw new SyntaxError("Unexpected token: " + lookahead);
        }
    }

    void match(TokenType expected) {
        if (lookahead.type == expected) {
            lookahead = lexer.nextToken();
        } else {
            throw new SyntaxError(
                "Expected " + expected + ", got " + lookahead.type
            );
        }
    }
}

5. FIRST集合とFOLLOW集合

予測パーサがどの生成規則を選択するか決定するためにFIRSTとFOLLOW集合が必要です。

FIRST(alpha)集合

alpha から導出可能な文字列の最初の終端記号の集合です。

計算規則:
1. Xが終端記号: FIRST(X) = {X}
2. X -> epsilon が規則: epsilonをFIRST(X)に追加
3. X -> Y1 Y2 ... Yk の場合:
   - FIRST(Y1)からepsilonを除いたものをFIRST(X)に追加
   - Y1がepsilonを導出すれば、FIRST(Y2)も追加（繰り返し）
   - 全てのYiがepsilonを導出すれば、epsilonもFIRST(X)に追加

FIRST集合の計算例

文法:
  E  -> T E'
  E' -> + T E' | epsilon
  T  -> F T'
  T' -> * F T' | epsilon
  F  -> ( E ) | id

FIRST(F)  = { (, id }
FIRST(T') = { *, epsilon }
FIRST(T)  = FIRST(F) = { (, id }
FIRST(E') = { +, epsilon }
FIRST(E)  = FIRST(T) = { (, id }

FOLLOW(A)集合

非終端記号Aの直後に現れ得る終端記号の集合です。

計算規則:
1. Sが開始記号: $をFOLLOW(S)に追加
2. A -> alpha B beta の場合:
   FIRST(beta)からepsilonを除いたものをFOLLOW(B)に追加
3. A -> alpha B の場合、またはA -> alpha B betaで
   epsilonがFIRST(beta)に含まれる場合:
   FOLLOW(A)をFOLLOW(B)に追加

FOLLOW集合の計算例

FOLLOW(E)  = { ), $ }
FOLLOW(E') = FOLLOW(E) = { ), $ }
FOLLOW(T)  = FIRST(E') - {epsilon} + FOLLOW(E) + FOLLOW(E')
           = { +, ), $ }
FOLLOW(T') = FOLLOW(T) = { +, ), $ }
FOLLOW(F)  = FIRST(T') - {epsilon} + FOLLOW(T) + FOLLOW(T')
           = { *, +, ), $ }

6. LL(1)文法と予測パーシングテーブル

LL(1)の意味

L: 入力を左から右にスキャン
L: 最左導出を生成
(1): 1つの先読みトークン（lookahead）を見て決定

予測パーシングテーブルの構成アルゴリズム

各生成規則 A -> alpha に対して:
  1. FIRST(alpha)の各終端記号aに対して:
     M[A, a]にA -> alphaを追加

  2. epsilonがFIRST(alpha)に含まれる場合:
     FOLLOW(A)の各終端記号bに対して:
     M[A, b]にA -> alphaを追加

  3. epsilonがFIRST(alpha)に含まれ、$がFOLLOW(A)に含まれる場合:
     M[A, $]にA -> alphaを追加

予測パーシングテーブルの例

       |  id         |  +          |  *          |  (           |  )          |  $
-------+-------------+-------------+-------------+--------------+-------------+--------
  E    | E -> T E'   |             |             | E -> T E'    |             |
  E'   |             | E' -> +TE'  |             |              | E' -> eps   | E' -> eps
  T    | T -> F T'   |             |             | T -> F T'    |             |
  T'   |             | T' -> eps   | T' -> *FT'  |              | T' -> eps   | T' -> eps
  F    | F -> id     |             |             | F -> ( E )   |             |

LL(1)文法の条件

文法がLL(1)であるためには、同じ非終端記号の2つの生成規則 A -> alpha | beta に対して以下が成立する必要があります。

FIRST(alpha) と FIRST(beta) が重複しないこと。
alphaとbetaのうち最大1つだけがepsilonを導出できること。
betaがepsilonを導出できる場合、FIRST(alpha) と FOLLOW(A) が重複しないこと。

7. テーブル駆動予測パーサ

スタックとパーシングテーブルを使用する予測パーサの動作を見てみましょう。

入力バッファ: id + id * id $
スタック:     $ E

パーシングテーブル: M[A, a]

パーシングアルゴリズム

スタックに$と開始記号をpush

repeat:
  X = スタックトップ, a = 現在の入力トークン

  if X == a:
    スタックからpop, 入力を進める（match）
  else if Xが終端記号:
    エラー
  else if M[X, a]が空:
    エラー
  else if M[X, a] = X -> Y1 Y2 ... Yk:
    スタックからXをpop
    Yk, ..., Y2, Y1を順にpush（逆順！）

until スタックが空で入力が$の時（受理）

パーシング追跡の例: `id + id * id`

スタック        入力              動作
$ E           id + id * id $   E -> T E'
$ E' T        id + id * id $   T -> F T'
$ E' T' F     id + id * id $   F -> id
$ E' T' id    id + id * id $   match id
$ E' T'       + id * id $      T' -> epsilon
$ E'          + id * id $      E' -> + T E'
$ E' T +      + id * id $      match +
$ E' T        id * id $        T -> F T'
$ E' T' F     id * id $        F -> id
$ E' T' id    id * id $        match id
$ E' T'       * id $           T' -> * F T'
$ E' T' F *   * id $           match *
$ E' T' F     id $             F -> id
$ E' T' id    id $             match id
$ E' T'       $                T' -> epsilon
$ E'          $                E' -> epsilon
$             $                受理！

8. エラー回復

パーサが構文エラーを発見した時の回復戦略です。

パニックモード（Panic Mode）

特定の**同期トークン（synchronizing token）**に出会うまで入力をスキップします。

同期トークンの選択基準:
- FOLLOW(A)の要素を同期トークンとして使用
- 文区切り子（セミコロン、中括弧など）
- キーワード（if、while、returnなど）

構文エラー報告の例

入力: int x = + 5;

エラーメッセージ:
  line 1:9 - syntax error: unexpected '+', expected expression

回復後に解析を続行して追加エラーを発見可能

エラープロダクション（Error Production）

頻繁に発生するエラーを文法にあらかじめ含めます。

// 正常な文法
stmt -> if ( expr ) stmt

// エラープロダクション追加（括弧を忘れた場合）
stmt -> if ( expr ) stmt
      | if expr stmt    { error("missing parentheses") }

まとめ

概念	核心内容
Top-Downパーシング	開始記号から出発して入力を導出
左再帰除去	`A -> A alpha` 形式を右再帰に変換
左括り出し	共通接頭辞を分離して選択を明確に
FIRST集合	文字列から導出可能な最初の終端記号
FOLLOW集合	非終端記号の後に来れる終端記号
LL(1)文法	1つのlookaheadで解析決定が可能
再帰下降パーサ	各非終端記号に対して関数を1つ作成
予測パーサ	スタックとパーシングテーブルに基づく

Top-Downパーシングは直感的で実装が容易ですが、表現できる文法に制限があります。次の記事では、より強力なBottom-DownパーシングとLRパーサを見ていきます。