南邮编译原理报告实验二

实验报告（2015/2016学年第二学期）课程名称编译原理实验名称语法分析器的构造实验时间2016年5月26日指导单位计算机软件教学中心指导教师黄海平学生姓名班级学号学院(系)计算机学院、软件学院专业计算机科学与技术-2-实验报告实验名称语法分析器的构造指导教师黄海平实验类型验证实验学时4实验时间2016.5.26一、实验目的和要求实验目的：设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。实验要求：1、检测左递归，如果有则进行消除；2、求解FIRST集和FOLLOW集；3、构建LL(1)分析表；4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。以上实验要求可分两个同学完成。例如构建分析表一个同学完成、构建分析程序并分析符号串另一个同学完成。二、实验环境(实验设备)硬件：计算机软件：VisualC++6.0-3-二、实验原理及内容实验内容：设计并实现一个LL(1)语法分析器，实现对算术文法G[E]:E-E+T|TT-T*F|FF-(E)|i所定义的符号串进行识别，例如符号串abc+age+80为文法所定义的句子，符号串(abc-80(*s5)不是文法所定义的句子。实验代码：#includecstdio#includestring#includeiostreamusingnamespacestd;voidinput_grammer(string*G)//输入文法G,n个非终结符{inti=0;//计数charch='y';while(ch=='y'){cinG[i++];cout继续输入?(y/n)\n;cinch;}-4-}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;i50;i++)P[i]=;//字符串如果不初始化，在使用P[i][j]=a时将不能改变，可以用P[i].append(1,a)U=u=;//字符串如果不初始化，无法使用U[i]=a赋值，可以用U.append(1,a)for(n=0;!G[n].empty();n++){U[n]=G[n][0];}//非终结符集合，n为非终结符个数for(i=0;in;i++){for(j=4;jG[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]!='^')-5-u[t++]=G[i][j];}}//终结符集合，t为终结符个数for(i=0;in;i++){flag=0;r=4;for(j=4;jG[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]='=';-6-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表示某条规则有左递归charC='A';//由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=0;i20&&U[i]!='';i++)-7-{flagg=0;arfa=beta=;for(j=0;j100&&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++;}-8-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];//指示非终结符能否推导到空串-9-inti,j,r;for(r=0;rn;r++)empty[r]=0;//默认所有非终结符都不能推导到空intflag=1;//1表示empty数组有修改intstep=100;//假设一条规则最大推导步数为步while(step--){for(i=0;ik;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;-10-}}}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--){//coutstep100-stependl;for(i=0;ik;i++){//coutP[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++)-11-{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]);//coutP[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);}}-12-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;is.length();i++){if(s[i]=='^')fir.append(1,'^');if(u.find(s[i])!=string::npos&&fir.find(s[i])==string::npos){fir.append(1,s[i]);brea-13-k;}//X1是终结符，添加并结束循环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;}string**create_table(string*P,stringU,stringu,intn,intt,intk,string*first)//构造分析表，P为文法G的产生式构成的集合-14-{inti,j,p,q;stringarfa;//记录规则右部stringfir,follow;stringFOLLOW[5]={)#,)#,+)#,+)#,+*)#};string**table=newstring*[n];for(i=0;in;i++)table[i]=newstring[t+1];for(i=0;in;i++)for(j=0;jt+1;j++)table