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

编译原理实验报告 姓名：叶玉虎 班级：计122班 指导老师：王森玉 实验日期：2015/5/11实验内容：1.求出每个非终结符的FIRST集合2.求出每个产生式右部的FIRST集合3.求出每个非终结符的Follow集合实验环境： Visual Studio2010实验目的: 让同学们掌握FIRST集合和FOLLOW集合的求法实验代码：#include#include#define MAX 50char cssMAXMAX;/保存所有的产生式int count=0;int cnt=0;struct L/保存所有的终结符char ch;int flag;/1:能推出,0:不能,初值:-1int num;char firstMAX;int s;/first的长度char followMAX;int l;/follow的长度lMAX;/对输入的格式进行控制,并校验输入是否符合格式int handle(char a)int len,i=0,j,k;len=strlen(a);while(ai!=10)if(ai=$)return 2;if( =ai)|(9=ai)i+;continue;if(ai=A)&(ai)printf(产生式格式错误n);return -1;elsej=i;k=0;while(aj!= )&(aj!=9)&(aj!=$)&(aj!=10)if(aj=|)csscountk=0;count+;if(aj+1= )|(aj=9)|(aj=$)|(aj=10)printf(产生式格式错误n);return 0;csscount0=ai;csscount1=ai+1;csscount2=ai+2;k=3;j+;continue;csscountk=aj;k+;j+;csscountk=0;i=j;count+;elseprintf(产生式格式错误n);return -1;return 0;/从键盘获得输入int input()char aMAX*MAX;int v;printf(输入产生式,产生式之间以空格回车或Tab键分隔,并以$键结束.n);printf(用表示虚拟符号,终结符用大写字母表示,其他字符表示非终结符n);while(1)fgets(a,MAX*MAX,stdin);v=handle(a);if(v=-1)return -1;if(v=2)return 0;/求出能推出的非终结符void seekEmpty()int i,j,k,t;int flag=0,flag2=0;int len,c;char aMAXMAX,ch;for(i=0;icount;i+)strcpy(ai,cssi);/求出含有的非终结符的个数,并把各终结符保存起来for(i=0;icount;i+)for(j=0;jcnt;j+)if(lj.ch=ai0)lj.num+;flag=1;break;elseflag=0;if(!cnt)|(!flag)lcnt.ch=ai0;lcnt.flag=-1;lcnt.num=1;lcnt.s=0;lcnt.l=0;cnt+;flag=1;continue;c=count;while(c)for(i=0;ic;i+)/如果该终结符推出，从a中删除所有带有该终结符的产生式if(ai3=)ch=ai0;for(j=0;jc;j+)if(ch=aj0)if(j!=c-1)for(k=j;kc-1;k+)strcpy(ak,ak+1);c-;j-;elsec-;j-;for(j=0;jcnt;j+)if(ch=lj.ch)lj.flag=1;break;i-;continue;len=strlen(ai);for(j=3;jlen;j+)/当该产生式右边含有非终结符时从a中删除该条记录if(aijZ)flag2=1;break;if(flag2)for(k=0;kcnt;k+)if(ai0=lk.ch)lk.num-;if(lk.num=0)lk.flag=0;break;if(i!=c-1)for(k=i;kc-1;k+)strcpy(ak,ak+1);c-;i-;flag2=0;continue;/如果产生式右边为非终结符看看该终结符能不能推出for(j=3;j=A)&(aij=Z)for(k=0;kcnt;k+)if(aij=lk.ch)if(lk.flag=0)flag2=1;break;else if(lk.flag=1)for(t=j;tlen-1;t+)ait=ait+1;ailen-1=0;j-;len-;break;break;if(flag2)break;if(ai3=0)ch=ai0;for(j=0;jc;j+)if(ch=aj0)if(j!=c-1)for(k=j;kc-1;k+)strcpy(ak,ak+1);c-;j-;elsec-;j-;i-;for(k=0;kcnt;k+)if(ch=lk.ch)lk.flag=1;break;if(flag2)for(k=0;kcnt;k+)if(ai0=lk.ch)lk.num-;if(lk.num=0)lk.flag=0;if(i!=c-1)for(k=i;kc-1;k+)strcpy(ak,ak+1);c-;i-;flag2=0;continue;/求每个非终结符的First集合void seekFirstVn()int i,j,k,t,t1,t2,c,item;int len,s,flag=0,flag2=0,fchange;char aMAXMAX,chMAX;for(i=0;icount;i+)strcpy(ai,cssi);c=count;while(1)fchange=0;for(i=0;ic;i+)/右部为,将并入到左部的First中if(ai3=)/*for(j=0;jcnt;j+)if(lj.ch=ai0)for(k=0;klj.s;k+)if(lj.firstk=ai3)flag=1;break;if(!flag)lj.firstlj.s=ai3;lj.s+;lj.firstlj.s=0;fchange=1;break;flag=0;*/从当前列表a中删除if(i!=c-1)for(j=i;jc-1;j+)strcpy(aj,aj+1);c-;i-;continue;len=strlen(ai);/产生式右边符号为终结符时,将该终结符并入到左部的First集合中for(j=3;jlen;j+)if(aijZ)for(k=0;kcnt;k+)if(ai0=lk.ch)for(t=0;tlk.s;t+)if(aij=lk.firstt)flag=1;break;if(!flag)lk.firstlk.s=aij;lk.s+;lk.firstlk.s=0;fchange=1;flag=0;break;/从a中删除该条产生式if(i!=c-1)for(k=i;k=A)&(aij=Z)/*将该非终结符的FIRST集合除去并入到当前非终结符的FIRST集合中*/for(k=0;kcnt;k+)if(aij=lk.ch)for(t=0;tcnt;t+)if(ai0=lt.ch)for(t1=0;t1lk.s;t1+)for(t2=0;t2lt.s;t2+)if(lk.firstt1=lt.firstt2)break;if(t2=lt.s)&(lk.firstt1)!=)fchange=1;lt.firstlt.s=lk.firstt1;lt.s+;lt.firstlt.s=0;break;break;if(lk.flag)continue;elsebreak;if(!fchange)for(i=0;icnt;i+)if(li.flag)li.firstli.s=;li.s+;li.firstli.s=0;printf(FIRST(%c): %sn,li.ch,li.first);printf(n);break;/求产生式右部的First集合void seekFirstRight()struct Rightchar aMAX;char firstMAX;int s; rMAX;int i,j,k,t;int cnt=0,len,len1,flag=0;for(i=0;icount;i+)for(j=0;jcnt;j+)if(!strcmp(cssi+3,rj.a)flag=1;break;if(flag)flag=0;continue;strcpy(rj.a,cssi+3);rj.s=0;cnt+;for(i=0;icnt;i+)len=strlen(ri.a);for(j=0;jlen;j+)/遇到终结符if(ri.aj=)ri.firstri.s=;ri.s+;ri.firstri.s=0;break;else if(ri.ajZ)ri.firstri.s=ri.aj;ri.s+;ri.firstri.s=0;break;elsefor(k=0;kcnt;k+)if(ri.aj=lk.ch)len1=strlen(lk.first);for(t=0;tlen1;t+)if(lk.firstt!=)ri.firstri.s=lk.firstt;ri.s+;ri.firstri.s=0;break;if(lk.flag)if(j=len-1)ri.firstri.s=;ri.s+;ri.firstri.s=0;continue;elsebreak;for(i=0;icnt;i+)printf(FIRST(%s): %sn,ri.a,ri.first);printf(n);/求每个非终极符的Follow集合void seekFollow()int i,j,k,t,t1,t2,t3,c=0;int flag=0,len;int fchange;/判断一次循环是否有改动的地方char aMAXMAX,chMAX;for(i=0;icount;i+)len=strlen(cssi);for(j=3;j=A)&(cssij=Z)break;if(j!=len)strcpy(ac,cssi);c+;l0.followl0.l=#;l0.l+;l0.followl0.l=0;while(1)fchange=0;for(i=0;ic;i+)len=strlen(ai);for(j=3;j=A)&(aij=A)&(aij-1=Z)for(k=0;kcnt;k+)if(aij-1=lk.ch)for(t=0;tcnt;t+)if(aij=lt.ch)for(t1=0;t1lt.s;t1+)if(lt.firstt1=)continue;for(t2=0;t2=A)&(cht3=Z)for(k=0;kcnt;k+)if(ch0=lk.ch)for(t=0;tcnt;t+)if(cht3=lt.ch)for(t1=0;t1lk.l;t1+)for(t2=0;t2=A)&(aij-1=Z)for(k=0;kcnt;k+)if(aij-1=lk.ch)for(t=0;tlk.l;t+)if(aij=lk.followt)break;if(t=lk.l)fchange=1;lk.followlk.l=aij;lk.l+;lk.followlk.l=0;if(!fchange)for(i=0;iMH|aH-LSo|K-dML|L-eHfM-K|bLM测试数据2：S-aHH-aMd|dM-Ab|A-aM|e实验感想：经过这几次的实验，不仅让我们更加深刻的知道了first集合和follow集合的计算步骤和方法，还很好的培养了我们动手能力。虽然这两个集合用笔算的方法很简单，但是要让计算机来演算就不是那么容易了，这需要设计合理的数据结构和算法才能正确地求出结果。当然在设计算法的时候难免会出现错误，这就需要我们这些程序员们仔细的去调试，发现错误并改正。本以为这次的实验代码不会很长，但是实际写好了却有好几百行，可能是我的算法不够好吧。总的来讲这次的实验没有遇到太大的问题，因为课上老师很认真的给我们讲解了它们的求法，笔推也做了好几次练习，让我们理清了思路。