递归下降语法分析器

《递归下降语法分析器》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实验报告实验名称：编写递归下降语法分析器实验类型：验证型实验指导教师：专业班级：姓名：学号：电子邮件：实验地点：实验成绩：日期：2012年4月26日15目录一、实验目的。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。2二、实验过程。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。21、背景知识。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。22、程序总体设计。。。。。。。。。

2、。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。23、程序流程图。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。3三、试验结果。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。5四、讨论与分析。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。7五、附录。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

3、。。。。7六、试验者自评。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。1115一、实验目的通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标：1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。2、掌握词法分析的实现方法。3、上机调试编出的语法分析程序。二、实验过程我们在设计递归下降语法分析器时，应该首先对递归下降语法的相关的背景知识有足够的了解以及熟练的掌握。从而在脑海里形成

4、语法分析的一般方案，根据方案一步步所要实现的目的，形成对递归下降语法分析器程序的模块划分和整体规划。1、背景知识无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。无左递归：既没有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部x1

5、x2

6、…

7、xn，其对应的字的首终结符号两两不相交。如果一个文法不含回路，也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。文法的左递归消除算法：1、将文法G的所有非终结符排序为U1,U2,…,Un;2、For(i=1；i++；i≥

8、n){forj→1toi-1把产生式Ui→Ujα替换成Ui→β1α

9、β2α

10、…

11、βmα；其中：Uj→β1

12、β2

13、…

14、βm消除Ui产生式中的直接左递归；}3.化简改写之后的文法，删除多余产生式。文法的直接左递归消除公式：直接左递归形式：U→Ux

15、y；其中：x，y∈（VN∪VT）*，y不以U打头。直接左递归的消除：U→yU‟U‟→xU‟

16、ε直接左递归的一般形式：U→Ux1

17、Ux2

18、…

19、Uxm

20、y1

21、y2

22、…

23、yn；其中：xi≠ε,yi都不以U打头。一般形式直接左递归的消除:U→y1U‟

24、y2U‟

25、…

26、ynU‟U‟→x1U‟

27、x2U‟

28、…

29、xmU‟

30、ε回溯的消除的前提是

31、文法不得含有左递归，可提左因子来消除回溯。2、程序总体设计1、分析对象分析算术表达式的BNF定义如下：15〈算术表达式〉→〈项〉

32、〈算术表达式〉＋〈项〉

33、〈算术表达式〉－〈项〉〈项〉→〈因式〉

34、〈项〉＊〈因式〉

35、〈项〉／〈因式〉〈因式〉→〈变量〉│（〈算术表达式〉）〈变量〉→i用符号表示如下：E→T

36、E＋T

37、E-TT→F

38、T＊F

39、T／FF→i│(E)2.经消除直接左递归后E→TE’E’→+TE’

40、-TE’

41、εT→FT’T’→*FT’

42、/FT’

43、εF→i

44、(E)3.根据递归下降法分析法，完成上述算术表达式的分析器构造。主要完成：(1)通知外界键入算术表达式；(2)控

45、制过程分析算术表达式；(3)根据分析结果正误，分别通知外界不同的信息。4、程序流程图1515三、实验结果（1）输入i+i#15（2）输入+i#（3）左右括号测试（4）测试回车15（5）综合测试1四、讨论与分析本次试验完成了指导报告上要求的基本功能,并且本程序具有以下几种情况的排错：对(i+i这种错误，以及i++i，ii这种错误等进行了错误排除。除此本程序对回车换行符也进行也处理，其处理方法就是每当在取得一个字符后，用if（sym==’’）sym=advance();进行处理即可。另外在编写程序时遇到了这样一种错误，当输入i+i+i时，PE返还给主函数的是+号，

46、解决方法是