编译原理实验报告《LL(1)语法分析器构造》(推荐文档)

1、ll（1）分析器的构造实验报告一、实验名称ll(1)分析器的构造二、实验目的设计、编制、调试一个ll(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。三、实验内容和要求设计并实现一个ll(1)语法分析器，实现对算术文法:ge:e-e+t|tt-t*f|ff-(e)|i所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+*i+不是文法所定义的句子。实验要求:1、检测左递归，如果有则进行消除；2、求解first集和follow集；3、构建ll(1)分析表；4、构建ll分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。四

2、、主要仪器设备硬件：微型计算机。软件：codeblocks（也可以是其它集成开发环境）。五、实验过程描述1、程序主要框架程序中编写了以下函数，各个函数实现的作用如下：voidinput_grammer(string*g);/输入文法gvoidpreprocess(string*g,string*p,string&u,string&u,int&n,int&t,int&k);1/将文法g预处理得到产生式集合p，非终结符、终结符集合u、u，inteliminate_1(string*g,string*p,stringu,string*gg);/消除文法g中所有直接左递归得到文法ggint*ifemp

3、ty(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集string*create_table(string*p,stringu,stringu,intn,intt,intk,string*first)；/构造分析表voidanalyse(string*table,str

4、ingu,stringu,intt,strings)；/分析符号串s2、编写的源程序#include#include#includeusingnamespacestd;voidinput_grammer(string*g)/输入文法g,n个非终结符inti=0;/计数charch=y;while(ch=y)cingi+;coutch;voidpreprocess(string*g,string*p,string&u,string&u,int&n,int&t,int&k)/将文法g预处理产生式集合p，非终结符、终结符集合u、u，inti,j,r,temp;/计数charc;/记录规则中（）后的符

5、号intflag;/检测到（）n=t=k=0;for(i=0;i50;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;in;i+)for(j=4;jgi.length();j+)if(u.find(gij)=string:npos&u.find(gij)=string:npos)if(gij!=|&gij!=)/if(gij!=(&gij!=)&gij

6、!=|&gij!=)ut+=gij;2/终结符集合，t为终结符个数for(i=0;in;i+)flag=0;r=4;for(j=4;jgi.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;elsepkr+=gij;k+;/

7、获得产生式集合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开始增加，只要不在原来问法的非终结符中即可加3入for(i=0;i20&ui!=;i+)flag

8、g=0;arfa=beta=;for(j=0;j100&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(|);/不止一个产生式含有左递归elsefor(temp=4;pjtemp!=;temp+)beta.append(1,pjtemp);if(pj+10=ui&pj+14!=ui)beta.append(|);if(flagg=0)/对于不含左递归的文法规则不重写ggm=gi;m+;elseflag=1;/

9、文法存在左递归ggm.append(1,ui);ggm.append(:=);if(beta.find(|)!=string:npos)ggm.append(+beta+);elseggm.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+);elseggm.append(arfa);ggm.append(1,c);ggm.append(|);m+;c+;/a:=a

10、|改写成a:=a，a=a|，returnflag;int*ifempty(string*p,stringu,intk,intn)4int*empty=newintn;/指示非终结符能否推导到空串inti,j,r;for(r=0;rn;r+)emptyr=0;/默认所有非终结符都不能推导到空intflag=1;/1表示empty数组有修改intstep=100;/假设一条规则最大推导步数为100步while(step-)for(i=0;ik;i+)r=u.find(pi0);if(pi4=)emptyr=1;/直接推导到空elsefor(j=4;pij!=;j+)if(u.find(pij)!=

11、string:npos)if(emptyu.find(pij)=0)break;elsebreak;if(pij=)emptyr=1;/多步推导到空elseflag=0;returnempty;string*first_x(string*p,stringu,stringu,int*empty,intk,intn)inti,j,r,s,tmp;string*first=newstringn;chara;intstep=100;/最大推导步数while(step-)/coutstep100-stependl;for(i=0;ik;i+)/coutpiendl;r=u.find(pi0);5if(p

12、i4=&firstr.find()=string:npos)firstr.append(1,);/规则右部首符号为空elsefor(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.yks=u.find(pij);/coutpij:n;for(tmp=0;firststmp!=0;tmp+)a=firststmp;

13、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都能推导到空，则加入空符号returnfirst;stringfirst(stringu,stringu,string*first,strings)/求符号串s=x1x2.xn的first集inti,j,r;chara;stringfir;for(i=0;is.lengt

14、h();i+)if(si=)fir.append(1,);if(u.find(si)!=string:npos&fir.find(si)=string:npos)fir.append(1,si);break;/x1是终结符，添6加并结束循环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

15、;/若x1不可推导到空，循环停止if(i=s.length()/若x1-xk都可推导到空if(fir.find(si)=string:npos)/fir中还未加入空符号fir.append(1,);returnfir;pstring*create_table(string*p,stringu,stringu,intn,intt,intk,string*first)/构造分析表，为文法g的产生式构成的集合inti,j,p,q;stringarfa;/记录规则右部stringfir,follow;stringfollow5=)#,)#,+)#,+)#,+*)#;string*table=newst

16、ring*n;for(i=0;in;i+)tablei=newstringt+1;for(i=0;in;i+)for(j=0;jt+1;j+)tableij=;/table存储分析表的元素，“”表示errorfor(i=0;ik;i+)arfa=pi;arfa.erase(0,4);/删除前4个字符，如：e:=e+t,则arfa=e+tfir=first(u,u,first,arfa);for(j=0;jt;j+)p=u.find(pi0);if(fir.find(uj)!=string:npos)q=j;tablepq=pi;/对first（）中的每一终结符置相应的规则7if(fir.fin

17、d()!=string:npos)follow=followp;/对规则左部求follow()for(j=0;jt;j+)if(q=follow.find(uj)!=string:npos)q=j;tablepq=pi;/对follow（）中的每一终结符置相应的规则tablept=pi;/对#所在元素置相应规则returntable;voidanalyse(string*table,stringu,stringu,intt,strings)/分析符号串sstringstack;/分析栈stringss=s;/记录原符号串charx;/栈顶符号chara;/下一个要输入的字符intflag=0;

18、/匹配成功标志inti=0,j=0,step=1;/符号栈计数、输入串计数、步骤数intp,q,r;stringtemp;for(i=0;!si;i+)if(u.find(si)=string:npos)/出现非法的符号couts不是该文法的句子n;return;s.append(1,#);stack.append(1,#);/#进入分析栈stack.append(1,u0);i+;/文法开始符进入分析栈a=s0;/coutstackendl;cout步骤分析栈余留输入串所用产生式n;while(!flag)/cout步骤分析栈余留输入串所用产生式ncoutstepstacks8;x=stac

19、ki;stack.erase(i,1);i-;/取栈顶符号x,并从栈顶退出/coutxendl;if(u.find(x)!=string:npos)/x是终结符的情况if(x=a)s.erase(0,1);a=s0;/栈顶符号与当前输入符号匹配，则输入下一个符号coutn;/未使用产生式，输出空elsecouterrorn;coutss不是该文法的句子n;break;if(x=#)if(a=#)flag=1;cout成功n;/栈顶和余留输入串都为#，匹配成功elsecouterrorn;coutss不是该文法的句子n;break;if(u.find(x)!=string:npos)/x是非终结

20、符的情况p=u.find(x);q=u.find(a);if(a=#)q=t;temp=tablepq;couttemp3)if(tempr!=)stack.append(1,tempr);/将x:=x1x2.的规则右部各符号压栈i+;9r-;elsecouterrorn;coutss不是该文法的句子n;break;step+;if(flag)coutendlss是该文法的句子n;intmain()inti,j;string*g=newstring50;/文法gstring*p=newstring50;/产生式集合pstringu,u;/文法g非终结符集合u，终结符集合uintn,t,k;/非

21、终结符、终结符个数,产生式数string*gg=newstring50;/消除左递归后的文法ggstring*pp=newstring50;/文法gg的产生式集合ppstringuu,uu;/文法gg非终结符集合u，终结符集合uintnn,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);coutn该文法有n个非终结符：n;for(i=

22、0;in;i+)coutui;coutendl;cout该文法有t个终结符：n;for(i=0;it;i+)coutui;coutnn左递归检测与消除nn;if(eliminate_1(g,p,u,gg)10preprocess(gg,pp,uu,uu,nn,tt,kk);cout该文法存在左递归！nn消除左递归后的文法:nn;for(i=0;inn;i+)coutggiendl;coutendl;cout新文法有nn个非终结符：n;for(i=0;inn;i+)coutuui;coutendl;cout新文法有tt个终结符：n;for(i=0;itt;i+)coutuui;coutendl;/cout新文法有kk个产生式：n;/for(i=0;ikk;i+)coutppiendl;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);