如何找到递归语法的 FIRST 和 FOLLOW 集合？

Question

假设我有以下 CFG：

S->aACD|BcAe

A->b | EPSILON

B->cf | d

C->fe

现在我在 CFG 上应用第一个规则：

FIRST(S)=FIRST(aAcd) U FIRST(BcAe)

={a} U FIRST(BcAe)

= {a} U FIRST(B)-{EPSILON} U FIRST(cAe)

= {a} U FIRST(B)-{EPSILON} U {c}

= {a} U FIRST(Cf) U FIRST(d) -{EPSILON} U {c}

= {a,f,d,c,EPSILON}

FIRST(A)=FIRST(b) U FIRST(EPSILON)= ={B,EPSILON}

FIRST(B)=FIRST(Cf) U FIRST(d)={d,f}

FIRST(C)=FIRST(fe)={F}

现在我在 CFG 上应用 FOLLOW 规则：

FOLLOW(S)={$}

FOLLOW(A)={c,e}

FOLLOW(B)={c}

FOLLOW(C)={f}

有没有错？如果错了请告诉我怎么做。

Answer 1

你上面的作业（问题）表明你的基础概念不好。所以你可以利用 this tutorial.

语法：

S->aACD|BcAe

A->b | EPSILON

B->cf | d

C->fe

没有生产意味着EPSILON所以，

D-> EPSILON

关于应用第一条规则：

FIRST(A)=FIRST(b) U FIRST(EPSILON)= ={b,EPSILON}

FIRST(B)=FIRST(cf) U FIRST(d)={c} U {d} = {c,d}

FIRST(C)=FIRST(fe)={f}

FIRST(D)={EPSILON}

FIRST(S)=FIRST(aACD) U FIRST(BcAe)

={a} U FIRST(BcAe)

= {a} U FIRST(B)

= {a} U {c,d}

= {a,c,d}

应用遵循规则：

FOLLOW(S)={$}

FOLLOW(A)= FIRST(C) U FIRST(e) = {f,e}

FOLLOW(B)={c}

FOLLOW(C)={$}

FOLLOW(D)={$}