武汉理工大学 DO-WHILE语句的翻译分析程序设计 ———递归下降法、输出四元式

1、武汉理工大学编译原理课程设计说明书DO-WHILE语句的翻译分析程序设计 递归下降法、输出四元式1问题描述1.1问题描述 设计一个DO-WHILE循环语句的词法语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。1.2主要任务通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。首先写出一个能识别DO-WHILE循环语句的文法，通过消除左递归使它符合LL(1)即递归下降法的要求，然后按照这个文法编写一个集词法分析，语法分析和语义分析为一体的程序，该程序首先可以检查输入语句

2、是否符合词法要求，若符合则继续识别输入的语句是否符合DO-WHILE语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。1.3测试数据编写好源代码后，进行调试，根据程序要求进输入一小段程序，进行词法、语法的分析，给出分析结果。2文法及属性文法的描述2.1文法的描述用扩充巴科斯-瑙尔范式（EBNF）给出的while循环语句的文法描述，如下：<while语句> :=do (<条件语句>) while <赋值语句> <条件语句> := <表达式><条件运算符> <表达式><条件运算符> :=

3、 > | < | = | >= | <=<表达式> := <表达式> + <表达式2> | <表达式> - <表达式2> | <表达式2> <表达式2>:=<表达式2> * <表达式3> |<表达式2> / <表达式3> | <表达式3><表达式3>:=(<表达式>) | <标识符>|<数字><赋值语句>:=<标识符>=<表达式>； 2.2 DO

4、-while循环语句文法的描述产生式为S-> do E while A，为便于语法制导翻译将其改写如下： 文法G(s)如下： S->DGWE （意思是do G while E） G->c=R R->dTe|d T->+|-|*|/ E->aFb F-> >|=|<2.3 DO-WHILE循环语句的属性文法产生式语义规则Sdo E while A S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin:E。codegen(E

5、.true:) S1.codegen(goto S.begin)3.语法分析方法及中间代码形式的描述 3.1语法分析方法 递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H)。每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S 是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=l.Yufa_Queue.front()来得到当前所分析到的

6、单词，然后在递归语法分析中根据这个单词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。 它的优点是简单直观，易于构造，很多编译系统所实现。缺点是对文法要求很高，由于递归调用多，影响分析器的效率。 其文法可以表示为： ETE+T TFT*F Fi（E） 可以用语法图来表示语言的文法，如图：+TTE*FFTE)(iF3.2中间代码形式描述 中间代码采用四元式输出，一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句do c=

7、a+b while a<b的四元式输出形式如下： 100 ( + , a , b , T ) 101 ( = , T , - , c ) 102 ( j<, a , b , 100 ) 4简要的分析与概要设计4.1全局程序概要设计 递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。在语法分析程序中，根据词法得到的

8、结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。 根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。 4.2词法分析 词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑

9、出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。 4.3递归下降翻译器的设计1. 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。2. 非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。3. 每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非终结符和语义动作分别做以下工作。（1）对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读

10、入一个输入符号。（2）对于每个非终结符号B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,，bk)（3）对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。 4.4语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存

11、放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。5测试方法和测试结果5.1测试方法 编写好源程序，连接运行无误后，用几个简单的while语句检测其正确性，如：输入do-while语句：Wa<bDa=a+b#，看其输出结果是否与我们所预期的结果一致，如果不一致，则需对源程序进行检查修正，我们可以用逐步调试的方法来对源程序进行跟踪分析，找出出错的地方和原因，在对其进行修改，重新调试运行，直到输出正确的结果为止。若输出结果正确，

12、还要多用几个while语句对其进行检测，直到所有输出结果正确。5.2测试结果测试结果如下：6经验与体会在做本次实验之前我对LL(1)文法的构成,递归下降原理不是很了解,在查阅了相关资料后,对此有了深入了解.在整个设计过程中,将词法分析做为一个单独的模块,它可以被任何语法分析调用,提高独立性.并且在编程之前就已经将程序的概要设计都做出来了，所以在编写程序的时候相对比较容易。词法分析，语法分析都是很容易的，只要理解了分析方法的实现原理，编写程序判断输入字符串是否满足给定的文法是比较简单的。本次的设计的不足主要体现在以下几个方面，首先，因为前几次的实验都没有把词法分析器编出来，因此程序中我没有采用词

