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

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

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

3、文法，給出該文法的屬性文法，用遞歸下降分析法實(shí)現(xiàn)對(duì)布爾表達(dá)式的翻譯，給出翻譯的逆波蘭式結(jié)果。3設(shè)計(jì)環(huán)境與工具visual c+4設(shè)計(jì)原則4.1基本方法 在本程序中，輸入一段布爾語(yǔ)句，使用遞歸下降的方法得到其推到過程，并利用遞歸下降翻譯的方法的到四元式序列，最終根據(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簡(jiǎn)要的分析與概要設(shè)計(jì) 在該程序中，總共包括3個(gè)主要功能，第一個(gè)功能是對(duì)輸入的布爾語(yǔ)句進(jìn)行遞歸下降的分析，從而得出從文法到該布爾語(yǔ)句的推導(dǎo)過程，第二個(gè)功能是使用遞歸下降的方法，該布爾語(yǔ)句的四元式序列，第三個(gè)功能對(duì)四元式序列進(jìn)行掃描并分析每個(gè)四元式的結(jié)構(gòu)特點(diǎn)，并據(jù)此將四元式轉(zhuǎn)化為逆波蘭式。main 函數(shù)的流程圖如下：開始遞歸下降分析得到推導(dǎo)過程

5、并輸出遞歸下降分析得到四元式序列并輸出讀四元式并得到逆波蘭式并輸出 結(jié)束 在開始進(jìn)行本次實(shí)驗(yàn)中，本來計(jì)劃在遞歸下降分析的過程中就得到逆波蘭式，但是經(jīng)過多次嘗試之后總是存在錯(cuò)誤，所以采用先得到四元式序列，再根據(jù)四元式序列生成逆波蘭式這種效率比較低的方法。6詳細(xì)的算法描述，框圖6.1主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)四元式類 在該類中，要包含四元式中的四個(gè)元素，運(yùn)算結(jié)果，兩個(gè)運(yùn)算數(shù)以及一個(gè)運(yùn)算符號(hào)class quadpublic:char result8;char arg18;char op8;char arg28; void print()/輸出該四元式coutresult=arg1 op arg2endl;q

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

7、token8;/記錄當(dāng)前讀到的單詞 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請(qǐng)輸入源代碼:endl;in.read();in.run();cout推導(dǎo)過程為：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（）流程圖為非終結(jié)符t對(duì)應(yīng)的函數(shù)t（） 該函數(shù)首先要寫入t=ft，然后執(zhí)行f（）與t1（）流程圖為：非終結(jié)符b對(duì)應(yīng)的函數(shù)b1（） 在該函數(shù)中如果讀入的下一個(gè)單詞是“and”則寫入b=and

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

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

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

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