编译原理-递归下降子程序-课程设计报告

编译原理课程设计报告设计题目递归下降分析程序的实现学生姓名 学号 专业班级计算机科学与技术指导教师

2011年12月2日

一、实验目的：掌握自上而下语法分析的要求与特点。掌握递归下降语法分析的基本原理和方法。掌握相应数据结构的设计方法。实验内容:设计内容及要求：对文法G设计内容及要求：对文法G：E-E+TITT-T*F|FFf(E)|i构造岀G的递归下降分析程序。程序显示输出匹配过程(即自上而下生成语法分析树的步骤，输出各匹配产生式序号即可)。三、设计思路:语法分析：语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。自上而下分析：从文法的开始符号出发，向下推导，推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。它的主旨是对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找〃匹配“的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。分析过程中遇到的问题：分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”o文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。构造不带回溯的自上而下分析算法：a.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以£为右部的产生式②不含回路。

b•克服回溯，构造不带回溯的自上而下分析的文法条件(6)满足LL(1)文法的三个条件：•文法不含左递归，.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A-cc1a2•••|an 则FIRST(ai)QFIRST(aj)=f(iHj).对文法中的每个非终结符A,若它存在某个候选首符集包含£，则FIRST(ai)DFOLLOW(A)=f i=l,2,.・.，n(7)因此我们可以把设计要求的文法首先改写为LL(1)文法E-TE'E'f+TE：sT-FT'Ff(E)Ff(E)然后构造每个非终结符的FIRST和然后构造每个非终结符的FIRST和FOLLOW集合:FIRST(E)={( ,i}FIRST(Ez)={+,e}FIRST(T) ={ (,I}FIRST(T')={*,s}FOLLOW(E) ={), #}FOLLOW(EO={),#}FOLLOW(T)={+,),#}FOLLOW(F)二{+,),#}FIRST(F)={(,I}FOLLOW(F)FIRST(F)={(,I}FOLLOW(F)二{*, +,),#}确定改写后的文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号吊的顺序编写。然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。(8)编写C++代码用到的变量和几个功能识别函数：.advanced； //字符串小标,表示使IP指向下一输入符号。・voidE()； //功能识别函数，表示规则E->TE,voidEl(); //功能识别函数，表示规则E—>+TE'/£voidT(); //功能识别函数，表示规则»FT,VOidTl(); //功能识别函数，表示规则r-XFT/evoidF(); //功能识别函数，表示规则F->(E)/i因为每个非终结符有对应的子程序的定义，功能识别函数的编写过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。功能识别函数的设计与编写：(1)当遇到终结符a时，则编写语句If(当前读到的输入符号=&)读入下一个输入符号(2)当遇到非终结符A时，则编写语句调用A()o

(3)当遇到A~>e规则时，则编写语句If(X前读到的输入符号不属于Follow(A))error()(4)当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导.结果截图：1、输入一个正确的句子:2、输入一个错误句子■inputsentence.txt本文件㈢编捐㈢格式9)查看⑪帮助但)i*i*(i+#|

Boutputrule.tx仁迟事本文件㈢编辑㈢格式9)查看遡帮助凹pleaseinputtherightsentence(endwith#)：E->TE‘t-》ftF->iT->问F->iT-冶E->TE，t->ft"F->i『-〉eE‘-〉+TE'T->FT5(〉isnotmatching,error!3、输入一个无#结束的错误句子:診inputsenterKe.txt-12爭本文件㈢編辑©格式9）查看2帮肋®i*i*iBoutputrule.txt•记爭本文件㈢编辑⑥格式9）查看⑷帮助凹bTFTFTFTEinputtherightsentence(endwith#)：E~>TEbTFTFTFTEsignalofU.fail!代码:#include<iostream>#include<fstream>usingnamespacestd;0}0}#include<string>chara[10];intadvance=0；voidE();voidEI();voidT();//字符串的存入//字符串小标，表示使IF指向下一输入符号//功能识别函数，表示规则E->TE,//功能识别函数，表示规则E'->+TE‘/e//功能识别函数，表示规则T->FT‘ifstreamimport(Hinputsentence.txtn);ofstreamexport(，zoutputrule・txt");voidTl()； //功能识别函数，表示规则T—XFT'/voidF();intmain()//功能识别函数，表示规则F->(E)/i//主函数吃xport<</zp1easeinputtherightsentence(endwith#) /输入提示import»a;E(); //从首个推导式E开始if((a[advance]—#'))export<<Z/Thesentenceisright,success!\n"；e1seexport«，，Nothesignalof#,fail!\n";°return0;}VOidE() //功能识别函数{export«，/E->TE,\n';TO;E10;}voidE1(){if(a[advance]二二'){export«，，E,->+TE,\nH； //输出使用E‘规则0advance++; //如果是”，则读取下一字符T();〃根据E'—>+TE规则右部符号串的顺序，调用其他非终结符的规则oEl();eIseexport«，，Er~>£\n";}voidT()export«，，T->FT,\rT;F()；〃根据T—>FT规则右部符号串的顺序，调用其他非终结符的规则T10;}voidT1(){if(a[advance]==? ) //如果是，则读取下一字符{export<〈"T->*FT，\n"；advance++;F0;//根据T‘-XFT'规则右部符号串的顺序，调用其他非终结符的规则呵1();}elseexport«，ZT"—>e\n";}voidF(){if(a[advance]=='i，) //如果是“i”,则读取下一字符{export«，，F—>i\nz，；advance++；}e1seif(a[advance]=‘(')〃如果是“(J则读取下一字符{。advance++；E(); //根据F-XE)规则右部符号串的顺序,调用非终结符E的规则if(a[advance]=')'){Q export«，zF—>(E)\nH;advance++;ooo)Qelse{0 export<<，z\n()isnotmatching,error!\nM;exit(0);〃正常结束程序运行}}else{export<<n\n()isnotmatehing,error!\n";exit(O)； 〃正常结束程序运行六、心得体会：一个星期的课程设计，当中有苦也有乐，但从苦乐中我学到了很多东西。通过这次课程设计我看到了自己的与别人的差距，有很多我自己不明白的地方别人都会。当我自己一开始进行递归下降分析程序的课程设计时，我发现我有好多相关的小知识点还不太熟悉，于是我在结合书本和图书馆相关资料基础上，将课堂学习的知识予以真正的吸收和应用，功夫不负有心人，我最终琢磨出了解决该设计题的基本思路和方法。这次课程设计，不仅巩固了课堂知识，很好的复习了一下编译原理所学的内容，而且提高了自己的上机实践能力，有效的和实际结合在了一起，加强了我的动手、思考、解决问题的能力，并扩展了所学知识。同时在设计过程中也发现了我的许多不足之处，比如对以前所学的知识理解的不够深刻，掌握的不够牢固。此外，因为设计程序的各项流程需要心静下来慢慢思考，所以克服了最近比较浮躁的心态，同时也让自己充实了很多。在设计过程中也遇到了一些问题，比如编写程序时，每读入一个字符，要执行相应的递归函数，因为调用过程中有再次调用，我有好儿次把函数的调用搞混，导致得出的结果不是我想要的。所以要在草稿纸上先画出程序的流程图，理顺各子程序之间的调用关系，才能避免程序出错。还有不仅要知道文法要改为LL(1)文法，还要明白为什么要改，修