找到以下语法的 FIRST & FOLLOW。S → A → A | B b B A → b B B → ε
解决方案
FIRST的计算
A→BB
∴FIRST(A)={b}
乙→ε
∴FIRST(B)={ε}
S→AaA
FIRST规则(4)的应用
即，比较S→AaA与X→Y1Y2Y3
∴第一(S)=第一(AaA)=第一(A)={b}
∴FIRST(S)={b}
S→BbB
∵FIRST(B)包含ε或B导出ε∴应用规则(4c)
∴第一(S)=第一（B到B）
∴FIRST(S)=FIRST(B)−{ε}∪FIRST(bB)
∴FIRST(S)=FIRST(B)−{ε}∪{b}={ε}−{ε}∪{b}={b}
∴第一个(A)={b}
第一(B)={ε}
第一(S)={b}
FOLLOW的计算
应用规则(1)FOLLOWFOLLOW(S)={$}.....(1)
S→AaA
应用规则(2)遵循
比较S→AaA与A→αBβ
∵第一(β)=第一(aA)={a}
不包含ε
∴FOLLOW规则2(a)
FOLLOW(A)={FIRST(aA)}={a}
∴FOLLOW(A)={a}……………。(2)
应用FOLLOW规则(3)
比较S→AaA与A→αBβ
∴FOLLOW(A)={FOLLOW(S)}………………………(3)
S→BbB
应用规则(2)遵循
比较S→BbB与A→αBβ
A=S,
α=ε
乙=乙
β=bB
∵第一(β)=第一(bB)={b}
不包含ε
∴FOLLOW规则2(a)
FOLLOW(B)={第一（bB）}
∴FOLLOW(B)={b}……………。(4)
应用FOLLOW规则(3)
比较S→BaB与A→αB
∴FOLLOW(B)={FOLLOW(S)}………………………(5)
A→bB
规则(2)不能适用。因为我们不能将A→bB与A→αBβ匹配
如果我们比较α=b,B=B,β=ε。
在这里，β将变为ε，这是不可能的
应用FOLLOW规则(3)
比较A→bB与A→αB
∴FOLLOW(B)={FOLLOW(A)}………………………(6)
从陈述(1)到(6)
FOLLOW(S)={$}(1)
FOLLOW(A)={a}(2)
FOLLOW(A)={关注(S)}(3)
FOLLOW(B)={b}(4)
FOLLOW(B)={FOLLOW(S)}(5)
FOLLOW(B)={跟随(A)}(6)
∴FOLLOW(S)={$}
从(1),(2),(3)
FOLLOW(A)={$,a}
从(4),(5),(6)
FOLLOW(B)={$,a,b}