FOR循環(huán)語句的翻譯程序設(shè)計(jì)(遞歸下降法、輸出三表示)-編譯課程設(shè)計(jì)書

1、學(xué) 號： 課 程 設(shè) 計(jì)題 目編譯原理課程設(shè)計(jì)學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班 級計(jì)算機(jī)0901班姓 名丁秀文指導(dǎo)教師陳天煌2012年1月7日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 丁秀文 專業(yè)班級： 計(jì)算機(jī)0901班 指導(dǎo)教師： 陳天煌 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題目: FOR循環(huán)語句的翻譯程序設(shè)計(jì)（遞歸下降法、輸出三地址表示）初始條件：理論：學(xué)完編譯課程，掌握一種計(jì)算機(jī)高級語言的使用。實(shí)踐：計(jì)算機(jī)實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件環(huán)境。如果自己有計(jì)算機(jī)可以在其上進(jìn)行設(shè)計(jì)。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語法分析方法的

2、文法及屬性文法。（2） 完成題目要求的中間代碼三地址表示的描述。（3） 寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計(jì)。（4） 編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)的分析程序。（5） 設(shè)計(jì)報(bào)告格式按附件要求書寫。課程設(shè)計(jì)報(bào)告書正文的內(nèi)容應(yīng)包括：1 系統(tǒng)描述（問題域描述）；2 文法及屬性文法的描述；3 語法分析方法描述及語法分析表設(shè)計(jì)；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計(jì)；5 編譯系統(tǒng)的概要設(shè)計(jì)；6 詳細(xì)的算法描述（流程圖或偽代碼）；7 軟件的測試方法和測試結(jié)果；8 研制報(bào)告（研制過程，本設(shè)計(jì)的評價(jià)、特點(diǎn)、不足、收獲與體會等）；9 參考文獻(xiàn)

3、（按公開發(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)教師簽名： 2011年 11月 18日系主任（或責(zé)任教師）簽名： 2011年 11月 18日1、系統(tǒng)描述（問題域描述）1.1、目的通過設(shè)計(jì)、編制、調(diào)試一個(gè)FOR循環(huán)語句的語法及語義分析程序，加深對語法及語義分析原理的理解，實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析，并且實(shí)現(xiàn)對單詞序列的語法分析、語義分析以及中間代碼生成。1.2、設(shè)計(jì)內(nèi)容寫出符合

4、給定的語法分析方法的文法及屬性文法。完成題目要求的中間代碼三地址表示的描述。寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計(jì)。編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)的分析程序。設(shè)計(jì)報(bào)告格式按附件要求書寫。2、文法及屬性文法的描述S->FOR 語句1 DO 語句2語句1->語句2 語句3 語句4語句2->表達(dá)式1 語句3->標(biāo)識符 i語句4->標(biāo)識符 jS ->for S1 do S2S1 ->S2ABS2 ->i=jA ->stepjB ->untilj3、 語法分析方法描述及語法分析表設(shè)計(jì)遞歸下降法又稱遞歸

5、子程序法。在程序語言的語法定義中有許多采用遞歸定義。我們在對它進(jìn)行語法分析時(shí)，編制的處理程序也采取遞歸的方式，可使其結(jié)構(gòu)簡單易讀。但由于頻繁地調(diào)用子程序大大地降低了分析速度。2.1、遞歸下降法的主要思想：對每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。2.2、用程序表示遞歸子程序的內(nèi)部結(jié)構(gòu)： 設(shè)A是一個(gè)非終結(jié)符： A1 A2 An 則寫(A) Û if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else i

6、f charfirst(n ) then (n) else ERROR其中(i)表示調(diào)用處理符號串i的子程序。1、任一非終結(jié)符B都不是左遞歸的，否則會產(chǎn)生死循環(huán)。2、對A的任意兩個(gè)右部i , j ,有：first(i)first(j)= 。First(i)表示i所能導(dǎo)出串的第一個(gè)符號的集合。顯然，每個(gè)i的first(i)是互不相同的，否則則無法判斷應(yīng)執(zhí)行哪個(gè)(i )。 4、按給定的題目給出中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計(jì)一般形式：x := y op z 如表達(dá)式x + y * z 翻譯成的三地址代碼序列是： t1 := y * z t2 := x + t1 常用的三地址表示:賦值語句

