南邮编译原理报告实验二

1、o实验报告（2015 / 2016 学年第二学期）课程名称编译原理实验名称语法分析器的构造实验时间2016 年 5 月 26 日指导单位 计算机软件教学中心指导教师黄海平-可编辑修改-学生姓名班级学号学院(系)计算机学院、专业 计算机科学与技术软件学院报告实验名称语法分析器的构造指导教师黄海平实验类型验证实验学时4实验时间2016.5.26一、实验目的和要求实验目的：设计、编制、调试 个LL(1)语法分析器，利用语法分析器对符号串的识 别，加深对语法分析原埋的理解。实验要求：1、检测左递归，如果有则进行消除；2、求解FIRST集和FOLLOW 集；3、构建LL(1)分析表；4、构建LL分析程序

2、，对于用户输入的句子，能够利用所构造的分析程 序进行分析，并显示出分析过程。以上实验要求可分两个同学完成。例如构建分析表一个同学完成、构建 分析程序并分析符号串另一个同学完成。、实验环境(实验设备)硬件：计算机软件：Visual C +6.0二、实验原理及内容实验内容：设计并实现一个LL(1)语法分析器，实现对算术文法GE:E->E+T|TT->T*F|FF->(E)|i所定义的符号串进行识别，例如符号串abc+age+80为文法所定义的句子，符号串(abc-80cs5)不是文法所定义的句子。实验代码：#include<cstdio>#include<str

3、ing>#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 &

4、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&

5、lt;Gi.length();j+)(if(U.find(Gij)=string二npos&&u.find(Gij)=string:npos) if(Gij!=T&&Gij!=w)Z/if(Gij!='C&&Gij!=')'&&Gij!='|'&&Gij!='A') ut+=Gij;)终结符集合，t为终结符个数for(i=0;i<n;i+)(flag=0;r=4;for( j=4;j<Gi.length();j+)(Pk0=Ui;Pk1='

6、:'Pk2=':'Pk3='='/* if(Gij='(')j+;flag=1;for(temp=j;Gitemp!=')'temp+);C=Gitemp+1;/C记录（）后跟的字符，将C添加到（）中所有字符串后面if(Gij=')') j+;flag=0;*/if(Gij=T)(/if(flag=1) Pkr+=C;k+;j+;Pk0=Ui；Pk1='：'；Pk2=':'Pk3='='r=4;Pkr+=Gi皿else(Pkr+=Gi皿k+;获得产生式集合P,

7、 k为产生式个数int eliminate_1(string *G,string *P ,string U,string *GG)消除文法G1中所有直接左递归得到文法G2,要能够消除含有多个左递归的情况）string arfa,beta;/所有形如A:=A o| B中的、禺I接起来形成的字符串arfa、beta int i,j,temp,m=0;/ 计数 int flag=0;/flag=1表示文法有左递归int flagg=0;/flagg=1表示某条规则有左递归char C='A'/由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=

8、0;i<20&&Ui!=' 'i+) flagg=0;arfa=beta=""for( j=0;j<100&&P皿0!=' 'j+)if(P j0=Ui) if(Pj4=Ui)产生式j有左递归flagg=1;for(temp=5;P jtemp!=' 'temp+) arfa.append(1,Pjtemp);if(P j+14=Ui) arfa.append(T);不止一个产生式含有左递归elsefor(temp=4;P jtemp!=' 'temp+)beta.a

