编译原理大作业.doc

1、课程论文递归下降分析器的实现课程名称所属学院班级学生姓名学号二零一四年十二月目录1、递归下降分析器的设计思想. 11.1 自顶向下的语法分析方法 . 11.2 递归下降分析法 . 11.3 递归下降分器意义： . 11.4 递归下降分析器思想： . 11.5 递归下降分析器的作用： . 21.6 递归下降分析器的形成过程： . 22、递归向下分析器实现. 22.2 待分析的简单词法 . 22.3 要求构造的递归下降程序 . 32.4 主函数分析 . 33、输入串运行分析：. 44、关键代码分析及运行过程：. 54.1 关键代码分析 . 54.2 文法函数调用过程 . 65、程序测试：. 75.

2、1、当程序运行时出现如下输入程序界面. 75.2、当程序运行时出现如下输入程序界面. 7总结 . 8参考文献：. 9附录： . 10信息工程学院编译原理课程论文递归下降分析器的实现摘要：本文分析了递归下降分析器的实现以及具体的功能，所谓递归下降分析法，就是对文法中的每个非终结符编写一个函数（子程序），每个函数（子程序）的功能是识别由该非终结符所标示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（子程序）一定是相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。关键词：递归下降分析器消除递归非终结符1、递归下降分析器的设计思想1.1 自顶向下的语法分析方法自顶向下分

3、析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下的确定分析方法需对文法有一定的限制，但由于实现方法简答、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。而自顶向下的不确定分析方法是带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。1.2 递归下降分析法递归下降分析法是确定的自上而下分析法，它要求文法是 LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成

4、分。并且由递归下降分析法，得出了递归下降分析器。1.3 递归下降分器意义：递归下降分析器，可以使已经消除左递归，回溯的文法，迅速判断出输入串是否满足该文法，并按照递归的方法，算出终结符,此分析器解决的手工计算繁琐问题。1.4 递归下降分析器思想：递归下降分析法是一种自顶向下的分析法，文法中的每一个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），第 1 页 共 12 页信息工程学院编译原理课程论文这样向下推到直到推出句子；或者是从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一个语法树。1.5 递归下降分析器的作用：（1）读入输入的符号串；（2）对

5、输入的符号串逐个与栈中的终结符比较；（3）识别出匹配的输入字符；（4）确定文法是否能推导出输入串1.6 递归下降分析器的形成过程：实现递归下降分析器，首先要消除产生式的左递归，其次要消除产生式的回溯，得到可以编写递归下降分析器的文法如（图 1）开始输入串进入消除左递归消除回溯根据文法编写递归下降分析器否通过递归下降分析器确定输入串是否正确是结束图 1 递归下降分析器形成过程2、递归向下分析器实现2.2 待分析的简单词法第 2 页 共 12 页信息工程学院编译原理课程论文（1）非终结符：EE TTF(代码中 T用 T1 代替) (代码中 E用 E1 代替)（2）终结符+* （ ） i2.3 要求

6、构造的递归下降程序文法 GE:E-E+T|TT-T*F|FF-(E)|i首先，消除该文法的左递归，得到文法 GE:E-TEE-+TE|T-FTT-*FT|F-(E)|i然后，根据 LL(1)文法的判断条件，对非终结符 S 和 T的不同产生式的集进行考察，经验证改进后的文法已经是 LL(1)文法。最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。（非终结符在这里统称为 A）输入的字符串以#结束。（1）当遇到终结符 a 时，则编写语句If(当前读到的输入符号=a)读入下一个输入符号（2）当遇到非终结符 A 时，则编写语句调用 A()。（3）当遇到 A-

