解决方案
FIRST 的计算
E →TE′
应用 FIRST 规则 (4b)
由于FIRST (T) 不包含ε，或者T 不导出ε。
∴ 第一 (E) = 第一 (TE') = FIRST(T)
∴ 第一 (E) = { FIRST(T)} (1)
E → +TE′|ε
应用 FIRST 规则 (3)
比较 E′ → +TE′ 与 X → aα
∴ FIRST(E′) = {+}
对 E′ → ε 应用规则 (2)
第一 (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)
第一 (E) = { FIRST(T)}
FIRST(E′) = {+, ε}
FIRST(T)= { FIRST(F)}
FIRST(T′) = {ε,*}
FIRST(F) = {(, id}
∴ 第一 (E) = FIRST(T)= FIRST(F)= {(, id}
FIRST(E′) = {+, ε}
FIRST(T′) = {ε,*}
FOLLOW的计算
E → TE′
E → +TE′|ε
T → FT′
T′ →∗ FT′|ε
F → (E)|id
应用规则 (1) 遵循
∴跟随 (E) = {$} (1)
E → TE′
应用规则 (2) 遵循
| E → | ε | T | Ｅ′ |
| A → | α | B | β |
∴ A = E, α = ε, B = T, β = E'
由于FIRST (β) = FIRST (E') 包含ε。
∴FOLLOW的规则(2b)
跟随 (T) = 第一 (E′) − {ε} ∪ 跟随 (E)
跟随 (T) = {+, ε} − {ε} ∪ 跟随 (E)
∴跟随 (T) = {+} ∪ 跟随 (E) (2)
应用 FOLLOW 规则 (3)
| E → | 吨 | E′ |
| A → | α | β |
A = E, α = T, B = E'
∴跟随 (E′) = {跟随 (E)} (3)
E′ → +TE′
应用规则 (2)
| 乙 → | 吨 | E′ |
| A → | 乙 | β |
A = E, α = +, B = T, β = E'
由于 FIRST(β) = FIRST(E') 包含 ε。
∴FOLLOW的规则(2b)
∴跟随 (T) = FIRST(E') − {ε} ∪ FOLLOW(E')
∴跟随(T) = {+, ε} − {ε} ∪ 跟随(E′)
∴跟随(T) = {+} ∪跟随(E′) (4)
应用规则 (3)
| 乙 → | +T | E′ |
| A → | α | B |
∴跟随(E′) = {跟随(E′)} (5)
T′→FT′
应用规则 (2)
| T → | ε | F | T′ |
| A → | α | B | β |
由于 FIRST(β) 导出 ε。
∴FOLLOW的规则(2b)
∴跟随 (F) = FIRST(T') − {ε} ∪ FOLLOW(T)
∴跟随 (F) = {∗, ε} − {ε} ∪ FOLLOW(T)
∴跟随 (F) = {∗} ∪ FOLLOW(T) (6)
应用规则 (3)
| T → | F | T′ |
| A → | α | B |
∴跟随(T′) = { FOLLOW(T)} (7)
T →*FT′|ε
应用规则 (2) 遵循
| T′ → | * | F | T′ |
| A → | α | B | β |
FIRST(β) = FIRST(T') 包含 ε 或 T' 导出 ε。
∴规则 (2b)
∴跟随 (F) = FIRST(T') − {ε} ∪ FOLLOW(T')
∴跟随(F) = {*, ε} − {ε} ∪跟随(T′)
∴跟随(F) = {*} ∪跟随(T′) (8)
应用 FOLLOW 规则 (3)
| T′ → | *F | T′ |
| A → | α | B |
∴ FOLLOW(T') = {FOLLOW(T')} (9)
F→(E)
应用规则 (2)
| F → | ( | E | ) |
| A → | α | B | β |
FIRST(β) 或FIRST( )) = {)} 不包含 ε。
∴规则(2a)
∴ 遵循 (E) = FIRST( ))
∴跟随 (E) = {)} (10)
规则 (3) 不适用于此生产。
由于 A → α B 在产生式 RH S 的右上角有 B 非终结符。但是 F → (E) 有 ) 终端在它的右上角。
规则 (2) 和规则 (3) 不适用于其余的产生式，因为它们与规则不匹配。
组合生产 (1) 至 (10)
跟随 (E) = {$} (1)
跟随 (T) = {+} ∪ 跟随 (E) (2)
跟随 (E′) = {跟随 (E)} (3)
跟随(T) = {+} ∪ 跟随(E′) (4)
跟随(E′) = {跟随(E′)} (5)
跟随 (F) = {*} ∪ FOLLOW(T) (6)
跟随(T′) = { FOLLOW(T)} (7)
跟随 (F) = {*} ∪ 跟随 (T') (8)
跟随(T') = {跟随(T')} (9)
跟随 (E) = {)} (10)
从 (1), (3) 和 (10)
跟随 (E) = 跟随 (E′) = {$, )} (11)
∴ 根据规则 4、7 和 11
∴跟随(T) = {+} ∪跟随(E′)
∴跟随 (T) = {+} ∪ {$, )}
∴跟随 (T) = {+, ), $}
跟随 (T′) = { 跟随 (T)} = {+, ), $} (12)
∴ 从陈述 6、8 和 12
跟随 (F) = {*} ∪ FOLLOW(T)
跟随 (F) = {*} ∪ {+, ), $, }
跟随 (F) = (*, +, ), $} (13)
∴ 陈述 11、12 和 13 给出了要求的答案
跟随 (E) = 跟随 (E′) = { ), $}
跟随(T) = 跟随(T′) = {+, ), $}
跟随 (F) = {+,*, ), $}