编译原理-递归下降子程序-课程设计报告(共8页).doc

《编译原理-递归下降子程序-课程设计报告(共8页).doc》由会员分享，可在线阅读，更多相关《编译原理-递归下降子程序-课程设计报告(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上编译原理课程设计报告设计题目 递归下降分析程序的实现 学生姓名 学 号 专业班级 计算机科学与技术指导教师 罗珣2011 年 12 月 2 日 一、实验目的：（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。二、实验内容：递归下降分析程序的实现设计内容及要求：对文法 G: EE+T|T 构造出G的递归下降分析程序。程序显示输出TT*F|F 匹配过程（即自上而下生成语法分析树的步骤，F（E）|i 输出各匹配产生式序号即可）。三、设计思路：（1）语法分析：语法分析是编译程序的核心部分，任务是分析一个文法的

2、句子结构。递归下降分析程序的实现的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。（2）自上而下分析：从文法的开始符号出发，向下推导，推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。它的主旨是对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。（3）递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。

3、（4）分析过程中遇到的问题：a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 b. 文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。（5）构造不带回溯的自上而下分析算法：a.要消除文法的左递归性：一个文法可以消除左递归的条件是不含以e为右部的产生式 不含回路。b.克服回溯，构造不带回溯的自上而下分析的文法条件（6）满足LL(1)文法的三个条件：. 文法不含左递归，. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若Aa 1|a 2|a n 则 FIRST(a i)FIRST(a j)f (ij). 对文法

4、中的每个非终结符A，若它存在某个候选首符集包含e，则FIRST(a i)FOLLOW(A)=f i=1,2,.,n（7）因此我们可以把设计要求的文法首先改写为LL(1)文法ETEE+TE | eTFT T*FT | eF(E) | i然后构造每个非终结符的FIRST和FOLLOW集合：专心-专注-专业FIRST(E) = ( , i FIRST(E)= + , e FIRST(T) = ( ,I FIRST(T)= * , e FIRST(F) = ( , I FOLLOW(E) = ) , # FOLLOW(E)= ) , # FOLLOW(T) = + , ) , # FOLLOW(T)=

5、 + , ) , # FOLLOW(F) = * , + , ) , # 确定改写后的文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。（8）编写C+代码用到的变量和几个功能识别函数：.advance=0; / 字符串小标，表示使IP指向下一输入符号。. void E(); / 功能识别函数,表示规则E-TEvoid E1(); / 功能识别函数,表示规则E-+TE/void T(); / 功能识别函数,表示规则T-F

6、Tvoid T1(); / 功能识别函数,表示规则T-*FT/void F(); / 功能识别函数,表示规则F-(E)/i因为每个非终结符有对应的子程序的定义，功能识别函数的编写过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。功能识别函数的设计与编写：（1）当遇到终结符a时，则编写语句If(当前读到的输入符号=a)读入下一个输入符号（2）当遇到非终结符A时，则编写语句调用A()。（3）当遇到A-规则时，则编写语句If(当前读到的输入符号不属于Follow(A)error()（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式

7、进行推导.四、结果截图：1、输入一个正确的句子：2、输入一个错误句子3、输入一个无#结束的错误句子：五、代码：#include#includeusing namespace std;ifstream import(input sentence.txt);ofstream export(output rule.txt);#includechar a10; / 字符串的存入int advance=0; / 字符串小标，表示使IP指向下一输入符号void E(); / 功能识别函数,表示规则E-TEvoid E1(); / 功能识别函数,表示规则E-+TE/void T(); / 功能识别函数,表示

8、规则T-FTvoid T1(); / 功能识别函数,表示规则T-*FT/void F(); / 功能识别函数,表示规则F-(E)/iint main() / 主函数exporta; E(); / 从首个推导式E开始if(aadvance=#) exportThe sentence is right,success!n; else exportNo the signal of #,fail!n;return 0;void E() / 功能识别函数 exportTEn; T(); E1();void E1()if(aadvance=+) export+TEn; /输出使用E规则 advance+;

9、 /如果是“+”，则读取下一字符T(); /根据E-+TE规则右部符号串的顺序，调用其他非终结符的规则E1(); else exportn;void T() exportFTn;F(); /根据T-FT规则右部符号串的顺序，调用其他非终结符的规则T1();void T1()if(aadvance=*) /如果是“*”，则读取下一字符export*FTn; advance+;F();/根据T-*FT规则右部符号串的顺序，调用其他非终结符的规则T1();else exportn;void F()if(aadvance=i) /如果是“i”，则读取下一字符 exportin; advance+; e

10、lse if (aadvance=() /如果是“(”，则读取下一字符 advance+; E(); /根据F-(E)规则右部符号串的顺序，调用非终结符E的规则if(aadvance=) export(E)n; advance+; elseexportn ()is not matching, error! n; exit (0); /正常结束程序运行 else exportn ()is not matching, error! n; exit(0); /正常结束程序运行 六、心得体会：（1）一个星期的课程设计，当中有苦也有乐，但从苦乐中我学到了很多东西。通过这次课程设计我看到了自己的与别人的差

11、距，有很多我自己不明白的地方别人都会。当我自己一开始进行递归下降分析程序的课程设计时，我发现我有好多相关的小知识点还不太熟悉，于是我在结合书本和图书馆相关资料基础上，将课堂学习的知识予以真正的吸收和应用，功夫不负有心人，我最终琢磨出了解决该设计题的基本思路和方法。（2）这次课程设计，不仅巩固了课堂知识，很好的复习了一下编译原理所学的内容，而且提高了自己的上机实践能力，有效的和实际结合在了一起，加强了我的动手、思考、解决问题的能力，并扩展了所学知识。 同时在设计过程中也发现了我的许多不足之处，比如对以前所学的知识理解的不够深刻，掌握的不够牢固。此外，因为设计程序的各项流程需要心静下来慢慢思考，所

12、以克服了最近比较浮躁的心态，同时也让自己充实了很多。（3）在设计过程中也遇到了一些问题，比如编写程序时，每读入一个字符，要执行相应的递归函数，因为调用过程中有再次调用，我有好几次把函数的调用搞混，导致得出的结果不是我想要的。所以要在草稿纸上先画出程序的流程图，理顺各子程序之间的调用关系，才能避免程序出错。 还有不仅要知道文法要改为LL(1)文法，还要明白为什么要改，修改后有哪些好处以及LL(1)文法的具体定义与判定方法。在最后进行程序的功能和结果的测试当中，我采用了文件输入输出流，把文件作为输入输出对象的流，实现结果的可视化，从而告别黑白屏界面，但如果能用MFC平台实现可视化界面就更好了，那样更有技术含量，更简洁美观。（4）既然是上机实践就会遇到各种问题，不畏艰难，不怕繁复，就是我们解决问题的方法。通过这次的设计，我发现只要不放弃，在最困难的时候坚持下去，那么所有的事情都能迎刃而解。感谢老师为我们提供上机实践的机会和悉心的指导。