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

《编译原理》课程实验报告实验六：计算first集合和follow集合编译原理实验报告姓名：滕雯娟学号：E10914008专业：计算机科学与技术年级：09级2班实验时间：2012/6/7成绩：实验六：计算first集合和follow集合实验目的：1．掌握求first和follow集合的算法2．熟悉运用C/C++语言对求first和follow集合进行实现实验要求：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合实验原理：设α＝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）或in为止。当一个文法中存在ε产生式时，例如，存在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）；实验内容：程序代码如下：#includeiostream#includestringusingnamespacestd;#definemax30typedefstructCSS//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}CSS;stringcon;//存放文法中的非终结符stringfirst[max];//存放非终结符的first集stringfollow[max];//存放非终结符的follow集//提取产生式中的非终结符voidsearch(CSS*p,intn){inti,j;for(i=0;in;i++){if(!(con.find(p[i].left[0])=0&&con.find(p[i].left[0])con.length()))con=con+p[i].left;for(j=0;jp[i].right.length();j++){if('A'=p[i].right[j]&&p[i].right[j]='Z'){if(con.find(p[i].right[j])=0&&con.find(p[i].right[j])con.length())break;elsecon=con+p[i].right.substr(j,1);}}}}//求文法中非终结符的First集voidFirst(CSS*p,intn,charm,intmm){intlength=con.length();stringf;inti,j,x,y;intflag=0;for(i=0;in;i++){if(m==p[i].left[0]){if('a'=p[i].right[0]&&'z'=p[i].right[0])first[mm]=first[mm]+p[i].right.substr(0,1);if(p[i].right[0]=='#')first[mm]=first[mm]+p[i].right.substr(0,1);if('A'=p[i].right[0]&&'Z'=p[i].right[0]){for(j=0;jp[i].right.length();j++){if('A'=p[i].right[j]&&p[i].right[j]='Z')flag++;}if(flag==j)//产生式的右部均为非终结符{flag=0;for(j=0;jp[i].right.length();j++){for(x=0;xn;x++)if(p[i].right[j]==p[x].left[0]&&p[x].right[0]=='#'){flag++;break;}}if(flag==j)//产生式右部的全部非终结符均能推出空{for(j=0;jp[i].right.length();j++){for(x=0;xn;x++){if(p[i].right[j]==con[x])break;}y=x;if(first[y]==)First(p,n,p[i].right[j],x);f=first[y];for(x=0;xf.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);elsef=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}first[mm]=first[mm]+#;}else{for(j=0;jp[i].right.length();j++){for(x=0;xn;x++){if(p[i].right[j]==con[x])break;}y=x;if(first[y]==)First(p,n,p[i].right[j],x);f=first[y];for(x=0;xf.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);elsef=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}}}}}}}//求文法的follow集voidFollow(CSS*p,intn,intm){inti,j,x,y,k;stringfo;for(i=0;in;i++){for(j=0;jp[i].right.length();j++){if(con[m]==p[i].right[j]){if(jp[i].right.length()-1&&'a'=p[i].right[j+1]&&p[i].right[j+1]='z')follow[m]=follow[m]+p[i].right.substr(j+1,1);if(jp[i].right.length()-1&&'A'=p[i].right[j+1]&&p[i].right[j+1]='Z'){for(y=0;ycon.length();y++){if(con[y]==p[i].right[j+1])break;}fo=first[y];for(x=0;xfirst[y].length();x++){if(0=first[y].find('#')&&first[y].find('#')first[y].length())fo=first[y].substr(0,first[m].find('#'))+first[y].substr(first[y].find('#')+1);}follow[m]=follow[m]+fo;for(x=0;xn;x++){if(p[i].right[j+1]==p[x].left[0]&&p[x].right[0]=='#')break;}if(x!=n)//非终结符后面的部分可以推出空{for(y=0;yn;y++){if(p[i].left[0]==con[y])break;}k=y;if(follow[k]==)Follow(p,n,y);follow[m]=follow[m]+follow[k];}}if(j==p[i].right.length()-1){for(y=0;yn;y++){if(p[i].left[0]==con[y])break;}k=y;if(follow[k]==)Follow(p,n,y);follow[m]=follow[m]+follow[k];}}}}}//去First集及follow集中的重复字符stringerase(strings){inti,j;for(i=0;is.length();i++){for(j=0;js.length();j++){if(i!=j&&s[i]==s[j])s=s.substr(0,j)+s.substr(j+1);}}returns;}voidmain(){inti,j,n,m;stringinput;charf;cout请输入文法产生式个数N：;cinn;CSS*p=newCSS[n];//初始化产生式数组for(i=0;in;i++)//输入产生式数组,用#代表空{input.erase();//清除cininput;//输入for(j=0;jinput.length();j++)//改变输入数据的形式{if(input[j]=='-'){p[i].left=input.substr(0,j);p[i].right=input.substr(j+2,input.length());}}}cout请输入该文法的开始符号：endl;cinf;search(p,n);//提取产生式中的非终结符for(m=0;mcon.length();m++){if(first[m]==)First(p,n,con[m],m);}cout该文法非终结符的first集：endl;for(i=0;icon.length();i++){first[i]=erase(first[i]);coutcon[i]:first[i]endl;}for(m=0;mcon.length();m++){if(con[m]==f)follow[m]=follow[m]+#;if(follow[m]==)Follow(p,n,m);}cout该文法非终结符的follow集：endl;for(i=0;icon.length();i++){follow[i]=erase(follow[i]);coutcon[i]:follow[i]endl;}system(pause);}实验结果：运行界面如下：