資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究求以下文法的 FIRST 集和 FOLLOW 集：\nE → TE′\nE → +TE′|ε\nT → FT′\nT′ →* FT′|ε\nF → (E)|id
解答
計算 FIRST 集
- E →TE′
應用 FIRST 集的規則 (4b)
由於 FIRST(T) 不包含 ε，或者 T 不能推匯出 ε。
∴ FIRST(E) = FIRST(TE′) = FIRST(T)
∴ FIRST(E) = {FIRST(T)} (1)
- E → +TE′|ε
應用 FIRST 集的規則 (3)
將 E′ → +TE′ 與 X → aα 進行比較
∴ FIRST(E′) = {+}
對 E′ → ε 應用規則 (2)
FIRST(E′) = {ε}
∴ FIRST(E′) = {+, ε} (2)
- T→FT′
應用 FIRST 集的規則 (4b)
由於 FIRST(F) 不能推匯出 ε
∴ FIRST(T) = FIRST(FT′) = FIRST(F)
∴ FIRST(T) = {FIRST(F)} (3)
- T′→*FT′|ε
根據 FIRST 集的規則 (2) 和 (3)，我們得到
∴ FIRST(T′) = {ε,∗} (4)
- F→(E)|id
根據 FIRST 集的規則 (3) 進行比較
∴ FIRST(F) = {(, id} (5)
結合語句 (1)、(2)、(3)、(4)、(5)
FIRST(E) = {FIRST(T)}
FIRST(E′) = {+, ε}
FIRST(T) = {FIRST(F)}
FIRST(T′) = {ε,*}
FIRST(F) = {(, id}
∴ FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FIRST(E′) = {+, ε}
FIRST(T′) = {ε,*}
計算 FOLLOW 集
E → TE′
E → +TE′|ε
T → FT′
T′ →∗ FT′|ε
F → (E)|id
應用 FOLLOW 集的規則 (1)
∴ FOLLOW(E) = {$} (1)
- E → TE′
應用 FOLLOW 集的規則 (2)
| E → | ε | T | E′ |
| A → | α | B | β |
∴ A = E, α = ε, B = T, β = E′
由於 FIRST(β) = FIRST(E′) 包含 ε。
∴ FOLLOW 集的規則 (2b)
FOLLOW(T) = FIRST(E′) - {ε} ∪ FOLLOW(E)
FOLLOW(T) = {+, ε} - {ε} ∪ FOLLOW(E)
∴ FOLLOW(T) = {+} ∪ FOLLOW(E) (2)
應用 FOLLOW 集的規則 (3)
| E → | T | E′ |
| A → | α | β |
A = E, α = T, B = E′
∴ FOLLOW(E′) = {FOLLOW(E)} (3)
- E′ → +TE′
應用規則 (2)
| E → | T | E′ |
| A → | B | β |
A = E, α = +, B = T, β = E′
由於 FIRST(β) = FIRST(E′) 包含 ε。
∴ **FOLLOW 集的規則 (2b)**
∴ FOLLOW(T) = FIRST(E′) - {ε} ∪ FOLLOW(E′)
∴ FOLLOW(T) = {+, ε} - {ε} ∪ FOLLOW(E′)
∴ FOLLOW(T) = {+} ∪ FOLLOW(E′) (4)
- 應用規則 (3)
| E → | +T | E′ |
| A → | α | B |
∴ FOLLOW(E′) = {FOLLOW(E′)} (5)
- T′ →FT′
應用規則 (2)
| T → | ε | F | T′ |
| A → | α | B | β |
由於 FIRST(β) 推匯出 ε。
∴ **FOLLOW 集的規則 (2b)**
∴ FOLLOW(F) = FIRST(T′) - {ε} ∪ FOLLOW(T)
∴ FOLLOW(F) = {∗, ε} - {ε} ∪ FOLLOW(T)
∴ FOLLOW(F) = {∗} ∪ FOLLOW(T) (6)
應用規則 (3)
| T → | F | T′ |
| A → | α | B |
∴ FOLLOW(T′) = {FOLLOW(T)} (7)
- T →*FT′|ε
應用 FOLLOW 集的規則 (2)
| T′ → | * | F | T′ |
| A → | α | B | β |
FIRST(β) = FIRST(T′) 包含 ε 或 T′ 推匯出 ε。
∴ **規則 (2b)**
∴ FOLLOW(F) = FIRST(T′) - {ε} ∪ FOLLOW(T′)
∴ FOLLOW(F) = {*, ε} - {ε} ∪ FOLLOW(T′)
∴ FOLLOW(F) = {*} ∪ FOLLOW(T′) (8)
應用 FOLLOW 集的規則 (3)
| T′ → | *F | T′ |
| A → | α | B |
∴ FOLLOW(T′) = {FOLLOW(T′)} (9)
- F→(E)
應用規則 (2)
| F → | ( | E | ) |
| A → | α | B | β |
FIRST(β) 或 FIRST( )) = {)} 不包含 ε。
∴ **規則 (2a)**
∴ FOLLOW(E) = FIRST( ))
∴ FOLLOW(E) = {)} (10)
規則 (3) 不適用於此產生式。
因為 A → α B 在產生式的右端有非終結符 B。但是 F → (E) 在其右端有 ) 終結符。
規則 (2) 和規則 (3) 不適用於其餘產生式，因為它們與規則不匹配。
結合產生式 (1) 到 (10)
FOLLOW(E) = {$} (1)
FOLLOW(T) = {+} ∪ FOLLOW(E) (2)
FOLLOW(E′) = {FOLLOW(E)} (3)
FOLLOW(T) = {+} ∪ FOLLOW(E′) (4)
FOLLOW(E′) = {FOLLOW(E′)} (5)
FOLLOW(F) = {*} ∪ FOLLOW(T) (6)
FOLLOW(T′) = {FOLLOW(T)} (7)
FOLLOW(F) = {*} ∪ FOLLOW(T′) (8)
FOLLOW(T′) = {FOLLOW(T′)} (9)
FOLLOW(E) = {)} (10)
根據 (1)、(3) 和 (10)
FOLLOW(E) = FOLLOW(E′) = {$, )} (11)
∴ 根據規則 4、7 和 11
∴ FOLLOW(T) = {+} ∪ FOLLOW(E′)
∴ FOLLOW(T) = {+} ∪ {$, )}
∴ FOLLOW(T) = {+, ), $}
FOLLOW(T′) = {FOLLOW(T)} = {+, ), $} (12)
∴ 根據語句 6、8 和 12
FOLLOW(F) = {*} ∪ FOLLOW(T)
FOLLOW(F) = {*} ∪ {+, ), $, }
FOLLOW(F) = {*, +, ), $} (13)
∴ 語句 11、12 和 13 給出了所需的答案
FOLLOW(E) = FOLLOW(E′) = { ), $}
FOLLOW(T) = FOLLOW(T′) = {+, ), $}
FOLLOW(F) = {+, *, ), $}
4K+ 瀏覽量
