安工大王森玉编译原理实验报告

编译原理实验报告老师：王森玉姓名：学号：班级：实验内容：输入一个文法1.求出每个非终结符的FIRST集合2.求出每个产生式右部的FIRST集合3.求出每个非终结符的Follow集合实验环境：VisualC++6.0实验目的:让同学们通过编写代码求出FIRST集合和FOLLOW集合，加深对这两种集合求法的理解。实验内容一：测试文法：S-S;D|DD-(T)|HH-a|(S)T-T+S|S源码：#includestdio.h#includestring.h#defineMAX50charcss[MAX][MAX];//保存所有的产生式intcount=0;intcnt=0;structL{//保存所有的终结符charch;intflag;//1:能推出ε,0:不能,初值:-1intnum;charfirst[MAX];ints;charfollow[MAX];intl;}l[MAX];//对输入的格式进行控制,并校验输入是否符合格式inthandle(chara[]){intlen,i=0,j,k;len=strlen(a);while(a[i]!=10){if(a[i]=='~')return2;if((''==a[i])||(9==a[i])){i++;continue;}if((a[i]='A')&&(a[i]='Z')){if((a[i+1]!='-')||(a[i+2]!='')){printf(产生式格式错误\n);return-1;}else{j=i;k=0;while((a[j]!='')&&(a[j]!=9)&&(a[j]!='~')&&(a[j]!=10)){if(a[j]=='|'){css[count][k]='\0';count++;if((a[j+1]=='')||(a[j]==9)||(a[j]=='~')||(a[j]==10)){printf(产生式格式错误\n);return0;}css[count][0]=a[i];css[count][1]=a[i+1];css[count][2]=a[i+2];k=3;j++;continue;}css[count][k]=a[j];k++;j++;}css[count][k]='\0';i=j;count++;}}else{printf(产生式格式错误\n);return-1;}}return0;}//从键盘获得输入intinput(){chara[MAX*MAX];intv;printf(输入产生式,产生式之间以空格回车或Tab键分隔,并以~键结束.\n);printf(用#表示空符号ε,非终结符用大写字母表示,其他字符表示终结符\n);while(1){fgets(a,MAX*MAX,stdin);v=handle(a);if(v==-1)return-1;if(v==2)return0;}}//求出能推出ε的非终结符voidseekEmpty(){inti,j,k,t;intflag=0,flag2=0;intlen,c;chara[MAX][MAX],ch;for(i=0;icount;i++){strcpy(a[i],css[i]);}//求出含有的非终结符的个数,并把各终结符保存起来for(i=0;icount;i++){for(j=0;jcnt;j++){if(l[j].ch==a[i][0]){l[j].num++;flag=1;break;}elseflag=0;}if((!cnt)||(!flag)){l[cnt].ch=a[i][0];l[cnt].flag=-1;l[cnt].num=1;l[cnt].s=0;l[cnt].l=0;cnt++;flag=1;continue;}}c=count;while(c){for(i=0;ic;i++){//如果该终结符推出ε，从a[]中删除所有带有该终结符的产生式if(a[i][3]=='#'){ch=a[i][0];for(j=0;jc;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;kc-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}for(j=0;jcnt;j++){if(ch==l[j].ch){l[j].flag=1;break;}}i--;continue;}len=strlen(a[i]);for(j=3;jlen;j++){//当该产生式右边含有非终结符时从a[]中删除该条记录if((a[i][j]'A')||(a[i][j]'Z')){flag2=1;break;}}if(flag2){for(k=0;kcnt;k++){if(a[i][0]==l[k].ch){l[k].num--;if(l[k].num==0)l[k].flag=0;break;}}if(i!=c-1)for(k=i;kc-1;k++){strcpy(a[k],a[k+1]);}c--;i--;flag2=0;continue;}//如果产生式右边为非终结符看看该终结符能不能推出εfor(j=3;jlen;j++){if((a[i][j]='A')&&(a[i][j]='Z')){for(k=0;kcnt;k++){if(a[i][j]==l[k].ch){if(l[k].flag==0){flag2=1;break;}elseif(l[k].flag==1){for(t=j;tlen-1;t++)a[i][t]=a[i][t+1];a[i][len-1]='\0';j--;len--;break;}break;}}if(flag2)break;}}if(a[i][3]=='\0'){ch=a[i][0];for(j=0;jc;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;kc-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}i--;for(k=0;kcnt;k++){if(ch==l[k].ch){l[k].flag=1;break;}}}if(flag2){for(k=0;kcnt;k++){if(a[i][0]==l[k].ch){l[k].num--;if(l[k].num==0)l[k].flag=0;}}if(i!=c-1)for(k=i;kc-1;k++){strcpy(a[k],a[k+1]);}c--;i--;flag2=0;continue;}}}}//求每个非终结符的First集合voidseekFirstVn(){inti,j,k,t,t1,t2,c,item;intlen,s,flag=0,flag2=0,fchange;chara[MAX][MAX],ch[MAX];for(i=0;icount;i++){strcpy(a[i],css[i]);}c=count;while(1){fchange=0;for(i=0;ic;i++){//右部为ε,将ε并入到左部的First中if(a[i][3]=='#'){//从当前列表a[]中删除if(i!=c-1)for(j=i;jc-1;j++)strcpy(a[j],a[j+1]);c--;i--;continue;}len=strlen(a[i]);//产生式右边符号为终结符时,将该终结符并入到左部的First集合中for(j=3;jlen;j++){if((a[i][j]'A')||(a[i][j]'Z')){for(k=0;kcnt;k++){if(a[i][0]==l[k].ch){for(t=0;tl[k].s;t++){if(a[i][j]==l[k].first[t]){flag=1;break;}}if(!flag){l[k].first[l[k].s]=a[i][j];l[k].s++;l[k].first[l[k].s]='\0';fchange=1;}flag=0;break;}}//从a[][]中删除该条产生式if(i!=c-1)for(k=i;kc-1;k++)strcpy(a[k],a[k+1]);c--;i--;break;}//产生式右边符号为非终结符时elseif((a[i][j]='A')&&(a[i][j]='Z')){/*将该非终结符的FIRST集合除去ε并入到当前非终结符的FIRST集合中*/for(k=0;kcnt;k++){if(a[i][j]==l[k].ch){for(t=0;tcnt;t++){if(a[i][0]==l[t].ch){for(t1=0;t1l[k].s;t1++){for(t2=0;t2l[t].s;t2++){if(l[k].first[t1]==l[t].first[t2]){break;}}if((t2==l[t].s)&&(l[k].first[t1])!='#'){fchange=1;l[t].first[l[t].s]=l[k].first[t1];l[t].s++;l[t].first[l[t].s]='\0';}}break;}}break;}}if(l[k].flag)continue;elsebreak;}}}if(!fchange){for(i=0;icnt;i++){if(l[i].flag){l[i].first[l[i].s]='#';l[i].s++;l[i].first[l[i].s]='\0';}printf(FIRST(%c):%s\n,l[i].ch,l[i].first);}printf(\n);break;}}}intmain(){inti;if(input()==-1)return-1;seekEmpty();seekFirstVn();return0;}实验内容二：测试文法：S-S;D|DD-(T)|HH-a|(S)T-T+S|S部分源码：//求产生式右部的First集合voidseekFirstRight(){structRight{chara[MAX];charfirst[MAX];ints;}r[MAX];inti,j,k,t;intcnt=0,len,len1,flag=0;for(i=0;icount;i++){for(j=0;jcnt;j++){if(!strcmp(css[i]+3,r[j].a)){flag=1;break;}}if(flag){flag=0;continue;}strcpy(r[j].a,css[i]+3);r[j].s=0;cnt++;}for(i=0;icnt;i++){len=strlen(r[i].a);for(j=0;jlen;j++){//遇到终结符if(r[i].a[j]=='#'){r[i].first[r[i].s]='#';r[i].s++;r[i].first[r[i].s]='\0';break;}elseif((r[i].a[j]'A')||(r[i].a[j]'Z')){r[i].first[r[i].s]=r[i].a[j];r[i].s++;r[i].first[r[i].s]='\0';break;}else{for(k=0;kcnt;k++){if(r[i].a[j]==l[k].ch){len1=strlen(l[k].first);for(t=0;tlen1;t++){if(l[k].first[t]!='#'){r[i].first[r[i].s]=l[k].first[t];r[i].s++;r[i].first[r[i].s]='\0';}}break;}}if(l[k].flag){if(j==len-1){r[i].first[r[i].s]='#';r[i].s++;r[i].first[r[i].s]='\0';}cont