編譯原理課程設計布爾表達式的翻譯程序設計

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

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

3、文法，給出該文法的屬性文法，用遞歸下降分析法實現(xiàn)對布爾表達式的翻譯，給出翻譯的逆波蘭式結果。3設計環(huán)境與工具visual c+4設計原則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.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個主要功能，第一個功能是對輸入的布爾語句進行遞歸下降的分析，從而得出從文法到該布爾語句的推導過程，第二個功能是使用遞歸下降的方法，該布爾語句的四元式序列，第三個功能對四元式序列進行掃描并分析每個四元式的結構特點，并據(jù)此將四元式轉化為逆波蘭式。main 函數(shù)的流程圖如下：開始遞歸下降分析得到推導過程

5、并輸出遞歸下降分析得到四元式序列并輸出讀四元式并得到逆波蘭式并輸出 結束 在開始進行本次實驗中，本來計劃在遞歸下降分析的過程中就得到逆波蘭式，但是經(jīng)過多次嘗試之后總是存在錯誤，所以采用先得到四元式序列，再根據(jù)四元式序列生成逆波蘭式這種效率比較低的方法。6詳細的算法描述，框圖6.1主要數(shù)據(jù)結構的設計四元式類 在該類中，要包含四元式中的四個元素，運算結果，兩個運算數(shù)以及一個運算符號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數(shù)組struct nipolanword nibolan100; n;翻譯器類用來存儲翻譯過程中的各個變量以及聲明主要的函數(shù)：class interpreter private:ifstream sourcefile;char buffercode200;/存放源碼的緩沖區(qū)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，然后執(zhí)行t（）與b1（）流程圖為非終結符t對應的函數(shù)t（） 該函數(shù)首先要寫入t=ft，然后執(zhí)行f（）與t1（）流程圖為：非終結符b對應的函數(shù)b1（） 在該函數(shù)中如果讀入的下一個單詞是“and”則寫入b=and

24、 t b.否則，要寫入b推出了空串。流程圖為：非終結符t對應的函數(shù)t1（） 在該函數(shù)中如果讀入的下一個單詞是“or”則寫入t=or ft.否則，要寫入t推出了空串。流程圖為：非終結符f對應的函數(shù)f（） 由于非終結符f對應的推出式比較多，所以該函數(shù)的分支也比較多，當讀入“not”時，則寫入f=not f并執(zhí)行f（）函數(shù),當讀入”true”或者”false”時，則要寫入f=true 或者f=false當讀入的字符為”(”時，則寫入f=(b),并執(zhí)行b（）函數(shù)，當讀入的單詞為i時，要寫入f=i rop i.流程圖為：在完成該功能時，推到過程存入到tuidao類生成的對象數(shù)組中。6.4遞歸下降得到四元

25、式序列 生成四元式必須分析布爾語句，and語句以及最小的分析單元三個部分expression（）函數(shù)分析布爾語句，term（）分析and語句，unit（）分析最小單元該過程的入口函數(shù)run1（）流程圖如下：expression（）函數(shù) 該函數(shù)首先調用了一個term函數(shù)，如果下一個讀到單詞是“or”則分析or后面的一個term并將or和兩個term寫入到四元式序列中，如果讀到的不是“or”則只把term返回到四元式序列中。流程圖如下：term()函數(shù) 該函數(shù)首先調用了一個factor函數(shù)，如果下一個讀到單詞是“and”則分析and后面的一個factor并將or和兩個factor寫入到四元式序列中

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

27、，主要函數(shù)為bolan（）函數(shù)，bolan函數(shù)將四元式序列從頭到尾掃描一遍，對于每一個四元式序列根據(jù)其操作數(shù)是臨時變量還是終結符將終結符以及操作符按照逆波蘭式規(guī)則寫入到逆波蘭式類生成的對象n中。 當當前四元式類型為 臨時變量=臨時變量 op 臨時變量是，則直接將op插入到逆波蘭式尾部。 當當前四元式類型為 臨時便令=arg1 op arg2時則按照arg1，arg2，op的順序將他們插入逆波蘭式的尾部。 當當前四元式類型為 臨時便令=臨時變量 op arg1時則按照arg1，op的順序將他們插入逆波蘭式的尾部。 當當前四元式類型為 臨時便令=arg1 op 臨時變量時則將op的順序將他們插入逆波蘭式的尾部，將arg1插入到逆波蘭式的首部。bolan函數(shù)的流程圖為：本過程結束之后，逆波蘭式存放在nibolan類定義的對象n中。7軟件的測試方法和測試結果輸入一個字符串，執(zhí)行改程序，觀察產(chǎn)生的四元式以及逆波蘭式是否正確。測試數(shù)據(jù)1：測試數(shù)據(jù)2測試數(shù)據(jù)38設計的特點、不足收獲與體會8.1設計的特點 這次課程設計中，使用遞歸下降分析方法完成了布爾語句的翻譯，程序不僅按照題目要求的到了翻譯的逆波蘭式，而且還求出了布