北邮大三上编译原理语法分析实验报告

1、编译原理第四章 语法分析班级：09211311学号：姓名：schnee目 录1.实验题目和要求12.递归调用预测分析实现 自顶向下分析（方法1）21. 消除左递归.22. 画状态转移图33. 编程实现递归调用自顶向下分析.33.lr实现 自底向上分析（方法三）61. 构造识别所有活前缀的dfa.62. 构造lr分析表.73. 编程实现算法4.3，实现自底向上lr分析.84. 运行结果截图.111. 实验题目和要求题目：语法分析程序的设计与实现。实验内容：编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。实验要求：在对输入表达式进行分析的过程中，输出所采用的产生

2、式。方法1：编写递归调用程序实现自顶向下的分析。方法2：编写ll(1)语法分析程序，要求如下。(1) 编程实现算法4.2，为给定文法自动构造预测分析表。(2) 编程实现算法4.1，构造ll(1)预测分析程序。方法3：编写语法分析程序实现自底向上的分析，要求如下。(1) 构造识别所有活前缀的dfa。(2) 构造lr分析表。(3) 编程实现算法4.3，构造lr分析程序。方法4：利用yacc自动生成语法分析程序，调用lex自动生成的词法分析程序。2. 递归调用预测分析实现 自顶向下分析（方法1）(1) 消除文法左递归。文法改写为：(2) 画出状态图得012e：teet3456e：+ -e789t：f

3、ttf10t：*/111312 e14151617（e）id numf：化简得036+ - ete：7813* / fet：14151617（e）id numf：(3) 预测分析程序的实现 说明定义函数error()为错误处理子程序。定义函数forward_pointer()为指向输入串的指针前进一位的相关子程序。定义字符cur_token为当前记号，即语法分析时的终结符。对应三个非终结符，各定义一个子程序。主函数从开始符出发。 源程序3. lr实现 自底向上分析（方法三）(1) 构造识别所有活前缀的dfa。构造扩展文法first和follow集如下etffirstid, (, numid,

4、(, numid, (, numfollow$, ), +, -$, ), +, -, *, /$, ), +, -, *, /构造识别所有活前缀的dfa如下(2) 构造lr分析表。 (1) (4) (7) (2) (5) (8) (3) (6) (9) 状态actiongoto+-*/idnum()$etf0s4s6s51231s7s8acc2r3r3s9s10r3r33r6r6r6 r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r8(3) 编程实现算法4.3， 构造lr分析程序。(4) 运行结果截图： 输入符号串为 id + id, 即记号流为 4 0 4时的运行结果 输入符号串为(id+id)*num/(id-num)， 即记号流为token=6, 4, 0,