找到以下语法 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)遵循
∴A=E,α=ε,B=T,β=E'
由于FIRST(β)=FIRST(E')包含ε。
∴FOLLOW的规则(2b)
跟随(T)=第一(E′)−{ε}∪跟随(E)
跟随(T)={+,ε}−{ε}∪跟随(E)
∴跟随(T)={+}∪跟随(E)(2)
应用FOLLOW规则(3)
A=E,α=T,B=E'
∴跟随(E′)={跟随(E)}(3)
E′→+TE′
应用规则(2)
A=E,α=+,B=T,β=E'
由于FIRST(β)=FIRST(E')包含ε。
∴FOLLOW的规则(2b)
∴跟随(T)=FIRST(E')−{ε}∪FOLLOW(E')
∴跟随(T)={+,ε}−{ε}∪跟随(E′)
∴跟随(T)={+}∪跟随(E′)(4)
应用规则(3)
∴跟随(E′)={跟随(E′)}(5)
T′→FT′
应用规则(2)
由于FIRST(β)导出ε。
∴FOLLOW的规则(2b)
∴跟随(F)=FIRST(T')−{ε}∪FOLLOW(T)
∴跟随(F)={∗,ε}−{ε}∪FOLLOW(T)
∴跟随(F)={∗}∪FOLLOW(T) (6)
应用规则(3)
∴跟随(T′)={FOLLOW(T)}(7)
T→*FT′|ε
应用规则(2)遵循
FIRST(β)=FIRST(T')包含ε或T'导出ε。
∴规则(2b)
∴跟随(F)=FIRST(T')−{ε}∪FOLLOW(T')
∴跟随(F)={*,ε}−{ε}∪跟随(T′)
∴跟随(F)={*}∪跟随(T′)(8)
应用FOLLOW规则(3)
∴FOLLOW(T')={FOLLOW(T')}(9)
F→(E)
应用规则(2)
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)={+,*,),$}