语法分析器实验报告

语法分析器的设计实验报告一、实验内容语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法：G[E]:E-E+T|TT-T*F|FF-i|(E)分析句子i+i*i是否符合文法。二、基本思想1、语法分析器实现语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。该程序可分为如下几步：（1）读入文法（2）判断正误（3）若无误，判断是否为LL(1)文法（4）若是，构造分析表；（5）由句型判别算法判断输入符号串是为该文法的句型。三、核心思想该分析程序有15部分组成：（1）首先定义各种需要用到的常量和变量；开始读入文法有效？判断句型报错结束语法分析程序流程图是LL(1)文法？（2）判断一个字符是否在指定字符串中；（3）读入一个文法；（4）将单个符号或符号串并入另一符号串；（5）求所有能直接推出&的符号；（6）求某一符号能否推出‘&’；（7）判断读入的文法是否正确；（8）求单个符号的FIRST；（9）求各产生式右部的FIRST；（10）求各产生式左部的FOLLOW；（11）判断读入文法是否为一个LL(1)文法；（12）构造分析表M；（13）句型判别算法；（14）一个用户调用函数；（15）主函数；下面是其中几部分程序段的算法思想：1、求能推出空的非终结符集Ⅰ、实例中求直接推出空的empty集的算法描述如下：voidemp(charc){参数c为空符号chartemp[10];定义临时数组inti;for(i=0;i=count-1;i++)从文法的第一个产生式开始查找{if产生式右部第一个符号是空符号并且右部长度为1,then将该条产生式左部符号保存在临时数组temp中将临时数组中的元素合并到记录可推出&符号的数组empty中。}Ⅱ、求某一符号能否推出'&'int_emp(charc){//若能推出&，返回1；否则，返回0inti,j,k,result=1,mark=0;chartemp[20];temp[0]=c;temp[1]='\0';存放到一个临时数组empt里,标识此字符已查找其是否可推出空字如果c在可直接推出空字的empty[]中,返回1for(i=0;;i++){if(i==count)return(0);找一个左部为c的产生式j=strlen(right[i]);//j为c所在产生式右部的长度if右部长度为1且右部第一个字符在empty[]中.then返回1(A-B,B可推出空)if右部长度为1但第一个字符为终结符,then返回0(A-a,a为终结符)else{for(k=0;k=j-1;k++){查找临时数组empt[].并标记mark-=1(A-AB)if找到的字符与当前字符相同(A-AB)结束本次循环else(mark等于0)查找右部符号是否可推出空字,把返回值赋给result把当前符号加入到临时数组empt[]里.}if当前字符不能推出空字且还没搜索完全部的产生式then跳出本次循环继续搜索下一条产生式elseif//当前字符可推出空字,返回1}}}2、计算每个符号的first集：实例中求单个符号的FIRST集的算法描述如下：voidfirst2(inti){参数i为符号在所有输入符号中的序号c等于指示器i所指向的符号在保存终结符元素的termin[]数组查找cifc为终结符(c∈VT)，thenFIRST(c)={c}在保存终结符元素的non_ter[]数组查找cifc是非终结符(c∈VN)在所有产生式中查找c所在的产生式if产生式右部第一个字符为终结符或空(即c→a(a∈VT)或c→&)then把a或&加进FIRST(c)if产生式右部第一个字符为非终结符thenif产生式右部的第一个符号等于当前字符then跳到下一条产生式进行查找求当前非终结符在所有字符集中的位置if当前非终结符还没求其FIRST集then查找它的FIRST集并标识此符号已求其FIRST集求得结果并入到c的FIRST集.if当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then获取右部符号下一个字符在所有字符集中的位置if此字符的FIRST集还未查找then找其FIRST集,并标其查找状态为1把求得的FIRST集并入到c的FIRST集.if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为c→Y1Y2…Yk,若对一切1=i=k，均有&∈FIRST(Yi)，则将&∈符号加进FIRST(c))then把空字加入到当前字符c的FIRST集.else不能推出空字则结束循环标识当前字符c已查找其FIRST集.}3.计算FOLLOW集FOLLOW集的构造可用如下方法来求：对于文法中的符号XVN，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。(1)对于文法开始符号S，因为SS，故#FOLLOW(S)；(2)若A→B，其中BVN，(VTVN)*、(VTVN)+，则FIRST()-{}FOLLOW(B)；(3)若A→B或A→B()，则FOLLOW(A)FOLLOW(B)。FOLLOW集的算法描述如下：voidFOLLOW(inti)X为待求的非终结符把当前字符放到一临时数组foll[]中,标识求已求其FOLLOW集.避免循环递归ifX为开始符号then#∈FOLLOW(X)对全部的产生式找一个右部含有当前字符X的产生式注：比如求FOLLOW(B)则找A→αX或A→X(ε)的产生式ifX在产生式右部的最后(形如产生式A→X)then查找非终结符A是否已经求过其FOLLOW集.避免循环递归if非终结符A已求过其FOLLOW集thenFOLLOW(A)∈FOLLOW(X)继续查下一条产生式是否含有Xelse求A之FOLLOW集，并标识为A已求其FOLLOW集elseifX不在产生式右部的最后(形如A→B)thenif右部X后面的符号串能推出空字then查找是否已经求过其FOLLOW集.避免循环递归if已求过的FOLLOW集thenFOLLOW(A)∈FOLLOW(B)结束本次循环elseif不能推出空字then求FIRST()把FIRST()中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过4.计算SELECT集SELECT集的构造算法如下：对所有的规则产生式A→x：(1)若x不能推出空字，则SELECT(A→x)=FIRST(x)；(2)若x可推出空字，则SELECT(A→x)=FIRST(x)–{}FOLLOW(A)。算法描述如下：for(i=0;i=产生式总数-1;i++)先把当前产生式右部的FIRST集(一切非空元素,不包括ε)放入到当前产生式的SELECT(i);if产生式右部符号串可推出空字then把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT(i)中5.判断是否LL(1)文法要判断是否为LL(1)文法，需要输入的文法G有如下要求：具有相同左部的规则的SELECT集两两不相交，即：SELECT(A→)∩SELECT(A→)=如果输入的文法都符合以上的要求，则该文法可以用LL(1)方法分析。算法描述如下：把第一条产生式的SELECT(0)集放到一个临时数组temp[]中for(i=1;i=产生式总数-1;i++)求temp的长度lengthifi指向的当前产生式的左部等于上一条产生式的左部then把SELECT(i)并入到temp数组中Iftemp的长度小于length加上SELECT(i)的长度返回0else把temp清空把SELECT(i)存放到temp中结果返回1；四、算法#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集合charfirstflag[50],followflag[50];//记录各符号的FIRST和FOLLOW是否已求过charempty[20];//记录可推出&的符号charnonempty[20];//记录不可推出&的符号charempt[20];//求_emp()时使用charTEMP[50];//求FOLLOW时存放某一符号串的FIRST集合intvalidity=1;//表示输入文法是否有效intll=1;//表示输入文法是否为LL(1)文法intM[20][20];//分析表charchoose;//用户输入时使用charfoll[20];//求FOLLOW集合时使用/*******************************************判断一个字符c是否在指定字符串p中********************************************/intin(charc,char*p){inti;if(strlen(p)==0)return(0);for(i=0;;i++){if(p[i]==c)return(1);//若在，返回1if(i==(int)strlen(p))return(0);//若不在，返回0}}/*******************************************将单个符号或符号串并入另一符号串********************************************/voidmerge(char*d,char*s,inttype){//是目标符号串，s是源串，type＝1，源串中的'&'一并并入目串；//type＝2，源串中的'&'不并入目串inti,j;for(i=0;i=(int)strlen(s)-1;i++){if(type==2&&s[i]=='&');else{for(j=0;;j++){if(j(int)strlen(d)&&s[i]==d[j])break;//若已存在，则退出，继续看下一个源串字符if(j==(int)strlen(d))//若不存在，则并入{d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************读入一个文法********************************************/chargrammer(char*t,char*n,char*left,charright[50][50]){charvn[50],vt[50];chars;charp[50][50];inti,j;printf(请输入文法的非终结符号串：);s