if-else-語句-遞歸下降法-輸出四元式

1、武漢理工 課程設(shè)計(jì)說明書學(xué) 號(hào)：0121課程設(shè)計(jì)課程名稱編譯原理課程設(shè)計(jì)題目IF-ELSE 條件語句的翻譯程序設(shè)計(jì)（遞 歸下降法、輸出四元式）學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)計(jì)算機(jī) 1001 班姓名指導(dǎo)教師陳天煌2013年 1 月 7 日武漢理工 課程設(shè)計(jì)說明書課程設(shè)計(jì)任務(wù)書學(xué)生姓名 專業(yè)班級(jí)： 計(jì)算機(jī) 1001 班指導(dǎo)教師： 陳天煌 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題目: IF-ELSE 條件語句的翻譯程序設(shè)計(jì)（遞歸下降法、 輸出四元式表 示）初始條件：理論：學(xué)完編譯課程，掌握一種計(jì)算機(jī)高級(jí)語言的使用。 實(shí)踐：計(jì)算機(jī)實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件環(huán)境。如果自己有計(jì)算機(jī)可以在其上進(jìn) 行設(shè)計(jì)

2、。要求完成的主要任務(wù) : （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）（1）寫出符合給定的語法分析方法的文法及屬性文法。（2）完成題目要求的中間代碼四元式的描述。（3）寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計(jì)。（4）編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)的分析程序。（5）設(shè)計(jì)報(bào)告格式按附件要求書寫。課程設(shè)計(jì)報(bào)告書正文的內(nèi)容應(yīng)包括：系統(tǒng)描述（問題域描述） ；文法及屬性文法的描述；語法分析方法描述及語法分析表設(shè)計(jì)；按給定的題目給出中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計(jì)；編譯系統(tǒng)的概要設(shè)計(jì)；詳細(xì)的算法描述（流程圖或偽代碼） ；軟件的測試方法和測試

3、結(jié)果；研制報(bào)告（研制過程，本設(shè)計(jì)的評(píng)價(jià)、特點(diǎn)、不足、收獲與體會(huì)等） ；參考文獻(xiàn)（按公開發(fā)表的規(guī)范書寫） 。時(shí)間安排：設(shè)計(jì)安排一周：周 1、周 2：完成系統(tǒng)分析及設(shè)計(jì)。周 3 、周 4 ：完成程序調(diào)試及測試。 周 5 ：撰寫課程設(shè)計(jì)報(bào)告。設(shè)計(jì)驗(yàn)收安排：設(shè)計(jì)周的星期五第 1 節(jié)課開始到實(shí)驗(yàn)室進(jìn)行上機(jī)驗(yàn)收。 設(shè)計(jì)報(bào)告書收取時(shí)間：設(shè)計(jì)周的次周星期一上午 10 點(diǎn)。年月日指導(dǎo)教師簽名：武漢理工 課程設(shè)計(jì)說明書IF-ELSE 條件語句的翻譯程序設(shè)計(jì)（遞歸下降法、輸出四元式）1. 系統(tǒng)描述（問題域描述）本次實(shí)驗(yàn)使用 windows XP 的 visual C+ 軟件，利用遞歸下降法實(shí)現(xiàn) IF-ELSE 的條

4、 件語句的翻譯程序設(shè)計(jì)，輸出四元式表示，程序只能處理簡單的布爾表達(dá)式和最簡單的 賦值語句，布爾表達(dá)式能夠?qū)崿F(xiàn)大于和小于的識(shí)別，也能處理關(guān)系運(yùn)算符 =和X then Y else Y;X-ididid;X-idid=id;Y-id=id ；2.3 屬性文法的描述：屬性文法（也稱屬性翻譯文法 ）是 Knuth在 1968年首先提出的。它是在上下文無關(guān)文法的基礎(chǔ)上， 為每個(gè)文法符號(hào) （ 終結(jié)符或非終結(jié)符 ） 配備若干相關(guān) 的“特性”（稱為屬性）。語法分析方法描述及語法分析表設(shè)計(jì)；語法分析方法描述：武漢理工 課程設(shè)計(jì)說明書在程序語言的語法定義中有許多采用遞歸定義。我們在對它進(jìn)行語法分析時(shí)，編制的 處理

