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

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

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

3、 not F |truefalse |（B）| i rop i設(shè)計布爾表達式文法，給出該文法的屬性文法，用遞歸下降分析法實現(xiàn)對布爾表達式的翻譯，給出翻譯的逆波蘭式結(jié)果。3設(shè)計環(huán)境與工具Visual C+4設(shè)計原則4.1基本方法 在本程序中，輸入一段布爾語句，使用遞歸下降的方法得到其推到過程，并利用遞歸下降翻譯的方法的到四元式序列，最終根據(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簡要的分析與概要設(shè)計 在該程序中，總共包括3個主要功能，第一個功能是對輸入的布爾語句進行遞歸下降的分析，從而得出從文法到該

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

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

7、":"wr200;逆波蘭式結(jié)構(gòu)體這個結(jié)構(gòu)體的對象用來存儲逆波蘭式，它的成員是一個word數(shù)組struct nipolanword nibolan100; n;翻譯器類用來存儲翻譯過程中的各個變量以及聲明主要的函數(shù)：class interpreter private:ifstream SourceFile;char buffercode200;/存放源碼的緩沖區(qū)int syn;int current;/buffercode中當前讀到的字符下標char token8;/記錄當前讀到的單詞 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<<"請輸入源代碼:"<<endl;in

29、.read();in.run();cout<<"推導過程為："<<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è)計int tear=51;/逆波蘭式尾部int head=50;/逆波蘭是首部int numberoftemp=0;/臨時變量個數(shù)int numberofquad=0;/四元式個數(shù)6.3遞歸下降得到推導過程

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

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

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

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

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