编译原理大作业

课程论文递归下降分析器的实现课程名称所属学院班级学生姓名学号二零二二年十二月图第二个输入串匹配5当程序运行时浮现如下输入程序界面

5.

2.如（图）所示时匹配失败，文法无法得到输入串60图匹配失败6总结首先遇到的艰难是对递归下降的分析法的不理解虽然课上老师曾经细致讲解过但还是生疏所以，花费大量时间重新学习递归重点回顾了进栈，匹配出栈等知识让我更清晰的认识到自顶向下的语法分析并且清晰的知道了递归向下分析器的分析法的用法，加深了语言编译器的用法，并更加清晰的熟练的运用了消C除递归，和消除回溯的用法，并自己进行了消除递归，消除回溯的计算并运用了递归的方法实现了算法，我对语法分析有了深入的认识，并在最后对算法进行了改进，不结束程序的情况下继续分析其次就是课程设计报告的书写我也也需要很大的精力，查找资料，请教同学，强老师请求匡助在对的排版方面，word有不少的细节需要认真注意虽然已经对代码有了清晰的认识，但在论文方面还是遇到了不少问题，比如专业术语欠缺，分析不够详细，但是在我请教了吴刚老师后，对概念有了更加深刻的认识自己独立完成课程设计，熟悉程序设计中浮现的所有问题以及解决方案，这无疑加深了程序设计人员对设计的项目的印象，并重现拾起了很久不使用的语言为以后的的课程设计和大作业打下了基础C参考文献张素琴等编著.编译原理清华大学出版社,

[1][M].2005胡元义主编.编译原理教程西安电子科技大学出版社,

[2][M].203⑶李文生编著.编译程序设计原理与技术北京邮电大学出版社,[M].2002程妍.《编译原理》实验教学体系综述与改革探讨福建电脑.李

[4][J].202205

[5]峰.提高《编译原理》实验效果的实践.重庆三峡学院学报[J].202203附录#includestdio.hvoid E;void T;void El;voidTlQ;void F;void readin;char s[l];int i,SIGN,n;void mainn=l;while n请输入一个语句，以#号结束语句SIGN=0;i=0;if s

[0]==#{无语句输入continue;；Eif s[i]==#SIGN==0输入串正确，结束语句符号正确!else ifs[i]==,#1SIGN==1结束语句符号正确！else结束语句符号不正确！是否继续输入为继续，为推出10void EifSIGN==0{；T；Elvoid ElifSIGN==0ifs[i]==+readin;；T；Elelseifs[i]!=#,s[i]!=y输入串字符不符合文法定义!SIGN=1;readin;void TifSIGN==0{；F；Tlvoid T1ifSIGN=0{readin;；F；Tlelse ifs[i]!=#s[i]!=,,s[i]!=+,输入串字符不符合文法定义！SIGN=1;void FifSIGN==0ifs[i]=={readin;；Eifs[i]==readin;else ifs[i]==*#*输入串字符不符合文法定义!SIGN=1;readin;else ifs[i]==,i!readin;else输入串字符不符合文法定义!readin;SIGN=1;void readin；i++目录、递归下降分析器的设计思想11自顶向下的语法分析方法

1.11递归下降分析法L21递归下降分器意义L31递归下降分析器思想

1.41递归下降分析器的作用

1.52递归下降分析器的形成过程

1.

62、递归向下分析器实现22待分析的简单词法

2.22要求构造的递归下降程序

2.33主函数分析

2.

43、输入串运行分析:34键代码分析及运行过程:

2.55关键代码分析

4.15文法函数调用过程

4.

27、程序测试

57、当程序运行时浮现如下输入程序界面

5.

17、当程序运行时浮现如下输入程序界面

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

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

1.3递归下降分析器，可以使已经消除左递归，回溯的文法，迅速判断出输入串是否满足该文法，并按照递归的方法，算出终结符,此分析器解决的手工计算繁琐问题递归下降分析器思想