9、ppend(1,Pjtemp);if(P j+10=Ui&&Pj+14!=Ui) beta.append("|");if(flagg=0)对于不含左递归的文法规则不重写GGm=Gi; m+;elseflag=1;/文法存在左递归GGm.append(1,Ui);GGm.append(":=");if(beta.find('|')!=string二npos) GGm.append("("+beta+")");else GGm.append(beta);while(U.find(C)!=

10、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("|A");m+;C+；/A:=A 吊改写成 A:=叫：A'= oA'| &return flag;int* ifempty(stri

11、ng* 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='N) emptyr=1; else for( j=4;Pij!=' 'j+) if(U.find(Pij)!=strin

12、g:npos) if(emptyU.find(Pij)=0) break; else break; if(P皿='')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"<<10

13、0-step<<endl;for(i=0;i<k;i+)/cout<<Pi<<endl;r=U.find(Pi0);if(Pi4='A'&&firstr.find('A')=string二npos)firstr.append(1,'A');规则右部首符号为空elsefor( j=4;Pij!=''j+)a=P皿;if(u.find(a)!=string:npos&&firstr.find(a)=string:npos)/规贝U右部首符号是终结符firstr.

14、append(1,a);break;/添加并结束if(U.find(Pij)!=string:npos)规则右部首符号是非终结符，形如X: : =Y1Y2Yks=U.find(Pij);cout<<Pij<<":n"for(tmp=0;firststmp!=''0'tmp+)a=firststmp;if(a!='A'&&firstr.find(a)=string:npos)将FIRSTY1中的非空符加入firstr.append(1,a);if(!emptys) break;/若Y1不能推导到空

15、，结束if(Pij='')if(firstr.find('A')=string:npos)firstr.append(1,'A');若Y1、Y2Yk都能推导到空，则加入空符号return first;string FIRST(string U,string u,string* first,string s)/ 求符号串 s=X1X2Xn 的 FIRST集int i,j,r； char a; string fir;for(i=0;i<s.length();i+)if(si='N)fir.append(i,'N)；if(u.fi

16、nd(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!='A'&&fir.find(a)=string:npos)将 FIRST(X1)中的非空符号加入fir.append(1,a);if(firstr.find('A&#

17、39;)=string:npos) break;/若 X1 不可推导到空，循环停止if(i=s.length()/若X1-Xk 都可推导到空if(fir.find(si)=string二npos)/fir 中还未加入空符号fir.append(1,'A');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;s

18、tring 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存储分析表的元素，表不errorfor(i=0;i<k;i+)arfa=Pi;arfa.erase(0,4);/ 删除前个字符，如：E:=E+T,

19、贝Uarfa="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;/ Xtfirst ()中的每一终结符置相应的规则if(fir.find('A')!=string:npos)follow=FOLLOWp;/对规则左部求 follow()for( j=0；j<t；j+) if(q=follow.find(uj)!=string二npos)q=j;tablepq=Pi;/ Xfollow (

20、)中的每一终结符置相应的规则 tablept=Pi;/对#所在元素置相应规则 return table;void analyse(string *table,string U,string u,int t,string s)/分析符号串sstring 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:npo

21、s)出现非法的符号cout<<s<<" 不是该文法的句子n"return;s.append(1,'#');stack.append(1,'#');'# '进入分析栈stack.append(1,U0);i+;文法开始符进入分析栈a=s0;cout<<stack<<endl;cout<<"步骤 分析栈余留输入串所用产生式n"while(用ag)/ cout<<"步骤 分析栈余留输入串所用产生式n"cout<<

22、;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"/未使用产生式，输出空elsecout<<"

23、;errorn"cout<<ss<<" 不是该文法的句子n"break;if(x='#')if(a='#') flag=1;cout<<"成功n" 栈顶和余留输入串都为#,匹配成功elsecout<<"errorn"cout<<ss<<" 不是该文法的句子n"break;if(U.find(x)!=string:npos)/x是非终结符的情况p=U.find(x);q=u.find(a); if(a=&

24、#39;#') q=t; temp=tablepq; cout<<temp<<endl;输出使用的产生式if(temp0!=' ')/ 分析表中对应项不为error r=9;while(tempr=' ') r-;while(r>3) if(tempr!='A') stack.append(1,tempr);将X:=x1x2的规则右部各符号压栈i+；r-；elsecout<<"errorn"cout<<ss<<"不是该文法的句子n"b

25、reak;step+;if(flag) cout<<endl<<ss<<”是该文法的句子 n"int main()int i,j；string *G=new string50;/文法 Gstring *P=new string50;/产生式集合 Pstring U,u;/文法G非终结符集合U,终结符集合uint n,t,k;非终结符、终结符个数，产生式数string *GG=new string50;/消除左递归后的文法 GGstring *PP=new string50;/文法GG 的产生式集合 PPstring UU,uu;/文法GG非终结符集

26、合U,终结符集合uint 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 该文法有"vvnvv" 个非终结符：n"for(i=0;i<n;i+) cout<&l

27、t;Ui;cout<<endl;cout<<"该文法有"vvtvv”个终结符：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);coutvv"该文法存在左递归！ nn消除左递归后的文法：nn"for(i=0;i<nn;i+) cout<<GGi<<endl;cout<<e

28、ndl;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”;/f

29、or(i=0;i<kk;i+) cout<<PPi<<endl;elsecout<<”该文法不存在左递归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=")#",")#","+)#","+)#&

30、quot;,"+*)#"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构

31、造文法分析表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<