資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學B → ε
解答
FIRST集的計算
- A → b B
∴ FIRST(A) = {b}
- B → ε
∴ FIRST(B) = {ε}
- S → A a A
應用FIRST集的規則(4)
即，將S → A a A與X → Y1Y2Y3進行比較
∴ FIRST(S) = FIRST(A a A) = FIRST(A) = {b}
∴ FIRST(S) = {b}
- S → B b B
∵ FIRST(B)包含ε 或 B 可推匯出 ε ∴ 應用規則(4c)
∴ FIRST(S) = FIRST(B b B)
∴ FIRST(S) = FIRST(B) - {ε} ∪ FIRST(bB)
∴ FIRST(S) = FIRST(B) - {ε} ∪ {b} = {ε} - {ε} ∪ {b} = {b}
∴ FIRST(A) = {b}
FIRST(B) = {ε}
FIRST(S) = {b}
FOLLOW集的計算
應用規則(1) FOLLOW(S) = {$}
- S → A a A
應用規則(2) FOLLOW
將S → A a A與A → αBβ進行比較
| S → | ε | A | a | A |
| A → | α | B | β |
∵ FIRST(β) = FIRST(aA) = {a}
不包含ε
∴ 應用FOLLOW規則2(a)
FOLLOW(A) = {FIRST(aA)} = {a}
∴ FOLLOW(A) = {a}
應用FOLLOW規則(3)
將S → A a A與A → αBβ進行比較
| S → | A | a | A |
| A → | α | B |
∴ FOLLOW(A) = {FOLLOW(S)}
- S → B b B
應用規則(2) FOLLOW
將S → B b B與A → αBβ進行比較
| S → | ε | B | b | B |
| A → | α | B | β |
A = S,
α = ε
B = B
β = bB
∵ FIRST(β) = FIRST(bB) = {b}
不包含ε
∴ 應用FOLLOW規則2(a)
FOLLOW(B) = {FIRST(bB)}
∴ FOLLOW(B) = {b}
應用FOLLOW規則(3)
將S → B a B與A → αB進行比較
| S → | B | a | B |
| A → | α | B |
∴ FOLLOW(B) = {FOLLOW(S)}
- A → bB
無法應用規則(2)。因為無法將A → b B與A → αBβ匹配。
如果比較α = b, B = B, β = ε。
這裡，β將變為ε，這是不可能的。
應用FOLLOW規則(3)
將A → b B與A → αB進行比較
| A → | b | B |
| A → | α | B |
∴ FOLLOW(B) = {FOLLOW(A)}
根據(1)到(6)
FOLLOW(S) = {$}
FOLLOW(A) = {a}
FOLLOW(A) = {FOLLOW(S)}
FOLLOW(B) = {b}
FOLLOW(B) = {FOLLOW(S)}
FOLLOW(B) = {FOLLOW(A)}
∴ FOLLOW(S) = {$}
根據(1)，(2)，(3)
FOLLOW(A) = {$, a}
根據(4)，(5)，(6)
FOLLOW(B) = {$, a, b}
781 次瀏覽
