数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学求解下列文法的FIRST集合和FOLLOW集合：
E → E + T|T
T → T ∗ F|F
F → (E)|id
解答
FIRST集合的计算
E → E + T|T
由于FIRST(E)不包含ε。
∴ FIRST(E) = FIRST(E + T) = FIRST(E)
因为 E → T
∴ FIRST(E) = {FIRST(T)} (1)
T → T ∗ F|F
由于FIRST(T)不包含ε，或者T不能推导出ε。
∴ FIRST(T) = FIRST(T ∗ F) = {FIRST(T)}
因为 T → F (FIRST(T) = {FIRST(F)} (2)
F → (E)|id
∴ 根据FIRST的规则(3)
FIRST(F) = {(, id} (3)
由(1)，(2)和(3)
FIRST(F) = {(, id} (3)
FIRST(T) = {FIRST(F)} (2)
FIRST(E) = {FIRST(T)} (1)
∴ FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FOLLOW集合的计算
E → E + T|T
T → T ∗ F|F
F → (E) |id
应用规则(1) FOLLOW(E) = {$} (1)
- E → E + T|T
应用FOLLOW的规则(2)
| E → | ε | E | + | T |
| A → | α | B | β |
α = ε, B = E, β = +T
由于FIRST(β) = FIRST(+T) = {+}不包含ε
∴ FOLLOW的规则(2a)
∴ FOLLOW(E) = FIRST(+T) = {+}
∴ FOLLOW(E) = {+} (2)
应用FOLLOW的规则(3)
| E → | E + | T |
| A → | α | B |
FOLLOW(T) = {FOLLOW(E)} (3)
- T → T * F
应用规则(2)
| T → | ε | T | *F |
| A → | α | B | β |
∴ A = T, α = ε, B = T, β = *F
由于FIRST(β) = {∗}不包含ε。
∴ FOLLOW的规则(2a)
∴ FOLLOW(T) = FIRST(* F)
∴ FOLLOW(T) = {∗} (4)
应用规则(3)
| T → | T* | F |
| A → | α | B |
FOLLOW(F) = {FOLLOW(T)} (5)
- F → (E)
应用规则(2)
| F → | ( | E | ) |
| A → | α | B | β |
由于FIRST(β) = {)}不包含ε。
∴ FOLLOW的规则(2a)
∴ FOLLOW(E) = FIRST())。
∴ FOLLOW(E) = {)} (6)
规则(3)不能应用于此产生式
它在右端有 )。
但在规则(3)中，我们应该在右端有一个非终结符。
即，我们不能将A → αB与F → (E)进行比较。
结合所有6个语句，我们得到
FOLLOW(E) = {$} (1)
FOLLOW(E) = {+} (2)
FOLLOW(T) = {FOLLOW(E)} (3)
FOLLOW(T) = {∗} (4)
FOLLOW(F) = {FOLLOW(T)} (5)
FOLLOW(E) = {)} (6)
∴ 由规则(1)，(2)和(6)
FOLLOW(E) = {$, +, )}
∴ 由规则(3)，(4)和(5)
FOLLOW(T) = FOLLOW(F) = {$, +, ),∗}
8K+ 浏览量
