C语言求文法的First集

C语言求文法的FIRST集//Copyright:ChenZexi,JXNU#includestring.h#includestdio.h#includestdlib.h#defineMAXS50#defineepsilon'*'charnoend[MAXS];//非终极符charEnd[MAXS];//终极符intN;structSTR{inthas_epsion;charleft;charright[MAXS];};structFirst{charletter;chargather[MAXS];};intgetlr(structSTR*p,inti,char*temp){intj;intk=0;intsucc=0;for(j=0;jstrlen(temp);j++){if(temp[j]=='-'&&temp[j+1]==''){succ=1;if(j==1){p[i].left=temp[0];j=3;p[i].has_epsion=0;while(temp[j]!='\0'){p[i].right[k]=temp[j];if(temp[j]==epsilon){p[i].has_epsion=1;}k++;j++;}p[i].right[k]='\0';}}}returnsucc;}intfindchar(char*s,charc){inti;intindex=-1;for(i=0;istrlen(s);i++){if(s[i]==c)index=i;}returnindex;}inthasepsilon(structSTR*p,charc){inti;intindex=-1;for(i=0;iN;i++){if(p[i].left==c&&p[i].has_epsion==1)index=1;}returnindex;}//求VN(终极符)和VT（非终极符）voidVNVT(structSTR*p){inti,j,x;for(i=0;iN;i++){for(j=0;j1;j++){if((p[i].left='A'&&p[i].left='Z')){if(findchar(noend,p[i].left)0){x=strlen(noend);noend[x]=p[i].left;noend[x+1]='\0';}}}for(j=0;jstrlen(p[i].right);j++){if(!(p[i].right[j]='A'&&p[i].right[j]='Z')){if(findchar(End,p[i].right[j])0){x=strlen(End);End[x]=p[i].right[j];End[x+1]='\0';}}else{if(findchar(noend,p[i].right[j])0){x=strlen(noend);noend[x]=p[i].right[j];noend[x+1]='\0';}}}}}//非终极符的FIRST集voidFirstgather(structSTR*p,structFirst*f){inti,j,k,l,m;intx,n;intchange=1;inteps;for(i=0;istrlen(noend);i++){strcpy(f[i].gather,);//清空缓存}//非终极符First集while(change==1){change=0;for(i=0;istrlen(noend);i++){f[i].letter=noend[i];//扫描产生式for(j=0;jN;j++){if(p[j].left==f[i].letter){//查看是否是非终极符n=findchar(noend,p[j].right[0]);//不是非终极符if(n0){k=0;//直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中if(findchar(f[i].gather,p[j].right[k])0){x=strlen(f[i].gather);f[i].gather[x]=p[j].right[k];f[i].gather[x+1]='\0';change=1;}}//是非终极符else{//反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中for(l=0;lstrlen(p[j].right);l++){//检测终极符if(findchar(End,p[j].right[l])=0&&findchar(f[i].gather,p[j].right[l])0){x=strlen(f[i].gather);f[i].gather[x]=p[j].right[l];f[i].gather[x+1]='\0';change=1;break;}//左递归继续if(p[j].right[l]==f[i].letter)continue;//其他情况for(m=0;mstrlen(noend);m++){if(noend[m]==p[j].right[l]){for(k=0;kstrlen(f[m].gather);k++){if(f[m].gather[k]!=epsilon&&findchar(f[i].gather,f[m].gather[k])0){x=strlen(f[i].gather);f[i].gather[x]=f[m].gather[k];f[i].gather[x+1]='\0';change=1;}}}}if(hasepsilon(p,p[j].right[l])0)break;if(l==strlen(p[j].right)-1&&findchar(f[i].gather,epsilon)0){x=strlen(f[i].gather);f[i].gather[x]=epsilon;f[i].gather[x+1]='\0';change=1;}}}}}}}}voidprintFirst(structFirst*f){intj,k;printf(非终极符的FIRST集\n);for(j=0;jstrlen(noend);j++){//printf(%s\n,f[j].gather);printf(FIRST(%c)={,f[j].letter);for(k=0;kstrlen(f[j].gather);k++){printf(%c,f[j].gather[k]);if(kstrlen(f[j].gather)-1){printf(,);}}printf(}\n);}}voidprintProduction(structSTR*p,inti){intj,k;printf([序号]产生式：\n);for(j=0;ji;j++){printf([%2d]%c-%s\n,j,p[j].left,p[j].right);}printf(非终极符集合：\nVT={);for(j=0;jstrlen(noend);j++){printf(%c,noend[j]);if(jstrlen(noend)-1){printf(,);}}printf(}\n);printf(终极符集合：\nVN={);for(j=0;jstrlen(End);j++){printf(%c,End[j]);if(jstrlen(End)-1){printf(,);}}printf(}\n);}//主函数intmain(){inti;intj[MAXS];structSTRp[MAXS];structFirstf[MAXS];chartemp[MAXS];do{printf(请输入产生式数目\n);scanf(%d,&N);getchar();}while(N=0);printf(请输入形如A-abc的产生式（*代表空）按回车换行：\n);for(i=0;iN;i++){scanf(%s,temp);j[i]=getlr(p,i,temp);}VNVT(p);Firstgather(p,f);printProduction(p,N);printFirst(f);return0;}