找到以下语法 E → TE′ E → +TE′|ε T → FT′ T′ →* FT′|ε F → (E)|id 的 FIRST & FOLLOW

解决方案

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)

乙→+TE′A→αB

∴跟随(E′)={跟随(E′)}(5)

T′→FT′

应用规则(2)

T→εFT′A→αBβ

由于FIRST(β)导出ε。

∴FOLLOW的规则(2b)

∴跟随(F)=FIRST(T)−{ε}∪FOLLOW(T)

∴跟随(F)={∗,ε}−{ε}∪FOLLOW(T)

∴跟随(F)={∗}∪FOLLOW(T) (6)

应用规则(3)

T→FT′A→αB

∴跟随(T′)={FOLLOW(T)}(7)

T→*FT′|ε

应用规则(2)遵循

T′→*FT′A→αBβ

FIRST(β)=FIRST(T)包含ε或T导出ε。

∴规则(2b)

∴跟随(F)=FIRST(T)−{ε}∪FOLLOW(T)

∴跟随(F)={*,ε}−{ε}∪跟随(T′)

∴跟随(F)={*}∪跟随(T′)(8)

应用FOLLOW规则(3)

T′→*FT′A→αB

∴FOLLOW(T)={FOLLOW(T)}(9)

F→(E)

应用规则(2)

F→(E)A→αBβ

FIRST(β)或FIRST())={)}不包含ε。

∴规则(2a)

∴遵循(E)=FIRST())

∴跟随(E)={)}(10)

规则(3)不适用于此生产。

由于A→αB在产生式RHS的右上角有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)={+,*,),$}