7、规则时，则编写语句。If(当前读到的输入符号不属于 Follow(A)error() (退出)。（4）当某个非终结符的规则有多个候选式时，按 LL(1)文法的条件能唯一地选择一个候选式进行推导。2.4 主函数分析第 3 页 共 12 页信息工程学院编译原理课程论文此文发一共可分为个函数，分别为 E(),E(),T(),T(),F(),其中在 E 函数中可调用 T(),E()两个函数。在 E()函数中可以判断输出串“+”，并调用 T （），E（）两个函数，在 T()函数中可以调用 F()，T()两个函数。在 T()函数中可以判断输入串“*”，并调用 F()和 T()两个函数。在 F()函数中可以

8、调用 E()函数并判断输入串“ (” ， “ )”，或判断输入串是否为“i”。通过递归调用实现进栈，匹配出栈，最终达到检测效果。3、输入串运行分析：当输入串为 i*(i+i)时，用栈的形式表现出运行过程以#为结束，首先将 E和分文法开始符 E 压入栈中，开始分析。首先将“#”和文法开始符 E 压入栈，可以从词条文法中的到终结符，并判断终结符是否与输入串的的字符相符合，如果符合出栈，并判断在栈中的下一个非终结符，在文法中找到对应的产生式，判断期栈顶的终结符是否与输入串一致，一致出栈，不一致则跳出，此文法无法得到输入串。如最后栈底剩“#“，并且输入串最后剩#，此输入串符合文法，语法分析成功如（图

9、2） 。第 4 页 共 12 页信息工程学院编译原理课程论文图 2 输入串运行分析在图中第五步执行函数 F（）时，因当前扫描的字符为“（”，所以匹配后应执行 E（）（用栈模型将 E 压栈）；并且；在执行完 E（）后还应执行其后的判断“）”与匹配“）”语句，这在栈的模拟中则是标出此时E 压栈之前的位置如图步骤（714）即出栈至此 14 步结束并执行这个判断“）”与匹配“）”语句。4、关键代码分析及运行过程：4.1 关键代码分析void E()/文法中调用 Eif(SIGN=0)T();/并在 E 中分别调用 TE1();/调用 Evoid E1()/进入 Eif(SIGN=0)if(si=+)/

10、判断输入串是否是非终结符+，如果是则出栈readin();T();/并继续调用 T 函数进入文法 T第 5 页 共 12 页信息工程学院编译原理课程论文E1();/出 T 函数进去 E中判断是否是else if(si!=#&si!=)printf(输入串字符不符合文法定义！n);SIGN=1;readin();void T()if(SIGN=0)F();T1();4.2 文法函数调用过程如（图 3）中用二叉树表示出递归下降分析器的递归过程，可得出详细的分析过程。ETE FT TE FT E图 3 文法函数调用过程第 6 页 共 12 页信息工程学院编译原理课程论文5、程序测试：5.1、当程序运

11、行时出现如下输入程序界面如（图 4） ， （ 图 5）所示时匹配成功：图 4 第一个输入串匹配图 5 第二个输入串匹配5.2、当程序运行时出现如下输入程序界面如（图 6）所示时匹配失败，文法无法得到输入串（）第 7 页 共 12 页信息工程学院编译原理课程论文图 6 匹配失败总结首先遇到的困难是对递归下降的分析法的不理解。虽然课上老师曾细致讲解过但还是生疏。所以，花费大量时间重新学习递归。重点回顾了进栈，匹配出栈等知识。让我更清楚的认识到自顶向下的语法分析并且清楚的知道了递归向下分析器的分析法的用法，加深了 C 语言编译器的用法，并更加清楚的熟练的运用了消除递归，和消除回溯的用法，并自己进行了

12、消除递归，消除回溯的计算。并运用了递归的方法实现了算法，我对语法分析有了深入的认识，并在最后对算法进行了改进，不结束程序的情况下继续分析。其次就是课程设计报告的书写。我也也需要很大的精力，查找资料，请教同学，强老师请求帮助。在对 word 的排版方面，有很多的细节需要认真注意。虽然已经对代码有了清楚的认识，但在论文方面还是遇到了很多问题，比如专业术语欠缺，分析不够详细，但是在我请教了吴刚老师后，对概念有了更加深刻的认识。自己独立完成课程设计，熟悉程序设计中出现的所有问题以及解决方案，这无疑加深了程序设计人员对设计的项目的印象，并重现拾起了很久不使用的 C 语言。为以后的的课程设计和大作业打下了

13、基础。第 8 页 共 12 页信息工程学院编译原理课程论文参考文献：1 张素琴等编著.编译原理M. 清华大学出版社, 20052 胡元义主编.编译原理教程M. 西安电子科技大学出版社, 20033 李文生编著.编译程序设计原理与技术M. 北京邮电大学出版社, 20024 程妍.编译原理实验教学体系综述与改革探讨J. 福建电脑. 2008(05)5 李峰.提高编译原理实验效果的实践J. 重庆三峡学院学报. 2007(03)第 9 页 共 12 页信息工程学院编译原理课程论文附录：#includevoid E();void T();void E1();void T1();void F();void

14、 readin();char s100;int i,SIGN,n;void main()n=1;while( n )printf(请输入一个语句，以#号结束语句n);SIGN = 0;i=0;scanf(%s,&s);if( s0 = #)printf(无语句输入n);continue;E();if(si=# & SIGN=0)printf(输入串正确，结束语句符号正确！n);else if(si=# & SIGN=1)printf(结束语句符号正确！n);elseprintf(结束语句符号不正确！n);printf(是否继续输入 1 为继续，0 为推出n);scanf(%d,&n);prin

15、tf(n);第 10 页 共 12 页信息工程学院编译原理课程论文void E()if(SIGN=0)T();E1();void E1()if(SIGN=0)if(si=+)readin();T();E1();else if(si!=#&si!=)printf(输入串字符不符合文法定义！n);SIGN=1;readin();void T()if(SIGN=0)F();T1();void T1()if(SIGN=0)if(si=*)readin();F();第 11 页 共 12 页信息工程学院编译原理课程论文T1();else if(si!=#&si!=)&si!=+)printf(输入串字符不符合文法定义！n);SIGN=1;void F()if(SIGN=0)if(si=()readin();E();if(si=)readin();else if(si= #)printf(输入串字符不符合文法定义！n);SIGN=1;readin();else if(si=i)readin();elseprintf(输入串字符不符合文法定义！n);readin();SIGN=1;void readin()i+;第 12 页 共 12 页