编译原理语法分析实验报告.docx

编译原理实验报告实验名称：编写语法分析程序 实验类型：设计性实验 指导教师：蒋 勇 专业班级：软件工程1401 姓 名：* 学 号：* 实验地点：东六E座301 实验成绩：_ 日期： 2016年5月17日实验一编写词法分析程序一、 实验目的：1. 设计、编写、调试一个递归下降分析程序，实现对词法分析程序提供的单词序列进行语法检查和结构分析。2. 掌握递归下降语法分析方法。3. 巩固理论知识。二、 实验设计：1. 设计原理：1) 对于文法的每一个非终结符U的文法规则是一个识别U的过程定义，为每一个非终结符构造子程序。2) 如果U的右部符号串只有一个候选式则从左到右依次构造U的识别代码。3) 如果U的右部符号串有终结符号，则判断输入的符号是否匹配终结符号，如果相等，则读入下一个符号；如果不相等，则有语法错误，应当报错。4) 如果是非终结符号，则调用非终结符号的子程序即可。5) 如果U的右部有多个候选式，应该根据每个候选式的第一个符号来确定该分支。6) 对于含有表达式的文法规则需要判断输入的符号是否在U的FOLLOW集里面。2. 设计方法：(1) 文法改造，消除二义性；(2) 对含有左递归或者左公因子的文法消除左递归，提取左公因子；(3) 求每一个右部符号串的FIRST集合，如果右部含有，则需要求出其产生式左部非终结符的FOLLOW集。判断文法是否是LL（1）文法，若不是LL(1)文法，说明文法的复杂性超过自顶向下方法的分析能力。(4) 根据改写后的文法设计程序，依据设计原理构造每一个非终结符的子程序。3. 设计过程：(1) 改写文法、消除左递归（将左递归改为右递归）、提取左公因子；(2) 求出相应的First集和Follow集；(3) 设计程序流程图，设计程序；(4) 编写程序；4. 框架思路，错误信息输出：对每一个非终结符构造其子程序，设定一个返回值。如果语法分析有错则返回1，没有错误就返回0；对于错误，在程序的相应行数报错。各个非终结符之间依据文法规则调用。每次遇到终结符函数都判断是否匹配当前终结符号，如果不匹配则报错，返回1。如果匹配，则读入下一个符号。三、 实验过程(一) 本次实验的TEST语言语法规则：1) 2) | 3) int ID;4) | 5) | | |6) if () | if () else 7) while () 8) for (;)9) write ;10) read ID;11)12);|;13) ID=|14) |(|=|=|=|!=) 15)+|-| 16)*|/|17)()|ID|NUM1. 将左递归改为右递归：2) | 改写后：:=:=|4) | 改写后：:=:=|15)+|-|改写后：:=:=+|-|16)*|/|改写后：:=:=*|/|2. 提取公因式：14) |(|=|=|=|!=)改写后： := :=|(|=|=|=|!=)3. 是否可以提取公因式6) if () | if () else 不可以提取公因式，if语句和ifelse语句是相互独立的,并没有必然的联系。 4规则13超前读入符号解决方案：如果识别出标识符的符号ID后，在读入一个符号，如果这个符号时=，说明选择的是赋值表达式，如果不是=，则说明选择是布尔表达式。(二) 、求出右部符号串的FIRST集和含有产生式的左部非终结符的FOLLOW集1)FIRST() = ;2) :=:=|FIRST() = int, ;FIRST() = int ;FOLLOW() = if,while,for,read,write,;,ID,(,NUM;3) int ID;FIRST(int ID;) = int ;4):=:=|FIRST() = if,while,for,read,write,;,ID,NUM,(;FIRST() = if,while,for,read,write,;,ID,NUM,(;FOLLOW() = ;5) | |FIRST() = if;FIRST()= whileFIRST() = forFIRST() = read;FIRST() = writeFIRST()=FIRST()=ID,NUM,;,(6) if () | if () else FIRST(if () ) = ifFIRST(if () else )=if7) while () FIRST(while () ) = while8) for (;)FIRST(for (;) = for9) write ;FIRST(write ;) = write10) read ID;FIRST(read ID;) = read11)FIRST() = 12);|;FIRST(;) = (,ID,NUM;FIRST(;) = ;13) ID=|FIRST(ID=) = ID;FIRST() = ID,NUM,(;14) |(|=|=|=|!=) := :=|(|=|=|=|!=)FIRST()=（，ID，NUMFIRST(|=|=|=|!=)=,=,=,=,!=FOLLOW()=),;15)+|-|:=:=+|-|FIRST()= (,ID,NUM FIRST(+)=+FIRST(-)=-FOLLOW()=,=,=,=,!=,;,)16)*|/|:=:=*|/|FIRST() = (,ID,NUM;FIRST(*)=*;FIRST(/)=/;FOLLOW() = +,-,;,=,=,=,!=17)()|ID|NUMFIRST()= (:FIRST(ID) =ID;FIRST(NUM) = NUM;(三) 、程序流程图(四) 、程序流程图四、 试验调试记录：1、问题表现：当语法分析到最后一行时进入死循环。分析原因：可能是文件没有结束条件，导致一直读取文件最后一个字符解决方案：经过百度发现fscanf()具有返回值，如果不为空返回1，为空则返回0。在文件结束时，它会默认将文件最后一个字符继续读入。程序就进入了死循环。 所以在每次读取文件是都判断fscanf()是否小于等于0，如果成立，则把读入的字符数组置为空。解决结果：读到最后一行时没有进入死循环。成功解决问题。2、问题表现：读到第5行时缺少； 按照常理应该在这一行报错。但是确报错在第6行。分析原因：因为第5行读到c时匹配，这个时候就继续读入下一个字符，但是这个字符是在下一行的for，并不是；所以就在for所在的这一行报错。就显示的第6行有错误。解决方案：其实我觉得这是没有错误的，所以就没有处理这个问题。像codeblocks这个编译软件遇到这种问题也是在下一行报错。所以我没有改变这个报错模式。五、实验结果:1、测试数据：int a;int i;int 2b;int cfor (i=1; i = 10 i=i+1);a=a+ib=b*i;c=a+b;while(xb) read a;else write b;write c2、实验现象：运用实验一词法分析的结果进行语法分析1)、第一处错误：int 2b;将int 2b;改为int b;后2)、第二处错误：int c加上;后解决该行错误3)、第三处错误：for (i=1; i = 10 i=i+1)分析这个语句可以判断缺少一个 ；在10后面加上分号后解决该行错误4)、第四处错误：a = a + i在句末加上;后解决该行问题5)、第五处错误：while(x=)改为 while(x = i) 6)、第六处错误：C=a+b+(x*y;改为 C=a+b+(x*y);7)、第七处错误：write c改为 write c;8)、第八处错误：在程序末尾加上 9)、第九处错误：在程序结尾加上 后解决了所有语法问题六、讨论与分析1、TEST语言中不满足无回溯递归下降分析的语法规则有：第（2）、（4）、（14）、（15）、（16）这几个语法规则。解决方案：将第（2）、（4）、（15）、（16）这几条规则改为右递归；对第（14）条语法规则提取左公因子。2、不是所有文法都可以满足递归下降分析条件，如：GS:SAU|BRAaAU|bBaBR|bUcRd对于规则SAU|BR，因为FIRST(AU) FIRST(BR) ，所以该文法不是LL(1)文法。将A、B的产生式代入S的产生式,得到：SaAUU|bU|aBRR|bR，提取公因子后得到：Sa(AUU|BRR)|b(U|R)，令S1AUU|BRR,S2U|R，则得到如下文法：SaS1|bS2S1AUU|BRRS2U|RAaAU|bBaBR|bUcRd对于规则S1AUU|BRR,因为FIRST(AUU) FIRST(BRR) ,所以它不是LL(1)文法，无论重复多少次都不能把它变为LL（1）文法。3、改写文法有什么弊端？递归算法的实现效率低，处理能力相对有限，通用性差，难以自动生成。七、自我评价本次实验自我感觉良好，独立完成了程序。对于规则（13）我参考了教材71页的设计方法，但是这一页的这个程序存在着一个小错误。最终的测试结果和我预想的并没有差别。总的来说这是一次很有意义的实验。但是代码本身却可以有优化，我对每一个表达式都设置了返回值。所以遇到错误就会停止分析。不会一次性把所有错误都显示出来，需要改错后再运行词法分析，然后再语法分析。在这一点上是不人性化的。每一次实验都是对理论知识的复习和巩固。通过这一次试验我也发现了自身存在很多的不足。八、关键代码：/语法分析程序的入口int TESTgrammar() int flag = 0; if(file = fopen(scanout,r) = NULL) printf(nOpen file %s error!n,scanout); flag = 1; if(flag = 0) flag = program(); fclose(file); return flag;语法规则：int statement() int flag = 0; if(strcmp(buff_0,if) = 0) flag = if_stat(); else if(strcmp(buff_0,while) = 0) flag = while_stat(); else if(strcmp(buff_0,for) = 0) flag = for_stat(); else if(strcmp(buff_0,read) = 0) flag = read_stat(); else if(strcmp(buff_0,write) = 0) flag = write_stat(); else if(strcmp(buff_0,) = 0) flag = compound_stat(); else if(strcmp(buff_0,;) = 0) | (strcmp(buff_0,ID) = 0) |(strcmp(buff_0,NUM) = 0) | (strcmp(buff_0,() = 0) flag = expression_stat(); else printf(%dterror: expected reserved words nt or delimiter or ID or NUM before %sn,line,buff_1); return 1; return flag;对于改造文法列举其中一个：/* := |消除左递归后得到 := := |*/int declaration_list() int flag = 0; if(strcmp(buff_0,int) = 0) flag = declaration_list1(); return flag; else printf(%dterror: expected int before %sn,line,buff_1); return 1; /|int declaration_list1() int flag = 0; if(strcmp(buff_0,int) = 0) flag = declaration_stat(); if(flag 0) return 1; flag = declaration_list1(); return flag; else if(strcmp(buff_0,if) = 0 | strcmp(buff_0,while) = 0 | strcmp(buff_0,for) = 0 | strcmp(buff_0,read) = 0 | strcmp(buff_0,write) = 0 | strcmp(buff_0,) = 0 | strcmp(buff_0,) = 0 | strcmp(buff_0,;) = 0 | strcmp(buff_0,ID) = 0 | strcmp(buff_0,() = 0 | strcmp(buff_0,NUM) = 0 ) return 0; else printf(%dterror: expected reserved words nt or delimiter or digit before %sn,line,buff_1); return 1; 其余形式的列举factor表达式：/ := ()|ID|NUMint factor() int flag = 0; if(strcmp(buff_0,() = 0) Input_output();