南邮编译原理报告实验二(共25页).doc

精选优质文档-倾情为你奉上实 验 报 告（2015 / 2016 学年 第 二 学期）课程名称编译原理实验名称语法分析器的构造实验时间2016年5月26日指导单位计算机软件教学中心指导教师黄海平学生姓名班级学号学院(系)计算机学院、软件学院专 业计算机科学与技术专心-专注-专业实 验 报 告实验名称语法分析器的构造指导教师黄海平实验类型验证实验学时4实验时间2016.5.26一、 实验目的和要求实验目的：设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。实验要求：1、检测左递归，如果有则进行消除；2、求解FIRST集和FOLLOW集；3、构建LL(1)分析表；4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。以上实验要求可分两个同学完成。例如构建分析表一个同学完成、构建分析程序并分析符号串另一个同学完成。二、实验环境(实验设备) 硬件：计算机 软件：Visual C +6.0二、 实验原理及内容实验内容：设计并实现一个LL(1)语法分析器，实现对算术文法GE:E->E+T|T T->T*F|F F->(E)|i所定义的符号串进行识别，例如符号串abc+age+80为文法所定义的句子，符号串(abc-80(*s5)不是文法所定义的句子。实验代码：#include<cstdio>#include<string>#include<iostream>using namespace std;void input_grammer(string *G)/输入文法G,n个非终结符 int i=0;/计数 char ch='y' while(ch='y') cin>>Gi+; cout<<"继续输入?(y/n)n" cin>>ch; void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)/将文法G预处理产生式集合P，非终结符、终结符集合U、u， int i,j,r,temp;/计数 char C;/记录规则中（）后的符号 int flag;/检测到（） n=t=k=0; for( i=0;i<50;i+) Pi=" "/字符串如果不初始化，在使用Pij=a时将不能改变，可以用Pi.append(1,a) U=u=" "/字符串如果不初始化，无法使用Ui=a赋值，可以用U.append(1,a) for(n=0;!Gn.empty();n+) Un=Gn0; /非终结符集合，n为非终结符个数 for(i=0;i<n;i+) for(j=4;j<Gi.length();j+) if(U.find(Gij)=string:npos&&u.find(Gij)=string:npos) if(Gij!='|'&&Gij!='') /if(Gij!='('&&Gij!=')'&&Gij!='|'&&Gij!='') ut+=Gij; /终结符集合，t为终结符个数 for(i=0;i<n;i+) flag=0;r=4; for(j=4;j<Gi.length();j+) Pk0=Ui;Pk1=':'Pk2=':'Pk3='=' /* if(Gij='(') j+;flag=1; for(temp=j;Gitemp!=')'temp+); C=Gitemp+1; /C记录（）后跟的字符，将C添加到（）中所有字符串后面 if(Gij=')') j+;flag=0; */ if(Gij='|') /if(flag=1) Pkr+=C; k+;j+; Pk0=Ui;Pk1=':'Pk2=':'Pk3='=' r=4; Pkr+=Gij; else Pkr+=Gij; k+; /获得产生式集合P，k为产生式个数int eliminate_1(string *G,string *P,string U,string *GG)/消除文法G1中所有直接左递归得到文法G2，要能够消除含有多个左递归的情况）string arfa,beta;/所有形如A:=A|中的、连接起来形成的字符串arfa、betaint i,j,temp,m=0;/计数int flag=0;/flag=1表示文法有左递归int flagg=0;/flagg=1表示某条规则有左递归char C='A'/由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=0;i<20&&Ui!=' 'i+) flagg=0; arfa=beta="" for(j=0;j<100&&Pj0!=' 'j+) if(Pj0=Ui) if(Pj4=Ui)/产生式j有左递归 flagg=1; for(temp=5;Pjtemp!=' 'temp+) arfa.append(1,Pjtemp); if(Pj+14=Ui) arfa.append("|");/不止一个产生式含有左递归 else for(temp=4;Pjtemp!=' 'temp+) beta.append(1,Pjtemp); if(Pj+10=Ui&&Pj+14!=Ui) beta.append("|"); if(flagg=0)/对于不含左递归的文法规则不重写 GGm=Gi; m+; else flag=1;/文法存在左递归 GGm.append(1,Ui);GGm.append(":="); if(beta.find('|')!=string:npos) GGm.append("("+beta+")"); else GGm.append(beta); while(U.find(C)!=string:npos)C+; GGm.append(1,C); m+; GGm.append(1,C);GGm.append(":="); if(arfa.find('|')!=string:npos) GGm.append("("+arfa+")"); else GGm.append(arfa); GGm.append(1,C);GGm.append("|"); m+; C+; /A:=A|改写成A:=A，A=A'|，return flag;int* ifempty(string* P,string U,int k,int n) int* empty=new int n;/指示非终结符能否推导到空串 int i,j,r; for(r=0;r<n;r+) emptyr=0;/默认所有非终结符都不能推导到空 int flag=1;/1表示empty数组有修改 int step=100;/假设一条规则最大推导步数为步 while(step-) for(i=0;i<k;i+) r=U.find(Pi0); if(Pi4='') emptyr=1;/直接推导到空 else for(j=4;Pij!=' 'j+) if(U.find(Pij)!=string:npos) if(emptyU.find(Pij)=0) break; else break; if(Pij=' ') emptyr=1;/多步推导到空 else flag=0; return empty;string* FIRST_X(string* P,string U,string u,int* empty,int k,int n) int i,j,r,s,tmp; string* first=new stringn; char a; int step=100;/最大推导步数 while(step-) / cout<<"step"<<100-step<<endl; for(i=0;i<k;i+) /cout<<Pi<<endl; r=U.find(Pi0); if(Pi4=''&&firstr.find('')=string:npos) firstr.append(1,'');/规则右部首符号为空 else for(j=4;Pij!=' 'j+) a=Pij; if(u.find(a)!=string:npos&&firstr.find(a)=string:npos)/规则右部首符号是终结符 firstr.append(1,a); break;/添加并结束 if(U.find(Pij)!=string:npos)/规则右部首符号是非终结符,形如X：=Y1Y2.Yk s=U.find(Pij); /cout<<Pij<<":n" for(tmp=0;firststmp!='0'tmp+) a=firststmp; if(a!=''&&firstr.find(a)=string:npos)/将FIRSTY1中的非空符加入 firstr.append(1,a); if(!emptys) break;/若Y1不能推导到空，结束 if(Pij=' ') if(firstr.find('')=string:npos) firstr.append(1,'');/若Y1、Y2.Yk都能推导到空，则加入空符号 return first;string FIRST(string U,string u,string* first,string s)/求符号串s=X1X2.Xn的FIRST集 int i,j,r; char a; string fir; for(i=0;i<s.length();i+) if(si='') fir.append(1,''); if(u.find(si)!=string:npos&&fir.find(si)=string:npos) fir.append(1,si);break;/X1是终结符，添加并结束循环 if(U.find(si)!=string:npos)/X1是非终结符 r=U.find(si); for(j=0;firstrj!='0'j+) a=firstrj; if(a!=''&&fir.find(a)=string:npos)/将FIRST(X1)中的非空符号加入 fir.append(1,a); if(firstr.find('')=string:npos) break;/若X1不可推导到空，循环停止 if(i=s.length()/若X1-Xk都可推导到空 if(fir.find(si)=string:npos) /fir中还未加入空符号 fir.append(1,''); return fir;string* create_table(string *P,string U,string u,int n,int t,int k,string* first)/构造分析表，P为文法G的产生式构成的集合 int i,j,p,q; string arfa;/记录规则右部 string fir,follow; string FOLLOW5=")#",")#","+)#","+)#","+*)#" string *table=new string*n; for(i=0;i<n;i+) tablei=new stringt+1; for(i=0;i<n;i+) for(j=0;j<t+1;j+) tableij=" "/table存储分析表的元素，“ ”表示error for(i=0;i<k;i+) arfa=Pi; arfa.erase(0,4);/删除前个字符，如：E:=E+T,则arfa="E+T" fir=FIRST(U,u,first,arfa); for(j=0;j<t;j+) p=U.find(Pi0); if(fir.find(uj)!=string:npos) q=j; tablepq=Pi; /对first（）中的每一终结符置相应的规则 if(fir.find('')!=string:npos) follow=FOLLOWp;/对规则左部求follow() for(j=0;j<t;j+) if(q=follow.find(uj)!=string:npos) q=j; tablepq=Pi; /对follow（）中的每一终结符置相应的规则 tablept=Pi;/对#所在元素置相应规则 return table; void analyse(string *table,string U,string u,int t,string s)/分析符号串s string stack;/分析栈 string ss=s;/记录原符号串 char x;/栈顶符号 char a;/下一个要输入的字符 int flag=0;/匹配成功标志 int i=0,j=0,step=1;/符号栈计数、输入串计数、步骤数 int p,q,r; string temp; for(i=0;!si;i+) if(u.find(si)=string:npos)/出现非法的符号 cout<<s<<"不是该文法的句子n" return; s.append(1,'#'); stack.append(1,'#');/#进入分析栈 stack.append(1,U0);i+;/文法开始符进入分析栈 a=s0; /cout<<stack<<endl; cout<<"步骤 分析栈 余留输入串 所用产生式n" while(!flag) / cout<<"步骤 分析栈 余留输入串 所用产生式n" cout<<step<<" "<<stack<<" "<<s<<" " x=stacki;stack.erase(i,1);i-;/取栈顶符号x,并从栈顶退出 /cout<<x<<endl; if(u.find(x)!=string:npos)/x是终结符的情况 if(x=a) s.erase(0,1);a=s0;/栈顶符号与当前输入符号匹配，则输入下一个符号 cout<<" n"/未使用产生式，输出空 else cout<<"errorn" cout<<ss<<"不是该文法的句子n" break; if(x='#') if(a='#') flag=1;cout<<"成功n"/栈顶和余留输入串都为#，匹配成功 else cout<<"errorn" cout<<ss<<"不是该文法的句子n" break; if(U.find(x)!=string:npos)/x是非终结符的情况 p=U.find(x); q=u.find(a); if(a='#') q=t; temp=tablepq; cout<<temp<<endl;/输出使用的产生式 if(temp0!=' ')/分析表中对应项不为error r=9; while(tempr=' ') r-; while(r>3) if(tempr!='') stack.append(1,tempr);/将X:=x1x2.的规则右部各符号压栈 i+; r-; else cout<<"errorn" cout<<ss<<"不是该文法的句子n" break; step+; if(flag) cout<<endl<<ss<<"是该文法的句子n" int main() int i,j; string *G=new string50;/文法G string *P=new string50;/产生式集合P string U,u;/文法G非终结符集合U，终结符集合u int n,t,k;/非终结符、终结符个数,产生式数 string *GG=new string50;/消除左递归后的文法GG string *PP=new string50;/文法GG的产生式集合PP string UU,uu;/文法GG非终结符集合U，终结符集合u int nn,tt,kk;/消除左递归后的非终结符、终结符个数,产生式数 string* table;/分析表 cout<<" 欢迎使用LL(1)语法分析器!nnn" 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<<Ui; cout<<endl; cout<<"该文法有"<<t<<"个终结符：n" for(i=0;i<t;i+) cout<<ui; cout<<"nn 左递归检测与消除nn" if(eliminate_1(G,P,U,GG) preprocess(GG,PP,UU,uu,nn,tt,kk); cout<<"该文法存在左递归！nn消除左递归后的文法:nn" for(i=0;i<nn;i+) cout<<GGi<<endl; cout<<endl; cout<<"新文法有"<<nn<<"个非终结符：n" for(i=0;i<nn;i+) cout<<UUi; cout<<endl; cout<<"新文法有"<<tt<<"个终结符：n" for(i=0;i<tt;i+) cout<<uui; cout<<endl; /cout<<"新文法有"<<kk<<"个产生式：n" /for(i=0;i<kk;i+) cout<<PPi<<endl; else cout<<"该文法不存在左递归n" GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k; cout<<" 求解FIRST集nn" int *empty=ifempty(PP,UU,kk,nn); string* first=FIRST_X(PP,UU,uu,empty,kk,nn); string FOLLOW5=")#",")#","+)#","+)#","+*)#" for(i=0;i<nn;i+) cout<<"FIRST("<<UUi<<"): "<<firsti<<endl; cout<<" 求解FOLLOW集nn" for(i=0;i<nn;i+) cout<<"FOLLOW("<<UUi<<"): "<<FOLLOWi<<endl; cout<<"nn 构造文法分析表nn" table=create_table(PP,UU,uu,nn,tt,kk,first); cout<<" " for(i=0;i<tt;i+) cout<<" "<<uui<<" " cout<<"# "<<endl; for( i=0;i<nn;i+) cout<<UUi<<" " for(j=0;j<t+1;j+) cout<<tableij; cout<<endl; cout<<"nn 分析符号串nn" string s; cout<<"请输入要分析的符号串n" cin>>s; analyse(table,UU,uu,tt,s);return 0;实验结果：四、实验小结（包括问题和解决方法、心得体会、意见与建议等）在这次实验中，我又一次复习了，什么是LL（1）语法分析器，如何对符号串进行分析。了解了什么是语法分析，熟悉了语法分析器的构造，更加深入了对语法分析原理的理解。这次上机实验对我帮助学习理论课程很大。五、指导教师评语成 绩批阅人日 期