7、 x := y op z， x := op y， x := y 無條件轉(zhuǎn)移 goto L條件轉(zhuǎn)移 if x relop y goto L過程調(diào)用 param x 和call p , n過程返回 return y索引賦值 x := yi和 xi := y 地址和指針賦值 x := &y，x := *y和*x := y三元式結(jié)構(gòu)形式: 編號 (OP，ARG1，ARG2)在本次課設(shè)中，以for i=1 step 1 until 10 do a=1#為例輸出的三地址代碼是：100 i=1101 goto 103102 i:=i+1103 if i<0 goto 105104 goto 1

8、07105 a:=1106 goto 102107 end我的中間代碼結(jié)構(gòu)是這樣設(shè)計(jì)的：第1條語句 輸出表達(dá)式1第2條語句 跳轉(zhuǎn)到條件判斷語句第3條語句 輸出表達(dá)式2第4條語句 條件判斷語句第5條語句 跳轉(zhuǎn)到結(jié)束第6條語句 輸出賦值表達(dá)式第7條語句 跳轉(zhuǎn)到第3條語句5、 編譯系統(tǒng)的概要設(shè)計(jì)5.1 問題分析在該階段嚴(yán)格按照設(shè)計(jì)指導(dǎo)書，分析要完成什么功能。詞法分析提取單詞，寫出正確的文法，語法分析檢查輸入單詞串是否符合文法，語義分析完成中間代碼的輸出，使用LL（1）法語法分析。5.2 遞歸下降分析法遞歸下降分析技術(shù)就是通過對每個(gè)非終結(jié)符編寫一個(gè)子程序來實(shí)現(xiàn)它的操作，然后通過遞歸的調(diào)用來實(shí)現(xiàn)對輸入字

9、符串的分析，這其中還包括對輸入字符串的詞法分析。在詞法分析的時(shí)，得到的字符單詞要和關(guān)鍵字比較，看是否是關(guān)鍵字，根據(jù)比較結(jié)果進(jìn)行返回相應(yīng)的單詞類型。單詞類型主要包括界限符，關(guān)鍵字，常量，標(biāo)識符，運(yùn)算符等，每種符號都是一種類型。在語法分析程序中，根據(jù)詞法得到的結(jié)果，進(jìn)行判斷是否是當(dāng)前需要的單詞類型，如果不是就說明輸入字符串不能由該文法推導(dǎo)出來；如果是當(dāng)前需要的類型，就相應(yīng)得做該單詞類型分支程序。根據(jù)文法可以得到這個(gè)遞歸下降程序可以分析for語句，在文法的開始符號S開始進(jìn)行遞歸調(diào)用，因此這個(gè)文法的遞歸中就要考慮到調(diào)用以及遞歸。在遞歸子程序中，在嵌套調(diào)用其他子程序時(shí)都是有一定條件的，當(dāng)滿足這個(gè)條件的時(shí)

10、候該程序可以按照滿足的條件執(zhí)行下去，當(dāng)沒有滿足程序中的條件時(shí)就會顯示語法錯誤6、 詳細(xì)的算法描述void main()/主函數(shù)Ofstream out(“”)/定義分析結(jié)果輸出文件cout<<"*產(chǎn)生式*"<<endl;/ for step until do i j = cout<<" S ->for S1 do S2"<<endl; / 編號 2 3 4 5 6 7 8 cout<<" S1 ->S2AB"<<endl; cout<<&q

11、uot; S2 ->i=j"<<endl; cout<<" A ->stepj"<<endl; cout<<" B ->untilj"<<endl;turn=0; num=buffer()-1; int x=0;/計(jì)識別的單詞的個(gè)數(shù)for(;turn<=num;turn+)/總循環(huán),ch存放剛讀入的字符，strtoken存放已識別的標(biāo)志付或保留字，turn是數(shù)組str的下標(biāo)if(IsLetter(ch)/判斷是否是字母/存放到strtokenfor(int i=

