编译原理实验报告LL语法解析总结器构造

编译原理实验报告LL语法分析总结器结构编译原理实验报告LL语法分析总结器结构15/15编译原理实验报告LL语法分析总结器结构《LL（1）分析器的结构》实验报告一、实验名称LL(1)分析器的结构二、实验目的设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的鉴别，加深对语法分析原理的理解。三、实验内容和要求设计并实现一个LL(1)语法分析器，实现对算术文法:G[E]:E->E+T|TT->T*F|FF->(E)|i所定义的符号串进行鉴别，比方符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。实验要求:、检测左递归，若是有则进行除掉；、求解FIRST集和FOLLOW集；、成立LL(1)分析表；、成立LL分析程序，对于用户输入的句子，能够利用所结构的分析程序进行分析，并显示出分析过程。四、主要仪器设备硬件：微型计算机。软件：Codeblocks（也能够是其他集成开发环境）。五、实验过程描述1、程序主要框架程序中编写了以下函数，各个函数实现的作用以下：voidinput_grammer(string*G);//输入文法Gvoidpreprocess(string*G,string*P,string&U,string&u,int&n,int&t,int&k);//将文法G预办理获得产生式会集P，非终结符、终结符会集U、u，inteliminate_1(string*G,string*P,stringU,string*GG);//除掉文法G中所有直接左递归获得文法GGint*ifempty(string*P,stringU,intk,intn);//判断各非终结符可否能推导为空string*FIRST_X(string*P,stringU,stringu,int*empty,intk,intn)；求所有非终结符的FIRST集stringFIRST(stringU,stringu,string*first,strings)；//求符号串s=X1X2...Xn的FIRST集stringcreate_table(string*P,stringU,stringu,intn,intt,intk,string*first)；//结构分析表voidanalyse(stringtable,stringU,stringu,intt,strings)；//分析符号串s2、编写的源程序#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;voidinput_grammer(string*G)//输入文法G,n个非终结符{inti=0;//计数charch='y';while(ch=='y'){cin>>G[i++];cout<<"连续输入?(y/n)\n";cin>>ch;}}voidpreprocess(string*G,string*P,string&U,string&u,int&n,int&t,int&k)//

将文法

G预办理产生式会集

P，非终结符、终结符会集

