编译原理实验报告：实验二编写递归下降语法分析程序

实验名称 实验类型 指导教师 专业班级 姓名 学号 电子邮箱 实验地点 实验成绩编译原理实验报告实验二编写递归下降语法分析器验证型实验何中胜13软件四丁越13030504862245792qq .com秋白楼B720日期：2016 年 4 月 1 日一、实验目的通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单 词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目 标：1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。2、掌握词法分析的实现方法。3、上机调试编出的语法分析程序。二、实验过程1、分析对象 分析算术表达式的 BNF 定义如下：算术表达式一项|算术表达式+项|算术表达式一项项一因式|项*因式|项/因式因式一变量丨(算术表达式)变量f i用符号表示如下：EfT|E+T|E-TTfF|T*F|T/ FFT|(E)递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因 为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一 个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号 时，调用该非终结符号对应的子程序来完成。自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推 导 出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的 产 生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没 有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部xl|x2|xn,其对应的字的首终结符 号 两两不相交。2. 递归下降语法分析流程图实验分为五个模块，分别是：E()函数，El()函数，T()函数，Tl()函数,F()函数。用递归下降算法分析上述算术表达式的框图，如下图所示。ZC过程为总控程序。开E提E-INPUT SSIONH打印RIGHTAGAIN 5*TZ： -0犠入字再川ifr是返回& 回图 1-1 ZC 过程” L .- 图1-2 E过程ADVANCE图 1-4 F 过程取ST的第一个 字符-SYM广 图1-5函数过程SYM 十y kzrt Ir、开始取ST首字符除去后的字符串STIJf*图追6函数过程习d vance三、实验结果1. 测试数据 测试数据时输入要测试的串并以#结束 数据共分为2 组，分别如下： 第一组数据i+i*i#第二组数据I*#2. 测试结果 测试结果如下图所示：第一组数据图 1-7 测试结果 1 第二组数据图 1-8 测试结果 2四、讨论与分析本次试验分为 5 个大步骤：ZC过程：开始，然后打印“INPUT EXPRESSION”，输入字符串ST,执行E过程，然后 判断SYM是否不等于#或者TZ是否等于1,如果是，打印“ERROR AGAIN”，给TZ赋值为0, 跳回到开始步骤继续；如果不是则打印“RIGHT AGAIN”，回到开始步骤继续。E过程：开始，执行T过程，判断SYM是否等于“+”或“一”，如果不是，返回，如 果是，执行 ADVANCE， 跳回到开始步骤。T过程：开始，执行F过程，判断SYM是否等于“*”或者“/”，如果不是，返回，如 果是，执行 ADVANCE， 在跳回到开始过程。F过程：开始，判断SYM是否不等于“A”或者SYM是否小于Z，如果不是，执行ADVACE, 然后执行返回，如果不是，再判断SYM是否不等于如果是，打印“ERROR”，TZ赋值 1,返回；如果不是，执行ADVANCE,在执行E过程，接着继续判断SYM是否不等于“)”， 如果是，打印ERROR,TZ赋值1,如果不是，执行ADVANCE，返回。SYM:取字符串ST的第一个字符给SYM。ADVANCE:取字符串ST去除首字符后留下的字符串。五、附录： 关键代码部分如下：(E ()函数和El()函数构成E过程，T ()函数和Tl()函数构成T过程，F()函数构成F 过程)/*E() 函数*/void E()if(x=0)output1(i); printf(E-TE1);output(i+1);T();E1();/*E1() 函数*/void E1()if(x=0)if(si=+)output1(i); printf(E1-+TE1);output(i+1); advance();T();E1();else if(si=-)output1(i);printf(E1-TE1);output(i+1);advance();T();E1();else if(si=#)output1(i-1);printf(El- ); output(i);else output1(i);printf(El- ); output(i+1);/*T() 函数*/void T()if(x=0)if(si!=#)output1(i);printf(T-FT1);output(i+1);F();T1(); else output1(i-1);printf(T-FT1); output(i);F();T1();/*T1 ()函数*/void T1()if(x=0) if(si=*)output1(i); printf(T1-*FT1); output(i+1); advance();F();T1();else if(si=/) output1(i);printf(T1-/FT1);output(i+1);advance();T1();F();else if(si=#)output1(i-1);printf(Tl- );output(i);elseoutput1(i);printf(Tl- ); output(i+1);/*F() 函数*/void F()if(x=0)if(si=i)output1(i);printf(F-i);output(i+1);advance();else if(si=()output1(i); printf(F-(E); output(i+1);advance();E();if(x!=1)if(si=)output1(i); printf(F-(E); output(i+1); advance();elsex=1;else if(si=#)x=1;else if(si=)x=1;六、实验者自评通过本次实验，我对递归下降词法分析器的结构，过程有了更进一步的了解，通过学 习书本和试验原理书上的内容，对它的工作原理，具体实行步骤有了进一步的掌握。这次 实验让我了解到如何设计、编制并调试递归下降语法分析程序，加深对递归下降语法分析 原理的理解；熟悉了构造递归下降语法分析程序的手工方式的相关原理，根据识别语言单 词的状态转换图，使用某种高级语言(例如C语言)直接编写此法分析程序。由于本次试 验是测试性试验，所以要求输出的结果是成功与否，输入一个句型，进过分析，判断它是 否合法，主要内容在于其判断过程中。本次试验不光提高了自己的编程能力，同时提高了 对递归下降的了解。