構文解析 (1) - Top-DownパーシングとLLパーサ
構文解析（Syntax Analysis）はトークンストリームがプログラミング言語の文法に合致するか検証し、構文木を生成する段階です。この記事ではTop-Down方式の構文解析を扱います。
1. パーサの役割
トークンストリーム
|
v
+---------+
| パーサ | <---> シンボルテーブル
+---------+
|
v
構文木 / AST
パーサの主な役割は以下の通りです。
1. **構文検証**: トークンストリームが文法に合致するか確認します。
2. **構文木生成**: 以降の意味解析とコード生成で使用されます。
3. **エラー報告**: 構文エラーの位置と種類を報告します。
4. **エラー回復**: エラー後も解析を継続して追加エラーを発見します。
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` に対して以下が成立する必要があります。
1. `FIRST(alpha)` と `FIRST(beta)` が**重複しない**こと。
2. alphaとbetaのうち最大1つだけがepsilonを導出できること。
3. 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パーサを見ていきます。
현재 단락 (1/256)
構文解析（Syntax Analysis）はトークンストリームがプログラミング言語の文法に合致するか検証し、構文木を生成する段階です。この記事ではTop-Down方式の構文解析を扱います。