数据结构
网络
关系数据库管理系统
操作系统
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+ 浏览量
