武汉理工大学-编译原理课程设计-中国好学长系列之小灰灰的爸爸教材

1、武汉理工大学编译原理课程设计说明书学 号：课程设计题目布尔表达式翻译为逆波兰式的算法实现学院计算机科学与技术学院专业软件工程班级中国好学长系列姓名小灰灰的爸爸指导教师何九周2014 年 1 月 2 日武汉理工大学编译原理课程设计说明书课程设计任务书目录错. 误！未定义书签1 引言 22 概述 32.1设计题目 32.2设计目的 32.3设计任务内容 33 设计环境与工具 44 设计原则 44.1基本方法 44.2属性文法 45 简要的分析与概要设计 46 详细的算法描述，框图 56.1主要数据结构的设计 56.2全局变量设计 76.3递归下降得到推导过程 76.4 递归下降得到四元式序列 1.

2、16.5分析四元式序列生成逆波兰式 147软件的测试方法和测试结果 168 设计的特点、不足收获与体会 168.1设计的特点 168.2设计的不足 168.3收获与体会 169 参考文献 16附录：本科生课程设计成绩评定表武汉理工大学编译原理课程设计说明书课程设计任务书学生姓名： 专业班级：指导教师： 何九周 工作单位：计算机科学与技术学院 题 目 : 布尔表达式翻译为逆波兰式的算法实现初始条件：程序设计语言 : 主要使用 C语言的开发工具，或者采用 LEX、YACC等工具，也可利用其他 熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务 : （包括课程设计工作

3、量及其技术要求，说明书撰写等具体要求）1. 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求， 学会设计的基本方法与步骤， 学会如何运用前修知识与收集、 归纳相关资料解决具体问题的方 法。严格要求自己，要独立思考， 按时、独立 完成课程设计任务。2. 主要功能包括：利用 LR 分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波 兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3. 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用 出错处理程序。4. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不

4、少于 0.3 万字。包含内 容： 课程设计的题目。 目录。 正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法 及中间代码形式的描述、文法和属性文法的设计） ，数据结构与模块说明（功能与流程图） 、详细的 算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。 结束语。 参考文献。 附录：软件清单（或者附盘） 。时间安排：消化资料、系统调查、形式描述1 天系统分析、总体设计、实施计划3 天撰写课程设计报告书1 天指导教师签名：2014 年 1 月 2 日系主任（或责任教师）签名： 2014 年 1 月 2 日武汉理工大学编译原理课程设计说明书布尔表

5、达式翻译为逆波兰式的算法实现1 引言实践离不开理论，而理论是为了实践，这一点在软件设计的学习过程中显得尤为重 要。而编译原理是一门研究设计和构造编译程序原理和方法的课程，是计算机各专 业的一门重要的专业基础课。编译原理这门课程蕴含着计算机学科中解决问题的思路、 形式化问题和解决问题的方法， 对应用软件和系统软件的设计与开发有一定的启发和指 导作用。“编译原理”是一门实践性较强的课程，要掌握这门课程中的思想，就必须要 把所学到的知识付诸实践。而课程设计是将理论与实践相互联系的一种重要方式。本文 是编译原理中的“布尔表达式翻译为逆波兰式的算法实现”课程设计的说明书。 2 概述2.1 设计题目布尔表

6、达式翻译为逆波兰式的算法实现2.2 设计目的课程设计是将理论加以实践较好的方法，也对学生的一种全面综合训练，是与课堂 听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时 的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求 学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数 据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思 考问题、分析问题、解决实际问题的动手能力。2.3 设计任务内容针对布尔表达式的二义性文法：B B and B | B or B | not B | ( B ) | tru

7、e false | i rop i将文法拓广为 G'B' ：(0) B ' B(1) BB and B(2) BB or B(3) Bnot B(4) B( B )(5) Btrue(6) Bfalse武汉理工大学编译原理课程设计说明书(7) Bi rop i利用 LR 分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3 设计环境与工具Visual C+4 设计原则4.1 基本方法在本程序中，要求利用 LR 分析法编制、调试其语法及语义分析程序，生成的中间代 码为逆波兰式。编制好分析程序后，

