布爾表達(dá)式的翻譯程序設(shè)計(jì)

1、學(xué) 號(hào)： 0120910680328課 程 設(shè) 計(jì)題 目布爾表達(dá)式的翻譯程序設(shè)計(jì)學(xué) 院計(jì)算機(jī)學(xué)院專(zhuān) 業(yè)軟件工程班 級(jí)0903姓 名陳銀指導(dǎo)教師何九周2012年1月2日布爾表達(dá)式的遞歸下降翻譯程序設(shè)計(jì)1引言 “編譯原理”是一門(mén)研究設(shè)計(jì)和構(gòu)造編譯程序原理和方法的課程，是計(jì)算機(jī)各專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課。編譯原理這門(mén)課程蘊(yùn)含著計(jì)算機(jī)學(xué)科中解決問(wèn)題的思路、形式化問(wèn)題和解決問(wèn)題的方法，對(duì)應(yīng)用軟件和系統(tǒng)軟件的設(shè)計(jì)與開(kāi)發(fā)有一定的啟發(fā)和指導(dǎo)作用?！熬幾g原理”是一門(mén)實(shí)踐性較強(qiáng)的課程，要掌握這門(mén)課程中的思想，就必須要把所學(xué)到的知識(shí)付諸實(shí)踐。而課程設(shè)計(jì)是將理論與實(shí)踐相互聯(lián)系的一種重要方式。2概述2.1設(shè)計(jì)題目 布

2、爾表達(dá)式的遞歸下降翻譯程序設(shè)計(jì)2.2設(shè)計(jì)目的 課程設(shè)計(jì)是對(duì)學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽(tīng)講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，設(shè)計(jì)題中的問(wèn)題比平時(shí)的練習(xí)題要復(fù)雜，也更接近實(shí)際。編譯原理這門(mén)課程安排的課程設(shè)計(jì)的目的是旨在要求學(xué)生進(jìn)一步鞏固課堂上所學(xué)的理論知識(shí)，深化理解和靈活掌握教學(xué)內(nèi)容，選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)表示問(wèn)題，然后編制算法和程序完成設(shè)計(jì)要求，從而進(jìn)一步培養(yǎng)學(xué)生獨(dú)立思考問(wèn)題、分析問(wèn)題、解決實(shí)際問(wèn)題的動(dòng)手能力。2.3設(shè)計(jì)任務(wù)內(nèi)容布爾表達(dá)式的文法：B ® TB B® and T B| T ® FT T® or FT| F ®

3、 not F |truefalse |（B）| i rop i設(shè)計(jì)布爾表達(dá)式文法，給出該文法的屬性文法，用遞歸下降分析法實(shí)現(xiàn)對(duì)布爾表達(dá)式的翻譯，給出翻譯的逆波蘭式結(jié)果。3設(shè)計(jì)環(huán)境與工具Visual C+4設(shè)計(jì)原則4.1基本方法 在本程序中，輸入一段布爾語(yǔ)句，使用遞歸下降的方法得到其推到過(guò)程，并利用遞歸下降翻譯的方法的到四元式序列，最終根據(jù)生成的四元式序列分析得到逆波蘭式。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

4、.type. T® or FT T.in=F.type addtype(or,entry,B.in)T® Tval=F ® not F 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簡(jiǎn)要的分析與概要設(shè)計(jì) 在該程序中，總共包括3個(gè)主要功能，第一個(gè)功能是對(duì)輸入的布爾語(yǔ)句進(jìn)行遞歸下降的分析，從而得出從文法到該

5、布爾語(yǔ)句的推導(dǎo)過(guò)程，第二個(gè)功能是使用遞歸下降的方法，該布爾語(yǔ)句的四元式序列，第三個(gè)功能對(duì)四元式序列進(jìn)行掃描并分析每個(gè)四元式的結(jié)構(gòu)特點(diǎn)，并據(jù)此將四元式轉(zhuǎn)化為逆波蘭式。main 函數(shù)的流程圖如下：開(kāi)始遞歸下降分析得到推導(dǎo)過(guò)程并輸出遞歸下降分析得到四元式序列并輸出讀四元式并得到逆波蘭式并輸出 結(jié)束 在開(kāi)始進(jìn)行本次實(shí)驗(yàn)中，本來(lái)計(jì)劃在遞歸下降分析的過(guò)程中就得到逆波蘭式，但是經(jīng)過(guò)多次嘗試之后總是存在錯(cuò)誤，所以采用先得到四元式序列，再根據(jù)四元式序列生成逆波蘭式這種效率比較低的方法。6詳細(xì)的算法描述，框圖6.1主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)四元式類(lèi) 在該類(lèi)中，要包含四元式中的四個(gè)元素，運(yùn)算結(jié)果，兩個(gè)運(yùn)算數(shù)以及一個(gè)運(yùn)算符號(hào)

