FIRST・FOLLOW計算（LL(1)構文解析表）
文法のnullable・FIRST・FOLLOW集合とLL(1)構文解析表を計算し、衝突と左再帰を検出して、予測構文解析の過程をたどります。
開始記号：E（最初の規則の左辺）。$は入力の終端を表します。
| 非終端記号 | 空列を導出可能 | FIRST | FOLLOW |
|---|---|---|---|
| E | いいえ | { (, id } | { ), $ } |
| E' | はい | { +, ε } | { ), $ } |
| T | いいえ | { (, id } | { +, ), $ } |
| T' | はい | { *, ε } | { +, ), $ } |
| F | いいえ | { (, id } | { +, *, ), $ } |
| + | * | ( | ) | id | $ | |
|---|---|---|---|---|---|---|
| E | E → T E' | E → T E' | ||||
| E' | E' → + T E' | E' → ε | E' → ε | |||
| T | T → F T' | T → F T' | ||||
| T' | T' → ε | T' → * F T' | T' → ε | T' → ε | ||
| F | F → ( E ) | F → id |
| スタック | 入力 | 動作 |
|---|---|---|
| E $ | id + id * id $ | E → T E' |
| T E' $ | id + id * id $ | T → F T' |
| F T' E' $ | id + id * id $ | F → id |
| id T' E' $ | id + id * id $ | 一致：id |
| T' E' $ | + id * id $ | T' → ε |
| E' $ | + id * id $ | E' → + T E' |
| + T E' $ | + id * id $ | 一致：+ |
| T E' $ | id * id $ | T → F T' |
| F T' E' $ | id * id $ | F → id |
| id T' E' $ | id * id $ | 一致：id |
| T' E' $ | * id $ | T' → * F T' |
| * F T' E' $ | * id $ | 一致：* |
| F T' E' $ | id $ | F → id |
| id T' E' $ | id $ | 一致：id |
| T' E' $ | $ | T' → ε |
| E' $ | $ | E' → ε |
| $ | $ | 受理 |
トップダウン（LL(1)）パーサーを作るには、まずすべての非終端記号について、空列を導出できるか、FIRST集合、FOLLOW集合の3つを求める必要があります。そこから予測構文解析表ができ、1つのセルに2つ以上の規則が入ると衝突となり、その文法はLL(1)に向きません。この計算ツールは、これらをすべて求め、衝突を一覧にし、左再帰を除去し、入力に対する予測構文解析の過程をたどります。
使い方
- 文法をE -> T E'のように1行に1規則で入力し、選択肢は|で区切ります。
- 空列にはε（またはeps）を使います。最初の規則の左辺が開始記号です。
- 必要なら、解析する入力文字列を入力します。
- 集合、LL(1)表、衝突、解析の過程を確認します。
計算式
FIRST(αβ) = FIRST(α) ∪ (α ⇒* ε ならFIRST(β)) · A → αBβ: FIRST(β) − {ε} ⊆ FOLLOW(B)、β ⇒* ε ならFOLLOW(A) ⊆ FOLLOW(B)
集合は、変化がなくなるまでこれらの規則を繰り返して求め、開始記号のFOLLOWには$を入れます。規則A → αは、FIRST(α)にあるすべての終端記号aについて表のセルM[A, a]に入り、αが空列になり得る場合はFOLLOW(A)のすべての記号についても入ります。左再帰は、空列を導出できる接頭辞を経由するもの（間接左再帰）まで検出し、Aho・Lam・Sethi・Ullmanの標準的なアルゴリズムでプライム付きの非終端記号を加えて除去します。
計算例
入力欄の式の文法では、FIRST(E) = FIRST(T) = FIRST(F) = { (, id }、FIRST(E') = { +, ε }、FIRST(T') = { *, ε }、FOLLOW(E) = FOLLOW(E') = { ), $ }、FOLLOW(T) = FOLLOW(T') = { +, ), $ }、FOLLOW(F) = { +, *, ), $ }となります。どのセルにも規則が2つ入らないため、この文法はLL(1)で、"id + id * id"は受理されます。左再帰のE -> E + T | Tは、まさにこの文法に書き換えられます。
よくある質問
εはFIRSTにはあるのに、FOLLOWにはないのはなぜですか？
Aが空列を導出できる場合、FIRST(A)にεが入ります。FOLLOW(A)は、Aの直後に現れ得る終端記号と、入力の終端を表す$を集めたものであり、εは何かの後に続き得る記号ではありません。
1文字より長い記号はどう書きますか？
すべての記号を空白で区切ってください。例：E -> E + T | id。1文字モードでは、大文字（'や数字を付けられます）が非終端記号で、それ以外の文字はすべて終端記号です。
衝突とはどういう意味ですか？
同じ非終端記号の2つの規則が同じ先読みトークンで始まるため、予測構文解析器が選べないということです。左括り出し、左再帰の除去、言語自体の変更で解決できることが多いですが、ぶら下がりelseのようにLL(1)にならない言語もあります。
出典
最終更新:
この入力内容のページアドレス： https://kakao.mobile/ja/tools/context-free-grammar-tool/
このツールを引用する
kakaoCalc. (2026, November 8). FIRST・FOLLOW計算（LL(1)構文解析表）. https://kakao.mobile/ja/tools/context-free-grammar-tool/
“FIRST・FOLLOW計算（LL(1)構文解析表）.” kakaoCalc, 8 Nov. 2026, kakao.mobile/ja/tools/context-free-grammar-tool/.