《赋值语句的递归下降翻译程序设计2》由会员分享,可在线阅读,更多相关《赋值语句的递归下降翻译程序设计2(18页珍藏版)》请在金锄头文库上搜索。
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*-
3、(4)(a=0b3)(exy)a0=b3exy(5)从上面的例子可以看出:(1) 在两种表示中,运算对象出现的顺序相同;(2) 在后缀表示中,运算符按实际计算顺序从左到右排列,且每一运算符总是跟在其运算对象之后。 顺便提及,Lukasiewicz原来提出的是前缀表示,即把每一运算符置于其运算对象之前。例如,中缀式a+b和(a+b)/c相应的前缀表示分别为+ab和/+abc。因此,为了区分前缀和后缀表示,通常将后缀表示称为逆波兰表示。因前缀表示并不常用,所以有时也将后缀表示就称为波兰表示。2 需求分析本课程设计的目的是为了实现赋值语句的递归下降翻译程序设计,并给出对应的逆波兰式中间代码。赋值语句
4、:= 标识符 := 算术表达式算术表达式的文法:算术表达式项加法运算符项项 因子乘法运算符因子因子 标识符无符号整数(表达式)加法运算符 乘法运算符 设计赋值语句文法,给出该文法的属性文法,用递归下降分析法实现对赋值语句的翻译,给出翻译的逆波兰式结果。3 总体设计本文采用用递归下降分析法实现对赋值语句的翻译,并给出翻译的逆波兰式结果。3.1 设计原则设计赋值语句文法,给出该文法的属性文法,用递归下降分析法实现对赋值语句的翻译,给出翻译的逆波兰式结果。按照递归下降分析技术,递归下降识别程序是由一组子程序组成,每个子程序对应于一个非终结符号。该子程序处理相应句型中相对于此非终结符号的产生式。3.1
5、.1 文法赋值语句:= 标识符 := 算术表达式算术表达式的文法:算术表达式项加法运算符项项 因子乘法运算符因子因子 标识符无符号整数(表达式)加法运算符 乘法运算符 3.1.2 属性文法的设计下面,我们按照以上文法,说明如何按语法制导翻译方法将简单算术表达式翻译成为后缀式。为了突出翻译的重点,这里不过多地涉及某些语义处理细节,属性文法中只给出了语义规则。产生式属性文法赋值语句:= 标识符 := 算术表达式POST=标识符&算术表达式&=算术表达式项加法运算符项POST=项&项&加法运算符项 因子乘法运算符因子POST=因子&因子&乘法运算符因子 标识符无符号整数(表达式)POST=标识符无符
6、号整数表达式在属性文法中,POST就是我们要得到的逆波兰式。“&”表示各个逆波兰式的连接。3.2 数据结构和模块说明3.2.1 主函数图1 主函数流程图3.2.2 语义分析函数本函数的功能是实现对赋值语句的语义分析。最后得到对应的逆波兰式结果。图2 语义分析函数流程图3.2.3 语句函数本函数实现了对语句的分析,结果返回的也是逆波兰式。图3 语句函数3.2.4 赋值语句函数赋值语句的产生式如下:赋值语句:= 标识符 := 算术表达式本函数的功能是将其转化为对应的逆波兰式:POST=标识符&算术表达式&=图4 赋值语句函数3.2.5 表达式函数表达式的产生式如下:算术表达式项加法运算符项本函数的
7、功能是将其转化为对应的逆波兰式:POST=项&项&加法运算符图5 表达式函数3.2.6 项函数项的产生式如下:项 因子乘法运算符因子本函数的功能是将其转化为对应的逆波兰式:POST=因子&因子&乘法运算符图6 项函数3.2.7 因子函数因子的产生式如下:因子 标识符无符号整数(表达式)本函数的功能是将其转化为对应的逆波兰式:POST=标识符无符号整数表达式图7 因子函数3.3 开发工具的选择操作系统:windows XP内存:1G平台:VC+ 6.04 详细的算法设计4.1 语义分析函数string lrparser()string temp=;scaner();kk=0;if(syn=1)t
8、emp=yucu();if(syn=6)scaner();if(syn=0 & kk=0)cout分析成功!endl;elseif(kk=0)couterror:lost end endl;kk=1;elsecouterror: cant find beginendl;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,epla
9、ce,temp;scaner();if(syn=10)ID=token;scaner();if(syn=18)eplace=expression();temp=ID+ +eplace+ = ;elsecouterror:lost :=endl;kk=1;elsecoutlost IDendl;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
10、aa=(tpsyn=13)?+:-;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+ ;scaner();return (string)temp;4.6 因子函数string factor()scaner();string fplac
11、e=;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 couterror: without ) endl;kk=1; elsecouterror: without ( word;switch(word0)case =:ag1=getValue(s.top();s.pop();ags=s.top();s.pop();insertTable(ags,ag1);br
12、eak;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.top();s.pop();ag2=getValue(s.top();s.pop();s.push(int2str(floor(ag2*ag1);break;case /:ag1=getValue(s.top();s.pop