6、class quadpublic:char result8;char arg18;char op8;char arg28; void print()/輸出該四元式cout<<result<<"="<<arg1<<" "<<op<<" "<<arg2<<endl;q20;Word結(jié)構(gòu)體這個(gè)結(jié)構(gòu)體的對(duì)要用來(lái)存儲(chǔ)單個(gè)單詞，包括一個(gè)字符串成員。struct wordchar w10;void print()cout<<w<<

7、":"wr200;逆波蘭式結(jié)構(gòu)體這個(gè)結(jié)構(gòu)體的對(duì)象用來(lái)存儲(chǔ)逆波蘭式，它的成員是一個(gè)word數(shù)組struct nipolanword nibolan100; n;翻譯器類(lèi)用來(lái)存儲(chǔ)翻譯過(guò)程中的各個(gè)變量以及聲明主要的函數(shù)：class interpreter private:ifstream SourceFile;char buffercode200;/存放源碼的緩沖區(qū)int syn;int current;/buffercode中當(dāng)前讀到的字符下標(biāo)char token8;/記錄當(dāng)前讀到的單詞 public: void scaner();void B();void B1();void

8、 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 |truefalse |（B）| i rop i*/#include <iostream.h>#include <

9、string.h>#include <fstream.h>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()cout<<result<<"="<<arg1<<" "<<op<<" "<<arg2<

10、<endl;q20;void qemit(char a,char b,char c,char d)strcpy(qnumberofquad.result,a);strcpy(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/1

11、0;if (temp=0) pi+1='0' break;numberoftemp+;return p;struct wordchar w10;void print()cout<<w<<":"wr200;struct nipolanword nibolan100; n;int tcount=0;int wcount=0;char *rwtab9="true","not","false","(",")","rop",&

12、quot;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() cout<<a<<"=>"<<b<<c<<d<<endl;t100;void tuidao:emit(char *m,char *n,char *p,char *q)strcpy(a,m);st

13、rcpy(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

14、 bolan();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<numberofquad;i+)for (int j=i-1;j>=0;j-)if (strcmp(qi.arg1,qj.result)=0)if (strcmp(qi.arg2,qj

15、+1.result)=0) strcpy(n.nibolantear.w,qi.op);tear+;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 (st

16、rcmp(qi.arg1,qj.result)!=0)&&(strcmp(qi.arg2,qj.result)!=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)

17、;wcount+;i+;void interpreter:read()cin.getline(buffercode,200);cout<<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

18、)=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'");tco

19、unt+;F();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 inter