5、程序也采取遞歸的方式，可使其結(jié)構(gòu)簡單易讀。但由于頻繁地調(diào)用子程序大大地降 低了分析速度。遞歸下降法的主要思想是：對每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程 序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此 種方法稱為遞歸子程序法或遞歸下降法。程序是以一個(gè)個(gè)單詞的形式向后讀取，讀取到 if 之后就開始執(zhí)行 E 的遞歸子程序， 程序根據(jù)布爾表達(dá)式的真假，進(jìn)而選擇執(zhí)行相應(yīng)的分支，即如果布爾表達(dá)式為真，就執(zhí) 行 then 后面的賦值語句，如果布爾表達(dá)式為假，就執(zhí)行 else 后面的賦值語句，遞歸子 程序 E 分別賦予布爾表達(dá)式真和假不同的地址， 并將跳轉(zhuǎn)相應(yīng)的信息寫到

6、處理四元式的 結(jié)構(gòu)體數(shù)組中去， E 執(zhí)行完以后，回到 S中繼續(xù)執(zhí)行后面的，讀取到 then 之后，就表示 當(dāng)條件為真的時(shí)候，執(zhí)行 then 之后的賦值表達(dá)式，處理賦值的信息寫到處理四元式的 結(jié)構(gòu)體數(shù)組中去，當(dāng)讀取到 else 之后，同理的執(zhí)行當(dāng)條件為假的時(shí)候的賦值表達(dá)式， 處理完了之后賦值相應(yīng)的信息也寫到處理四元式的結(jié)構(gòu)體數(shù)組中去， 這樣反復(fù)執(zhí)行就實(shí) 現(xiàn)的對語法的分析。語法分析表設(shè)計(jì)：實(shí)驗(yàn)要求的是遞歸下降法， 主要是調(diào)用不同的遞歸子程序， 所以沒有什么語法分析表， 流程圖在后面。按給定的題目給出中間代碼形式的描述及中間代碼序列 的結(jié)構(gòu)設(shè)計(jì)；4.1if-else 四元式表示的描述 : 中間代碼，

7、也稱中間語言，是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。 四元式可看成中間代碼的一種抽象形式。武漢理工 課程設(shè)計(jì)說明書編譯系統(tǒng)的概要設(shè)計(jì)5.1 概要分析：首先在源程序相同的目錄下創(chuàng)建一個(gè) txt 文檔，并在文檔中輸入需要編譯的程序即 if-else 語句，然后定義一個(gè)輸入流文件， 利用這個(gè)流文件中的 open 函數(shù)打開我需要編 譯的 txt 文件，在調(diào)用初始化各種變量的初始化函數(shù)。接著開始進(jìn)行詞法分析， 詞法分析程序的主要任務(wù)是對構(gòu)成源程序的字符串從左到右 的掃描，逐個(gè)字符地讀入源程序字符并按照構(gòu)詞規(guī)則切分成一個(gè)一個(gè)具有獨(dú)立意義的單 詞。并確定其屬性（如保留字、標(biāo)識(shí)符、運(yùn)算符、界限符和常

8、量等） 。再把它們轉(zhuǎn)換成 長度統(tǒng)一的標(biāo)準(zhǔn)形式屬性字。詞法分析是編譯過程中的第一個(gè)階段，在語法分析前進(jìn)行 。也可以和語法分析結(jié)合 在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。 單詞的分類（五類）：關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)識(shí)符。也稱為保留字或基本字。標(biāo)識(shí)符：用來表示程序中各種名字的字符串。常 數(shù)：常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型。界限符：如逗號(hào)、分號(hào)、括號(hào)等。但是我做的這個(gè)實(shí)驗(yàn)沒有用到那么多東西， 詞法分析的有效字符串為 : IF,ELSE,THEN, ,.=,= ，和從 a 到 z 的單個(gè)標(biāo)識(shí)符，但是程序還是相對來說比較簡單，復(fù)雜的表 達(dá)

9、式可能不能處理，以后會(huì)改進(jìn)。而詞法分析的結(jié)果就是將相應(yīng)的單詞賦予不同的屬性 值，利用詞法分析表將結(jié)果保存起來，為后面的語義分析做準(zhǔn)備。詞法分析完成之后就 是把詞法分析的結(jié)果都顯示出來。語法分析的過程在上面已經(jīng)有了說明， 語法分析完了之后就是打印中間代碼的四元式 形式，根據(jù)上面的結(jié)果，四元式的數(shù)組里面已經(jīng)存儲(chǔ)了編譯的具體信息，之需要按照相 應(yīng)的算符，將他們輸出出來，即可看到中間代碼的四元式表示形式。詞法分析的具體實(shí)現(xiàn)： 詞法分析的具體過程如下，首先將我們需要的編譯的內(nèi)容讀到 a 這個(gè)數(shù)組之中，利 用輸入流函數(shù)的 seekg（） 和 get（） 函數(shù)配合完成，在利用 for 循環(huán)將 a 數(shù)組的的空

