编译原理课程设计赋值语句的翻译程序

武汉理工大学《编译原理》课程设计说明书PAGE22-学号：课程设计题目赋值语句的翻译程序学院计算机学院专业软件工程班级姓名指导教师年月日课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目:赋值语句的翻译程序初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据《编译原理》课程所讲授的算法进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。主要功能包括：对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181）进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：①课程设计的题目。②目录。③正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。④结束语。⑤参考文献。⑥附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述 1天系统分析、总体设计、实施计划 3天撰写课程设计报告书 1天指导教师签名：年月日系主任（或责任教师）签名：年月日目录1 引言 32 需求分析 43 总体设计 53.1 设计原则 53.1.1 文法 53.1.2 属性文法的设计 53.2 数据结构和模块说明 63.2.1 主函数 63.2.2 语义分析函数 73.2.3 语句函数 83.2.4 赋值语句函数 93.2.5 表达式函数 93.2.6 项函数 103.2.7 因子函数 113.3 开发工具的选择 114 详细的算法设计 114.1 语义分析函数 114.2 语句函数 134.3 赋值语句函数 134.4 表达式函数 144.5 项函数 154.6 因子函数 154.7 对目标代码的翻译函数 175 软件调试 186 软件的测试方法和结果 187 有关技术的讨论 208 收获与体会 209 结束语 20赋值语句的翻译程序引言递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。本文将采用这种方法对赋值语句进行翻译，并得到逆波兰式的中间代码结果。逆波兰式简介在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，要从中缀表达式直接产生目标代码一般比较麻烦。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。这种表示法的一个特点是，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式。下面我们对照地给出一些表达式的两种表示：中缀表示后缀表示A+BAB+（1）A+B*CABC*+（2）(A+B)*(C+D)AB+CD+*（3）x/y^z-d*exyz^/de*-（4）(a=0∧b>3)∨(e∧x<>y)a0=b3>∧exy<>∧∨（5）从上面的例子可以看出：(1)在两种表示中，运算对象出现的顺序相同；(2)在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。顺便提及，Lukasiewicz原来提出的是前缀表示，即把每一运算符置于其运算对象之前。例如，中缀式a+b和(a+b)/c相应的前缀表示分别为+ab和/+abc。因此，为了区分前缀和后缀表示，通常将后缀表示称为逆波兰表示。因前缀表示并不常用，所以有时也将后缀表示就称为波兰表示。需求分析本课程设计的目的是为了实现赋值语句的递归下降翻译程序设计，并给出对应的逆波兰式中间代码。〈赋值语句〉::=〈标识符〉：=〈算术表达式〉算术表达式的文法：〈算术表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／设计赋值语句文法，给出该文法的属性文法，用递归下降分析法实现对赋值语句的翻译，给出翻译的逆波兰式结果。总体设计本文采用用递归下降分析法实现对赋值语句的翻译，并给出翻译的逆波兰式结果。设计原则设计赋值语句文法，给出该文法的属性文法，用递归下降分析法实现对赋值语句的翻译，给出翻译的逆波兰式结果。按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。该子程序处理相应句型中相对于此非终结符号的产生式。文法〈赋值语句〉::=〈标识符〉：=〈算术表达式〉算术表达式的文法：〈算术表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／属性文法的设计下面，我们按照以上文法，说明如何按语法制导翻译方法将简单算术表达式翻译成为后缀式。为了突出翻译的重点，这里不过多地涉及某些语义处理细节，属性文法中只给出了语义规则。产生式属性文法〈赋值语句〉::=〈标识符〉：=〈算术表达式〉POST=〈标识符〉&〈算术表达式〉&=〈算术表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}POST=〈项〉&{〈项〉&〈加法运算符〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}POST=〈因子〉&{〈因子〉&〈乘法运算符〉}〈因子〉∷＝〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’POST=〈标识符〉｜〈无符号整数〉｜〈表达式〉在属性文法中，POST就是我们要得到的逆波兰式。“&”表示各个逆波兰式的连接。数据结构和模块说明主函数图1主函数流程图语义分析函数本函数的功能是实现对赋值语句的语义分析。最后得到对应的逆波兰式结果。图2语义分析函数流程图语句函数本函数实现了对语句的分析，结果返回的也是逆波兰式。图3语句函数赋值语句函数赋值语句的产生式如下：〈赋值语句〉::=〈标识符〉：=〈算术表达式〉本函数的功能是将其转化为对应的逆波兰式：POST=〈标识符〉&〈算术表达式〉&=图4赋值语句函数表达式函数表达式的产生式如下：〈算术表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}本函数的功能是将其转化为对应的逆波兰式：POST=〈项〉&{〈项〉&〈加法运算符〉}图5表达式函数项函数项的产生式如下：〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}本函数的功能是将其转化为对应的逆波兰式：POST=〈因子〉&{〈因子〉&〈乘法运算符〉}图6项函数因子函数因子的产生式如下：〈因子〉∷＝〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’本函数的功能是将其转化为对应的逆波兰式：POST=〈标识符〉｜〈无符号整数〉｜〈表达式〉图7因子函数开发工具的选择操作系统：windows7平台：VC++6.0详细的算法设计语义分析函数stringlrparser(){ stringtemp=""; scaner(); kk=0; if(syn==1) { temp=yucu(); if(syn==6) { scaner(); if(syn==0&&kk==0) { cout<<"分析成功！"<<endl; } } else { if(kk==0) { cout<<"error:lostend"<<endl; } kk=1; } } else { cout<<"error:can'tfindbegin"<<endl; kk=1; } return(string)temp;}语句函数stringyucu(){ stringtemp=statement(); while(syn==26) { temp+="\n"+statement(); } return(string)temp;}赋值语句函数stringstatement(){ stringID,eplace,temp; scaner(); if(syn==10) { ID=token; scaner(); if(syn==18) { eplace=expression(); temp=ID+""+eplace+"="; } else { cout<<"error:lost:="<<endl; kk=1; } } else { cout<<"lostID"<<endl; kk=1; } return(string)temp;}表达式函数stringexpression(){ stringag1,ag2,temp; inttpsyn; ag1=term(); temp=ag1; while(syn==13||syn==14) { tpsyn=syn; ag2=term(); stringaa=(tpsyn==13)?"+":"-"; temp+=""+ag2+""+aa+""; } return(string)temp;}项函数stringterm(){ stringag1,ag2,temp; inttpsyn; ag1=factor(); temp=ag1; scaner(); while(syn==15||syn==16) { tpsyn=syn; ag2=factor(); stringaa=(tpsyn==15)?"*":"/"; temp+=""+ag2+""+aa+""; scaner(); } return(string)temp;}因子函数stringfactor(){ scaner(); stringfplace=""; if(syn==10) { returntoken; } elseif(syn==11) { sprintf(temp,"%d",sum); return(string)temp; } elseif(syn==27) { fplace=expression(); if(syn==28) { returnfplace; } else { cout<<"error:without)"<<endl; kk=1; } }else { cout<<"error:without("<<endl; kk=1; } return"";}对目标代码的翻译函数这里只给出了关键的代码： do { fin>>word; switch(word[0]) { 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());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(); ag2=getValue(s.top());s.pop(); if(ag1==0)s.push("9999999");elses.push(int2str(floor(ag2/ag1))); break; default: s.push(word); } }while(!fin.eof());软件调试使用VC++自带的功能对源代码进行了调试，直至没有语法错误和语义错误。软件的测试方法和结果采用文本文件输入源代码，然后程序通过读取文本文件中的源代码，进行语义分析，最后输出逆波兰式的中间代码结果。本文一共测试了三组典型数据：begina:=(2+3*4)*4/(3+7)end#begina:=2+3*4;x:=(a+b)/cend#begina:=(x*y/(zmvj8969-r))-sdf;x:=(a+b)/c;yue:=123+r+1+2-4end#图8测试结果另外本文还实现了对逆波兰式的翻译结果。计算出了在程序中的每个变量的值。图9命令行方式执行图10对逆波兰式的翻译执行结果有关技术的讨论在对赋值语句的翻译过程中，我只是实现了对语句的翻译，并给出逆波兰式。而实际有用的还必须要能计算出运行的结果，也就是能够达到计算出变量数值的结果。收获与体会在本课程设计的过程中，我学习到了好多书本上学不到的东西，真正体会到了编译原理的强大。也同时为自己能够编写出这样一个强大的程序而感到欣慰。通过这次课程设计，我体会到了编译原理的实用性,提高了学习兴趣。同时这次课程设计消除了我对编译原理学习的畏难情绪.另外这次课程设计使我获得了对词法分析器和语法分析器的感性认识,加深了对理论的理解.在这次编译原理的课程设计中，我采用了递归子程序方法进行语法分析,对文法中的每个非终极符号按其产生式结构产生相应的语法分析子程序,完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。因为使用了递归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。另外，我使用了一种简单的语义规则实现了用递归下降分析法实现了输出逆波兰式的目的。不过这种方