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

《编译原理-递归下降子程序-课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编译原理课程设计报告设计题目递归下降分析程序的实现学生姓名学号专业班级计算机科学与技术指导教师罗珣2011年12月2日一、实验目的：（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。二、实验内容：递归下降分析程序的实现设计内容及要求：对文法G:E→E+T

2、T构造出G的递归下降分析程序。程序显示输出T→T*F

3、F匹配过程（即自上而下生成语法分析树的步骤，F→（E）

4、i输出各匹配产生式序号即可）。三、设计思路：（1）语法分析：语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。

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

6、的信息反馈和联合作用实现对输入串的识别。（4）分析过程中遇到的问题：a.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。b.文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。（5）构造不带回溯的自上而下分析算法：a.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以e为右部的产生式②不含回路。b.克服回溯，构造不带回溯的自上而下分析的文法条件（6）满足LL(1)文法的三个条件：①.文法不含左递归，②.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→a1

7、

8、a2

9、…

10、an则FIRST(ai)∩FIRST(aj)＝f(i¹j)③.对文法中的每个非终结符A，若它存在某个候选首符集包含e，则FIRST(ai)∩FOLLOW(A)=fi=1,2,...,n（7）因此我们可以把设计要求的文法首先改写为LL(1)文法E→TE¢E¢→+TE¢

11、eT→FT¢T¢→*FT¢

12、eF→(E)

13、i然后构造每个非终结符的FIRST和FOLLOW集合：FIRST(E)={(,i}FIRST(E¢)={+,e}FIRST(T)={(,I}FIRST(T¢)={*,e}FIRST(F)={(,I}FOLLOW(E)={),#}FOL

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

15、idE1();//功能识别函数,表示规则E'->+TE'/εvoidT();//功能识别函数,表示规则T->FT'voidT1();//功能识别函数,表示规则T'->*FT'/εvoidF();//功能识别函数,表示规则F->(E)/i因为每个非终结符有对应的子程序的定义，功能识别函数的编写过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。功能识别函数的设计与编写：（1）当遇到终结符a时，则编写语句If(当前读到的输入符号==a)读入下一个输入符号（2）当遇到非终结符A时，则编写语句调用A()。（3）当遇到A-->

16、ε规则时，则编写语句If(当前读到的输入符号不属于Follow(A))error()（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导.四、结果截图：1、输入一个正确的句子：2、输入一个错误句子3、输入一个无#结束的错误句子：五、代码：#include#includeusingnamespacestd;ifstreamimport("inputsentence.txt");ofstreamexport("outputrule.txt");#include

17、>chara[10];//字符串的存入intadvance=0;//字符串小标，表示使IP指向下一输入符号voidE();