13、法分析器，只能够对唯一的Da=a+bWa<b#进行识别，同样后面的语义分析也只能对这个起作用；再次，由于我所设计的栈中只能一个字符一个字符的存放，因此只能用D W分别表示do while；而且我对语法制导翻译这一块很不熟悉，因此我始终不能用程序实现语法制导翻译输出四元式，于是根据自己的理解，直接把四元式写了出来。在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了在编写程序时要有耐心。如果你没有耐心，即使再好的思路也不会得到很好的表达，特别是在调试的过程中，对于各种各样的错误，要特别的有耐心去自习分析原因，特别是一些基本的语法错误，不能一看到错误很多就乱了阵脚，更不能轻易

14、的放弃，半途而废。 通过此次课程设计，再次对编译原理的基础知识和一些实际操作只是有了一定的了解，对高级语言在计算机上进行编译分析的过程有了一定的了解。7附录源代码： /*文法G(s) s->DGWE G->c=R R->dTe|d T->+|-|*|/ E->aFb F-> >|=|< */#include <stdio.h> #include<dos.h> #include<stdlib.h> #include<string.h>char a50,g5050;char ch;int n1,i1=0

15、,i2=0;int total=0;void S(); void D(); void G(); void W(); void E(); void R(); void T(); void F(); void main() int p,j=0; printf("请输入do-while语句(D代表do,W代表while),并以#结束:n");do scanf("%c",&ch); aj=ch; j+; while(ch!='#'); n1=j;ch=a0;S(); printf("n")； if (ch='#

16、') printf("输出四元式为：n"); p=0; for(;p<i2;p+) printf("10%d %sn",p,gp); /*输出推导式*/ else printf("errorn"); printf("press any key to continue.n"); getchar(); getchar(); return; printf("n"); printf("press any key to continue.n"); getchar(); g

17、etchar();/*出错情况分析*/void S() printf("%dtS->DGWEn",total);total+; D(); G(); void D() if(ch!='D') printf("有非法字符%c请按回车返回!",ch); getchar(); getchar(); exit(1); ch=a+i1; void G() int i=i1+1; if(ch!='c'&&ai!='=') printf("有非法字符%c %c请按回车返回!",ch

18、,ai); getchar(); getchar(); exit(1); printf("%dtG->c=Rn",total);total+; R();void R() int i; i=i1+1;i1=i1+2; ch=ai1; if(ai!='='&&ch!='d') printf("有非法字符%c %c请按回车返回!",ai,ch); getchar(); getchar(); exit(1); else if(ai1+1='+')|(ai1+1='-')|(ai

19、1+1='*')|(ai1+1='/') printf("%dtR->dTen",total);total+; i2=3; T(); else printf("%dtR->dn",total);total+; i2=2; strcpy(g0,"(=,c,d,_)"); W(); E(); void T() ch=a+i1; switch(ch) case '+': printf("%dtT->+n",total);total+;strcpy(g0,&

20、quot;(+,d,e,T)");strcpy(g1,"(=,c,T,_)");break; case '-': printf("%dtT->-n",total);total+; strcpy(g0,"(-,d,e,T)");strcpy(g1,"(=,c,T,_)");break; case '*': printf("%dtT->*n",total);total+; strcpy(g0,"(*,d,e,T)");strc

21、py(g1,"(=,c,T,_)");break; default: printf("%dtT->/n",total);total+; strcpy(g0,"(/,d,e,T)");strcpy(g1,"(=,c,T,_)");break; W(); E();void W() +i1; ch=a+i1; if(ch!='W') printf("有非法字符%c请按回车返回!",ch); getchar(); getchar(); exit(1); void E() ch=a+i1; if(ch!='a') printf("有非法字符%c %c请按回车返回!",ch); getchar(); getchar(); exit(1); printf("%dtE->aFbn",total);total+; F();void F() int i;ch=a+i1;i=i1+1;if(ai!='b') printf("有非法字符%c请按回车返回!",ai); getchar(); getchar(); e