递归下降语法分析器

1、 编译原理实验报告实验名称：编写递归下降语法分析器实验类型：验证型实验指导教师：专业班级：姓 名：学 号：电子邮件：实验地点：实验成绩： 日期： 2012 年4 月 26 日目录一、 实验目的。2二、 实验过程。21、 背景知识。22、 程序总体设计。23、 程序流程图。3三、 试验结果。5四、 讨论与分析。7五、 附录。7六、 试验者自评。11一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、

2、掌握词法分析的实现方法。 3、上机调试编出的语法分析程序。二、实验过程 我们在设计递归下降语法分析器时，应该首先对递归下降语法的相关的背景知识有足够的了解以及熟练的掌握。从而在脑海里形成语法分析的一般方案，根据方案一步步所要实现的目的，形成对递归下降语法分析器程序的模块划分和整体规划。1、 背景知识无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部x1|x2|xn，其对应的字的首终结符号两两不相交。如果一个文法不含回路，也不含以为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递

3、归（改写后的文法可能含有以为右部的产生式）。文法的左递归消除算法： 1、将文法G的所有非终结符排序为U1 ,U2 , ,Un; 2、For(i=1；i+；in) for j1 to i-1 把产生式UiUj替换成Ui1| 2|m； 其中：Uj 1| 2 | |m 消除Ui产生式中的直接左递归； 3.化简改写之后的文法，删除多余产生式。文法的直接左递归消除公式： 直接左递归形式：UUx|y； 其中：x，y（VNVT）* ，y不以U打头。 直接左递归的消除： UyU UxU| 直接左递归的一般形式：UUx1|Ux2|Uxm|y1|y2|yn； 其中：xi ,yi都不以U打头。 一般形式直接左递归的

4、消除: Uy1U| y2U | ynUUx1U| x2U| | xmU| 回溯的消除的前提是文法不得含有左递归，可提左因子来消除回溯。2、 程序总体设计1、分析对象 分析算术表达式的BNF定义如下： 算术表达式项|算术表达式项|算术表达式项 项因式|项因式|项因式 因式变量（算术表达式） 变量i 用符号表示如下： ET|ET|E-T TF|TF|TF Fi(E)2.经消除直接左递归后ETEE +TE|-TE|TFTT *FT|/FT|F i|(E)3.根据递归下降法分析法，完成上述算术表达式的分析器构造。主要完成： (1) 通知外界键入算术表达式；(2) 控制过程分析算术表达式； (3) 根据

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

6、码#include"stdio.h"#include "string.h"#include "stdlib.h"#include "ctype.h"intpT(char sym);intp_E(char sym);intp_T(char sym);intpF(char sym);int i=0,j=0;/char sym;char instring20;char advance()char cc;i=i+1;cc=instringi;return cc;int pE(char sym)char xx;xx=sym;

7、xx=pT(sym);/printf("%c",xx);xx=p_E(xx);/printf("/n%c",xx);returnxx;int p_E(char sym)char s,hh;s=sym;hh=sym;if (sym='+'|sym='-')printf("%c",sym);sym=advance();if(sym='n')sym=advance();hh=pT(sym);/printf("%c",hh);hh=p_E(hh); else if(s=

8、9;)'|s='#'|s='/0'|'n') else printf("error!"); return -1; return hh;int pT(char sym)char yy;yy=sym;yy=pF(sym);/printf("%c",yy);yy=p_T(yy);/printf("%c",yy);return yy;int p_T(char sym)char s,zz;zz=sym;if (sym='*'|sym='/')printf(&

9、quot;%c",sym);s=sym;sym=advance();if(sym='n')sym=advance();/zz=sym;zz=pF(sym);/printf("%c",zz);p_T(zz);else if(sym=')'|sym='#'|sym='/0'|sym='+'|'n') else printf("error2!"); return -1; return zz;int pF(char sym)if (sym='i

10、9;)printf("%c",sym);printf("%d",j+);sym=advance();if(sym='n')sym=advance();/printf("%c",sym);else if(sym='(')printf("%c",sym);sym=advance();if(sym='n')sym=advance();sym=pE(sym);if(sym=')')printf("%c",sym);sym=advance()

11、;if(sym='n')sym=advance();else printf("error");return -1; else if(sym='/0'|sym='n') elseprintf("err");return -1;return sym;void main()int b=0;char sym,c,mm;printf("input a stringn");doc=getchar();instringb+=c;while(c!='#');getchar();sym=instring0;mm=pE(sym);printf("n%c",mm);if(mm='#') printf("nright again!");elseprint