《语法分析器实验报告》由会员分享,可在线阅读,更多相关《语法分析器实验报告(23页珍藏版)》请在金锄头文库上搜索。
1、语法分析器的设计实验报告一、实验内容语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析),先求出所输入的文法的每个非终结符是否能推出空,再分别计算非终结符号的FIRST集合,每个非终结符号的FOLLOW集合,以及每个规则的SELECT集合,并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空,如果是,则输入文法符合LL(1)文法,可以进行分析。对于文法:GE:E-E+T|TT-T*F|FF-i|(E)分析句子i+i*i是否符合文法。二、基本思想1、语法分析器实现语法分析是编译过程的核心部分,它的主要任务是按照程序的语法规则,从
2、由词法分析输出的源程序符号串中识别出各类语法成分,同时进行词法检查,为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。开始读入文法有效?判断句型报错结束语法分析程序流程图是LL(1) 文法?该程序可分为如下几步:(1)读入文法 (2)判断正误 (3)若无误,判断是否为LL(1)文法 (4)若是,构造分析表;(5)由句型判别算法判断输入符号串是为该文法的句型。三、核心思想该分析程序有15部分组成:(1)首先定义各种需要用到的常量和变量;(2)判断一个字符是否在指定字符串中;(3)读入一个文法;(4)将单个符号或符号串并入另一符号串;(5)求所有
3、能直接推出&的符号;(6)求某一符号能否推出 & ;(7)判断读入的文法是否正确;(8)求单个符号的FIRST;(9)求各产生式右部的FIRST;(10)求各产生式左部的FOLLOW;(11)判断读入文法是否为一个LL(1)文法;(12)构造分析表M;(13)句型判别算法;(14)一个用户调用函数;(15)主函数;下面是其中几部分程序段的算法思想:1、求能推出空的非终结符集、实例中求直接推出空的empty集的算法描述如下:void emp(char c) 参数c为空符号 char temp10;定义临时数组int i;for(i=0;iB,B可推出空)if 右部长度为1但第一个字符为终结符,t
4、hen 返回0(A-a,a为终结符)else for(k=0;kAB)if 找到的字符与当前字符相同(A-AB)结束本次循环else(mark等于0)查找右部符号是否可推出空字,把返回值赋给result 把当前符号加入到临时数组empt里.if 当前字符不能推出空字且还没搜索完全部的产生式then 跳出本次循环继续搜索下一条产生式else if /当前字符可推出空字,返回12、计算每个符号的first集:实例中求单个符号的FIRST集的算法描述如下:void first2 (int i) 参数i为符号在所有输入符号中的序号c等于指示器i所指向的符号在保存终结符元素的termin数组查找cif
5、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 当前产生式右部符号可推出空字且当前字符不是右
6、部的最后一个字符 then获取右部符号下一个字符在所有字符集中的位置if 此字符的FIRST集还未查找 then找其FIRST集,并标其查找状态为1把求得的FIRST集并入到c的FIRST集.if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为cY1Y2Yk,若对一切1=i=k,均有&FIRST(Yi),则将&符号加进FIRST(c) ) then把空字加入到当前字符c的FIRST集.else不能推出空字则结束循环标识当前字符c已查找其FIRST集. 3. 计算FOLLOW集FOLLOW集的构造可用如下方法来求:对于文法中的符号X VN ,其FOLLOW(A)集合可反复应用下列规
7、则计算,直到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)则找A
8、X或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
9、求FIRST(b)把FIRST(b)中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过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指向的当前产生式左部的非终结符号的FO
10、LLOW集并入到SELECT(i)中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)的长度返回
11、0else把temp清空把SELECT (i)存放到temp中结果返回1;四、算法#include#include#include/*/int count=0; /产生式的个数int number; /所有终结符和非终结符的总数char start; /开始符号char termin50; /终结符号char non_ter50; /非终结符号char v50; /所有符号char left50; /左部char right5050; /右部char first5050,follow5050; /各产生式右部的FIRST和左部的FOLLOW集合char first15050; /所有单个符号的FIRST集合char select5050; /各个产生式的SELECT集合char firstflag50,followflag50; /记录各符号的FIRST和FOLLOW是否已求过char empty20; /记录可推出&的符号char nonempty20; /记录不可推出&的符号char empt20; /求_emp()时使用char TEMP50; /求FOLLOW时存放某一符号串的FIRST集合int validity=1; /表示输入文法是否有效int ll=1;