U、u，{inti,j,r,temp;//计数charC;//记录规则中（）后的符号intflag;//检测到（）n=t=k=0;for(i=0;i<50;i++)P[i]="用P[i].append(1,a)U=u="";//

";//字符串若是不初始化，在使用P[i][j]=a时将不能够改变，能够字符串若是不初始化，无法使用U[i]=a赋值，能够用U.append(1,a)for(n=0;!G[n].empty();n++){U[n]=G[n][0];}//非终结符会集，n为非终结符个数for(i=0;i<n;i++){for(j=4;j<G[i].length();j++){if(U.find(G[i][j])==string::npos&&u.find(G[i][j])==string::npos)if(G[i][j]!='|'&&G[i][j]!='^')//if(G[i][j]!='('&&G[i][j]!=')'&&G[i][j]!='|'&&G[i][j]!='^')u[t++]=G[i][j];}}//终结符会集，t为终结符个数for(i=0;i<n;i++){flag=0;r=4;for(j=4;j<G[i].length();j++){P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';/*if(G[i][j]=='('){j++;flag=1;for(temp=j;G[i][temp]!=')';temp++);C=G[i][temp+1];//C记录（）后跟的字符，将C增加到（）中所有字符串后边}if(G[i][j]==')'){j++;flag=0;}*/if(G[i][j]=='|'){//if(flag==1)P[k][r++]=C;k++;j++;P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';r=4;P[k][r++]=G[i][j];}else{P[k][r++]=G[i][j];}}k++;}//获得产生式会集P，k为产生式个数}inteliminate_1(string*G,string*P,stringU,string*GG)//除掉文法G1中所有直接左递归获得文法G2，要能够除掉含有多个左递归的情况）{stringarfa,beta;//所有形如A::=Aα|中β的α、β连接起来形成的字符串arfa、betainti,j,temp,m=0;//计数intflag=0;//flag=1表示文法有左递归intflagg=0;//flagg=1表示某条规则有左递归由于除掉左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=0;i<20&&U[i]!='';i++){flagg=0;arfa=beta="";for(j=0;j<100&&P[j][0]!='';j++){if(P[j][0]==U[i]){if(P[j][4]==U[i])//产生式j有左递归{flagg=1;for(temp=5;P[j][temp]!='';temp++)arfa.append(1,P[j][temp]);if(P[j+1][4]==U[i])arfa.append("|");//不仅一个产生式含有左递归}else{for(temp=4;P[j][temp]!='';temp++)beta.append(1,P[j][temp]);if(P[j+1][0]==U[i]&&P[j+1][4]!=U[i])beta.append("|");}}}if(flagg==0)//对于不含左递归的文法规则不重写{GG[m]=G[i];m++;}else{flag=1;//文法存在左递归GG[m].append(1,U[i]);GG[m].append("::=");if(beta.find('|')!=string::npos)GG[m].append("("+beta+")");elseGG[m].append(beta);while(U.find(C)!=string::npos){C++;}GG[m].append(1,C);m++;GG[m].append(1,C);GG[m].append("::=");if(arfa.find('|')!=string::npos)GG[m].append("("+arfa+")");elseGG[m].append(arfa);GG[m].append(1,C);GG[m].append("|^");m++;C++;}//A::=Aα改|β写成A::=βA‘，A’=αA'|β，}returnflag;}int*ifempty(string*P,stringU,intk,intn){int*empty=newint[n];//指示非终结符可否推导到空串inti,j,r;for(r=0;r<n;r++)empty[r]=0;//默认所有非终结符都不能够推导到空intflag=1;//1表示empty数组有更正intstep=100;//假设一条规则最大推导步数为100步while(step--){for(i=0;i<k;i++){r=U.find(P[i][0]);if(P[i][4]=='^')empty[r]=1;//直接推导到空else{for(j=4;P[i][j]!='';j++){if(U.find(P[i][j])!=string::npos){if(empty[U.find(P[i][j])]==0)break;}elsebreak;}if(P[i][j]=='')empty[r]=1;//多步推导到空elseflag=0;}}}returnempty;}string*FIRST_X(string*P,stringU,stringu,int*empty,intk,intn){inti,j,r,s,tmp;string*first=newstring[n];chara;intstep=100;//最大推导步数while(step--){cout<<"step"<<100-step<<endl;for(i=0;i<k;i++){//cout<<P[i]<<endl;r=U.find(P[i][0]);if(P[i][4]=='^'&&first[r].find('^')==string::npos)

first[r].append(1,'^');//

规则右部首符号为空else{for(j=4;P[i][j]!='';j++){a=P[i][j];if(u.find(a)!=string::npos&&first[r].find(a)==string::npos)//规则右部首符号是终结符{first[r].append(1,a);break;//增加并结束}if(U.find(P[i][j])!=string::npos)//

规则右部首符号是非终结符

,形如

X：：=Y1Y2...Yk{s=U.find(P[i][j]);//cout<<P[i][j]<<":\n";for(tmp=0;first[s][tmp]!='\0';tmp++){a=first[s][tmp];if(a!='^'&&first[r].find(a)==string::npos)//将FIRST[Y1]中的非空符加入first[r].append(1,a);}}if(!empty[s])break;//若Y1不能够推导到空，结束}if(P[i][j]=='')if(first[r].find('^')==string::npos)first[r].append(1,'^');//若Y1、Y2...Yk都能推导到空，则加入空符号}}}returnfirst;}stringFIRST(stringU,stringu,string*first,strings)//

求符号串

s=X1X2...Xn

的FIRST

集{inti,j,r;chara;stringfir;for(i=0;i<s.length();i++){if(s[i]=='^')fir.append(1,'^');

是终结符，添加并结束循环if(U.find(s[i])!=string::npos)//X1{

是非终结符r=U.find(s[i]);for(j=0;first[r][j]!='\0';j++){a=first[r][j];if(a!='^'&&fir.find(a)==string::npos)//

将FIRST(X1)中的非空符号加入fir.append(1,a);}if(first[r].find('^')==string::npos)break;//

若

X1

不能推导到空，循环停止}if(i==s.length())//若X1-Xk都可推导到空if(fir.find(s[i])==string::npos)//fir中还未加入空符号fir.append(1,'^');}returnfir;}stringcreate_table(string*P,stringU,stringu,intn,intt,intk,string*first)//结构分析表，P为文法G的产生式构成的会集{inti,j,p,q;stringarfa;//记录规则右部stringfir,follow;stringFOLLOW[5]={")#",")#","+)#","+)#","+*)#"};stringtable=newstring*[n];for(i=0;i<n;i++)table[i]=newstring[t+1];for(i=0;i<n;i++)for(j=0;j<t+1;j++)table[i][j]="

";//table

储藏分析表的元素，“

”表示

errorfor(i=0;i<k;i++){arfa=P[i];arfa.erase(0,4);//删除前4个字符，如：E::=E+T,则arfa="E+T"fir=FIRST(U,u,first,arfa);for(j=0;j<t;j++){p=U.find(P[i][0]);if(fir.find(u[j])!=string::npos){q=j;table[p][q]=P[i];}//对first（）中的每一终结符置相应的规则}if(fir.find('^')!=string::npos){follow=FOLLOW[p];//对规则左部求follow()for(j=0;j<t;j++){if((q=follow.find(u[j]))!=string::npos){q=j;table[p][q]=P[i];}//对follow（）中的每一终结符置相应的规则}table[p][t]=P[i];//对#所在元素置相应规则}}returntable;}voidanalyse(stringtable,stringU,stringu,intt,strings)//分析符号串s{stringstack;//分析栈stringss=s;//记录原符号串charx;//栈顶符号chara;//下一个要输入的字符intflag=0;//般配成功标志inti=0,j=0,step=1;//符号栈计数、输入串计数、步骤数intp,q,r;stringtemp;for(i=0;!s[i];i++){if(u.find(s[i])==string::npos)//出现非法的符号cout<<s<<"不是该文法的句子\n";return;}s.append(1,'#');stack.append(1,'#');//’#’进入分析栈stack.append(1,U[0]);i++;//文法开始符进入分析栈a=s[0];//cout<<stack<<endl;cout<<"步骤分析栈余留输入串所用产生式\n";while(!flag){//cout<<"

步骤

分析栈

余留输入串

所用产生式

\n"x=stack[i];stack.erase(i,1);i--;//取栈顶符号x,并从栈顶退出//cout<<x<<endl;if(u.find(x)!=string::npos)//x是终结符的情况{if(x==a){s.erase(0,1);a=s[0];//栈顶符号与当前输入符号般配，则输入下一个符号cout<<"\n";//未使用产生式，输出空}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}if(x=='#'){if(a=='#')

{flag=1;cout<<"

成功\n";}//

栈顶和余留输入串都为

#，般配成功else{cout<<"error\n";cout<<ss<<"

不是该文法的句子

\n";break;}}if(U.find(x)!=string::npos)//x是非终结符的情况{p=U.find(x);q=u.find(a);if(a=='#')q=t;temp=table[p][q];cout<<temp<<endl;//输出使用的产生式if(temp[0]!='')//分析表中对应项不为error{r=9;while(temp[r]=='')r--;while(r>3){if(temp[r]!='^'){stack.append(1,temp[r]);//将X::=x1x2...的规则右部各符号压栈i++;}r--;}}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}step++;}if(flag)cout<<endl<<ss<<"是该文法的句子\n";}intmain(){inti,j;string*G=newstring[50];//文法Gstring*P=newstring[50];//产生式会集PstringU,u;//文法G非终结符会集U，终结符会集uintn,t,k;//非终结符、终结符个数,产生式数string*GG=newstring[50];//除掉左递归后的文法GGstring*PP=newstring[50];//文法GG的产生式会集PPstringUU,uu;//文法GG非终结符会集U，终结符会集uintnn,tt,kk;//除掉左递归后的非终结符、终结符个数,产生式数stringtable;//分析表cout<<"欢迎使用LL(1)语法分析器

!\n\n\n";cout<<"请输入文法（同一左部的规则在同一行输入，比方：

E::=E+T|T

；用^表示空串）

\n";input_grammer(G);preprocess(G,P,U,u,n,t,k);cout<<"\n该文法有"<<n<<"个非终结符：\n";for(i=0;i<n;i++)cout<<U[i];cout<<endl;cout<<"该文法有"<<t<<"个终结符：\n";for(i=0;i<t;i++)cout<<u[i];cout<<"\n\n

左递归检测与除掉

\n\n";{preprocess(GG,PP,UU,uu,nn,tt,kk);cout<<"该文法存在左递归！\n\n除掉左递归后的文法:\n\n";for(i=0;i<nn;i++)cout<<GG[i]<<endl;cout<<endl;cout<<"新文法有"<<nn<<"个非终结符：\n";for(i=0;i<nn;i++)cout<<UU[i];cout<<endl;cout<<"新文法有"<<tt<<"个终结符：\n";for(i=0;i<tt;i++)cout<<uu[i];cout<<endl;//cout<<"新文法有"<<kk<<"个产生式：\n";//for(i=0;i<kk;i++)cout<<PP[i]<<endl;}else{cout<<"该文法不存在左递归\n";GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k;}cout<<"求解FIRST集\n\n";int*empty=ifempty(PP,UU,kk,nn);string*first=FIRST_X(PP,U