编译原理实验报告
- 格式：doc
- 大小：116.50 KB
- 文档页数：20
编译原理实验报告姓名：唐义平班级：软124学号：129074273指导老师：王森玉实验日期：2015/5/20实验内容：1.求出每个非终结符的FIRST集合2.求出每个产生式右部的FIRST集合3.求出每个非终结符的Follow集合实验环境：Visual Studio2010实验目的:让同学们掌握FIRST集合和FOLLOW集合的求法实验代码：#include<stdio.h>#include<string.h>#define MAX 50char css[MAX][MAX];//保存所有的产生式int count=0;int cnt=0;struct L{//保存所有的终结符char ch;int flag;//1:能推出ε,0:不能,初值:-1int num;char first[MAX];int s;//first的长度char follow[MAX];int l;//follow的长度}l[MAX];//对输入的格式进行控制,并校验输入是否符合格式int handle(char a[]){int len,i=0,j,k;len=strlen(a);while(a[i]!=10){if(a[i]=='$')return 2;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");return 0;}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;}}return 0;}//从键盘获得输入int input(){char a[MAX*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 a[MAX][MAX],ch;for(i=0;i<count;i++){strcpy(a[i],css[i]);}//求出含有的非终结符的个数,并把各终结符保存起来for(i=0;i<count;i++){for(j=0;j<cnt;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;i<c;i++){//如果该终结符推出ε，从a[]中删除所有带有该终结符的产生式if(a[i][3]=='@'){ch=a[i][0];for(j=0;j<c;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;k<c-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}for(j=0;j<cnt;j++){if(ch==l[j].ch){l[j].flag=1;break;}}i--;continue;}len=strlen(a[i]);for(j=3;j<len;j++){//当该产生式右边含有非终结符时从a[]中删除该条记录if((a[i][j]<'A')||(a[i][j]>'Z')){flag2=1;break;}}if(flag2){for(k=0;k<cnt;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;k<c-1;k++){strcpy(a[k],a[k+1]);}c--;i--;flag2=0;continue;}//如果产生式右边为非终结符看看该终结符能不能推出εfor(j=3;j<len;j++){if((a[i][j]>='A')&&(a[i][j]<='Z')){for(k=0;k<cnt;k++){if(a[i][j]==l[k].ch){if(l[k].flag==0){flag2=1;break;}else if(l[k].flag==1){for(t=j;t<len-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;j<c;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;k<c-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}i--;for(k=0;k<cnt;k++){if(ch==l[k].ch){l[k].flag=1;break;}}}if(flag2){for(k=0;k<cnt;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;k<c-1;k++){strcpy(a[k],a[k+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 a[MAX][MAX],ch[MAX];for(i=0;i<count;i++){strcpy(a[i],css[i]);}c=count;while(1){fchange=0;for(i=0;i<c;i++){//右部为ε,将ε并入到左部的First中if(a[i][3]=='@'){/*for(j=0;j<cnt;j++){if(l[j].ch==a[i][0]){for(k=0;k<l[j].s;k++)if(l[j].first[k]==a[i][3]){flag=1;break;}if(!flag){l[j].first[l[j].s]=a[i][3];l[j].s++;l[j].first[l[j].s]='\0';fchange=1;break;}flag=0;}}*///从当前列表a[]中删除if(i!=c-1)for(j=i;j<c-1;j++)strcpy(a[j],a[j+1]);c--;i--;continue;}len=strlen(a[i]);//产生式右边符号为终结符时,将该终结符并入到左部的First集合中for(j=3;j<len;j++){if((a[i][j]<'A')||(a[i][j]>'Z')){for(k=0;k<cnt;k++){if(a[i][0]==l[k].ch){for(t=0;t<l[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;k<c-1;k++)strcpy(a[k],a[k+1]);c--;i--;break;}//产生式右边符号为非终结符时else if((a[i][j]>='A')&&(a[i][j]<='Z')){/*将该非终结符的FIRST集合除去ε并入到当前非终结符的FIRST集合中*/for(k=0;k<cnt;k++){if(a[i][j]==l[k].ch){for(t=0;t<cnt;t++){if(a[i][0]==l[t].ch){for(t1=0;t1<l[k].s;t1++){for(t2=0;t2<l[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;i<cnt;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;}}}//求产生式右部的First集合void seekFirstRight(){struct Right{char a[MAX];char first[MAX];int s;}r[MAX];int i,j,k,t;int cnt=0,len,len1,flag=0;for(i=0;i<count;i++){for(j=0;j<cnt;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;i<cnt;i++){len=strlen(r[i].a);for(j=0;j<len;j++){//遇到终结符if(r[i].a[j]=='@'){r[i].first[r[i].s]='@';r[i].s++;r[i].first[r[i].s]='\0';break;}else if((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;k<cnt;k++){if(r[i].a[j]==l[k].ch){len1=strlen(l[k].first);for(t=0;t<len1;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';}continue;}elsebreak;}}}for(i=0;i<cnt;i++){printf("FIRST(%s): %s\n",r[i].a,r[i].first);}printf("\n");}//求每个非终极符的Follow集合void seekFollow(){int i,j,k,t,t1,t2,t3,c=0;int flag=0,len;int fchange;//判断一次循环是否有改动的地方char a[MAX][MAX],ch[MAX];for(i=0;i<count;i++){len=strlen(css[i]);for(j=3;j<len;j++){if((css[i][j]>='A')&&(css[i][j]<='Z')){break;}}if(j!=len){strcpy(a[c],css[i]);c++;}}l[0].follow[l[0].l]='#';l[0].l++;l[0].follow[l[0].l]='\0';while(1){fchange=0;for(i=0;i<c;i++){len=strlen(a[i]);for(j=3;j<len;j++){if((a[i][j]>='A')&&(a[i][j]<='Z')){//判断该非终结符的前一位是否为非终结符,是的话,//将其First集合去ε后并到其前一位非终结符的Follow集合中if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')){for(k=0;k<cnt;k++){if(a[i][j-1]==l[k].ch){for(t=0;t<cnt;t++){if(a[i][j]==l[t].ch){for(t1=0;t1<l[t].s;t1++){if(l[t].first[t1]=='@')continue;for(t2=0;t2<l[k].l;t2++)if(l[t].first[t1]==l[k].follow[t2])break;if(t2==l[k].l){fchange=1;l[k].follow[l[k].l]=l[t].first[t1];l[k].l++;l[k].follow[l[k].l]='\0';}}break;}}break;}}}//如果该非终结符是最后一位,//将该产生式左部非终结符的Follow集合//加入到当前非终结符的Follow集合中.//然后从当前终结符开始向右判断是否为非终结符，是的话,进行相应处理//循环直到当前非终结符推不出ε或当前为终结符时退出if(j==len-1){t3=j;strcpy(ch,a[i]);while(!flag){if((ch[t3]>='A')&&(ch[t3]<='Z')){for(k=0;k<cnt;k++){if(ch[0]==l[k].ch){for(t=0;t<cnt;t++){if(ch[t3]==l[t].ch){for(t1=0;t1<l[k].l;t1++){for(t2=0;t2<l[t].l;t2++)if(l[k].follow[t1]==l[t].follow[t2])break;if(t2!=l[t].l)continue;else{fchange=1;l[t].follow[l[t].l]=l[k].follow[t1];l[t].l++;l[t].follow[l[t].l]='\0';}}if(l[t].flag)ch[t3--]='\0';else{flag=1;t3--;}break;}}break;}}}elsebreak;}flag=0;}}//如果当前位为终结符，判断其前一位是否为非终结符//是的话,将该终结符并到该非终结符的Follow集合中else{if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')){for(k=0;k<cnt;k++){if(a[i][j-1]==l[k].ch){for(t=0;t<l[k].l;t++)if(a[i][j]==l[k].follow[t])break;if(t==l[k].l){fchange=1;l[k].follow[l[k].l]=a[i][j];l[k].l++;l[k].follow[l[k].l]='\0';}}}}}}}if(!fchange){for(i=0;i<cnt;i++)printf("FOLLOW(%c): %s\n",l[i].ch,l[i].follow);break;}}}int main(){int i;if(input()==-1)return -1;seekEmpty();seekFirstVn();seekFirstRight();seekFollow();return 0;}实验演示：因为不知道怎么用电脑输出’ε’符号，我在代码里用’@’来表示‘ε’.以‘$’来结束输入测试数据1：S->MH|aH->LSo|@K->dML|@L->eHfM->K|bLM测试数据2：S->aHH->aMd|dM->Ab|@A->aM|e实验感想：经过这几次的实验，不仅让我们更加深刻的知道了first集合和follow集合的计算步骤和方法，还很好的培养了我们动手能力。
