编译原理实验报告材料FIRST集和FOLLOW集.doc

实用标准文案 精彩文档 编译原理实验报告 实验名称 计算first集合和follow集合 实验时间 院系 计算机科学与技术 班级 软件工程1班 学号 姓名 实验目的 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。 实验原理 设文法G[S]＝（VN，VT，P，S），则首字符集为： FIRST（α）＝{a | α 若αε，ε∈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）或in为止。 当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。 设文法G[S]＝（VN，VT，P，S），则 FOLLOW（A）＝{a | S… 若S…A，#∈FOLLOW（A）。 由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。 FOLLOW集可按下列方法求得： 对于文法G[S]的开始符号S，有#∈FOLLOW（S）； 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε} 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）； 3.实验内容 计算first集合和follow集合 4.实验心得 通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。 5.实验代码与结果 #includeiostream #includestring #includealgorithm using namespace std; #define MAXS 50 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;iN;i++) { for(j=0;j(int)p[i].left.length();j++) { if((p[i].left[j]=Ap[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[