布尔表达式的翻译程序设计

1学号：0120910680328课程设计题目布尔表达式的翻译程序设计学院计算机学院专业软件工程班级0903姓名陈银指导教师何九周2012年1月2日2布尔表达式的递归下降翻译程序设计1引言“编译原理”是一门研究设计和构造编译程序原理和方法的课程，是计算机各专业的一门重要的专业基础课。编译原理这门课程蕴含着计算机学科中解决问题的思路、形式化问题和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性较强的课程，要掌握这门课程中的思想，就必须要把所学到的知识付诸实践。而课程设计是将理论与实践相互联系的一种重要方式。2概述2.1设计题目布尔表达式的递归下降翻译程序设计2.2设计目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。2.3设计任务内容布尔表达式的文法：BTB′B′andTB′|εTFT′T′orFT′|εFnotF|true｜false|（B）|iropi设计布尔表达式文法，给出该文法的属性文法，用递归下降分析法实现对布尔表达式的翻译，给出翻译的逆波兰式结果。33设计环境与工具VisualC++4设计原则4.1基本方法在本程序中，输入一段布尔语句，使用递归下降的方法得到其推到过程，并利用递归下降翻译的方法的到四元式序列，最终根据生成的四元式序列分析得到逆波兰式。4.2属性文法BTB′B’.in=T.typeB′andTB′B’.in=T.typeaddtype(and,entry,B.in)B′εB’.val=εTFTT.in=F.type.T′orFT′T’.in=F.typeaddtype(or,entry,B.in)T′εT’val=εFnotFF.val=not.F.valFtrueF.val=trueFfalseF.val=falseF（B）F.val=B.valFiropiF.val=i.lexvalropi.lexvaladdtype(i，entry，l.in)5简要的分析与概要设计在该程序中，总共包括3个主要功能，第一个功能是对输入的布尔语句进行递归下降的分析，从而得出从文法到该布尔语句的推导过程，第二个功能是使用递归下降的方法，该布尔语句的四元式序列，第三个功能对四元式序列进行扫描并分析每个四元式的结构特点，并据此将四元式转化为逆波兰式。main函数的流程图如下：4在开始进行本次实验中，本来计划在递归下降分析的过程中就得到逆波兰式，但是经过多次尝试之后总是存在错误，所以采用先得到四元式序列，再根据四元式序列生成逆波兰式这种效率比较低的方法。6详细的算法描述，框图6.1主要数据结构的设计四元式类在该类中，要包含四元式中的四个元素，运算结果，两个运算数以及一个运算符号classquad{public:charresult[8];chararg1[8];charop[8];chararg2[8];voidprint()//输出该四元式{coutresult=arg1oparg2endl;开始递归下降分析得到推导过程并输出递归下降分析得到四元式序列并输出读四元式并得到逆波兰式并输出结束5}}q[20];Word结构体这个结构体的对要用来存储单个单词，包括一个字符串成员。structword{charw[10];voidprint(){coutw:;}}wr[200];逆波兰式结构体这个结构体的对象用来存储逆波兰式，它的成员是一个word数组structnipolan{wordnibolan[100];}n;翻译器类用来存储翻译过程中的各个变量以及声明主要的函数：classinterpreter{private:ifstreamSourceFile;charbuffercode[200];//存放源码的缓冲区intsyn;intcurrent;//buffercode中当前读到的字符下标chartoken[8];//记录当前读到的单词public:6voidscaner();voidB();voidB1();voidT();voidF();voidT1();voidrun();voidread();voidbolon();voidtoword();char*factor();char*expression();char*term();voidbolan();voidreset(){current=0;};voidrun1(){scaner();expression();};};源程序：/*BTB′B′andTB′|εTFT′7T′orFT′|εFnotF|true｜false|（B）|iropi*/#includeiostream.h#includestring.h#includefstream.hintkk;inttear=51;inthead=50;intnumberoftemp=0;intnumberofquad=0;classquad{public:charresult[8];chararg1[8];charop[8];chararg2[8];voidprint(){coutresult=arg1oparg2endl;}}q[20];voidqemit(chara[],charb[],charc[],chard[]){strcpy(q[numberofquad].result,a);strcpy(q[numberofquad].arg1,b);strcpy(q[numberofquad].op,c);strcpy(q[numberofquad].arg2,d);8numberofquad++;}char*newtemp(){char*p;inttemp=numberoftemp;p=newchar[8];p[0]='t';for(inti=0;;i++){p[++i]=char(temp%10+48);temp=temp/10;if(temp==0){p[i+1]='\0';break;}}numberoftemp++;returnp;};structword{charw[10];voidprint(){coutw:;}}wr[200];structnipolan{wordnibolan[100];}n;9inttcount=0;intwcount=0;char*rwtab[9]={true,not,false,(,),rop,i,or,and};classtuidao{public:chara[10];charb[10];charc[10];chard[10];voidemit(char*m,char*n,char*p,char*q);voidprint(){couta=bcdendl;}}t[100];voidtuidao::emit(char*m,char*n,char*p,char*q){strcpy(a,m);strcpy(b,n);strcpy(c,p);strcpy(d,q);}classinterpreter{private:ifstreamSourceFile;charbuffercode[200];intsyn;intcurrent;chartoken[8];10public:voidscaner();voidB();voidB1();voidT();voidF();voidT1();voidrun();voidread();voidbolon();voidtoword();char*unit();char*expression();char*term();voidbolan();voidreset(){current=0;};voidrun1(){scaner();expression();};};voidbolan(){strcpy(n.nibolan[tear].w,q[0].arg1);tear++;strcpy(n.nibolan[tear].w,q[0].arg2);tear++;11strcpy(n.nibolan[tear].w,q[0].op);tear++;for(inti=0;inumberofquad;i++){for(intj=i-1;j=0;j--){if(strcmp(q[i].arg1,q[j].result)==0){if(strcmp(q[i].arg2,q[j+1].result)==0){strcpy(n.nibolan[tear].w,q[i].op);tear++;break;}else{strcpy(n.nibolan[tear].w,q[i].arg2);tear++;strcpy(n.nibolan[tear].w,q[i].op);tear++;break;}}if((strcmp(q[i].arg1,q[j].result)!=0)&&(strcmp(q[i].arg2,q[j+1].result)==0)){strcpy(n.nibolan[tear].w,q[i].op);tear++;strcpy(n.nibolan[head].w,q[i].arg1);head--;break;}if((strcmp(q[i].arg1,q[j].result)!=0)&&(strcmp(q[i].arg2,q[j].result)!=0)){strcpy(n.nibolan[tear].w,q[i].arg1);tear++;12strcpy(n.nibolan[tear].w,q[i].arg2);tear++;strcpy(n.nibolan[tear].w,q[i].op);tear++;break;}}}}voidinterpreter::toword(){current=0;inti=0;while(buffercode[current]!='#'){scaner();strcpy(wr[wcount].w,token);wcount++;i++;}};voidinterpreter::read(){cin.getline(buffercode,200);coutbuffercodeendl;}voidinterpreter::run(){current=0;{13scaner();B();}}voidinterpreter::B(){t[tcount].emit(B,,T,B');tcount++;T();B1();}voidinterpreter::B1(){if(strcmp(token,rwtab[8])==0){t[tcount].emit(B',and,T,B');tcount++;scaner();T();B1();scaner();}elset[tcount].emit(B',empty,,);}voidinterpreter::T(){t[tcount].emit(T,,F,T');tcount++;F();T1();}voidinterpreter::T1(){14if(strcmp(token,rwtab[7])==0){t[tcount].emit(T',or,F,T'');tcount++;scaner();F();T1();}elset[tcount].emit(T',empty,,);}//FnotF|true｜false|（B）|iropivoidinterpreter::F(){if(strcmp(token,rwtab[1])==0){t[