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

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

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

3、（按公開(kāi)發(fā)表的規(guī)范書(shū)寫(xiě)）。時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計(jì)。周3、周4：完成程序調(diào)試及測(cè)試。周5：撰寫(xiě)課程設(shè)計(jì)報(bào)告。設(shè)計(jì)驗(yàn)收安排：設(shè)計(jì)周的星期五第1節(jié)課開(kāi)始到實(shí)驗(yàn)室進(jìn)行上機(jī)驗(yàn)收。設(shè)計(jì)報(bào)告書(shū)收取時(shí)間：設(shè)計(jì)周的次周星期一上午10點(diǎn)。指導(dǎo)教師簽名： 2011年 11月 18日系主任（或責(zé)任教師）簽名： 2011年 11月 18日1、系統(tǒng)描述（問(wèn)題域描述）1.1、目的通過(guò)設(shè)計(jì)、編制、調(diào)試一個(gè)FOR循環(huán)語(yǔ)句的語(yǔ)法及語(yǔ)義分析程序，加深對(duì)語(yǔ)法及語(yǔ)義分析原理的理解，實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析，并且實(shí)現(xiàn)對(duì)單詞序列的語(yǔ)法分析、語(yǔ)義分析以及中間代碼生成。1.2、設(shè)計(jì)內(nèi)容寫(xiě)出符合

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

5、子程序法。在程序語(yǔ)言的語(yǔ)法定義中有許多采用遞歸定義。我們?cè)趯?duì)它進(jìn)行語(yǔ)法分析時(shí)，編制的處理程序也采取遞歸的方式，可使其結(jié)構(gòu)簡(jiǎn)單易讀。但由于頻繁地調(diào)用子程序大大地降低了分析速度。2.1、遞歸下降法的主要思想：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫(xiě)出相應(yīng)語(yǔ)法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱(chēng)此種方法稱(chēng)為遞歸子程序法或遞歸下降法。2.2、用程序表示遞歸子程序的內(nèi)部結(jié)構(gòu)： 設(shè)A是一個(gè)非終結(jié)符： A1 A2 An 則寫(xiě)(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)用處理符號(hào)串i的子程序。1、任一非終結(jié)符B都不是左遞歸的，否則會(huì)產(chǎn)生死循環(huán)。2、對(duì)A的任意兩個(gè)右部i , j ,有：first(i)first(j)= 。First(i)表示i所能導(dǎo)出串的第一個(gè)符號(hào)的集合。顯然，每個(gè)i的first(i)是互不相同的，否則則無(wú)法判斷應(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 常用的三地址表示:賦值語(yǔ)句

7、 x := y op z， x := op y， x := y 無(wú)條件轉(zhuǎn)移 goto L條件轉(zhuǎn)移 if x relop y goto L過(guò)程調(diào)用 param x 和call p , n過(guò)程返回 return y索引賦值 x := yi和 xi := y 地址和指針賦值 x := &y，x := *y和*x := y三元式結(jié)構(gòu)形式: 編號(hào) (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條語(yǔ)句 輸出表達(dá)式1第2條語(yǔ)句 跳轉(zhuǎn)到條件判斷語(yǔ)句第3條語(yǔ)句 輸出表達(dá)式2第4條語(yǔ)句 條件判斷語(yǔ)句第5條語(yǔ)句 跳轉(zhuǎn)到結(jié)束第6條語(yǔ)句 輸出賦值表達(dá)式第7條語(yǔ)句 跳轉(zhuǎn)到第3條語(yǔ)句5、 編譯系統(tǒng)的概要設(shè)計(jì)5.1 問(wèn)題分析在該階段嚴(yán)格按照設(shè)計(jì)指導(dǎo)書(shū)，分析要完成什么功能。詞法分析提取單詞，寫(xiě)出正確的文法，語(yǔ)法分析檢查輸入單詞串是否符合文法，語(yǔ)義分析完成中間代碼的輸出，使用LL（1）法語(yǔ)法分析。5.2 遞歸下降分析法遞歸下降分析技術(shù)就是通過(guò)對(duì)每個(gè)非終結(jié)符編寫(xiě)一個(gè)子程序來(lái)實(shí)現(xiàn)它的操作，然后通過(guò)遞歸的調(diào)用來(lái)實(shí)現(xiàn)對(duì)輸入字

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

10、候該程序可以按照滿(mǎn)足的條件執(zhí)行下去，當(dāng)沒(méi)有滿(mǎn)足程序中的條件時(shí)就會(huì)顯示語(yǔ)法錯(cuò)誤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; / 編號(hào) 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ì)識(shí)別的單詞的個(gè)數(shù)for(;turn<=num;turn+)/總循環(huán),ch存放剛讀入的字符，strtoken存放已識(shí)別的標(biāo)志付或保留字，turn是數(shù)組str的下標(biāo)if(IsLetter(ch)/判斷是否是字母/存放到strtokenfor(int i=

12、0;i<n;i+) recordx->wordi=strTokeni; cout<<recordx->wordi;/輸出識(shí)別的標(biāo)志符或保留字 cout<<","<<kind<<")"<<endl; recordx->wordi='0' clear(); x+;詞法分析/*語(yǔ)法分析*/打印單詞的編號(hào)/制導(dǎo)翻譯/if(!S(ana,j) cout<<"語(yǔ)法出錯(cuò)!"<<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，用來(lái)區(qū)分標(biāo)志符和保留字/*語(yǔ)法遞歸分析*/int A(int * c,int & q)if(cq+=3) if(cq=7) q+;return 1; else cout<<"step右部出錯(cuò)"<<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右部出錯(cuò)"<<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;<"賦值語(yǔ)句右部出錯(cuò) "<<endl;return 0; else cout<<"賦值語(yǔ)句缺少賦值運(yùn)算符 "<<endl;return 0; else cout<<"賦值語(yǔ)句左部出錯(cuò) "<<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、軟件的測(cè)試方法和測(cè)試結(jié)果針

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