Table of Contents

構文解析表 · 作り方

🎓 発展コース です。
正準集合で、状態を12個と、その間の遷移をすべて集めましたね。
今度はそれを — パーサーが実際に見て動く — 一枚の表に変えます。それが構文解析表です。

📍 ある場所 · LRParsingTable.CreateParsingTable · …/Parsers/Collections/…

構文解析表とは

パーサーは入力を読みながらその都度「いま何をすべきか？」を決めなければなりません。その答えをあらかじめ全部書いておいた表が 構文解析表です。
ひとことで言えば — パーサーの行動マニュアルですね。*「いまどの状態にいて（行）、次の入力記号が何か（列）→ ならこの行動をしなさい」*を、マスごとに書いておいたものです。

表は二つの部分に分かれます。

  • ACTION — 列が終端記号 + $（入力の終わり）。各マスには三つの行動のうち一つが入ります。
    • shift（シフト） — 次の終端記号を読んでスタックに押し込み、指し示す次の状態へ行く。s5 = 「読んで I₅ へ」。
    • reduce（還元） — ある生成規則の右辺をすべて読み終えたので、それを左辺の非終端記号へまとめる。r2 = 「2番の生成規則で還元せよ」。
    • accept（受理） — 入力全体が文法に合った。終わり。acc。
  • GOTO — 列が非終端記号。非終端記号を一つまとめたあとどの状態へ行くか、です。（正準集合 の遷移表の非終端記号のマスそのままです。）

💡 shift・reduce、どこで見ましたっけ？状態の章で*「ドットの後ろが終端記号ならもっと読み（shift）、ドットが 末尾ならまとめる（reduce）」と言っていた、あれです。
その判断をすべての状態 × すべての入力*についてあらかじめ表に書いておくのが — 構文解析表です。

埋めるルール

表を埋めることは、正準集合で作った状態たちの項目と遷移をそのまま移す 作業です。ルールは四つだけです。

まず生成規則に番号を振ります。（reduce が*「何番でまとめるか」*を指すからです。）

   1:  Expr   → Expr '+' Term
   2:  Expr   → Term
   3:  Term   → Term '*' Factor
   4:  Term   → Factor
   5:  Factor → '(' Expr ')'
   6:  Factor → id

では各状態 Iᵢ ごとに —

① shift — ドットの後ろが終端記号 a の項目があり GOTO(Iᵢ, a) = Iⱼ なら → ACTION[Iᵢ][a] = sⱼ
② goto — ドットの後ろが非終端記号 A で GOTO(Iᵢ, A) = Iⱼ なら → GOTO[Iᵢ][A] = j
③ reduce — 完了項目 A → α •（ドットが末尾）があれば → A の FOLLOW にある終端記号 x ごとに ACTION[Iᵢ][x] = rN（N = その生成規則の番号）
④ accept — Accept → Expr • があれば → ACTION[Iᵢ][$] = acc

①②は遷移表をそのまま移すこと（終端記号は ACTION、非終端記号は GOTO）、③④は完了項目から出てきます。

③の*「FOLLOW にある終端記号ごとに」*が肝です — *「この規則でまとめたあとに来られるトークン」の ときだけまとめるのですね。状態の章で「reduce は FOLLOW のとき」*と言っていた、あの約束です。
（このようにFOLLOW で reduce のマスを決める方式をSLRと呼びます — 衝突を見たあと、SLR の章できちんと扱います。）

自分で埋めてみる

ルールを私たちの状態いくつかに直接当てはめてみましょう。（正準集合の状態・遷移表を傍らに置いて。）

① I₀ の ACTION・GOTO — 完了項目がないので①②だけ

I₀ には完了項目がないので①②だけ使います。

  • ドットの後ろの終端記号: '('（Factor → • '(' Expr ')'）と id（Factor → • id）。遷移表で GOTO(I₀,'(') = I₄、GOTO(I₀,id) = I₅ でしたね → '(' = s4, id = s5
  • ドットの後ろの非終端記号: Expr→I₁、Term→I₂、Factor→I₃ → GOTO: Expr = 1, Term = 2, Factor = 3

② I₂ の reduce — 完了項目の FOLLOW のマスに r2

I₂ には完了項目 Expr → Term •（2番の規則）があります。

  • Expr の FOLLOW は { $, '+', ')' } ですね → その三つのマスに '+' = r2, ')' = r2, $ = r2
  • 一緒にある Term → Term • '*' Factor から shift も出ます: '*'→I₇ → '*' = s7

③ I₁ の accept — $ のマスが受理

I₁ には Accept → Expr • があるので → $ = acc。
（そして Expr → Expr • '+' Term から '+'→I₆ → '+' = s6。）

このようにして12個の状態をすべて埋めると — 表が完成します。

完成した SLR 構文解析表

左の六列（id 〜 $）が ACTION、右の三列（Expr・Term・Factor）が GOTO です。

状態 id '+' '*' '(' ')' $ Expr Term Factor
I₀ s5 s4 1 2 3
I₁ s6 acc
I₂ r2 s7 r2 r2
I₃ r4 r4 r4 r4
I₄ s5 s4 8 2 3
I₅ r6 r6 r6 r6
I₆ s5 s4 9 3
I₇ s5 s4 10
I₈ s6 s11
I₉ r1 s7 r1 r1
I₁₀ r3 r3 r3 r3
I₁₁ r5 r5 r5 r5

表の読み方 — sⱼ = 読んで Iⱼ へ（shift）、rN = N番の規則でまとめる（reduce）、acc = 受理、 GOTO のマスの数字 = 非終端記号をまとめたあと行く状態。
空のマスはその入力はここでエラーという意味です。

次へ

表は全部作りました。ところが二つ残っています。

  • もし一つのマスに行動が二つ入ったらどうしましょう？（状態の章で植えておいた、あの衝突の種。）
  • reduce のマスを FOLLOW で決めたこの方式（SLR）は — どんな限界があって、どうすればもっと精密になるのでしょう？

👉 構文解析表 · 衝突とは？

👈 前へ: 正準集合

Edit this page