找到以下语法的 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β

S→εA一种AA→ΑBβ

∵第一(β)=第一(aA)={a}

不包含ε

∴FOLLOW规则2(a)

FOLLOW(A)={FIRST(aA)}={a}

∴FOLLOW(A)={a}……………。(2)

应用FOLLOW规则(3)

比较S→AaA与A→αBβ

S→一种a一种A→Α

乙

∴FOLLOW(A)={FOLLOW(S)}………………………(3)

S→BbB

应用规则(2)遵循

比较S→BbB与A→αBβ

S→乙B乙BA→ΑBβ

A=S,

α=ε

乙=乙

β=bB

∵第一(β)=第一(bB)={b}

不包含ε

∴FOLLOW规则2(a)

FOLLOW(B)={第一（bB）}

∴FOLLOW(B)={b}……………。(4)

应用FOLLOW规则(3)

比较S→BaB与A→αB

S→乙a乙A→Α

乙

∴FOLLOW(B)={FOLLOW(S)}………………………(5)

A→bB

规则(2)不能适用。因为我们不能将A→bB与A→αBβ匹配

如果我们比较α=b,B=B,β=ε。

在这里，β将变为ε，这是不可能的

应用FOLLOW规则(3)

比较A→bB与A→αB

A→乙BA→α乙

∴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}