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

设文法G[S]＝（V_N，V_T，P，S），则首字符集为：

FIRST（α）＝{a | αaβ，a∈V_T，α,β∈V ^*}。

若αε，ε∈FIRST（α）。

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

设α＝x₁x₂…x_n，FIRST（α）可按下列方法求得：

令FIRST（α）＝Φ，i＝1；

• 若x_i∈V_T，则x_i∈FIRST（α）；
• 若x_i∈V_N；

① 若εFIRST（x_i），则FIRST（x_i）∈FIRST（α）；

② 若ε∈FIRST（x_i），则FIRST（x_i）－{ε}∈FIRST（α）；

• i＝i+1，重复（1）、（2），直到x_i∈V_T，（i＝2，3，…，n）或x_i∈V_N且若εFIRST（x_i）或i>n为止。

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

设文法G[S]＝（V_N，V_T，P，S），则

 FOLLOW（A）＝{a | S… Aa …，a∈V_T}。

若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的情况，这种情况可以在求解程序中一个一个分析产生式的右部。这样才能保证不遗漏。