赋值语句的递归下降翻译程序设计2

1、赋值语句的递归下降翻译程序设计1 引言递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。本文将采用这种方法对赋值语句进行翻译，并得到逆波兰式的中间代码结果。另外我还完成了对逆波兰式的中间代码翻译执行的程序。1.1 逆波兰式简介在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来

2、执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，要从中缀表达式直接产生目标代码一般比较麻烦。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。这种表示法的一个特点是，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式。下面我们对照地给出一些表达式的两种表示：中缀表示后缀表示A+BAB+（1）A+B*CABC*+（2）(A+B)*(C+D)AB+CD+*（3）x/yz-d*exyz/de*-（4）(a=0b>3)(ex

3、<>y)a0=b3>exy<>（5）从上面的例子可以看出：(1) 在两种表示中，运算对象出现的顺序相同；(2) 在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。 顺便提及，Lukasiewicz原来提出的是前缀表示，即把每一运算符置于其运算对象之前。例如，中缀式a+b和(a+b)/c相应的前缀表示分别为+ab和/+abc。因此，为了区分前缀和后缀表示，通常将后缀表示称为逆波兰表示。因前缀表示并不常用，所以有时也将后缀表示就称为波兰表示。2 需求分析本课程设计的目的是为了实现赋值语句的递归下降翻译程序设计，并给出对应的逆波兰式中间

4、代码。赋值语句:= 标识符 ：= 算术表达式算术表达式的文法：算术表达式项加法运算符项项 因子乘法运算符因子因子 标识符无符号整数（表达式）加法运算符 乘法运算符 设计赋值语句文法，给出该文法的属性文法，用递归下降分析法实现对赋值语句的翻译，给出翻译的逆波兰式结果。3 总体设计本文采用用递归下降分析法实现对赋值语句的翻译，并给出翻译的逆波兰式结果。3.1 设计原则设计赋值语句文法，给出该文法的属性文法，用递归下降分析法实现对赋值语句的翻译，给出翻译的逆波兰式结果。按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。该子程序处理相应句型中相对于此非终结符号的

5、产生式。3.1.1 文法赋值语句:= 标识符 ：= 算术表达式算术表达式的文法：算术表达式项加法运算符项项 因子乘法运算符因子因子 标识符无符号整数（表达式）加法运算符 乘法运算符 3.1.2 属性文法的设计下面，我们按照以上文法，说明如何按语法制导翻译方法将简单算术表达式翻译成为后缀式。为了突出翻译的重点，这里不过多地涉及某些语义处理细节，属性文法中只给出了语义规则。产生式属性文法赋值语句:= 标识符 ：= 算术表达式POST=标识符&算术表达式&=算术表达式项加法运算符项POST=项&项&加法运算符项 因子乘法运算符因子POST=因子&因子&

6、乘法运算符因子 标识符无符号整数（表达式）POST=标识符无符号整数表达式在属性文法中，POST就是我们要得到的逆波兰式。“&”表示各个逆波兰式的连接。3.2 数据结构和模块说明3.2.1 主函数图1 主函数流程图3.2.2 语义分析函数本函数的功能是实现对赋值语句的语义分析。最后得到对应的逆波兰式结果。图2 语义分析函数流程图3.2.3 语句函数本函数实现了对语句的分析，结果返回的也是逆波兰式。图3 语句函数3.2.4 赋值语句函数赋值语句的产生式如下：赋值语句:= 标识符 ：= 算术表达式本函数的功能是将其转化为对应的逆波兰式：POST=标识符&算术表达式&=图4

7、赋值语句函数3.2.5 表达式函数表达式的产生式如下：算术表达式项加法运算符项本函数的功能是将其转化为对应的逆波兰式：POST=项&项&加法运算符图5 表达式函数3.2.6 项函数项的产生式如下：项 因子乘法运算符因子本函数的功能是将其转化为对应的逆波兰式：POST=因子&因子&乘法运算符图6 项函数3.2.7 因子函数因子的产生式如下：因子 标识符无符号整数（表达式）本函数的功能是将其转化为对应的逆波兰式：POST=标识符无符号整数表达式图7 因子函数3.3 开发工具的选择操作系统：windows XP内存：1G平台：VC+ 6.04 详细的算法设计4.1 语

8、义分析函数string lrparser()string temp=""scaner();kk=0;if(syn=1)temp=yucu();if(syn=6)scaner();if(syn=0 && kk=0)cout<<"分析成功！"<<endl;elseif(kk=0)cout<<"error:lost end "<<endl;kk=1;elsecout<<"error: can't find begin"<<en

