实验六计算first集合和follow集合

1、编译原理课程实验报告实验六：计算first集合和follow集合编译原理实验报告姓名：滕雯娟 学号：E 专业：计算机科学与技术 年级 ：09 级2班 实验时间：2012/6/7 成绩：实验六：计算first集合和follow集合实验目的：1掌握求first和follow集合的算法2熟悉运用C/C+语言对求first和follow集合进行实现实验要求：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合实验原理：设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1）若xiVT，则xiFIRST（）；（2）若xiVN； 若

2、FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3）ii+1，重复（1）、（2），直到xiVT，（i2，3，n）或xiVN且若 FIRST（xi）或in为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若S A，#FOLLOW（A）。由定义可以看出，FOLLOW（A

3、）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1）对于文法GS的开始符号S，有#FOLLOW（S）；（2）若文法GS中有形如BxAy的规则，其中x，yV *，则FIRST（y）FOLLOW（A）；（3）若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；实验内容：程序代码如下：#include#includeusing namespace std;#define max 30typedef struct CSS /定义一个产生式结构体 string left; /

4、定义产生式的左部 string right; /定义产生式的右部CSS;string con;/存放文法中的非终结符string firstmax;/存放非终结符的first集string followmax;/存放非终结符的follow集/提取产生式中的非终结符void search(CSS *p,int n)int i,j;for(i=0;i=0&con.find(pi.left0)con.length()con=con+pi.left;for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=0&con.find(pi.rightj)c

5、on.length()break;elsecon=con+pi.right.substr(j,1);/求文法中非终结符的First集void First(CSS *p,int n,char m,int mm)int length=con.length();string f;int i,j,x,y;int flag=0;for(i=0;in;i+)if(m=pi.left0)if(a=pi.right0) firstmm=firstmm+pi.right.substr(0,1);if(pi.right0=#) firstmm=firstmm+pi.right.substr(0,1);if(A=p

6、i.right0)for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=Z)flag+;if(flag=j)/产生式的右部均为非终结符flag=0;for(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=px.left0&px.right0=#)flag+;break;if(flag=j)/产生式右部的全部非终结符均能推出空for(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=conx)break;y=x;if(first

7、y=)First(p,n,pi.rightj,x); f=firsty;for(x=0;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f; firstmm=firstmm+#;elsefor(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=conx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=firsty;for(x=0

8、;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f;/求文法的follow集void Follow(CSS *p,int n,int m)int i,j,x,y,k;string fo;for(i=0;in;i+)for(j=0;jpi.right.length();j+)if(conm=pi.rightj)if(jpi.right.length()-1&a=pi.rightj+1&pi.rightj+1=z) follow

9、m=followm+pi.right.substr(j+1,1); if(jpi.right.length()-1&A=pi.rightj+1&pi.rightj+1=Z)for(y=0;ycon.length();y+)if(cony=pi.rightj+1)break;fo=firsty;for(x=0;xfirsty.length();x+)if(0=firsty.find(#)&firsty.find(#)firsty.length()fo=firsty.substr(0,firstm.find(#)+firsty.substr(firsty.find(#)+1); followm=f

10、ollowm+fo; for(x=0;xn;x+)if(pi.rightj+1=px.left0&px.right0=#)break; if(x!=n)/非终结符后面的部分可以推出空for(y=0;yn;y+)if(pi.left0=cony)break; k=y; if(followk=)Follow(p,n,y); followm=followm+followk; if(j=pi.right.length()-1) for(y=0;yn;y+) if(pi.left0=cony)break; k=y; if(followk=)Follow(p,n,y); followm=followm+f

11、ollowk; /去First集及follow集中的重复字符string erase(string s)int i,j;for(i=0;is.length();i+)for(j=0;js.length();j+)if(i!=j&si=sj)s=s.substr(0,j)+s.substr(j+1);return s;void main()int i,j,n,m;string input;char f;coutn;CSS *p=new CSSn; / 初始化产生式数组for(i=0;iinput; /输入 for(j=0;jinput.length();j+)/改变输入数据的形式 if(inputj=-) pi.left=input.substr(0,j); pi.right=input.substr(j+2,input.length(); cout请输入该文法的开始符号：f;search(p,n);/提取产生式中的非终结符for(m=0;mcon.length();m+)if(firstm=)First(p,n,conm,m);cout该文法非终结符的first集：endl;for(i=0;icon.length();i+)firsti=erase(firsti);coutconi:firstiendl;for(m=0;mco