1.4递归下降分析法是一种自顶向下的分析法，文法中的每一个非终结符对应一个递归过程（函数）分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推到直到推出句子；或者是从根节点出发，自顶向下为输入串寻觅一个最左匹配序列，建立一个语法树递归下降分析器的作用

1.5读入输入的符号串；1对输入的符号串逐个与栈中的终结符比较；2识别出匹配的输入字符；3确定文法是否能推导出输入串4递归下降分析器的形成过程

1.6实现递归下降分析器，首先要消除产生式的左递归，其次要消除产生式的回溯，输入串进入消除左递归得到可以编写递归下降分析器的文法如图1消除回溯根据文法编写递归下降分析器否/通过递归下降分析器确定输*串是否止犷图递归下降分析器形成过程

1、递归向下分析器实现2待分析的简单词法

2.2非终结符1E ET TF代码中T，用T1代替代码中E，用E1代替终结符2+*i要求构造的递归下降程序

2.3文法G[E]:E-E+T|TT--T*F|FF-E|i首先,消除该文法的左递归，得到文法」G E]:E-TEE»TE I£T-FTT-*FT18F-E|i然后，根据LL1文法的判断条件，对非终结符S和T，的不同产生式的集进行考察，经验证改进后的文法已是文法LL1最后构造递归下降分析程序每一个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写非终结符在这里统称为输入的字符串以#结束A当遇到终结符时，则编写语句1a当前读到的输入符号==鲂读入下一个输入符号If当遇到非终结符时，则编写语句调用2A Ao当遇到规则时，则编写语句3A-当前读到的输入符号不属于退出当某个非If FollowAeiror4终结符的规则有多个候选式时，按文法的条件能惟一地选择一个候选式进行LL1推导主函数分析

2.4此文发一共可分为个函数，分别为E0,E，0,T0,r,F0,其中在E函数中可调用TOEO两个函数在F0函数中可以判断输出串“十”，并调用TO，E两个函数，在函数中可以调用两个函数在函数中可以判断输入串“*”，并调T F,r T用和「两个函数在函数中可以调用函数并判断输入串或者判断输入F0F0E0串是否为通过递归调用实现进栈，匹配出栈，最终达到检测效果T、输入串运行分析3当输入串为时，用栈的形式表现出运行过程以#为结束，首先将和分i*i+i E文法开始符压入栈中，开始分析E首先将“#”和文法开始符压入栈，可以从词条文法中的到终结符，并判断终E结符是否与输入串的的字符相符合，如果符合出栈，并判断在栈中的下一个非终结符，在文法中找到对应的产生式，判断期栈顶的终结符是否与输入串一致，一致出栈，不一致则跳出，此文法无法得到输入串如最后栈底剩”#，并且输入串最后剩#,此输入串符合文法，语法分析成功如图2图输入串运行分析2在图中第五步执行函数时，因当前扫描的字符为“，所以匹配后应执行F用栈模型将压栈；并且；在执行完后还应执行其后的判断”与匹配”E EE语句，这在栈的摹拟中则是标出此时压栈之前的位置如图步骤即出栈至E7〜14此步结束并执行这个判断”与匹配”语句

14、关键代码分析及运行过程4关键代码分析

4.1//文法中调用void EEifSIGN==0TO；//并在E中分别调用TE10；〃调用E//进入}voidEl EifSIGN==0〃判断输入串是否是非终结符+,如果是则出栈readin;T;三八//并继续调用函数进入文法T TEl；//出函数进去日中判断是否是T elseifs[i]!=,#,s[i]!=y输入串字符不符合文法定义！SIGN=1;readin;}}void TifSIGN==0F；Tl；文法函数调用过程

4.2如（图）中用二叉树表示出递归下降分析器的递归过程，可得出详细的分析3过程、程序测试

5、当程序运行时浮现如下输入程序界面

5.1如（图）（图）所示时匹配成功:4,5图第一个输入串匹配4。