8、设计若干用例，上机测试并通过所设计的分析程序4.2 属性文法B TB B' .in=T.typeB and T B B ' .in=T.typeaddtype(and,entry,B.in)B B ' .val= T FTT.in=F.type.T or FT T ' .in=F.typeaddtype(or,entry,B.in)T T' val= F not FF.val= not.F.valF trueF.val=trueF falseF.val=falseF ( B)F.val=B.valF i rop iF.val=i.lexvalrop i.

9、lexval addtype(i5 简要的分析与概要设计，entry ，l.in)该程序共包括 3 个模块， 第一个模块是对输入的布尔语句进行递归下降的分 析，从而得出从文法到该布尔语句的推导过程，第二个 模块是使用递归下降的 方法，该布尔语句的四元式序列，第三个 模块对四元式序列进行扫描并分析每 个四元式的结构特点，并据此将四元式转化为逆波兰式。main 函数的流程图如下：武汉理工大学编译原理课程设计说明书开始递归下降分析得到推导过程并输出递归下降分析得到四元式序列并输出读四元式并得到逆波兰式并输出结束在开始进行本次实验中，本来计划在递归下降分析的过程中就得到逆波兰式，但是经过多次尝 试之后

10、总是存在错误，所以采用先得到四元式序列，再根据四元式序列生成逆波兰式这种效率比较 低的方法。6 详细的算法描述，框图6.1 主要数据结构的设计逆波兰式结构体这个结构体的对象用来存储逆波兰式，它的成员是一个word 数组struct nipolanword nibolan100; n;四元式类在该类中，要包含四元式中的四个元素，运算结果，两个运算数以及一个运算符号class quad武汉理工大学编译原理课程设计说明书public:char result8;char arg18;char op8;char arg28;void print()/ 输出该四元式 cout<<result&

11、lt;<"="<<arg1<<" "<<op<<" "<<arg2<<endl;q20;Word结构体这个结构体的对要用来存储单个单词，包括一个字符串成员 struct wordchar w10;void print()cout<<w<<":"wr200;翻译器类用来存储翻译过程中的各个变量以及声明主要的函数： class interpreterprivate:ifstream SourceFile;武汉理工大学编

12、译原理课程设计说明书char buffercode200;/ 存放源码的缓冲区int syn;int current;/buffercode中当前读到的字符下标char token8;/ 记录当前读到的单词public:void scaner();void B();void B1();void T();void F();void T1();void run();void read();void bolon();void toword();char *factor();char *expression();char *term();void bolan();void reset()current

13、=0;void run1()scaner();expression();6.2 全局变量设计int tear=51;/ 逆波兰式尾部int head=50;/ 逆波兰是首部int numberoftemp=0;/ 临时变量个数int numberofquad=0;/ 四元式个数6.3 递归下降得到推导过程根据递归下降的思想，对于文法中的每个非终结符编写一个函数，每个函数的功能 是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此 相应的这组函数必然以相互递归的方式进行调用。 该过程的基本思想为每执行一个非终 结符对应的函数就根据读入的单词符号来写入该非终结符对应的推出式

14、。该功能的入口函数 run1 的流程图如下：武汉理工大学编译原理课程设计说明书开始结束非终结符 B 对应的函数 B（） 该函数首先要写入 B=>TB'，然后执行 T（）与 B1（） 流程图为开始写入非终结符 B 的推出式T()B1()结束非终结符 T 对应的函数 T（）该函数首先要写入 T=>FT'，然后执行 F（）与 T1（）武汉理工大学编译原理课程设计说明书流程图为：开始结束非终结符 B'对应的函数 B1（）在该函数中如果读入的下一个单词是“and”则写入 B'=>and T B'. 否则，要写入B'推出了空串流程图为：开始

15、YN写入非终结符B'的推导式T()写入 B '推出空串B1()9结束武汉理工大学编译原理课程设计说明书非终结符 T'对应的函数 T1（） 在该函数中如果读入的下一个单词是“ or ”则写入 T'=>or FT'. 否则，要写入 T' 推出了空串。流程图为：开始读入“ or”Y写入非终结符T'的推导式写入 T'推出空串结束非终结符 F 对应的函数 F（）由于非终结符 F 对应的推出式比较多，所以该函数的分支也比较多，当读入“ not 时，则写入 F=>not F 并执行 F（）函数 , 当读入” true ”或者” fa

16、lse ”时，则要写入 F=>true 或者 F=>false 当读入的字符为” （ ”时，则写入 F=>（B）, 并执行 B（）函数， 当读入的单词为 i 时，要写入 F=>i rop i.流程图为：10武汉理工大学编译原理课程设计说明书开始读入下一字符nottruefalsei写入 F=>true写入 F=>i rop iF()B()写入 F=>not F写入 F=>false写入 F=>(B)结束在完成该功能时，推到过程存入到 tuidao 类生成的对象数组中 。6.4 递归下降得到四元式序列生成四元式必须分析布尔语句， and 语句

17、以及最小的分析单元三个部分 expression （） 函数分析布尔语句， term （）分析 and 语句， unit （）分析最小单元 该过程的入口函数 run1 （）流程图如下：开始结束11武汉理工大学编译原理课程设计说明书expression ()函数该函数首先调用了一个 term 函数，如果下一个读到单词是“ or ”则分析 or 后面的 一个 term 并将 or 和两个 term 写入到四元式序列中， 如果读到的不是“ or ”则只把 term 返回到四元式序列中。流程图如下：开始Token=orY NSacaner;term();写入四元式return结束term() 函数该函

18、数首先调用了一个 factor 函数，如果下一个读到单词是“ and”则分析 and 后 面的一个 factor 并将 or 和两个 factor 写入到四元式序列中，如果读到的不是“ and” 则只把 factor 返回到四元式序列中。12武汉理工大学编译原理课程设计说明书流程图为:开始Token=andY NSacaner;unit(); 写入四元式return结束unit（） 函数在该函数中， 分析了优先级最高的运算或者是单个终结符， 如果读入的是 true 或者 false 则直接返回 token ，如果读入的是 i 则把 i rop i 写入到四元式序列中，如果读 入的是 not ，

19、则分析 not 后面的 expression （），并将 not 以及 expression （）写入 到四元式中，返回生成的 newtemp 流程图：13武汉理工大学编译原理课程设计说明书开始tokentrue|falsei(not写入 i rop iscanerfplace<-token;scaner();scaner();fplace<-experssion()fplace<-newtemp()fplace<-tokenfplace<-newtemp()写入四元式 expression();Fplace<-newtemp()return fplace开

20、始该过程结束后，布尔语句对应的四元式存放在 quad类生成的对象数组 q 中.6.5 分析四元式序列生成逆波兰式本过程根据四元式序列以及每一个四元式的类型，将四元式中的信息按照一定规则 写入到逆波兰式中，主要函数为 bolan （）函数， bolan 函数将四元式序列从头到尾扫 描一遍，对于每一个四元式序列根据其操作数是临时变量还是终结符将终结符以及操作 符按照逆波兰式规则写入到逆波兰式类生成的对象 n 中。当当前四元式类型为 临时变量 =临时变量 OP 临时变量是，则直接将 op 插入到逆波14武汉理工大学编译原理课程设计说明书兰式尾部。当当前四元式类型为 临时便令 =arg1 op arg

21、2 时则按照 arg1， arg2，op 的顺序将 他们插入逆波兰式的尾部。当当前四元式类型为 临时便令 =临时变量 op arg1 时则按照 arg1 ， op的顺序将他 们插入逆波兰式的尾部。当当前四元式类型为 临时便令 =arg1 op 临时变量时则将 op 的顺序将他们插入逆波 兰式的尾部，将 arg1 插入到逆波兰式的首部。bolan 函数的流程图为：开始将第一个四元式依次写入逆波兰式i=0i四元式数T=T op T 型T=a op a 型T=T op a 型T=a op T 型Y第i 个四元式类型在队列尾部插入 op在队列尾部插入在队列尾部插入arg1,arg2,oparg2,op

22、在队列尾部插入 op在队列尾部插入 arg1T 为临时变量 a 为终结符结束15武汉理工大学编译原理课程设计说明书本过程结束之后，逆波兰式存放在 nibolan 类定义的对象 n 中。7 软件的测试方法和测试结果输入一个字符串，执行改程序，观察产生的四元式以及逆波兰式是否正确。8 设计的特点、不足收获与体会8.1 设计的特点该程序不仅按照题目要求的到了翻译的逆波兰式，而且还求出了布尔语句的推导过 程和四元式，实现的功能比较多，对翻译的过程和结果有一个比较全面的描述。程序的 逻辑明确，易于理解。8.2 设计的不足在本次课程设计的程序中存在着两个主要问题是没有在递归下降的过程中直接求出 逆波兰式，

23、而是根据生成的四元式序列产生的逆波兰式，虽然可以达到题目的要求，但 是程序的效率比较低。另外，在递归下降生成逆波兰式的过程中，由于最小单元函数中 读入” not ”以及” （ ”的分支中出现了问题， 导致了在调试过程中 not 语句以及括号中 语句必须放在最后，否则在分析完该单元之后程序不再继续向后扫描。导致了布尔语句 分析不全。8.3 收获与体会通过本次课程设计，我学会了将理论知识运用到实际编码中，同时也知道严谨细心 对于一个程序员来说有多么重要。这次课程设计在让我对编译原理更加熟悉的同时 也训练了我的耐心和毅力。虽然程序写得很一般，有的地方甚至有些小错误，但是我仍 然收获了很多平时学习中没

24、有学到的知识，锻炼了平时学习中没有的学习和实践能力。 9 参考文献编译原理（第二版） , 主编：吕映芝、张素琴、蒋维杜 , 出版社：清华大学出版社 , 出 版时间： 2004年 11 月编译原理 ,主编：张幸儿 ,出版社：科学出版社 ,出版时间： 1999年 4月16武汉理工大学编译原理课程设计说明书本科生课程设计成绩评定表班级： 姓名： 学号：序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、 可行性、 创造性204设计结果正确性405设计报告的规范性106设计验收10总得分 /等级评语：注：最终成绩以五级分制记。优（ 90-100分）、良（ 80-89

25、 分）、中（ 70-79分）、 及格（ 60-69分）、60 分以下为不及格指导教师签名：2014 年 1 月 日武汉理工大学编译原理课程设计说明书附录：代码不要求加入实验报告，上传时考虑到如果分成多个文档可能会让大家难以找到，就 贴在后面了。#include <iostream.h>#include <string.h>#include <fstream.h>int kk;int tear=51;int head=50;int numberoftemp=0;int numberofquad=0;class quadpublic:char result8;c

26、har arg18;char op8;char arg28;void print()cout<<result<<"="<<arg1<<" "<<op<<" "<<arg2<<endl;q20;void qemit(char a,char b,char c,char d)strcpy(qnumberofquad.result,a);strcpy(qnumberofquad.arg1,b);strcpy(qnumberofquad.op,c);

27、strcpy(qnumberofquad.arg2,d); numberofquad+;char* newtemp()char *p;int temp=numberoftemp;p=new char8;p0='t'for(int i=0;i+)p+i=char(temp%10+48); temp=temp/10;if (temp=0) pi+1='0' break;武汉理工大学编译原理课程设计说明书numberoftemp+;return p;struct wordchar w10;void print() cout<<w<<"

28、:" wr200; struct nipolan word nibolan100; n;int tcount=0;int wcount=0;char *rwtab9="true","not","false","(",")","rop","i","or","and" class tuidaopublic:char a10;char b10;char c10;char d10;void emit(char *m

29、,char *n,char *p,char *q);void print() cout<<a<<"=>"<<b<<c<<d<<endl; t100;void tuidao:emit(char *m,char *n,char *p,char *q)strcpy(a,m);strcpy(b,n);strcpy(c,p);strcpy(d,q);class interpreterprivate: ifstream SourceFile; char buffercode200; int syn; int

