课程设计（论文）-语法分析器的实现.doc

目录1语法分析方法11.1 实验内容11.2 语法分析器的实现21.3 语法分析的程序流程图22程序设计32.1 总体设计32.2 子程序设计83程序中的结构说明103.1 重要函数介绍及函数代码104程序测试294.1 程序测试截图：295 实验总结311语法分析方法1.1 实验内容语法分析程序用ll(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用ll(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的first集合，每个非终结符号的follow集合，以及每个规则的select集合，并判断任意一个非终结符号的任意两个规则的select集的交集是不是都为空，如果是，则输入文法符合ll(1)文法，可以进行分析。题目：已知文法gs：smh|a hlso| kdml| lehf mk|blm判断g 是否是ll(1)文法。解：文法展开为：0） sm h1） sa2） hl s o3） h4） kd m l5） k6） le h f7） mk8） mb l m非终结符first 集follow 集sa,d,b,e#,omd,b.e,#,oh,e. #,f,o.le.a,d,b,e,o,#kd,.e,#,o.对相同左部的产生式可知：select(sm h)select(sa) = d,b ,e，#,o a =空集select(hl s o)select(h) = e #,f,o =空集select(kd m l)select(k) = d e,#,o =空集select(mk)select(mb l m) = d，e,#,o b =空集所以文法是ll(1)的。1.2 语法分析器的实现语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的ll(1)分析方法。该程序可分为如下几步：（1）读入文法 （2）判断正误 （3）若无误，判断是否为ll(1)文法 （4）若是，构造分析表；（5）由句型判别算法判断输入符号串是为该文法的句型。1.3 语法分析的程序流程图开 始读入文法有效？是ll（1）文法？判断句型报错结 束2程序设计 2.1 总体设计2.1.1 求能推出空的非终结符集、实例中求直接推出空的empty集的算法描述如下：void emp(char c) 参数c为空符号 char temp10;定义临时数组int i;for(i=0;ib,b可推出空)if 右部长度为1但第一个字符为终结符,then 返回0(a-a,a为终结符)else for(k=0;kab)if 找到的字符与当前字符相同(a-ab)结束本次循环else(mark等于0)查找右部符号是否可推出空字,把返回值赋给result 把当前符号加入到临时数组empt里.if 当前字符不能推出空字且还没搜索完全部的产生式then 跳出本次循环继续搜索下一条产生式else if /当前字符可推出空字,返回12.1.2 计算每个符号的first集：实例中求单个符号的first集的算法描述如下：void first2 (int i) 参数i为符号在所有输入符号中的序号c等于指示器i所指向的符号在保存终结符元素的termin数组查找cif c为终结符(cvt )，then first(c)=c在保存终结符元素的non_ter数组查找cif c是非终结符(cvn )在所有产生式中查找c所在的产生式if 产生式右部第一个字符为终结符或空(即ca (avt)或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当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为cy1y2yk,若对一切1=i=k，均有&first(yi)，则将&符号加进first(c) ) then把空字加入到当前字符c的first集.else不能推出空字则结束循环标识当前字符c已查找其first集. 2.1.3 计算follow集follow集的构造可用如下方法来求：对于文法中的符号x vn ，其follow(a)集合可反复应用下列规则计算，直到follow(a)集合不再增大为止。(1)对于文法开始符号s，因为ss，故#follow(s)；(2)若aa bb，其中bvn，a(vt uvn)*、b(vt uvn)+，则first(b)-efollow(b)；(3)若aa b或aa bb (b e)，则follow(a) follow(b)。follow集的算法描述如下：void follow(int i)x为待求的非终结符把当前字符放到一临时数组foll中,标识求已求其follow集.避免循环递归if x为开始符号 then #follow(x)对全部的产生式找一个右部含有当前字符x的产生式注：比如求follow(b)则找ax或aaxb(b)的产生式if x在产生式右部的最后(形如产生式aax) then查找非终结符a是否已经求过其follow集.避免循环递归if 非终结符a已求过其follow集 thenfollow(a)follow(x)继续查下一条产生式是否含有xelse求a之follow集，并标识为a已求其follow集else if x不在产生式右部的最后(形如aabb) thenif右部x后面的符号串b能推出空字e then查找b是否已经求过其follow集.避免循环递归if 已求过b的follow集 then follow(a)follow(b)结束本次循环else if b不能推出空字 then 求first(b)把first(b)中所有非空元素加入到follow(b)中标识当前要求的非终结符x的follow集已求过2.1.4 计算select集select集的构造算法如下：对所有的规则产生式ax：(1)若x不能推出空字e，则select(ax) = first(x)；(2)若x可推出空字e，则select(ax)=first(x)e u follow(a)。算法描述如下： for(i=0;i=产生式总数-1;i+)先把当前产生式右部的first集(一切非空元素,不包括)放入到当前产生式的select(i);if 产生式右部符号串可推出空字e then把i指向的当前产生式左部的非终结符号的follow集并入到select(i)中2.1.5 判断是否ll(1)文法要判断是否为ll(1)文法，需要输入的文法g有如下要求：具有相同左部的规则的select集两两不相交，即：select(aa) select(ab)= 如果输入的文法都符合以上的要求，则该文法可以用ll(1)方法分析。算法描述如下：把第一条产生式的select(0)集放到一个临时数组temp中for(i=1;i=产生式总数-1;i+) 求temp的长度lengthif i指向的当前产生式的左部等于上一条产生式的左部 then把select(i)并入到temp数组中if temp的长度小于length加上select (i)的长度返回0else把temp清空把select (i)存放到temp中结果返回1；2.2 子程序设计2.2.1 first：2.2.2 follow：2.2.3 主函数：3程序中的结构说明3.1 重要函数介绍及函数代码3.1.1 读入一个文法:char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j;printf(请输入文法的非终结符号串：); scanf(%s,vn);getchar(); i=strlen(vn); memcpy(n,vn,i);ni=0;printf(请输入文法的终结符号串：); scanf(%s,vt);getchar(); i=strlen(vt); memcpy(t,vt,i);ti=0; printf(请输入文法的开始符号：);scanf(%c,&s);getchar();printf(请输入文法产生式的条数：); scanf(%d,&i);getchar();count=i; for(j=1;j=i;j+)printf(请输入文法的第%d条（共%d条）产生式：,j,i);scanf(%s,pj-1); getchar(); for(j=0;j) /检测输入错误 printf(n输入错误!);validity=0;return(0); return(s);3.1.2 判断读入的文法是否正确:int judge() int i,j;for(i=0;i=count-1;i+)if(in(lefti,non_ter)=0) /若左部不在非终结符中，报错printf(n文法左部出错!);validity=0;return(0);for(j=0;j=(int)strlen(righti)-1;j+)if(in(rightij,non_ter)=0&in(rightij,termin)=0&rightij!=&) /若右部某一符号不在非终结符、终结符中且不为&，报错printf(n文法右部出错!);validity=0;return(0);return(1);3.1.3 求单个符号的first:void first2(int i) /i为符号在所有输入符号中的序号 char c,temp20;int j,k,m;char ch=&;c=vi;emp(ch);/求所有能直接推出空字的符号,结果保存到empty中if(in(c,termin)=1) /若为终结符-cvt，则first(c)=c first1i0=c;first1i1=0; else if(in(c,non_ter)=1) /若为非终结符for(j=0;j=count-1;j+) /j为所有产生式中的序列 if(leftj=c) /找一个左部为c的产生式if(in(rightj0,termin)=1|rightj0=&)/若产生式右部第一个字符为终结符或空.-产生式xa (avt)或x&,则把a或&加进first(x) temp0=rightj0;temp1=0;merge(first1i,temp,1); /-xy1y2yk的产生式，若y1vn，则把first(y1)中的一切非空符号加进first(x)else if(in(rightj0,non_ter)=1)/产生式右部第一个字符为非终结符if(rightj0=c)/产生式右部的第一个符号等于当前字符,则跳到下一条产生式进行查找continue;for(k=0;k+)if(vk=rightj0)/求右部第一个字符在所有字符集中的位置kbreak;if(firstflagk=0) first2(k);/求其first集firstflagk=1;/标识其为查找状态merge(first1i,first1k,2);/求得结果并入到x的first集.for(k=0;k(int)strlen(rightj);k+)empt0=0;/存放到一个临时数组里,标识此字符已查找其是否可推出空字if(_emp(rightjk)=1&k(int)strlen(rightj)-1)/当前产生式右部符号可推出空字,且当前字符不是右部的最后一个字符for(m=0;m+)if(vm=rightjk+1)/获取右部符号下一个字符在所有字符集中的位置break;if(firstflagm=0)/如果此字符的first集还未查找,则找其first集,并标其查找状态为1first2(m);firstflagm=1;merge(first1i,first1m,2);/把求得结果并入到x的first集./-产生式为xy1y2yk,若对一切1=i=0)/i不为-1时是产生式的序号 firsti0=&;/把&加入到当前符号串的first集firsti1=0;else/i为-1时,表示求follow时用到的产生式右部的first集,保存在temp中temp0=&;temp1=0;else/右部符号串字符不为&空字 for(j=0;j+)if(vj=p0)/求右部符号的第一个字符p0在所有字符集中的位置jbreak;if(i=0)memcpy(firsti,first1j,strlen(first1j);/把j所指向的单个符号的first集拷贝到该右部符号串的first集firstistrlen(first1j)=0;elsememcpy(temp,first1j,strlen(first1j);tempstrlen(first1j)=0; else /如果右部为符号串for(j=0;j+)if(vj=p0)/求右部符号的第一个字符p0在所有字符集中的位置jbreak;if(i=0)merge(firsti,first1j,2);elsemerge(temp,first1j,2);for(k=0;k=length-1;k+)empt0=0;if(_emp(pk)=1&k=0)merge(firsti,first1m,2);elsemerge(temp,first1m,2);else if(_emp(pk)=1&k=length-1)/当前右部符号串可推出空且是右部符号串的最后一个字符temp0=&;temp1=0;if(i=0)merge(firsti,temp,1); elsemerge(temp,temp,1);else if(_emp(pk)=0)break;3.1.5 求各产生式左部的follow:void follow(int i) /参数i为该符号在非终结符中的位置int j,k,m,n,result=1;char c,temp20;c=non_teri; /c为待求的非终结符temp0=c;temp1=0;merge(foll,temp,1);/把当前字符放到一临时数组foll中,标识求已求其follow集.避免循环递归if(c=start) /若为开始符号-开始符号s，则#follow(s)temp0=#;temp1=0;merge(followi,temp,1); for(j=0;j*&)的产生式for(k=0;k+)if(rightjk=c)break; /k为c在该产生式右部的序号,如b在产生式ab中的位置 for(m=0;m+)if(vm=leftj)break; /m为产生式左部非终结符在所有符号中的序号/如果c在产生式右部的最后,形如产生式ab,则follow(a)follow(b)if(k=(int)strlen(rightj)-1) if(in(vm,foll)=1)/查找该非终结符是否已经求过其follow集.避免循环递归/是则follow(a)follow(b)merge(followi,followm,1);/把c所在产生式的左部非终结符的follow集加入到follow(c)中continue;/结束本次循环,进入j+循环 if(followflagm=0)/如果该非终结符的follow未求过follow(m);/求之follow集followflagm=1;/标识为1merge(followi,followm,1);/follow(a)follow(b)else /如果c不在产生式右部的最后,形如abfor(n=k+1;n*&)则follow(a)follow(b) if(in(vm,foll)=1) /查找该非终结符是否已经求过其follow集.避免循环递归merge(followi,followm,1);/follow(a)follow(b)continue;if(followflagm=0)follow(m);followflagm=1;merge(followi,followm,1);/若ab，其中bvn，(vt u vn)*、(vt u vn)+，则first()-follow(b)；for(n=k+1;n=(int)strlen(rightj)-1;n+) tempn-k-1=rightjn; tempstrlen(rightj)-k-1=0;first(-1,temp);/求first()merge(followi,temp,2);/把first()中所有非空元素加入到follow(b)中followflagi=1;/标识当前要求的非终结符的follow集已求过3.1.6 判断读入文法是否为一个ll(1)文法:int ll1() int i,j,length,result=1;char temp50;for(j=0;j=49;j+) /初始化firstj0=0; followj0=0;first1j0=0;selectj0=0;tempj=0;tempj=0;firstflagj=0;/用来记录该字符的first集是否已求过.1表示已求,0表示未求followflagj=0;/用来记录该字符的follow集是否已求过.1表示已求,0表示未求for(j=0;j=(int)strlen(v)-1;j+)first2(j); /求单个符号的first集合,结果保存在first1里printf(n各非终结符推出的first集:n);for(j=0;j=(int)strlen(v)-1;j+)printf(%c:%s ,vj,first1j); printf(n能导空的非终结符集合:%s,empty);printf(n_emp:);for(j=0;j=(int)strlen(v)-1;j+)printf(%d ,_emp(vj);for(i=0;i=count-1;i+)first(i,righti); /求firstfor(j=0;j=(int)strlen(non_ter)-1;j+) /求followif(follj=0)foll0=0;follow(j); printf(nfirst集:);for(i=0;i=count-1;i+)printf(%s ,firsti);printf(nfollow集合:); for(i=0;i=(int)strlen(non_ter)-1;i+)printf(%s ,followi);for(i=0;i=count-1;i+) /求每一产生式的select集合 memcpy(selecti,firsti,strlen(firsti);/first存放的是各产生式右部的first集 selectistrlen(firsti)=0;for(j=0;j&result=1;if(result=1) for(j=0;j+)if(vj=lefti)/j为左部符号在所有字符集中的位置break;merge(selecti,followj,1);printf(nselect集合顺序是:);for(i=0;i=count-1;i+)printf(%s ,selecti);memcpy(temp,select0,strlen(