编译原理first,select,follow实验源代码

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct Node { char nonTerminal; char str[10]; //用来存放各个产生式右边的字符串 int tag; //用来标记是否能推出空 char first[10]; //用来存放非终结符的first集合 char firsts[10]; //用来存放字符串的first集合 char follow[10]; //用来存放各个非终结符的follow集 char formFollow[10];//用来存放各个非终结符的follow集合的组成部分 int fol; //用来标记非终结符是否已经计算过follow集 char sellect[10];//用来存放sellect集合 int fir; //用来标志非终结符的first集合是否计算过，0表示没有，1表示计算过 }nonTer,*nonTerminal; typedef struct { char Ldata; // int tag1; //用来标记是否能推出空 int tag2;//用来标记该产生式是否被删除 }LeftData; typedef struct node { LeftData lData; char mData[2]; char rData[10];//产生式右边字符串最大值为10 }Pro; typedef struct { Pro proNum[50]; //输入产生式的最大数量 }Production; static int num=0; //统计实际输入产生式的数量 int sum=1; //统计非终结符的数量 Production init() //初始化产生式 { Production p; int i,j; for(i=0;i<50;i++) { for(j=0;j<10;j++) { p.proNum[i].rData[j]='\0'; } } return p; } Production input() //输入产生式 { int i=0,j=0; Production p; p=init(); printf("依次输入各个产生式，每次以回车结束; 用'#'结束，表示不再有产生式要输入\n"); while((p.proNum[i].lData.Ldata=getchar())!='#') { scanf("%c%c",&p.proNum[i].mData[0],&p.proNum[i].mData[1]); scanf("%s",&p.proNum[i].rData); // p.proNum[i].lData.tag1=0; p.proNum[i].lData.tag2=1; getchar(); if(j>20) { printf("输入产生是的数量超过上限,程序不能处理\n"); } num++; i++; } return p; } Production copyProduction(Production p) { Production cp; int i,j; for(i=0;i<num;i++) { cp.proNum[i].lData.Ldata=p.proNum[i].lData.Ldata; // cp.proNum[i].lData.tag1=p.proNum[i].lData.tag1; cp.proNum[i].lData.tag2=p.proNum[i].lData.tag2; cp.proNum[i].mData[0]=p.proNum[i].mData[0]; cp.proNum[i].mData[1]=p.proNum[i].mData[1]; for(j=0;j<10;j++) { cp.proNum[i].rData[j]=p.proNum[i].rData[j]; } } return cp; } int isJudLegal(Production p) //判断产生式是否合法 { int mid1,mid2,right=0; int i; int flag=0; mid1=0; mid2=1; right=0; if(num==0) { printf("产生式个数为零\n"); return 0; } for(i=0;i<num;i++) { if(p.proNum[i].lData.Ldata>'Z'||p.proNum[i].lData.Ldata<'A') { printf("产生式左部应该为非终结符（大写字母）\n"); return 0; } if(p.proNum[i].mData[mid1]!='-'||p.proNum[i].mData[mid2]!='>') { printf("产生式中间->有误\n"); return 0; } while(p.proNum[i].rData[right]!='\0') { if((p.proNum[i].rData[right]=='*')||(p.proNum[i].rData[right]>='a'&&p.proNum[i].rData[right]<='z') ||(p.proNum[i].rData[right]>='A'&&(p.proNum[i].rData[right]<='Z'))) flag=1; if(flag!=1) { printf("产生式右部输入不符合要求！\n"); return 0; } right++; flag=0; } right=0; } return 1; } int leftRecursive(Production p,nonTer nT[20]) //判断是否有左递归，有则返回1，否则返回0 { int i,j; char ch1,ch2; for(i=0;i<num;i++) { if(p.proNum[i].lData.Ldata==p.proNum[i].rData[0]) { printf("文法含有直接左递归!!!!!\n"); return 1; } } for(i=0;i<num;i++) { ch1=p.proNum[i].lData.Ldata; ch2=p.proNum[i].rData[0]; for(j=0;j<num;j++) { if(p.proNum[j].lData.Ldata==ch2&&p.proNum[j].rData[0]==ch1) { printf("文法中含有间接左递归!!!!!\n"); return 1; } } } return 0; } Production delProduction1(Production p) //删除产生式 { int j, right; right=0; for(j=0;j<num;j++) { while(p.proNum[j].rData[right]!='\0') { if((p.proNum[j].rData[right]>='a'&&p.proNum[j].rData[right]<='z')) { p.proNum[j].lData.tag2=0; //printf("%c\n",p.proNum[j].lData.Ldata); break; } right++; } right=0; } return p; } Production delProduction(Production p,char ch) //删除产生式 { int j; //printf("ch=%c\n",ch); for(j=0;j<num;j++) { if(p.proNum[j].lData.Ldata==ch&&p.proNum[j].lData.tag2==1) { p.proNum[j].lData.tag2=0; } // printf("p.proNum[%d].lData.tag2=%d\n",j,p.proNum[j].lData.tag2); } return p; } Production delProduction2(Production p,char ch) //删除产生式 { int j; printf("ch=%c\n"); for(j=0;j<num;j++) { if(p.proNum[j].lData.Ldata==ch) { p.proNum[j].lData.tag2=0; break; } } return p; } Production delNonTer(Production p,int position,int n) //删除非终结符 { int i=position+1; int j=position; for(;i<10;i++) { p.proNum[n].rData[j]=p.proNum[n].rData[i]; j++; } return p; } int isExist(nonTer nT[20]) //判断是否有未处理的产生式，有则返回1 否则返回0 { int i=0; for(i=0;i<sum;i++) { if(nT[i].tag==-1) { return 1; } } return 0; } void isInferNull(Production p,nonTer nT[20]) //判断非终结符能否推出空 { //nonTer nT[20]; //用于存放非终结符 int i,right=0,t,k,a,j=0,b=0; //用来统计非终结符的个数 int flag,flag1=0; t=0; sum=1; // nT=saveNonTerminal(p); nT[0].nonTerminal=p.proNum[0].lData.Ldata; nT[0].tag=-1; for(i=1;i<num;i++) { j=0; flag1=0; while(nT[j].nonTerminal!='\0') { if(nT[j].nonTerminal==p.proNum[i].lData.Ldata) { flag1=1; break; } j++; } if(flag1!=1) { nT[sum].nonTerminal=p.proNum[i].lData.Ldata; nT[sum].tag=-1; sum++; } } //for(i=0;i<sum;i++) // printf("nT[%d].nonTerminal=%c\n",i,nT[i].nonTerminal); //i=0; p=delProduction1(p); //删除所有右边含有终结符的产生式 for(k=0;k<sum;k++) { for(i=0;i<num;i++) { if(p.proNum[i].lData.Ldata==nT[k].nonTerminal&&p.proNum[i].lData.tag2==1) { break; } } if(i==num) { nT[k].tag=0; } } for(i=0;i<num;i++) //步骤二 { if(p.proNum[i].rData[0]=='*') { for(k=0;k<sum;k++) { if(nT[k].nonTerminal==p.proNum[i].lData.Ldata) { nT[k].tag=1; // printf("left=%c\n",p.proNum[i].lData.Ldata); p=delProduction(p,p.proNum[i].lData.Ldata) ; break; } } } } while(isExist(nT)) { for(i=0;i<num;)//步骤三 { flag=1; if(p.proNum[i].lData.tag2==1) { right=0; while(p.proNum[i].rData[right]!='\0'&&flag) { for(k=0;k<sum&&flag;k++) { if(nT[k].nonTerminal==p.proNum[i].rData[right]) { if(nT[k].tag==1) { p=delNonTer(p,right,i); if(p.proNum[i].rData[0]=='\0') {