20、preter:F()if(strcmp(token,rwtab1)=0)ttcount.emit("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&

21、quot;,"","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+

22、;scaner();scaner();scaner();void interpreter:scaner()int m=0;for(int i=0;i<8;i+) tokeni=' 'while (buffercodecurrent=' ') current+;if(buffercodecurrent>='a')&&(buffercodecurrent<='z')|(buffercodecurrent>='A')&&(buffercodecurrent<=

23、'Z')while (buffercodecurrent>='a')&&(buffercodecurrent<='z')|(buffercodecurrent>='A')&&(buffercodecurrent<='Z')|(buffercodecurrent>='0')&&(buffercodecurrent<='9')tokenm=buffercodecurrent;m+;current+;tok

24、enm+='0'else if (buffercodecurrent='(') 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;st

25、rcpy(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,*eplace,*tt;tp=new char8;ep2=new char8;eplace=new char8;tt=new char8;strcpy(eplace,unit

26、();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 (strcmp(token,"true")=0)|(strcmp(token,"false")=0)s

27、trcpy(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

28、;scaner();if (strcmp(token,"(")=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<<"請(qǐng)輸入源代碼:"<<endl;in

29、.read();in.run();cout<<"推導(dǎo)過(guò)程為："<<endl;for(int i=0;i<tcount;i+)ti.print();in.toword();cout<<"分析的單詞為："<<endl;for (i=0;i<wcount;i+)wri.print();cout<<endl;cout<<"四元式為："<<endl;in.reset();/cout<<"here"<<end

30、l;in.run1();for(i=0;i<numberofquad;i+)qi.print();cout<<"逆波蘭式為:"<<endl;bolan();for(i=head;i<tear;i+)cout<<n.nibolani.w<<" "cout<<endl;6.2全局變量設(shè)計(jì)int tear=51;/逆波蘭式尾部int head=50;/逆波蘭是首部int numberoftemp=0;/臨時(shí)變量個(gè)數(shù)int numberofquad=0;/四元式個(gè)數(shù)6.3遞歸下降得到推導(dǎo)過(guò)程

31、 根據(jù)遞歸下降的思想，對(duì)于文法中的每個(gè)非終結(jié)符編寫(xiě)一個(gè)函數(shù)，每個(gè)函數(shù)的功能是識(shí)別由該非終結(jié)符所表示的語(yǔ)法成分。由于描述語(yǔ)言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)必然以相互遞歸的方式進(jìn)行調(diào)用。該過(guò)程的基本思想為每執(zhí)行一個(gè)非終結(jié)符對(duì)應(yīng)的函數(shù)就根據(jù)讀入的單詞符號(hào)來(lái)寫(xiě)入該非終結(jié)符對(duì)應(yīng)的推出式。 該功能的入口函數(shù)run1的流程圖如下：scaner()B() 開(kāi)始end非終結(jié)符B對(duì)應(yīng)的函數(shù)B（） 該函數(shù)首先要寫(xiě)入B=>TB，然后執(zhí)行T（）與B1（）流程圖為非終結(jié)符T對(duì)應(yīng)的函數(shù)T（） 該函數(shù)首先要寫(xiě)入T=>FT，然后執(zhí)行F（）與T1（）流程圖為：非終結(jié)符B對(duì)應(yīng)的函數(shù)B1（） 在該函數(shù)中如果讀

32、入的下一個(gè)單詞是“and”則寫(xiě)入B=>and T B.否則，要寫(xiě)入B推出了空串。流程圖為：非終結(jié)符T對(duì)應(yīng)的函數(shù)T1（） 在該函數(shù)中如果讀入的下一個(gè)單詞是“or”則寫(xiě)入T=>or FT.否則，要寫(xiě)入T推出了空串。流程圖為：非終結(jié)符F對(duì)應(yīng)的函數(shù)F（） 由于非終結(jié)符F對(duì)應(yīng)的推出式比較多，所以該函數(shù)的分支也比較多，當(dāng)讀入“not”時(shí)，則寫(xiě)入F=>not F并執(zhí)行F（）函數(shù),當(dāng)讀入”true”或者”false”時(shí)，則要寫(xiě)入F=>true 或者F=>false當(dāng)讀入的字符為”(”時(shí)，則寫(xiě)入F=>(B),并執(zhí)行B（）函數(shù)，當(dāng)讀入的單詞為i時(shí)，要寫(xiě)入F=>i rop

33、i.流程圖為：在完成該功能時(shí)，推到過(guò)程存入到tuidao類(lèi)生成的對(duì)象數(shù)組中。6.4遞歸下降得到四元式序列 生成四元式必須分析布爾語(yǔ)句，and語(yǔ)句以及最小的分析單元三個(gè)部分expression（）函數(shù)分析布爾語(yǔ)句，term（）分析and語(yǔ)句，unit（）分析最小單元該過(guò)程的入口函數(shù)run1（）流程圖如下：expression（）函數(shù) 該函數(shù)首先調(diào)用了一個(gè)term函數(shù)，如果下一個(gè)讀到單詞是“or”則分析or后面的一個(gè)term并將or和兩個(gè)term寫(xiě)入到四元式序列中，如果讀到的不是“or”則只把term返回到四元式序列中。流程圖如下：term()函數(shù) 該函數(shù)首先調(diào)用了一個(gè)factor函數(shù)，如果下一個(gè)

34、讀到單詞是“and”則分析and后面的一個(gè)factor并將or和兩個(gè)factor寫(xiě)入到四元式序列中，如果讀到的不是“and”則只把factor返回到四元式序列中。流程圖為:unit()函數(shù) 在該函數(shù)中，分析了優(yōu)先級(jí)最高的運(yùn)算或者是單個(gè)終結(jié)符，如果讀入的是true或者false則直接返回token，如果讀入的是 i則把i rop i寫(xiě)入到四元式序列中，如果讀入的是not，則分析not后面的expression（），并將not 以及expression（）寫(xiě)入到四元式中，返回生成的newtemp流程圖： 該過(guò)程結(jié)束后，布爾語(yǔ)句對(duì)應(yīng)的四元式存放在quad類(lèi)生成的對(duì)象數(shù)組q中.6.5分析四元式序列生成

35、逆波蘭式 本過(guò)程根據(jù)四元式序列以及每一個(gè)四元式的類(lèi)型，將四元式中的信息按照一定規(guī)則寫(xiě)入到逆波蘭式中，主要函數(shù)為bolan（）函數(shù)，bolan函數(shù)將四元式序列從頭到尾掃描一遍，對(duì)于每一個(gè)四元式序列根據(jù)其操作數(shù)是臨時(shí)變量還是終結(jié)符將終結(jié)符以及操作符按照逆波蘭式規(guī)則寫(xiě)入到逆波蘭式類(lèi)生成的對(duì)象n中。 當(dāng)當(dāng)前四元式類(lèi)型為 臨時(shí)變量=臨時(shí)變量 OP 臨時(shí)變量是，則直接將op插入到逆波蘭式尾部。 當(dāng)當(dāng)前四元式類(lèi)型為 臨時(shí)便令=arg1 op arg2時(shí)則按照arg1，arg2，op的順序?qū)⑺麄儾迦肽娌ㄌm式的尾部。 當(dāng)當(dāng)前四元式類(lèi)型為 臨時(shí)便令=臨時(shí)變量 op arg1時(shí)則按照arg1，op的順序?qū)⑺麄儾迦肽娌ㄌm式的尾部。 當(dāng)當(dāng)前四元