编译原理大作业详解.doc

课程论文 递归下降分析器的实现 课程名称 所属学院 班 级 学生姓名 学 号 二零一四年十二月 目录 1、递归下降分析器的设计思想 1 1.1自顶向下的语法分析方法 1 1.2递归下降分析法 1 1.3递归下降分器意义： 1 1.4递归下降分析器思想： 1 1.5递归下降分析器的作用： 1 1.6递归下降分析器的形成过程： 2 2、递归向下分析器实现 2 2.2待分析的简单词法 2 2.3要求构造的递归下降程序 3 2.4主函数分析 3 3、输入串运行分析： 4 4、关键代码分析及运行过程： 5 4.1关键代码分析 5 4.2文法函数调用过程 6 5、程序测试： 6 5.1、当程序运行时出现如下输入程序界面 6 5.2、当程序运行时出现如下输入程序界面 7 总结 8 参考文献： 8 附录： 9 递归下降分析器的实现 摘要：本文分析了递归下降分析器的实现以及具体的功能，所谓递归下降分析法，就是对文法中的每个非终结符编写一个函数（子程序），每个函数（子程序）的功能是识别由该非终结符所标示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（子程序）一定是相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。 关键词：递归下降分析器 消除递归 非终结符 1、递归下降分析器的设计思想 1.1自顶向下的语法分析方法 自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下的确定分析方法需对文法有一定的限制，但由于实现方法简答、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。而自顶向下的不确定分析方法是带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。 1.2递归下降分析法 递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。并且由递归下降分析法，得出了递归下降分析器。 1.3递归下降分器意义： 递归下降分析器，可以使已经消除左递归，回溯的文法，迅速判断出输入串是否满足该文法，并按照递归的方法，算出终结符,此分析器解决的手工计算繁琐问题。 1.4递归下降分析器思想： 递归下降分析法是一种自顶向下的分析法，文法中的每一个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推到直到推出句子；或者是从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一个语法树。 1.5递归下降分析器的作用： （1）读入输入的符号串； （2）对输入的符号串逐个与栈中的终结符比较； （3）识别出匹配的输入字符； （4）确定文法是否能推导出输入串 1.6递归下降分析器的形成过程： 实现递归下降分析器，首先要消除产生式的左递归，其次要消除产生式的回溯，得到可以编写递归下降分析器的文法如（图1） 图1递归下降分析器形成过程 2、递归向下分析器实现 2.2待分析的简单词法 （1）非终结符： E E’ T T’F (代码中T’用T1代替) (代码中E’用E1代替) （2）终结符 + * （ ） i 2.3要求构造的递归下降程序 文法G[E]: E--E+T|T T--T*F|F F--(E)|i 首先，消除该文法的左递归，得到文法G’[E]: E--TE E--+TE|ε T--FT T--*FT|ε F--(E)|i 然后，根据LL(1)文法的判断条件，对非终结符S和T’的不同产生式的集进行考察，经验证改进后的文法已经是LL(1)文法。 最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。（非终结符在这里统称为A） 输入的字符串以#结束。 （1）当遇到终结符a时，则编写语句 If(当前读到的输入符号==a)读入下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A()。 （3）当遇到A--ε规则时，则编写语句。If(当前读到的输入符号不属于Follow(A))error() (退出)。 （4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。 2.4主函数分析 此文发一共可分为个函数，分别为E(),E’(),T(),T’(),F(),其中在E函数中可调用T(),E()两个函数。在E’()函数中可以判断输出串“+”，并调用