编译原理实验报告
实验名称计算first集合和follow集合
实验时间
院系 计算机科学与技术
班级 软件工程1班 学号 姓名
1. 实验目的
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。
2. 实验原理
设文法G[S]＝（VN，VT，P，S），则首字符集为：
* FIRST（α）＝{a | α?aβ，a∈VT，α,β∈V *}。
*若α?ε，ε∈FIRST（α）。
由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中
处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。
设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1； （1） 若xi∈VT，则xi∈FIRST（α）； （2） 若xi∈VN；
① 若ε?FIRST（xi），则FIRST（xi）∈FIRST（α）；
② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； （3） 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），则
FOLLOW（A）＝{a | S?… Aa …，a∈VT}。
*若S?…A，#∈FOLLOW（A）。
由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得： （1） 对于文法G[S]的开始符号S，有#∈FOLLOW（S）； （2） 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则
FIRST（y）－{ε}∈FOLLOW（A）； （3） 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε
∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）；
3.实验内容
计算first集合和follow集合
4.实验心得
通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。
5.实验代码与结果
#include
int NONE[MAXS]={0}。
string strings。//产生式 string Vn。//非终结符 string Vt。//终结符
string first[MAXS]。// 用于存放每个终结符的first集 string First[MAXS]。// 用于存放每个非终结符的first集
string Follow[MAXS]。 // 用于存放每个非终结符的follow集 int N。//产生式个数
struct STR {
string left。 string right。 }。
//求VN和VT
void VNVT(STR *p) {
int i,j。
for(i=0。i for(j=0。j<(int)p[i].left.length()。j++) { if((p[i].left[j]>='A'&&p[i].left[j]<='Z')) { if(Vn.find(p[i].left[j])>100) Vn+=p[i].left[j]。 } else { if(Vt.find(p[i].left[j])>100) Vt +=p[i].left[j]。 } } for(j=0。j<(int)p[i].right.length()。j++) { if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z')) { if(Vt.find(p[i].right[j])>100) Vt +=p[i].right[j]。 } else {