编译原理课程设计---基于LL(1)方法的语法分析程序

“编译原理课程设计”基于LL(1)方法的语法分析程序姓名：王宇学号：090104010139学院：信息科学与工程学院班级：09级科学2班指导教师：张世辉编译环境：VS2010日期：2011.12.30-1-一、课程设计目的设计、编制和调试一个典型的语法分析方法，进一步掌握常用的语法分析方法。二、要求(1)根据LL(1)分析法编写一个语法分析程序，可根据自己实际情况，选择以下一项作为分析算法的输入：a.直接输入根据已知文法构造的分析表M;b.输入文法的FIRST(α)和FOLLOW(U)集合，由程序自动生成文法的分析表M；c.输入已知文法，由程序自动构造文法的分析表M。(2)所开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为LL(1)文法。(3)如完成前两项，可增加运行实例，对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。三、设计思想该程序可分为如下几步：（1）设计文法（2）判断正误（3）若无误，判断是否为LL(1)文法（4）若是，构造分析表；（5）由总控算法判断输入符号串是否为该文法的句型。四、主要变量说明‘^’表示空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集合-2-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)判断一个字符是否在指定字符串中charc()得到一个不是非终结符的符号voidrecur(char*point)分解含有左递归的产生式voidnon_re(char*point)分解不含有左递归的产生式chargrammer(char*t,char*n,char*left,charright[50][50])读入一个文法voidmerge(char*d,char*s,inttype)将单个符号或符号串并入另一符号串voidemp(charc)求所有能直接推出^的符号int_emp(charc)求某一符号能否推出‘^’intjudge()判断读入的文法是否正确voidfirst2(inti)求单个符号的FIRSTvoidFIRST(inti,char*p)求各产生式右部的FIRSTvoidFOLLOW(inti)求各产生式左部的FOLLOWintll1()判断读入文法是否为一个LL(1)文法voidMM()构造分析表Mvoidsyntax()总控算法voidmenu()一个用户调用函数四、算法描述1.输入文法的终结符，非终结符，开始符，和产生式，以字符数组分别记录终结符，非终结符，开始符和产生式2.通过检查产生式格式是否符合要求，测试输入产生式是否合法3.如果合法，判断是否有递归，进而判断直接递归还是间接递归，使用设置好的临时变量（非终结符），消除递归，统计新产生式个数，归并新的非终结符，终结符，若没有递归存在，保持其原值量；若不符合，则终止4.化解产生式，求firth，follow，select集，判断是否LL（1），构造分析表-3-5.使用分析表分析输入的句型，并监视分析过程6.结束五、程序结构第一部分：源文件/*******************************************主函数LL1.cpp********************************************/#includeLL1.hvoidmain(){inti,j;start=grammer(termin,non_ter,left,right);//读入一个文法printf(count=%d,count);printf(\nstart:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(\nv:%s,v);printf(\nnon_ter:%s,non_ter);printf(\ntermin:%s,termin);printf(\nright:);for(i=0;i=count-1;i++)printf(%s,right[i]);printf(\nleft:);for(i=0;i=count-1;i++)printf(%c,left[i]);if(validity==1)validity=judge();printf(\nvalidity=%d,validity);if(validity==1){printf(\n文法有效);ll=ll1();if(dg==1)printf(\n消除递归后：\n);printf(\nll=%d,ll);if(ll==0)printf(\n该文法不是一个LL(1)文法！);else{-4-MM();printf(\n);for(i=0;i=19;i++)for(j=0;j=19;j++)if(M[i][j]=0)printf(M[%d][%d]=%d,i,j,M[i][j]);printf(\n);menu();}}}第二部分：头文件/*******************************************读入一个文法getawenfa.h********************************************/#includestdio.h#includestring.h#includedef.hvoidrecur(char*point);voidnon_re(char*point);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);-5-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]){printf(存在递归\n);recur(p[k]);}elsenon_re(p[k]);}return(s);}/*******************************************求所有能直接推出^的符号^.h********************************************/#includestring.h#includedef.hvoidmerge(char*d,char*s,inttype);intin(charc,char*p);-6-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-7-{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);}}}/*******************************************将单个符号或符号串并入另一符号串afuhaochuanintoanother.h********************************************/#includestring.hvoidmerge(char*d,char*s,inttype){/*d是目标括符号串，s是源串，type＝1，源串中的‘^’一并并入目标串；type＝2，源串中的‘^ˉ不并入目串*/inti,j;for(i=0;i=strlen(s)-1;i++){if(type==2&&s[i]=='^');else{for(j=0;;j++)-8-{if(jstrlen(d)&&s[i]==d[j])break;if(j==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************判断一个字符是否在指定字符串中charInORNot.h********************************************/#includestring.hintin(charc,char*p){inti;if(strlen(p)==0)return(0);for(i