First、Follow、Select集

#include<stdio.h>
#include<windows.h>
typedef struct{             //文法结构体int Vnnum;              //非终结符个数char Vn[100][100];      //非终结符int Vtnum;              //终结符个数char Vt[100][100];      //终结符int snum;               //产生式个数int S[100][100];       //产生式char begin[100];char blank[4]={"ε"};
}G;
typedef struct{         //产生式结构体char state[100];    //产生式左部非终结符int num=0;            //该非终结符产生式个数int cs[100][100];  //产生式右部}rule;typedef struct{         //firstchar state[100];    //非终结符int num=0;            //fisrt集个数char sym[100][100];     //first集
}first,follow;typedef struct{char state[100];int snum=0;              //产生式数量int s[100][100];         //产生式int num[100]={0};            //每个产生式的select集的个数char sym[100][100][100]; //每个产生式的select集}SELECT;int info(first *f,char a[],int n){for(int i=0;i<n;i++)if(strcmp(f[i].state,a)==0)return i;}
int info1(G g,char s[]){int i;for(i=0;i<g.Vnnum;i++)if(strcmp(g.Vn[i],s)==0)return i;for(i;i-g.Vnnum<g.Vtnum;i++)if(strcmp(g.Vt[i-g.Vnnum],s)==0)return i;return -1;
}
int  split(char s[][100],char a[],char c){int k=0,j=0;for(int i=0;i<strlen(a);i++){if(a[i]!=c){if(a[i]!='\n')s[k][j++]=a[i];}else {k++;j=0;}}return k;
}
int kinG(G g){for(int i=0;i<g.Vtnum;i++)if(strcmp(g.Vt[i],"ε")==0)return 1;return 0;
}
void stradd(char s[],char c[]){for(int i=0;i<=strlen(c);i++)s[i]=c[i];
}void getrule(G &g){                             //读取文法FILE *fp;char name[20];scanf("%s",&name);if((fp=fopen(name,"r"))!=NULL){fscanf(fp,"%d",&g.Vnnum);                     //读取非终结符的数量//getchar();                              //屏蔽回车for(int i=0;i<g.Vnnum;i++){               //读取非终结符 fscanf(fp,"%s",&g.Vn[i]);//fgets(VN[i],20,fp);}fscanf(fp,"%d",&g.Vtnum);                     //读取终结符的数量//getchar();                              //屏蔽回车for(int i=0;i<g.Vtnum;i++){               //读取终结符 fscanf(fp,"%s",&g.Vt[i]);//fgets(VT[i],20,fp);}fscanf(fp,"%d",&g.snum);                     //读取规则的数量//getchar();                              //屏蔽回车char blank,p[100];fscanf(fp,"%c",&blank);for(int i=0;i<g.snum;i++){               //读取规则 fgets(p,20,fp);if(strstr(p,"ε")){if(!kinG(g)){stradd(g.Vt[g.Vtnum++],"ε");}}char s[100][100]={'\0'};int k;k=split(s,p,' ')+1;g.S[i][0]=info1(g,s[0]);for(int j=1;j<=k-1;j++)g.S[i][j]=info1(g,s[j+1]);}//getchar();                              //屏蔽回车fscanf(fp,"%s",&g.begin);                         //读取开始符号fclose(fp);}else {printf("文件不存在\n");exit(0);}
}void print(G g1){printf("非终结符：\n\t");for(int i=0;i<g1.Vnnum;i++)printf("%s ",g1.Vn[i]);printf("\n终结符：\n\t");for(int i=0;i<g1.Vtnum;i++)if(strcmp(g1.Vt[i],"ε"))printf("%s ",g1.Vt[i]);printf("\n产生式集:\n");for(int i=0;i<g1.snum;i++){printf("\t%d：",i);printf("%s->",g1.Vn[g1.S[i][0]]);int temp=1,k=g1.S[i][temp];while(k!=-1){if(k<g1.Vnnum){printf(" %s",g1.Vn[k]);}   else if(k<(g1.Vnnum+g1.Vtnum)){printf(" %s",g1.Vt[k-g1.Vnnum]);}else printf(" %s",g1.blank);temp++;k=g1.S[i][temp];}printf("\n");}printf("开始符号:\n");printf("\t%s\n",g1.begin);
}
int ifin(first f,char s[]){for(int i=0;i<f.num;i++)if(strcmp(f.sym[i],s)==0)return 1;return 0;}
int add(first &sf,first df,G g){  //df添加到sfint f=0;for(int i=0;i<df.num;i++){if(!ifin(sf,df.sym[i])&&strcmp(df.sym[i],"ε")){for(int j=0;j<strlen(df.sym[i]);j++)sf.sym[sf.num][j]=df.sym[i][j];sf.sym[sf.num][strlen(df.sym[i])]='\0';sf.num++;f=1;}}//printf("%s<-%s-f=%d-num=%d\n",sf.state,df.state,f,sf.num);return f;
}
int kinf(first f){for(int i=0;i<f.num;i++)if(strcmp(f.sym[i],"ε")==0)return 1;return 0;}void firstset(G g,first *F){//first集置空for(int i=0;i<g.Vnnum;i++){   for(int j=0;j<=strlen(g.Vn[i]);j++)F[i].state[j]=g.Vn[i][j];//F[i].state[strlen(g.Vn[i])]='\0';F[i].num=0;//printf("%s\n",F[i].state);}int flag=1;while(flag){//只要first集还在变化就一直迭代flag=0;for(int i=0;i<g.snum;i++){//printf("%d\n",i);int ctn=1,k=1;while(ctn&&g.S[i][k]!=-1){if(g.S[i][k]>=g.Vnnum){int ifo=info(F,g.Vn[g.S[i][0]],g.Vnnum);if(!ifin(F[ifo],g.Vt[g.S[i][k]-g.Vnnum])){int x=F[ifo].num++;for(int j2=0;j2<strlen(g.Vt[g.S[i][k]-g.Vnnum]);j2++)F[ifo].sym[x][j2]=g.Vt[g.S[i][k]-g.Vnnum][j2];F[ifo].sym[x][strlen(g.Vt[g.S[i][k]-g.Vnnum])]='\0';flag=1;}//break;ctn=0;}else{int f1=add(F[info(F,g.Vn[g.S[i][0]],g.Vnnum)],F[info(F,g.Vn[g.S[i][k]],g.Vnnum)],g);//printf("f1=%d\n",f1);if(f1)flag=1;if(!kinf(F[info(F,g.Vn[g.S[i][k]],g.Vnnum)])){ctn=0;}k++;}}if(ctn){//空符号加入到firstif(!kinf(F[info(F,g.Vn[g.S[i][0]],g.Vnnum)])){F[info(F,g.Vn[g.S[i][0]],g.Vnnum)].sym[F[info(F,g.Vn[g.S[i][0]],g.Vnnum)].num++][0]='ε';F[info(F,g.Vn[g.S[i][0]],g.Vnnum)].sym[F[info(F,g.Vn[g.S[i][0]],g.Vnnum)].num-1][1]='\0';flag=1;}}}}printf("First Set:\n");     for(int i=0;i<g.Vnnum;i++){printf("\t%s:",F[i].state);for(int j=0;j<F[i].num;j++)    {   printf("%s ",F[i].sym[j]);}printf("\n");}
}
void stringfisrt(G g,first &f,int a[],int left,first *Fst){int flag=1;if(a[left]==-1){stradd(f.sym[f.num++],"ε");return;}while(a[left]!=-1&&flag){if(a[left]>=g.Vnnum){int x=f.num;if(strcmp(g.Vt[a[left]-g.Vnnum],"ε")){stradd(f.sym[x],g.Vt[a[left]-g.Vnnum]);f.num++;}return;}else{int ifo=info(Fst,g.Vn[a[left]],g.Vnnum);add(f,Fst[ifo],g);if(!kinf(Fst[ifo])){flag=0;}else{left++;}}}if(flag){if(!kinf(f)){stradd(f.sym[f.num++],"ε");}}
}
void followset(G g,first *F,first *fst){//follow集置空for(int i=0;i<g.Vnnum;i++){   for(int j=0;j<=strlen(g.Vn[i]);j++)F[i].state[j]=g.Vn[i][j];F[i].state[strlen(g.Vn[i])]='\0';F[i].num=0;//printf("%s\n",F[i].state);}int ifo=info(F,g.begin,g.Vnnum);F[ifo].num++;F[ifo].sym[F[ifo].num-1][0]='#';F[ifo].sym[F[ifo].num-1][1]='\0';int flag=1;while(flag){flag=0;for(int i=0;i<g.snum;i++){int k=1,ifo=info(F,g.Vn[g.S[i][0]],g.Vnnum);while(g.S[i][k]!=-1){if(g.S[i][k]<g.Vnnum){if(g.S[i][k]==-1){int ifo1=info(F,g.Vn[g.S[i][k+1]],g.Vnnum);int p=add(F[ifo1],F[ifo],g);if(p)flag=1;k++;}else {first temp;int ifo1=info(F,g.Vn[g.S[i][k]],g.Vnnum);stringfisrt(g,temp,g.S[i],k+1,fst);int p=add(F[ifo1],temp,g);if(p)flag=1;if(kinf(temp)){int p1=add(F[ifo1],F[ifo],g);if(p1)flag=1;}k++;}}else k++;}}}printf("Follow Set:\n");      for(int i=0;i<g.Vnnum;i++){printf("\t%s:",F[i].state);for(int j=0;j<F[i].num;j++)    {   printf("%s ",F[i].sym[j]);}printf("\n");}
}
int info(SELECT *s,char a[],G g){for(int i=0;i<g.Vnnum;i++)if(strcmp(s[i].state,a)==0)return i;}
int ifin(char s[100][100],char a[],int n){int flag=0;for(int i=0;i<n;i++)if(strcmp(s[i],a)==0)flag=1;return flag;}
void adds(SELECT &S,first f,G g, int j){for(int i=0;i<f.num;i++){if(strcmp(f.sym[i],"ε")&&(!ifin(S.sym[j],f.sym[i],S.num[j]))){stradd(S.sym[j][S.num[j]++],f.sym[i]);}}}
void stringfisrt1(G g,first &f,int a[],int left,first *Fst){int flag=1;if(a[left]==-1){stradd(f.sym[f.num++],"ε");return;}while(a[left]!=-1&&flag){if(a[left]>=g.Vnnum){int x=f.num;stradd(f.sym[x],g.Vt[a[left]-g.Vnnum]);f.num++;return;}else{int ifo=info(Fst,g.Vn[a[left]],g.Vnnum);add(f,Fst[ifo],g);if(!kinf(Fst[ifo])){flag=0;}else{left++;}}}if(flag){if(!kinf(f)){stradd(f.sym[f.num++],"ε");}}
}
void selectset(SELECT *S,first *fst,first *flw,G g){for(int i=0;i<g.Vnnum;i++)stradd(S[i].state,g.Vn[i]);for(int i=0;i<g.snum;i++){int ifo=info(S,g.Vn[g.S[i][0]],g);int k=1,x=S[ifo].snum++;while(g.S[i][k]!=-1){S[ifo].s[x][k-1]=g.S[i][k];k++;}S[ifo].s[x][k-1]=-1;    }for(int i=0;i<g.Vnnum;i++){for(int j=0;j<S[i].snum;j++){first temp;int y;stringfisrt1(g,temp,S[i].s[j],0,fst);adds(S[i],temp,g,j);if(kinf(temp)){adds(S[i],flw[i],g,j);}}}printf("Select Set:\n");     for(int i=0;i<g.Vnnum;i++){for(int j=0;j<S[i].snum;j++){printf("\t%s->",S[i].state);int k=0;while(S[i].s[j][k]!=-1){int l=S[i].s[j][k];if(l>=g.Vnnum)printf("%s ",g.Vt[l-g.Vnnum]);else printf("%s ",g.Vn[l]);k++;}printf(": ");for(int k=0;k<S[i].num[j];k++)printf("%s ",S[i].sym[j][k]);printf("\n");}}}
int main(){G g;first *FST,*FLW;SELECT *SEL;getrule(g);FST=(first*)malloc(sizeof(first)*g.Vnnum); FLW=(first*)malloc(sizeof(first)*g.Vnnum); SEL=(SELECT*)malloc(sizeof(SELECT)*g.Vnnum); print(g);firstset(g,FST);followset(g,FLW,FST);selectset(SEL,FST,FLW,g);system("pause");}