9、dl;kk=1;return (string)temp;4.2 语句函数string yucu()string temp=statement();while(syn=26)temp+="n"+statement();return (string)temp;4.3 赋值语句函数string statement()string ID,eplace,temp;scaner();if(syn=10)ID=token;scaner();if(syn=18)eplace=expression();temp=ID+" "+eplace+" = "e

10、lsecout<<"error:lost :="<<endl;kk=1;elsecout<<"lost ID"<<endl;kk=1;return (string)temp;4.4 表达式函数string expression()string ag1,ag2,temp;int tpsyn;ag1=term();temp=ag1;while(syn=13 | syn=14)tpsyn=syn;ag2=term();string aa=(tpsyn=13)?"+":"-"

11、temp+=" "+ag2+" "+aa+" "return (string)temp;4.5 项函数string term()string ag1,ag2,temp;int tpsyn;ag1=factor();temp=ag1;scaner();while(syn=15 | syn=16)tpsyn=syn;ag2=factor();string aa=(tpsyn=15)?"*":"/"temp+=" "+ag2+" "+aa+" &quo

12、t;scaner();return (string)temp;4.6 因子函数string factor()scaner();string fplace=""if(syn=10)return token;else if(syn=11)sprintf(temp,"%d",sum);return (string)temp;else if(syn=27)fplace=expression();if(syn=28)return fplace;else cout<<"error: without ) "<<endl;kk

13、=1; elsecout<<"error: without ( "<<endl;kk=1;return ""4.7 对目标代码的翻译函数这里只给出了关键的代码：dofin>>word;switch(word0)case '=':ag1=getValue(s.top();s.pop();ags=s.top();s.pop();insertTable(ags,ag1);break;case '+':ag1=getValue(s.top();s.pop();ag2=getValue(s.top

14、();s.pop();s.push(int2str(floor(ag2+ag1);break;case '-':ag1=getValue(s.top();s.pop();ag2=getValue(s.top();s.pop();s.push(int2str(floor(ag2-ag1);break;case '*':ag1=getValue(s.top();s.pop();ag2=getValue(s.top();s.pop();s.push(int2str(floor(ag2*ag1);break;case '/':ag1=getValue(s

15、.top();s.pop();ag2=getValue(s.top();s.pop();if(ag1=0)s.push("9999999");else s.push(int2str(floor(ag2/ag1);break;default:s.push(word);while(!fin.eof();5 软件调试使用VC+自带的功能对源代码进行了调试，直至没有语法错误和语义错误。6 软件的测试方法和结果采用文本文件输入源代码，然后程序通过读取文本文件中的源代码，进行语义分析，最后输出逆波兰式的中间代码结果。本文一共测试了三组典型数据：begin a:=(2+3*4)*4/(3

16、+7) end #begin a:=2+3*4; x:=(a+b)/c end #begin a:=(x*y/(zmvj8969-r)-sdf; x:=(a+b)/c; yue:=123+r +1+2-4 end #图8 测试结果另外本文还实现了对逆波兰式的翻译结果。计算出了在程序中的每个变量的值。图9 命令行方式执行图10 对逆波兰式的翻译执行结果7 有关技术的讨论在对赋值语句的翻译过程中，我只是实现了对语句的翻译，并给出逆波兰式。而实际有用的还必须要能计算出运行的结果，也就是能够达到计算出变量数值的结果。8 收获与体会在本课程设计的过程中，我学习到了好多书本上学不到的东西，真正体会到了编译

17、原理的强大。也同时为自己能够编写出这样一个强大的程序而感到欣慰。通过这次课程设计，我体会到了编译原理的实用性,提高了学习兴趣。同时这次课程设计消除了我对编译原理学习的畏难情绪. 另外这次课程设计使我获得了对词法分析器和语法分析器的感性认识,加深了对理论的理解.在这次编译原理的课程设计中，我采用了递归子程序方法进行语法分析,对文法中的每个非终极符号按其产生式结构产生相应的语法分析子程序,完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。因为使用了递归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。另外，我使用了一种简单的语义规则实现了用递归下降分析法实现了输出逆波兰式的目的。不过这种方法是一种十分有效的方法，可以推广到while，if等语句，虽然本课程设计并没有这个要求。本文还实现了对逆波兰式的翻译结果