安徽工业大学编译原理实验报告.docx

编译原理试验报告姓名：叶玉虎班级1计122班指导老师，王森玉试验日期，2015/5/11试验内容：1.求出每个非终结符的FIRST集合2,求出每个产生式右部的FIRST集合3.求出每个非终结符的Fo1.1.ow集合试验环境：Visua1.Studio2010试验目的：让同学们驾驭FIRST集合和FO1.1.oW集合的求法试验代码：ftinc1.ude<stdio.h>«inc1.ude<string.h>JtdefineMAX50CharCSSMAXMAX;保存全部的产生式intcount=0;intcnt=0:struct1.保存全部的终结符charch:intf1.ag"1.:能推出,0:不能,初值:Tintnum：CharfirSIMAX;ints;firsr的长度charfo1.1.owMAX;int】/fo1.1.ow的长度1MX;/对输入的格式进行限制，并校验输入是否符合格式inthandIe(chara)int1.en,i=0,j,k;Ien=Str1.en（八）：whi1.e(ai!-10)if-')return2;if(*,=ai)(9=ai)i+;continue;if(a>='A')&&(a<='Z')if(ai+1.!='')I1.(ai+2!='>')Printf(“产生式格式错误n");return-1;e1.seJ=i:k=0;whi1.e(aj!-')(aj!=9)&&(aj！='S,)&&(aj!=10)i-，)csscountk三,0,;count+;if(aj+1.=,)1.1.(aj=9)(aj='S,)1.(aj=10)Printf("产生式格式错误n");return0;csscountOj=ai;csscount1.=ai+1.;csscount2=ai+2;k=3;j+；continue;csscountk=aj：k+;j+；csscountk=，0'count+;e1.sePrintf("产生式格式错误n");return-1：return0:从键盘获得输入intinput()charaMAX*MAX;intv;Printf("输入产生式,产生式之间以空格回车或Tab键分隔，并以$键结束.n");Printf("用表示虚拟符号£,终结符用大写字母表示,其他字符表示非终结符n"):whi1.e(1.)fgets(a,MAX*MAX,stdin);v=hand1.e（八）:if(v=-1.)return-1：if(v=2)return0;求出能推出E的非终结符voidSeekEmptyOinti,j,k,t;intf1.ag=O,f1.ag2-0;int1.en»c;charaMAXMAX,ch;for(i=0;i<count;i+)strcpy(ai,cssi)：/求出含有的非终结符的个数，并把各终结符保存起来for(i=0;i<count;i+)for(j=0;j<cnt;J+)if(1.j.ch=ai0)1.j.num+：f1.ag=1.;break;e1.sef1.ag=0:if(!cnt)II(!f1.ag)1cnt.ch=ai0;1cnt.f1.ag=-1.;1cnt.num=1.;1cntj.s=0;1cnt.1=0;ent+;f1.ag=1.;continue;c=count;whi1.e(c)for(i=0;i<c：i+)假如该终结符推出*从a中删除全部带有该终结符的产生式if(ai='')ch=ai0;for(j=0d<cj+)if(ch=aj0)if(j!=c-1.)for(k=j;k<c-1.:k+)strcpy(ak,ak+1.);c-;j：e1.sec-:J-；for(j=0;j<cnt;j+)if(ch=1.j.ch)1.jfIag=I;break：continue;Ien=Str1.en(ai);for(j=3:j<1.en;j+)当该产生式右边含有非终结符时从a中删除该条记录if(aij<,A(aij>,Z,)f1.ag2=1.;break：if(f1.ag2)for(k=0：k<cnt;k+)if(ai0=1.k.ch)1k.num-：if(1.k.num=0)1.k.f1.ag=0:break;if(i!=c-1.)for(k=ijk<c-1.：k+)strcpy(ak,ak+1.);f1.ag2-O;continue:假如产生式右边为非终结符看看该终结符能不能推出Efor(j=3:j<1.en;j+)if(aij>,A')&&(aij<=,Z,)for(k=0：k<cnt;k+)if(aij=1.k.ch)if(1.k.f1.ag=O)f1.ag2=1.;break:e1.seif(1k.f1.ag=1.)or(t=j;t<1.en-1.;t+)ait=at+1.;ai1.en-1.=0,;j一；Ien一;break;break:if(f1.ag2)break：if(ai3'0,)ch=ai0：if(ch=ajO)if(j!=c-1.)for(k=j;k<c-1.;k+)strcpy(ak,ak+1.);c一;j；e1.sec-：j-：i；for(k=0：k<cnt;k+)if(ch=1.k.ch)1.k.fIag=I；break;if(f1.ag2)for(k=0;k<cnt：k+)if(aiO=1.k.ch)1.k.num;if(1k.nutn=0)1.k.f1.ag=0;if(i!=c-1.)strcpy(ak,ak+1.);c;i；f1.ag2=0;continue;求每个非终结符的FirSt集合voidSeekFirstVnOinti,j,k,t,t1.,t2,c,item：int1.en,s,f1.ag=0,f1.ag2=0,fchange;charaMAXMAX,chMAX：for(i=0:i<count;i+)strcpy(ai,cssi);c=count：whi1.e(1.)fchange=0:for(i=0:i<c:i+)/右部为J将£并入到左部的FirSt中if(ai3=,)/*for(j=0;j<cnt;j+)if(1.j.ch=ai0)for(k=0：k<1.j.s;k+)if(1j.firstk=ai3)fIag=I：break;if(!f1.ag)1.jfirst1.j.s=ai3:1j.s+：1j.first1.j.s,0,;fchange=1.：break;fIag=O:从当前列表a中删除if(i!=c-1.)for(j=ij<c-1.j+)s1.rcpy(aj,aj+1.):C-;i-；continue;Ien=Str1.en(ai)：产生式右边符号为终结符时,将该终结符并入到左部的FirSt集合中for(j=3d<Ienjj+)if(aij<,A,)1.1.(aijyZ,)for(k=0;k<cnt;k+)if(aiOJ=1kj.ch)for(t=0;t<1.kJ.s;t+)if(aij=1.k.firstt)fIag=I：break：if(!f1.ag)1.k.firs1.1.k.s=aij：1k.s+;1.k.first1.k.s=,O>:fchange-1;f1.ag=0:break：从a口中删除该条产生式if(i!=c1.)for(k=ijk<c-1.;k+)strcpy(ak,ak+1.);c;i；break;产生式右边符号为非终结符时e1.seif(aij>=,)&&(aij<='Z')*将该非终结符的F1.RST集合除去£并入到当前非终结符的F1.RST集合中的for(k=0;k<cnt：k+)if(aij=1.k.ch)for(t=0;t<cnt;t+)i(ai0=1.t.ch)for(t1.=Ot1.<1.k.s;t1.+)for(t2=0:t2<1.t.s;t2+)if(1k1.firstt1.=1.1.firstt2)break;if(t2=1.t.s)&&(1k.firstt1.)!=,)fchange=1.;1t.first1t.s=1.k.firstt1.：1.t.s+;1.t.first1.t.s,0,;break;break;if(1.k.f1.ag)continue;e1.sebreak：if(!fchange)for(i=0：i<cnt;i+)if(1.i.f1.ag)1.i.first1.i.s三,;1.i.s+;1.i.first1i.s=,0,;printf(*FIRST(%c):%sn*,1.i.ch,1i.first):printf(*,n,):break;求产生式右部的FirSI集合voidSeekFirstRightOstructRightcharaMAX：charfirstMAX;ints;rNIAX;inti,jrk.t；intcnt=0,1.en,1.en1.,f1.ag=0;for(i=0:i<count;i+)for(j=0;j<cnt;J+)if(!strcmp(cssi+3,rj.a)f1.ag=1.:break;if(f1.ag)f1.ag=O;continue;strcpy(rjJ.a,cssiJ+3);rj.s=O:ent+;for(i=0;i<cnt:i+)1.en=str1.en(ri.a);for(j=0;j<1.en;J+)遇到终结符if(ri.aj=>,)ri.firstri.s,©':ri.s+;ri.firstri.s=t0,：break;e1.seif(ri.aj<,A,)11(ri.aj>,Z,)ri.firstri.s=ri.aj：ri.s+;ri.firstri.s三*0,;break;e1.sefor(k=0;k<cnt;k+)if(ri.aj=1.k.ch)1.en1.=str1.en(1.k.first);for(t=0;t<1.en1.;t+)if(1.k.firstt!=')ri.firstri.s=1.k.firstt;ri.s+:ri.firs1.ri.s='0'break：if(1.k.f1.ag)if(j=1.en-1.)ri.firstri.s='ri.s+;ri.firstri.s=，0>:continue;e1.sebreak;for(i=0;i<cnt:i+)printf(*FIRST(%s):%sn*,ri.a,ri.first);prin1.f(r);求每个非终极符的Fo1.1.OW集合voidSeekFo1.1.ow()inti,jrk,t,t1.,t2,t3,c=0:intf1.ag=O,Ien;intfchange;推断次循环是否有改动的地方charaMAXMAX,chMAX：for(i=0:i<count;i+)1.en=str1.en(cssi);for(j=3;j<1.en;j+)if(cssij>-')&&(cssij<=,Z')break;if(j!=1.en)strcpy(ac,cssi);c+：1.0.fo1.1.ow1.0.1,;1.0.1+：1.0.fo1.1.ow1.0.1=0'：whi1.e(1.)fchange=O;for(i=0;i<c：i+)Ien=Str1.en(aiJ);for(j=3:j<1.en;j+)if(aij>三,A,)(aij<=*Z,)推断该非终结符的前一位是否为非终结符,是的话，将其FirSt集合去后并到其前位非终结符的FO1.1.oW集合中if(aij-1.>三,A,)&&(aij-1.j<='T)for(k=0：k<cnt：k*+)if(aij-1.=1.k.ch)for(t=0;t<cnt:t+)if(aij=1.t.ch)for(1.1.=Ot1.<1.t.s;t1.+)continue;for(t2=0t2<1.k.I;t2+)if(1t.firstt1.=1.k.fo1.1.owt2)break：if(t2=1.k.1)fchange=1;1.k.fo1.1.ow1.k.1.=1.t.firstt1.;1.k.1.+;1.k.fo1.1.ow1.k.1.=,0,;break;break:假如该非终结符是最终一位，将该产生式左部非终结符的Fo1.1。W集合加入到当前非终结符的FouOW集合中.然后从当前终结符起先向右推断是否为非终结符，是的话,进行相应处理循环直到当前非终结符推不出£或当前为终结符时退出if(J=Ien-I)3=j;strcpy(ch,ai);whiIe(!f1.ag)if(cht3>=A,)U(cht3<=T)for(k=0;k<cn1.：k+)if(ch0=1.k.Ch)for(1.=0;Kcn1.it+)if(cht3三=1.t.ch)for(t1.=Ot1.<1.k.1.;t1.+)for(t2=0t2<1.t.I;t2+)if(1k1.fo1.1.owt1.=1.t.fo1.1.owt2)break;if(t2!=1.t.1)continue;e1.sefchange=1.;1t.fo1.1.ow1.t.1.=1.k.fo1.1.owt1.;1.t.1+;1.t.fo1.1.ow1.t.1.=0,;if(1.t.f1.ag)cht3-=0,;e1.sef1.ag=1.:t3：break;break;e1.sebreak;f1.ag=0:假如当前位为终结符，推断其前一位是否为非终结符是的话,将该终结符并到该非终结符的Foi1.。W集合中e1.seif(aij-1.>三,A,)M(aij-1.<=Z,)for(k=0;k<cnt:k+)if(aij-1.=1.k.ch)for(t=Ot<1.k.1.;t+)if(aij=1.k.fo1.1.owt)break;if(t=1.k.1.)fchange=1.;1.k.fo1.1.ow1.k.1.=aij;1.k.1.+;1.k.fo1.1.ow1.k.1.三,0,;if(!fchange)for(i=0：i<cnt;i+)printf(*FO1.1.OW(%c):%sn*,1.i.ch,1i.fo1.1.ow);break;intmain()inti;if(input()=-1)return_1;SeekEmptyO;SeekFirstVnO：SeekFirstRight()：seek'o1.1.ow();returnO;试验演示：因为不知道怎么用电脑输出'£'符号，我在代码里用'来表示'E'.以'$'来结束输入测试数据1：S->MIIaH->1.So<9K->dM1.01.->eHfM->Kb1.M测试数据2；S->a1.1.H->aMddM->Ab0A->aMe试验感想：经过这几次的试验，不仅让我们更加深刻的知道了first集合和fo1.1.ow集合的计算步骤和方法，还很好的培育/我们动手实力。虽然这两个集合用笔算的方法很简洁，但是要让计算机来演算就不是那么简洁了，这须要设计合理的数据结构和算法才能正确地求出结果。当然在设巾算法的时候难免会出现错误，这就须要我们这些程序员们细致的去调试，发觉错误并改正。本以为这次的试验代码不会很长，但是实际写好r却有好几百行，可能是我的算法不够好吧。总的来讲这次的试验没有遇到太大的问题，因为课上老师很细致的给我们讲解了它们的求法，笔推也做了好几次练习，让我们理清了思路。