10、格、 回車等無用的內(nèi)容去掉， 從而將處理過后的轉(zhuǎn)存到 a1 這個(gè)數(shù)組中， 在利用的這個(gè)數(shù)組 中符號(hào)書寫的連貫性來進(jìn)行進(jìn)行詞法分析。例如， then 的寫法是先寫 t ，再寫 h，再寫 e，再寫 n，那么詞法分析一個(gè)個(gè)單詞來進(jìn)行，發(fā)現(xiàn) a1i 中存儲(chǔ)的是 t ，在判斷數(shù)組接 下來的三個(gè)單元里面存儲(chǔ)的分別是 h、e、n，就能夠識(shí)別關(guān)鍵字 then 了，其他的是一個(gè) 道理，處理完成之后就對每個(gè)單詞的屬性都做了出來，就實(shí)現(xiàn)了詞法分析應(yīng)該的功能，詳細(xì)的算法描述（流程圖或偽代碼）武漢理工 課程設(shè)計(jì)說明書6.1 詞法分析的全部代碼：6.1 程序代碼/有效字符串 : IF,ELSE,THEN, a,b,x,=

11、/*武漢理工 課程設(shè)計(jì)說明書文法 :S-id=id | if E then S else SE-id id id*/#include #include #include#define $ASSIGN 249#define $IF 250#define $THEN 251#define $ELSE 252#define $GREAT 253#define $LESS 248#define $ID 254 typedef struct Wtokenint type;char ch;Wtoken;typedef enumJUMP,JG ,JL,ASSIGN,ENDOpKind;typedef str

12、uctint label;/ 標(biāo)號(hào)OpKind op;char par1,par2;unionchar result;int address;Fourtable;/ 四元式#define MAX_TOKEN 256 /Wtoken 表大小#define MAX_QUAD 256 / 四元式數(shù)組大小武漢理工 課程設(shè)計(jì)說明書Wtoken tokentableMAX_TOKEN;Fourtable quadMAX_QUAD;int token_index;/token 表索引int total_len;/token 表有效長度int quad_len;/ 四元式表有效長度int quad_index

