编译原理计算first集合和follow集合C++实现

设文法G[S]=(VN,VT,P,S),则首字符集为:

FIRST(α)={a | αaβ,aVT,α,β∈V *}

若αε,ε∈FIRST(α)。

由定义可以看出,FIRST(α)是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。

设α=x1x2…xn,FIRST(α)可按下列方法求得:

令FIRST(α)=Φ,i=1;

  • 若xi∈VT,则xi∈FIRST(α);
  • 若xi∈VN

① 若εFIRST(xi),则FIRST(xi)∈FIRST(α);

② 若ε∈FIRST(xi),则FIRST(xi)-{ε}∈FIRST(α);

  • i=i+1,重复(1)、(2),直到xi∈VT,(i=2,3,…,n)或xi∈VN且若εFIRST(xi)或i>n为止。

当一个文法中存在ε产生式时,例如,存在A→ε,只有知道哪些符号可以合法地出现在非终结符A之后,才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。

设文法G[S]=(VN,VT,P,S),则

 FOLLOWA)={a | S… Aa …aVT}

若S…A,#∈FOLLOW(A)。

由定义可以看出,FOLLOW(A)是指在文法G[S]的所有句型中,紧跟在非终结符A后的终结符号的集合。

FOLLOW集可按下列方法求得:

  • 对于文法G[S]的开始符号S,有#∈FOLLOW(S);
  • 若文法G[S]中有形如B→xAy的规则,其中x,y∈V *,则FIRST(y)-{ε}∈FOLLOW(A);
  • 若文法G[S]中有形如B→xA的规则,或形如B→xAy的规则且ε∈FIRST(y),其中x,y∈V *,则FOLLOW(B)∈FOLLOW(A);

求First集合的流程图:

求follow集合的流程图:

代码

 

实验

测试数据:

  • S->AB
  • S->bC
  • A->~
  • A->b
  • B->~
  • B->aD
  • C->AD
  • C->b
  • D->aS
  • D->c

结果:

问题和难点

  • 本次实验使用需要计算非终结符的first和follow集合,在求解过程中,如果遇到类似FOLLOW(A)=FOLLOW(B)的情况,此时,B的FOLLOW集合还未求解,因此需要使用递归调用solveFollow的函数。
  • 由于本次是上下文无关的文法,不是正规文法求解集合,因此需要要注意文法产生式右部长度大于等于3的情况,这种情况可以在求解程序中一个一个分析产生式的右部。这样才能保证不遗漏。

2 评论

  1. 思路非常好。借助了博主的算法,成功实现了自己的语法分析器

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注