递归下降语法分析器报告

编译原理实验报告实验名称：编写递归下降语法分析器实验类型：验证型实验指导教师：专业班级：姓名：学号：电子邮件：实验地点：实验成绩：日期：年月日一、实验目的通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标：1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。2、掌握词法分析的实现方法。3、上机调试编出的语法分析程序。二、实验原理递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。无左递归：既没有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部x1|x2|…|xn，其对应的字的首终结符号两两不相交。如果一个文法不含回路（形如P⇒+P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。三、实验过程1、分析对象分析算术表达式的BNF定义如下：〈算术表达式〉→〈项〉|〈算术表达式〉＋〈项〉|〈算术表达式〉－〈项〉〈项〉→〈因式〉|〈项〉＊〈因式〉|〈项〉／〈因式〉〈因式〉→〈变量〉│（〈算术表达式〉）〈变量〉→i用符号表示如下：E→T|E＋T|E-TT→F|T*F|T／FF→i│(E)2.递归下降语法分析流程图实验分为五个模块，分别是：E()函数，E1()函数，T()函数，T1()函数,F()函数。用递归下降算法分析上述算术表达式的框图，如下图所示。ZC过程为总控程序。四、实验结果输入想要验证的字符串：（i）#（以#号键结束）。系统就会自动给出分析算术表达式的过程，并将结果用right或false表示。若想继续验证，就输入y,并输入想继续验证的字符串。若不想继续验证，就输入n，则将退出该系统。五、讨论与分析要求不打印之前分析过的待分析字符，思考后觉得在打印待分析的字符时，将用到的循环语句删除掉即可。六、实验总结：通过本次实验对递归下降词法分析器的结构，过程有了更进一步的了解，通过学习书本和试验原理书上的内容，对它的工作原理，具体实行步骤有了进一步的掌握，由于本次试验是测试性试验，所以要求输出的结果是成功与否，输入一个句型，进过分析，判断它是否合法，主要内容在于其判断过程中。本次试验不光提高了自己的编程能力，同时提高了对递归下降的了解。七、附录（主要代码）：/*E()函数*/voidE(){if(x==0){output1(i);printf(E-TE1);output(i+1);T();E1();}}/*E1()函数*/voidE1(){if(x==0){if(s[i]=='+'){output1(i);printf(E1-+TE1);output(i+1);advance();T();E1();}elseif(s[i]=='-'){output1(i);printf(E1--TE1);output(i+1);advance();T();E1();}elseif(s[i]=='#'){output1(i-1);printf(E1-ε);output(i);}else{output1(i);printf(E1-ε);output(i+1);}}}/*T()函数*/voidT(){if(x==0){if(s[i]!='#'){output1(i);printf(T-FT1);output(i+1);F();T1();}else{output1(i-1);printf(T-FT1);output(i);F();T1();}}}/*T1()函数*/voidT1(){if(x==0){if(s[i]=='*'){output1(i);printf(T1-*FT1);output(i+1);advance();F();T1();}elseif(s[i]=='/'){output1(i);printf(T1-/FT1);output(i+1);advance();T1();F();}elseif(s[i]=='#'){output1(i-1);printf(T1-ε);output(i);}else{output1(i);printf(T1-ε);output(i+1);}}}/*F()函数*/voidF(){if(x==0){if(s[i]=='i'){output1(i);printf(F-i);output(i+1);advance();}elseif(s[i]=='('){output1(i);printf(F-(E));output(i+1);advance();E();if(x!=1){if(s[i]==')'){output1(i);printf(F-(E));output(i+1);advance();}else{x=1;}}}elseif(s[i]=='#'){x=1;}elseif(s[i]==')')x=1;}}