2022年编译原理递归下降子程序课程设计报告 .pdf
编译原理课程设计报告2011 年 12 月 2 日设计题目递归下降分析程序的实现学号专业班级计算机科学与技术学生姓名指导教师名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -一、实验目的：（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。二、实验内容：递归下降分析程序的实现设计内容及要求：对文法 G:E E+T|T 构造出 G的递归下降分析程序。程序显示输出TT*F|F 匹配过程（即自上而下生成语法分析树的步骤，F（E）|i 输出各匹配产生式序号即可）。三、设计思路：（1）语法分析：语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。（2）自上而下分析：从文法的开始符号出发，向下推导，推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。它的主旨是对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找 匹配 的推导。（3）递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。（4）分析过程中遇到的问题：a.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。b.文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。（5）构造不带回溯的自上而下分析算法：a.要消除文法的左递归性：一个文法可以消除左递归的条件是不含以为右部的产生式不含回路。b.克服回溯，构造不带回溯的自上而下分析的文法条件名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -（6）满足 LL(1)文法的三个条件：.文法不含左递归，.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1|2|,|n 则 FIRST(i)FIRST(j)(ij).对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n（7）因此我们可以把设计要求的文法首先改写为LL(1)文法ETEE+TE|TFTT*FT|F(E)|i 然后构造每个非终结符的FIRST和 FOLLOW 集合：FIRST(E)=(,i FIRST(E)=+,FIRST(T)=(,I FIRST(T)=*,FIRST(F)=(,I FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#确定改写后的文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。（8）编写 C+代码用到的变量和几个功能识别函数：.advance=0;/字符串小标，表示使IP 指向下一输入符号。.void E();/功能识别函数,表示规则 E-TE void E1();/功能识别函数,表示规则 E-+TE/void T();/功能识别函数,表示规则 T-FT void T1();/功能识别函数,表示规则 T-*FT/void F();/功能识别函数,表示规则 F-(E)/i 因为每个非终结符有对应的子程序的定义，功能识别函数的编写过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。功能识别函数的设计与编写：（1）当遇到终结符 a 时，则编写语句If(当前读到的输入符号=a)读入下一个输入符号（2）当遇到非终结符A时，则编写语句调用A()。（3）当遇到 A-规则时，则编写语句If(当前读到的输入符号不属于Follow(A)error()名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导.四、结果截图：1、输入一个正确的句子：2、输入一个错误句子名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -3、输入一个无#结束的错误句子：五、代码：#include#include using namespace std;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -ifstream import(input sentence.txt);ofstream export(output rule.txt);#include char a10;/字符串的存入int advance=0;/字符串小标，表示使IP 指向下一输入符号void E();/功能识别函数,表示规则 E-TE void E1();/功能识别函数,表示规则 E-+TE/void T();/功能识别函数,表示规则 T-FT void T1();/功能识别函数,表示规则 T-*FT/void F();/功能识别函数,表示规则 F-(E)/i int 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+;/如果是“+”，则读取下一字符T();/根据 E-+TE 规则右部符号串的顺序，调用其他非终结符的规则E1();else exportn;void T()名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -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+;else if(aadvance=()/如果是“(”，则读取下一字符 advance+;E();/根据 F-(E)规则右部符号串的顺序，调用非终结符 E的规则if(aadvance=)export(E)n;advance+;else exportn()is not matching,error!n;exit(0);/正常结束程序运行 else exportn()is not matching,error!n;exit(0);/正常结束程序运行 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -六、心得体会：名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -
