编译原理课程设计布尔表达式的翻译程序设计

1、学 号： 0120910680328课 程 设 计题 目布尔表达式的翻译程序设计学 院计算机学院专 业软件工程班 级0903姓 名指导教师2012年1月2日布尔表达式的递归下降翻译程序设计1引言 “编译原理”是一门研究设计和构造编译程序原理和方法的课程，是计算机各专业的一门重要的专业基础课。编译原理这门课程蕴含着计算机学科中解决问题的思路、形式化问题和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性较强的课程，要掌握这门课程中的思想，就必须要把所学到的知识付诸实践。而课程设计是将理论与实践相互联系的一种重要方式。2概述2.1设计题目 布尔表达式的

2、递归下降翻译程序设计2.2设计目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。2.3设计任务内容布尔表达式的文法：b tb b and t b| t ft t or ft| f not f |truefalse |（b）| i rop i设计布尔表达式

3、文法，给出该文法的属性文法，用递归下降分析法实现对布尔表达式的翻译，给出翻译的逆波兰式结果。3设计环境与工具visual c+4设计原则4.1基本方法 在本程序中，输入一段布尔语句，使用递归下降的方法得到其推到过程，并利用递归下降翻译的方法的到四元式序列，最终根据生成的四元式序列分析得到逆波兰式。4.2属性文法b tb b.in=t.typeb and t b b.in=t.type addtype(and,entry,b.in)b b.val=t ft t.in=f.type. t or ft t.in=f.type addtype(or,entry,b.in)t tval=f not f

4、f.val= not.f.valf true f.val=truef false f.val=falsef （b） f.val=b.valf i rop i f.val=i.lexval rop i.lexval addtype(i，entry，l.in)5简要的分析与概要设计 在该程序中，总共包括3个主要功能，第一个功能是对输入的布尔语句进行递归下降的分析，从而得出从文法到该布尔语句的推导过程，第二个功能是使用递归下降的方法，该布尔语句的四元式序列，第三个功能对四元式序列进行扫描并分析每个四元式的结构特点，并据此将四元式转化为逆波兰式。main 函数的流程图如下：开始递归下降分析得到推导过程

5、并输出递归下降分析得到四元式序列并输出读四元式并得到逆波兰式并输出 结束 在开始进行本次实验中，本来计划在递归下降分析的过程中就得到逆波兰式，但是经过多次尝试之后总是存在错误，所以采用先得到四元式序列，再根据四元式序列生成逆波兰式这种效率比较低的方法。6详细的算法描述，框图6.1主要数据结构的设计四元式类 在该类中，要包含四元式中的四个元素，运算结果，两个运算数以及一个运算符号class quadpublic:char result8;char arg18;char op8;char arg28; void print()/输出该四元式coutresult=arg1 op arg2endl;q

6、20;word结构体这个结构体的对要用来存储单个单词，包括一个字符串成员。struct wordchar w10;void print()coutw:;wr200;逆波兰式结构体这个结构体的对象用来存储逆波兰式，它的成员是一个word数组struct nipolanword nibolan100; n;翻译器类用来存储翻译过程中的各个变量以及声明主要的函数：class interpreter private:ifstream sourcefile;char buffercode200;/存放源码的缓冲区int syn;int current;/buffercode中当前读到的字符下标char

7、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=0;void run1()scaner();expression();源程序：/* b tb b and t b| t ft t or ft| f not f |tr

8、uefalse |（b）| i rop i*/#include #include #include int kk;int tear=51;int head=50;int numberoftemp=0;int numberofquad=0;class quadpublic:char result8;char arg18;char op8;char arg28; void print()coutresult=arg1 op arg2endl;q20;void qemit(char a,char b,char c,char d)strcpy(qnumberofquad.result,a);strcp

9、y(qnumberofquad.arg1,b);strcpy(qnumberofquad.op,c);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()coutw:;wr200;s

10、truct nipolanword 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,char *n,char *p,char *q);void print() coutabcdendl;t100;void tuidao:emit(char *m,char *n,char *p,char *q)strcpy(a,m);strcpy(

11、b,n);strcpy(c,p);strcpy(d,q);class interpreter private:ifstream sourcefile;char buffercode200;int syn;int 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 bola

12、n();void reset()current=0;void run1()scaner();expression();void bolan()strcpy(n.nibolantear.w,q0.arg1);tear+;strcpy(n.nibolantear.w,q0.arg2);tear+;strcpy(n.nibolantear.w,q0.op);tear+;for(int i=0;i=0;j-)if (strcmp(qi.arg1,qj.result)=0)if (strcmp(qi.arg2,qj+1.result)=0) strcpy(n.nibolantear.w,qi.op);t

13、ear+;break;elsestrcpy(n.nibolantear.w,qi.arg2);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)

14、!=0)strcpy(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);coutbuffer

15、codeendl;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,t,b);tcount+;scaner();t();b1();scaner();else ttcount.emit(b,empty,);void interpreter:t()ttcount.emit(t,f,t);tcount+;f()

16、;t1();void interpreter:t1()if (strcmp(token,rwtab7)=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(f,not,f,);tcount+;scaner();f();else if(strcmp(token,rwtab0)=0)ttcount.emit(f

17、,true,);tcount+;scaner();else if(strcmp(token,rwtab2)=0) ttcount.emit(f,false,);tcount+;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();scaner();void interpreter:scaner()int m=0;for(int

18、 i=0;i=a)&(buffercodecurrent=a)&(buffercodecurrent=a)&(buffercodecurrent=a)&(buffercodecurrent=0)&(buffercodecurrent=9)tokenm=buffercodecurrent;m+;current+;tokenm+=0;else if (buffercodecurrent=() token0=(;token1=0;current+;else if (buffercodecurrent=) token0=);token1=0;current+;char*interpreter:expr

19、ession()char *tp,*ep2,*eplace,*tt;tp=new char8;ep2=new char8;eplace=new char8;tt=new char8;strcpy(eplace,term();while(strcmp(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,*eplac

20、e,*tt;tp=new char8;ep2=new char8;eplace=new char8;tt=new char8;strcpy(eplace,unit();while (strcmp(token,and)=0)strcpy(tt,token);scaner();strcpy(ep2,unit();strcpy(tp,newtemp();qemit(tp,eplace,tt,ep2);strcpy(eplace,tp);/scaner();return eplace;char* interpreter:unit()char *fplace;fplace=new char8;if (s

21、trcmp(token,true)=0)|(strcmp(token,false)=0)strcpy(fplace,token);scaner();if(strcmp(token,i)=0) strcpy(fplace,newtemp();qemit(fplace,i,rop,i); if(strcmp(token,()=0)scaner(); strcpy(fplace,expression();if (syn=28)return fplace; if(strcmp(token,not)=0)char *fplace1=new char8;scaner();if (strcmp(token,

22、()=0) strcpy(fplace1,expression();else strcpy(fplace1,token);strcpy(fplace,newtemp();qemit(fplace,not,fplace1);if (syn=28)return fplace;/elseerror(4);return fplace;void main()interpreter in;cout请输入源代码:endl;in.read();in.run();cout推导过程为：endl;for(int i=0;itcount;i+)ti.print();in.toword();cout分析的单词为：end

23、l;for (i=0;iwcount;i+)wri.print();coutendl;cout四元式为：endl;in.reset();/couthereendl;in.run1();for(i=0;inumberofquad;i+)qi.print();cout逆波兰式为:endl;bolan();for(i=head;itear;i+)coutn.nibolani.w ;couttb，然后执行t（）与b1（）流程图为非终结符t对应的函数t（） 该函数首先要写入t=ft，然后执行f（）与t1（）流程图为：非终结符b对应的函数b1（） 在该函数中如果读入的下一个单词是“and”则写入b=and

24、 t b.否则，要写入b推出了空串。流程图为：非终结符t对应的函数t1（） 在该函数中如果读入的下一个单词是“or”则写入t=or ft.否则，要写入t推出了空串。流程图为：非终结符f对应的函数f（） 由于非终结符f对应的推出式比较多，所以该函数的分支也比较多，当读入“not”时，则写入f=not f并执行f（）函数,当读入”true”或者”false”时，则要写入f=true 或者f=false当读入的字符为”(”时，则写入f=(b),并执行b（）函数，当读入的单词为i时，要写入f=i rop i.流程图为：在完成该功能时，推到过程存入到tuidao类生成的对象数组中。6.4递归下降得到四元

25、式序列 生成四元式必须分析布尔语句，and语句以及最小的分析单元三个部分expression（）函数分析布尔语句，term（）分析and语句，unit（）分析最小单元该过程的入口函数run1（）流程图如下：expression（）函数 该函数首先调用了一个term函数，如果下一个读到单词是“or”则分析or后面的一个term并将or和两个term写入到四元式序列中，如果读到的不是“or”则只把term返回到四元式序列中。流程图如下：term()函数 该函数首先调用了一个factor函数，如果下一个读到单词是“and”则分析and后面的一个factor并将or和两个factor写入到四元式序列中

26、，如果读到的不是“and”则只把factor返回到四元式序列中。流程图为:unit()函数 在该函数中，分析了优先级最高的运算或者是单个终结符，如果读入的是true或者false则直接返回token，如果读入的是 i则把i rop i写入到四元式序列中，如果读入的是not，则分析not后面的expression（），并将not 以及expression（）写入到四元式中，返回生成的newtemp流程图： 该过程结束后，布尔语句对应的四元式存放在quad类生成的对象数组q中.6.5分析四元式序列生成逆波兰式 本过程根据四元式序列以及每一个四元式的类型，将四元式中的信息按照一定规则写入到逆波兰式中

27、，主要函数为bolan（）函数，bolan函数将四元式序列从头到尾扫描一遍，对于每一个四元式序列根据其操作数是临时变量还是终结符将终结符以及操作符按照逆波兰式规则写入到逆波兰式类生成的对象n中。 当当前四元式类型为 临时变量=临时变量 op 临时变量是，则直接将op插入到逆波兰式尾部。 当当前四元式类型为 临时便令=arg1 op arg2时则按照arg1，arg2，op的顺序将他们插入逆波兰式的尾部。 当当前四元式类型为 临时便令=临时变量 op arg1时则按照arg1，op的顺序将他们插入逆波兰式的尾部。 当当前四元式类型为 临时便令=arg1 op 临时变量时则将op的顺序将他们插入逆波兰式的尾部，将arg1插入到逆波兰式的首部。bolan函数的流程图为：本过程结束之后，逆波兰式存放在nibolan类定义的对象n中。7软件的测试方法和测试结果输入一个字符串，执行改程序，观察产生的四元式以及逆波兰式是否正确。测试数据1：测试数据2测试数据38设计的特点、不足收获与体会8.1设计的特点 这次课程设计中，使用递归下降分析方法完成了布尔语句的翻译，程序不仅按照题目要求的到了翻译的逆波兰式，而且还求出了布