30、current;武汉理工大学编译原理课程设计说明书char token8;public:void scaner();void B();void B1();void T();void F();void T1();void run();void read();void bolon();void toword();char *unit();char *expression();char *term();void bolan();void reset()current=0;void run1()scaner(); expression();void bolan() strcpy(n.nibolante

31、ar.w,q0.arg1);tear+; strcpy(n.nibolantear.w,q0.arg2);tear+; strcpy(n.nibolantear.w,q0.op);tear+; for(int i=0;i<numberofquad;i+)for (int j=i-1;j>=0;j-)if (strcmp(qi.arg1,qj.result)=0)if (strcmp(qi.arg2,qj+1.result)=0) strcpy(n.nibolantear.w,qi.op);tear+;break;else strcpy(n.nibolantear.w,qi.arg2

32、);tear+; strcpy(n.nibolantear.w,qi.op);tear+; break;武汉理工大学编译原理课程设计说明书if (strcmp(qi.arg1,qj.result)!=0)&&(strcmp(qi.arg2,qj+1.result)=0)strcpy(n.nibolantear.w,qi.op);tear+;strcpy(n.nibolanhead.w,qi.arg1);head-;break;if (strcmp(qi.arg1,qj.result)!=0)&&(strcmp(qi.arg2,qj.result)!=0)strc

33、py(n.nibolantear.w,qi.arg1);tear+;strcpy(n.nibolantear.w,qi.arg2);tear+;strcpy(n.nibolantear.w,qi.op);tear+;break;void interpreter:toword()current=0;int i=0;while (buffercodecurrent!='#')scaner();strcpy(wrwcount.w,token);wcount+;i+;void interpreter:read()cin.getline(buffercode,200);cout<&

34、lt;buffercode<<endl;void interpreter:run()current=0;scaner();B();武汉理工大学编译原理课程设计说明书void interpreter:B()ttcount.emit("B"," ","T","B'");tcount+;T();B1();void interpreter:B1()if (strcmp(token,rwtab8)=0)ttcount.emit("B'","and",&quo

35、t;T","B'");tcount+;scaner();T();B1();s caner();else ttcount.emit("B'","empty","","");void interpreter:T()ttcount.emit("T","","F","T'");tcount+;F();T1();void interpreter:T1()if (strcmp(token,rwt

36、ab7)=0)ttcount.emit("T'","or","F","T''");tcount+;scaner();F();T1();else ttcount.emit("T'","empty","","");/ F not F |truefalse |( B)| i rop ivoid interpreter:F()if(strcmp(token,rwtab1)=0)ttcount.emit("

37、;F","not","F","");tcount+;scaner();F() ;else if(strcmp(token,rwtab0)=0)ttcount.emit("F","","true","");tcount+;scaner();else if(strcmp(token,rwtab2)=0) ttcount.emit("F","","false","");tc

38、ount+;scaner();else if(strcmp(token,rwtab3)=0)ttcount.emit("F","(","B",")");tcount+;scaner();B();else if(strcmp(token,rwtab6)=0)ttcount.emit("F","i","rop","i");tcount+;scaner();scaner();sca ner();武汉理工大学编译原理课程设计说明书void in

39、terpreter:scaner()int m=0;for(int i=0;i<8;i+) tokeni=' 'while (buffercodecurrent=' ') current+;if(buffercodecurrent>='a')&&(buffercodecurrent<='z')|(buffercodecurrent>=' A')&&(buffercodecurrent<='Z') while (buffercodecurr

40、ent>='a')&&(buffercodecurrent<='z')|(buffercodecurrent>='A')&&(b uffercodecurrent<='Z')|(buffercodecurrent>='0')&&(buffercodecurrent<='9') tokenm=buffercodecurrent;m+; current+;tokenm+='0'else if (buffe

41、rcodecurrent='(') token0='('token1='0'current+;else if (buffercodecurrent=')') token0=')'token1='0'current+; char*interpreter:expression()char *tp,*ep2,*eplace,*tt;tp=new char8;ep2=new char8;eplace=new char8;tt=new char8;strcpy(eplace,term(); while(str

42、cmp(token,"or")=0)strcpy(tt,token); scaner(); strcpy(ep2,term(); strcpy(tp,newtemp(); qemit(tp,eplace,tt,ep2); strcpy(eplace,tp);return eplace; char*interpreter:term()char *tp,*ep2,*eplace,*tt;武汉理工大学编译原理课程设计说明书tp=new char8;ep2=new char8;eplace=new char8;tt=new char8;strcpy(eplace,unit();while (strcmp(token,"and