编译原理大作业

课程论文二零一四年十二月目录1、递归下降分析器的设计思想11.1自顶向下的语法分析方法11.2递归下降分析法11.3递归下降分器意义：11.4递归下降分析器思想：11.5递归下降分析器的作用：11.6递归下降分析器的形成过程：22、递归向下分析器实现22.2待分析的简单词法22.3要求构造的递归下降程序32.4主函数分析33、输入串运行分析：44、关键代码分析及运行过程：54.1关键代码分析54.2文法函数调用过程65、程序测试：65.1、当程序运行时出现如下输入程序界面65.2、当程序运行时出现如下输入程序界面7总结8摘要：本文分析了递归下降分析器的实现以及具体的功能，所谓递归下降分析法，就是对文法中的每个非终结符编写一个函数（子程序），每个函数（子程序）的功能是识别由该非终结符所标示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（子程序）一定是相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。关键词：递归下降分析器消除递归非终结符1、递归下降分析器的设计思想1.1自顶向下的语法分析方法自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下的确定分析方法需对文法有一定的限制，但由于实现方法简答、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。而自顶向下的不确定分析方法是带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。1.2递归下降分析法递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。并且由递归下降分析法，得出了递归下降分析器。1.3递归下降分器意义：递归下降分析器，可以使已经消除左递归，回溯的文法，迅速判断出输入串是否满足该文法，并按照递归的方法，算出终结符,此分析器解决的手工计算繁琐问题。1.4递归下降分析器思想：递归下降分析法是一种自顶向下的分析法，文法中的每一个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推到直到推出句子；或者是从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一个语法树。实现递归下降分析器，首先要消除产生式的左递归，其次要消除产生式的回溯，得到可以编写递归下降分析器的文法如（图1）图1递归下降分析器形成过程2、递归向下分析器实现2.2待分析的简单词法（1）非终结符： EE’TT’F(代码中T’用T1代替)(代码中E’用E1代替)（2）终结符 +*（）i2.3要求构造的递归下降程序文法G[E]:E-->E+T|TT-->T*F|FF-->(E)|i首先，消除该文法的左递归，得到文法G’[E]:E-->TE'E'-->+TE'|εT-->FT'T'-->*FT'|εF-->(E)|i然后，根据LL(1)文法的判断条件，对非终结符S和T’的不同产生式的集进行考察，经验证改进后的文法已经是LL(1)文法。（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’()函数中可以判断输出串“+”，并调用T（），E'（）两个函数，在T()函数中可以调用F()，T’()两个函数。在T'()函数中可以判断输入串“*”，并调用F()和T’()两个函数。在F()函数中可以调用E()函数并判断输入串“(”，“)”，或判断输入串是否为“i”。通过递归调用实现进栈，匹配出栈，最终达到检测效果。3、输入串运行分析：当输入串为i*(i+i)时，用栈的形式表现出运行过程以#为结束，首先将E和分文法开始符E压入栈中，开始分析。首先将“#”和文法开始符E压入栈，可以从词条文法中的到终结符，并判断终结符是否与输入串的的字符相符合，如果符合出栈，并判断在栈中的下一个非终结符，在文法中找到对应的产生式，判断期栈顶的终结符是否与输入串一致，一致出栈，不一致则跳出，此文法无法得到输入串。如最后栈底剩“#“，并且输入串最后剩#，此输入串符合文法，语法分析成功如（图2）。图2输入串运行分析在图中第五步执行函数F（）时，因当前扫描的字符为“（”，所以匹配后应执行E（）（用栈模型将E压栈）；并且；在执行完E（）后还应执行其后的判断“）”与匹配“）”语句，这在栈的模拟中则是标出此时E压栈之前的位置如图步voidE()//文法中调用E{if(SIGN==0){T();//并在E中分别调用TE1();//调用E’}}voidE1()//进入E’{if(SIGN==0){if(s[i]=='+')//判断输入串是否是非终结符+，如果是则出栈{readin();T();//并继续调用T函数进入文法TE1(); //出T函数进去E’中判断是否是}elseif(s[i]!='#'&&s[i]!=')'){printf("输入串字符不符合文法定义！\n");SIGN=1;readin();}}}F();T1();}}4.2文法函数调用过程如（图3）中用二叉树表示出递归下降分析器的递归过程，可得出详细的分析过程。图3文法函数调用过程5、程序测试：5.1、当程序运行时出现如下输入程序界面如（图4），（图5）所示时匹配成功：图4第一个输入串匹配图5第二个输入串匹配5.2、当程序运行时出现如下输入程序界面如（图6）所示时匹配失败，文法无法得到输入串（）图6匹配失败总结首先遇到的困难是对递归下降的分析法的不理解。虽然课上老师曾细致讲解过但还是生疏。所以，花费大量时间重新学习递归。重点回顾了进栈，匹配出栈等知识。让我更清楚的认识到自顶向下的语法分析并且清楚的知道了递归向下分析器的分析法的用法，加深了C语言编译器的用法，并更加清楚的熟练的运用了消除递归，和消除回溯的用法，并自己进行了消除递归，消除回溯的计算。并运用了递归的方法实现了算法，我对语法分析有了深入的认识，并在最后对算法进行了改进，不结束程序的情况下继续分析。其次就是课程设计报告的书写。我也也需要很大的精力，查找资料，请教同学，强老师请求帮助。在对word的排版参考文献：[1]张素琴等编著.编译原理[M].清华大学出版社,2005[2]胡元义主编.编译原理教程[M].西安电子科技大学出版社,2003[3]李文生编著.编译程序设计原理与技术[M].北京邮电大学出版社,2002[4]程妍.《编译原理》实验教学体系综述与改革探讨[J].福建电脑.2023(05)[5]李峰.提高《编译原理》实验效果的实践[J].重庆三峡学院学报.2007(03)附录：#include<stdio.h>voidE();voidT();voidE1();voidT1();voidF();voidreadin();chars[100];inti,SIGN,n;voidmain(){n=1;while(n){printf("请输入一个语句，以#号结束语句\n");SIGN=0;i=0;scanf("%s",&s);if(s[0]=='#'){printf("无语句输入\n");continue;}E();if(s[i]=='#'&&SIGN==0)printf("输入串正确，结束语句符号正确！\n");}}voidE(){if(SIGN==0){T();E1();}}voidE1(){if(SIGN==0){if(s[i]=='+'){readin();T();E1();}elseif(s[i]!='#'&&s[i]!=')'){printf("输入串字符不符合文法定义！\n");SIGN=1;readin();}}}voidT(){if(SIGN==