13、;/ 四元式索引int label;ifstream ins;bool init(char 255);bool cifafenxi();void print();void ERROR();void S(int,int);void E(int,int,int);bool nexttoken();int newlabel();void yufafenxi();void printFourtable();void main()coutfname; if(!init(fname) return;if(!cifafenxi() return;char ch;while(1)if(ins.eof()bre

14、ak; insch;coutThe result of CIFA analyse :endl; print();coutendlendl; nexttoken();武漢理工 課程設(shè)計(jì)說明書coutThe Grammar:endl; yufafenxi();coutThe FourTable as followings:endl; printFourtable();int newlabel()return label+;bool init(char 255) token_index=0; total_len=0; quad_len=0; quad_index=0; label=100; ins.

15、open( | ios:in); if(ins.fail() cout 文件打開出錯(cuò) !ch; if(ins.fail() break;if(ch=I) insbuf; if(strcmp(buf,F)=0) tokentabletotal_len+.type=$IF;else if(ch=T)武漢理工 課程設(shè)計(jì)說明書insbuf;if(strcmp(buf,HEN)=0)tokentabletotal_len+.type=$THEN;else if(ch=E)insbuf;if(strcmp(buf,LSE)=0)tokentabletotal_len+.type=$ELSE;else if

16、(ch=)tokentabletotal_len+.type=$GREAT;else if(ch=a & ch=total_len)return false;10武漢理工 課程設(shè)計(jì)說明書cur.type=tokentabletoken_index.type; cur.ch=tokentabletoken_index.ch; token_index+;return true;void ERROR(char str20)couterror! strendl;void S(int begin,int next)if(cur.type=$ID)char a,b;coutcur.ch;a=cur.ch;

17、if(!nexttoken()ERROR(S);if(cur.type!=$ASSIGN)ERROR(S);cout=;if(!nexttoken()ERROR(S);if(cur.type!=$ID)ERROR(S); coutcur.chendl; b=cur.ch; AD_RESULT(begin,ASSIGN,b,0,a); AD_ADDRESS(-1,JUMP,0,0,next); nexttoken();else if(cur.type=$IF)if(!nexttoken()ERROR(S);coutif E then S else Sendl; int etrue=newlabe

18、l(); int efalse=newlabel();11武漢理工 課程設(shè)計(jì)說明書E(begin,etrue,efalse); if(cur.type=$THEN) if(!nexttoken() ERROR(S);S(etrue,next);if(cur.type=$ELSE) if(!nexttoken()ERROR(S);S(efalse,next); else ERROR(S);elseERROR(S);void E(int begin,int etrue,int efalse)if(cur.type=$ID)char a,b;int mark=0;a=cur.ch; coutcur.

19、ch; if(!nexttoken() ERROR(E();if(cur.type=$GREAT) cout;mark=1; else if(cur.type=$LESS) cout;elseERROR(E();if(!nexttoken()12武漢理工 課程設(shè)計(jì)說明書ERROR(E();if(cur.type!=$ID)ERROR(E();coutcur.chendl;b=cur.ch;if(mark=0)AD_ADDRESS(begin,JL,a,b,etrue);if(mark=1)AD_ADDRESS(begin,JG ,a,b,etrue);AD_ADDRESS(-1,JUMP,0,

20、0,efalse);if(!nexttoken()ERROR(E();elseERROR(E();void yufafenxi()S(-1,1000);AD_RESULT(1000,END,0,0,-);void print() for(token_index=0;token_indextotal_len;token_index+) if(tokentabletoken_index.type=$IF)coutIF 關(guān)鍵字 endl; if(tokentabletoken_index.type=$ELSE) coutELSE 關(guān)鍵字 endl;if(tokentabletoken_index.t

21、ype=$THEN) coutTHEN 關(guān)鍵字 endl;if(tokentabletoken_index.type=$ID) couttokentabletoken_index.ch 標(biāo)識(shí)符 endl; if(tokentabletoken_index.type=$ASSIGN) cout= 運(yùn)算符 endl; if(tokentabletoken_index.type=$GREAT) cout 運(yùn)算符 endl;if(tokentabletoken_index.type=$LESS) cout 運(yùn)算符 endl;13武漢理工 課程設(shè)計(jì)說明書token_index=0;void printF

22、ourtable()for(int i=0;i-1) coutLquadi.label:;else cout ;if(quadi.op=JG) cout,quadi.par1,quadi.par2,Lquadi.address)endl;else if(quadi.op=JL) cout(,quadi.par1,quadi.par2,Lquadi.address)endl;else if(quadi.op=JUMP) cout,-,-,Lquadi.addressendl;else if(quadi.op=ASSIGN)cout(= ,quadi.par1,-,quadi.result)end

23、l;else if(quadi.op=END) cout-,-,-,-endl;軟件的測試方法和測試結(jié)果以下是輸入文件內(nèi)容：IF (ad) THENx=f;14武漢理工 課程設(shè)計(jì)說明書ELSE x=t;ELSEIF (by) THENx=y;ELSE x=r;程序運(yùn)行結(jié)果：圖一 詞法分析結(jié)果圖二 文法分析15武漢理工 課程設(shè)計(jì)說明書圖三 四元式輸出16武漢理工 課程設(shè)計(jì)說明書8. 研制報(bào)告（研制過程，本設(shè)計(jì)的評(píng)價(jià)、特點(diǎn)、不足、收獲與體會(huì)等）本次實(shí)驗(yàn)做的比較簡單，不能對復(fù)雜的布爾表達(dá)式和復(fù)雜賦值語句進(jìn)行處理 , 基本上 滿足了實(shí)驗(yàn)的基本要求，輸出的格式也符合四元式表示的形式，特點(diǎn)是基本實(shí)現(xiàn)了嵌套，可以實(shí)現(xiàn)對 =,=, 等的處理，體現(xiàn)出了遞歸下降法的思 想，遞歸函數(shù)的算法符合題目的要求。本次實(shí)驗(yàn)的不足還有很多，程序只能對單個(gè)字母的標(biāo)識(shí)符進(jìn)行識(shí)別，上面的錯(cuò)誤例子1 就是這樣的不足導(dǎo)致的。同時(shí)對于復(fù)雜的賦值語句也無法進(jìn)行處理，也就是上面的錯(cuò) 誤例子 2。對于帶有運(yùn)算符的賦值語句，暫時(shí)還沒有實(shí)現(xiàn)，等以后水平提升了以后，應(yīng) 該會(huì)進(jìn)一步完善改算法。收獲：通過本次實(shí)驗(yàn)，我收獲了很錯(cuò)東西