LL(1)文法 - nofx @Wiki

α　：　記号列（空列εを含む）　　　α∈（Ｎ∪Σ）*
First(α)　：　αの始動記号の集合

• First(α)　＝　｛　ａ　|　ａ∈Ｎ，　α⇒ａ…｝

A　：　非終端記号
Follow(Ａ)　：　Ａの追随記号の集合

• Follow(Ａ)　＝　｛　ａ　|　ａ∈Ｎ，　Ｓ⊥⇒…Ａａ…｝

　　　（開始記号Ｓ、Follow(Ｓ)は文末記号⊥を含む）

生成規則
　　　Ａ→α　　　（Ａ：非終端記号、　α：記号列）
に対して、
Director(Ａ，α)　：　生成規則　Ａ→α　の引率記号の集合h

Director(Ａ，α)	＝	First(α)	（α⇒εでないとき）
		First(α)　∪　Follow(Ａ)	（α⇒εのとき）

文法Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）において、右辺だけ異なる任意の生成規則
Ａ→α
と
Ａ→β
に対して
Director(Ａ，α)∩Director(Ａ，β)＝Φ
が成り立つとき、ＧはＬＬ（１）文法であるという。

与えられた文法がLL(1)文法であれば、入力トークン列の先頭の終端記号を見れば、次にＡのどの生成規則を使用すべきかが決定できる。

---

■非終端記号Ｘに対してＸが空列を生成しうるか否かを判定するアルゴリズム
　　（Ｘ⇒εか否か？）

配列ary[]を用意し、Ｘに対応するary[Ｘ]は次のような値を持つものとする。

		yes	（Ｘが空列を生成すると決定したとき）
ary[Ｘ]	＝	no	（Ｘが空列を生成しないと決定したとき）
		u	（未定）

1. まず、全ての非終端記号Ｘに対して
   ary[Ｘ]＝　u
   とする
2. 右辺に終端記号を含む全ての生成規則をチェックする。
   この結果、ある終端記号Ｘに対して全ての生成規則がチェックされたら
   ary[Ｘ]＝　no
   とする
3. 右辺に　ε　を持つ生成規則であれば、チェックし、その生成規則の左辺の非終端記号Ｘに対して
   ary[Ｘ]＝　yes
   とする
4. この時点で　ary[Ｘ]＝　u　であるＸが残っているならば、次を　ary[Ｘ]＝　u　が無くなるまで以下を繰り返す。
   ①　　右辺に　ary[Ｘ]＝　no　を満たす非終端記号を持つ全ての生成規則をチェックする。
   この結果、ある非終端記号Ｙに関して全ての生成規則がチェックされたなら
   ary[Ｘ]＝　no
   とする
   ②　　右辺に　ary[Ｘ]＝　yes　を満たす非終端記号を持つ全ての生成規則からＸを削除する。
   この結果、生成規則の右辺が空になったら、この生成規則をチェックしその左辺の非終端記号Ｙに関して
   ary[Ｘ]＝　yes
   とする
   

■非終端記号Ｘに対して、始動記号の集合Ｓ（Ｘ）を求める手順

• Ｓ（Ｘ）＝φで初期化

Ｓ（Ｘ）が変化しなくなるまで以下を繰り返す。

1. Ｘ→aαなる生成規則があれば
   Ｓ（Ｘ）＝Ｓ（Ｘ）　∪　｛ a ｝
2. Ｘ→Ｙαなる生成規則があれば
   ①　Ｙ⇒ε　　なら
   Ｓ（Ｘ）＝Ｓ（Ｘ）　∪　Ｓ（Ｙ）　∪　Ｓ（α）
   
   Ｓ（α）の求め方は下に示す。
   
   ②　そうでないなら
   Ｓ（Ｘ）＝Ｓ（Ｘ）　∪　Ｓ（Ｙ）

■記号列αに対して、始動記号の集合Ｓ（α）を求める手順

1. α＝εのとき
   Ｓ（α）＝φ
2. αの先頭が終端記号aのとき
   Ｓ（α）＝｛ a ｝
3. α＝Ｙβのとき
   ①　Ｙ⇒ε　　なら
   Ｓ（α）＝Ｓ（Ｙ）　∪　Ｓ（β）
   
   ②　そうでないなら
   Ｓ（α）＝Ｓ（Ｙ）

■非終端記号Ｂに対して追随記号の集合Ｆ（Ｂ）を求める手順

• Ｂ：開始記号なら　　Ｆ（Ｂ）＝｛⊥｝　　　（⊥：文末記号）
• Ｂ：開始記号以外なら　　　Ｆ（Ｂ）＝φ　　で初期化

Ｆ（Ｂ）が変化しなくなるまで以下を繰り返す。

右辺にＢを含む生成規則を　Ａ→αＢβで表す

1. β＝ε　（Ｂが最後の記号）のとき
   Ｂ≠Ａなら　　　Ｆ（Ｂ）＝Ｆ（Ｂ）∪Ｆ（Ａ）
   Ｂ＝Ａなら　　　何もしない
2. βの先頭が終端記号aのとき
   Ｆ（Ｂ）＝Ｆ（Ｂ）∪｛ a ｝
3. １．、２．以外の場合
   ①　β⇒εのとき
   Ｆ（Ｂ）＝Ｆ（Ｂ）∪Ｓ（β）∪Ｆ（Ａ）
   ②　それ以外のとき
   Ｆ（Ｂ）＝Ｆ（Ｂ）∪Ｓ（β）