12、0;i<n;i+) recordx->wordi=strTokeni; cout<<recordx->wordi;/輸出識別的標(biāo)志符或保留字 cout<<","<<kind<<")"<<endl; recordx->wordi='0' clear(); x+;詞法分析/*語法分析*/打印單詞的編號/制導(dǎo)翻譯/if(!S(ana,j) cout<<"語法出錯!"<<endl; else cout<<&q

13、uot;三地址碼如下："<<endl; out<<"三地址碼如下："<<endl; cout<<"100 " out<<"100 " int i=0; while(record1->wordi!='0')cout<<record1->wordi+;out<<record1->wordi-1;cout<<record2->word0;out<<record2->word0;

14、i=0; while(record3->wordi!='0') cout<<record3->wordi+;cout<<endl; cout<<"101 goto 103"<<endl; /詞法分析/int buffer()/載入單詞while(ch!=#) str/i+=ch; fin.get(ch); stri='0'/輸入程序，以“#”作為結(jié)束標(biāo)志bool IsLetter(char ch)/判斷是否是字母bool IsDigit(char ch)/判斷是否是數(shù)字char Ge

15、tChar(int i)/讀取字符char GetBC(char ch)/判斷是不是空格或者換行，如果是，直接讀取下一個(gè)字符直道不再空白為止int Reserve()/以單詞為單位查找保留字，是則返回編碼，不是則返回0，用來區(qū)分標(biāo)志符和保留字/*語法遞歸分析*/int A(int * c,int & q)if(cq+=3) if(cq=7) q+;return 1; else cout<<"step右部出錯"<<endl;return 0; else cout<<"error 'step'"&l

16、t;<endl;return 0;int B(int * b,int & o) if(bo+=4) if(bo=7) o+; return 1; else cout<<"until右部出錯"<<endl;return 0; else cout<<"error 'until'"<<endl;return 0;int S2(int * d,int & h) if(dh+=6) if(dh+=8) if(dh=6|dh=7) h+; return 1; else cout&l

17、t;<"賦值語句右部出錯 "<<endl;return 0; else cout<<"賦值語句缺少賦值運(yùn)算符 "<<endl;return 0; else cout<<"賦值語句左部出錯 "<<endl;return 0;int S1(int * m,int & n) if(S2(m,n) if(A(m,n) if(B(m,n) return 1; else return 0; else return 0; else return 0; int S(int *a

18、,int & z) if (az+=2) if (S1(a,z) if(az+=5) if(S2(a,z) cout<<"succeed!"<<endl;return 1; else return 0; else cout<<"error 'do'"<<endl; return 0; else return 0; else cout<<"error 'for'"<<endl; return 0;7、軟件的測試方法和測試結(jié)果針

19、對所設(shè)計(jì)的關(guān)于 for循環(huán)語句的翻譯程序，分別用正確的程序和有錯誤的程序進(jìn)行測試，測試出結(jié)果程序的可用性和健壯性。測試中分別使用了合法程序和非法程序，對結(jié)果程序進(jìn)行測試，具體的測試程序、測試過程和測試結(jié)果如下： 正確的測試輸入文件執(zhí)行結(jié)果輸出文件錯誤的測試輸入文件執(zhí)行結(jié)果8、 研制報(bào)告在課程設(shè)計(jì)期間，通過不斷地閱讀書籍資料，上網(wǎng)搜查各種實(shí)例，根據(jù)相關(guān)的知識，參考一些經(jīng)典的例子，寫出較為簡單的FOR循環(huán)語句的翻譯程序設(shè)計(jì)（遞歸下降法、輸出三地址表示）先設(shè)計(jì)簡單的語法規(guī)則的屬性文法，畫出流程圖，對程序進(jìn)行概要設(shè)計(jì)，要想實(shí)現(xiàn)此算法，主要分成詞法分析和語法分析。詞法分析從文本中逐個(gè)讀出各個(gè)單詞，并對單詞進(jìn)行識別和分類，并且保存單詞個(gè)信息。語法分析負(fù)責(zé)對輸入流中的單詞進(jìn)行分析，檢驗(yàn)是否符合所寫的語法規(guī)則，并對其進(jìn)行初步翻譯。利用流程圖，設(shè)計(jì)出大致的流程，對詞法分析和語法分析進(jìn)行詳細(xì)的設(shè)計(jì)，對主函數(shù)進(jìn)