LL(1)语法分析程序实验报告

《编译原理》上机实验报告1.设计要求（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止；（2）输入已知文法，由程序自动生成它的LL(1)分析表；（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。2.分析该程序可分为如下几步：（1）读入文法（2）判断正误（3）若无误，判断是否为LL(1)文法（4）若是，构造分析表；（5）由总控算法判断输入符号串是否为该文法的句型。3.流程图是是开始读入文法有效？是LL(1)文法？判断句型报错结束4.源程序/*******************************************语法分析程序作者：学号：********************************************/#includestdlib.h#includestdio.h#includestring.h/*******************************************/intcount=0;/*分解的产生式的个数*/intnumber;/*所有终结符和非终结符的总数*/charstart;/*开始符号*/chartermin[50];/*终结符号*/charnon_ter[50];/*非终结符号*/charv[50];/*所有符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有单个符号的FIRST集合*/charselect[50][50];/*各单个产生式的SELECT集合*/charf[50],F[50];/*记录各符号的FIRST和FOLLOW是否已求过*/charempty[20];/*记录可直接推出^的符号*/charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST集合*/intvalidity=1;/*表示输入文法是否有效*/intll=1;/*表示输入文法是否为LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用户输入时使用*/charempt[20];/*求_emp()时使用*/charfo[20];/*求FOLLOW集合时使用*//*******************************************判断一个字符是否在指定字符串中********************************************/intin(charc,char*p){//inti;size_ti;if(strlen(p)==0)return(0);for(i=0;;i++){if(p[i]==c)return(1);/*若在，返回1*/if(i==strlen(p))return(0);/*若不在，返回0*/}}/*******************************************得到一个不是非终结符的符号********************************************/charc(){charc='A';while(in(c,non_ter)==1)c++;return(c);}/*******************************************分解含有左递归的产生式********************************************/voidrecur(char*point){/*完整的产生式在point[]中*/intj,m=0,n=3,k;chartemp[20],ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter);non_ter[k]=ch;non_ter[k+1]='\0';for(j=0;size_t(j)=strlen(point)-1;j++){if(point[n]==point[0]){/*如果'|'后的首符号和左部相同*/for(j=n+1;size_t(j)=strlen(point)-1;j++){while(point[j]!='|'&&point[j]!='\0')temp[m++]=point[j++];left[count]=ch;memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';m=0;count++;if(point[j]=='|'){n=j+1;break;}}}else{/*如果'|'后的首符号和左部不同*/left[count]=ch;right[count][0]='^';right[count][1]='\0';count++;for(j=n;size_t(j)=strlen(point)-1;j++){if(point[j]!='|')temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';printf(count=%d,count);m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';count++;m=0;}}}/*******************************************分解不含有左递归的产生式********************************************/voidnon_re(char*point){intm=0,j;chartemp[20];for(j=3;size_t(j)=strlen(point)-1;j++){if(point[j]!='|')temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';count++;m=0;}/*******************************************读入一个文法********************************************/chargrammer(char*t,char*n,char*left,charright[50][50]){charvn[50],vt[50];chars;charp[50][50];inti,j,k;printf(\n请输入文法的非终结符号串：);scanf(%s,vn);getchar();i=strlen(vn);memcpy(n,vn,i);n[i]='\0';printf(请输入文法的终结符号串：);scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i);t[i]='\0';printf(请输入文法的开始符号：);scanf(%c,&s);getchar();printf(请输入文法产生式的条数：);scanf(%d,&i);getchar();for(j=1;j=i;j++){printf(请输入文法的第%d条（共%d条）产生式：,j,i);scanf(%s,p[j-1]);getchar();}for(j=0;j=i-1;j++)if(p[j][1]!='-'||p[j][2]!=''){printf(\ninputerror!);validity=0;return('\0');}/*检测输入错误*/for(k=0;k=i-1;k++){/*分解输入的各产生式*/if(p[k][3]==p[k][0])recur(p[k]);elsenon_re(p[k]);}return(s);}/*******************************************将单个符号或符号串并入另一符号串********************************************/voidmerge(char*d,char*s,inttype){/*d是目标符号串，s是源串，type＝1，源串中的'^'一并并入目串；type＝2，源串中的'^'不并入目串*/inti,j;for(i=0;size_t(i)=strlen(s)-1;i++){if(type==2&&s[i]=='^');else{for(j=0;;j++){if(size_t(j)strlen(d)&&s[i]==d[j])break;if(size_t(j)==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************求所有能直接推出^的符号********************************************/voidemp(charc){/*即求所有由'^'推出的符号*/chartemp[10];inti;for(i=0;i=count-1;i++){if(right[i][0]==c&&strlen(right[i])==1){temp[0]=left[i];temp[1]='\0';merge(empty,temp,1);emp(left[i]);}}}/*******************************************求某一符号能否推出'^'********************************************/int_emp(charc){/*若能推出，返回1；否则，返回0*/inti,j,k,result=1,mark=0;chartemp[20];temp[0]=c;temp[1]='\0';merge(empt,temp,1);if(in(c,empty)==1)return(1);for(i=0;;i++){if(i==count)return(0);if(left[i]==c)/*找一个左部为c的产生式*/{j=strlen(right[i]);/*j为右部的长度*/if(j==1&&in(right[i][0],empty)==1)return(1);elseif(j==1&&in(right[i][0],termin)==1)return(0);else{for(k=0;k=j-1;k++)if(in(right[i][k],empt)==1)mark=1;if(mark==1)continue;else{for(k=0;k=j-1;k++){result*=_emp(right[i][k]);temp[0]=right[i][k];temp[1]='\0';merge(empt,temp,1);}}}if(result==0&&icount)continue;elseif(result==1&&icount)return(1);}}}/*******************************************判断读入的文法是否正确********************************************/intjudge(){inti,j;for(i=0;i=count-1;i++){if(in(le