《編譯原理》課程設計說明書WHILE循環(huán)語句的翻譯程序設計

1、附件1：學 號： 課 程 設 計題 目while循環(huán)語句的翻譯程序設計學 院計算機科學與技術學院專 業(yè)計算機科學與技術班 級計算機0702姓 名指導教師 2010年1月8日課程設計任務書學生姓名： 專業(yè)班級： 計算機0702班 指導教師： 工作單位：計算機科學與技術學院 題目: while循環(huán)語句的翻譯程序設計（lr方法、輸出三地址表示） 初始條件：理論：學完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設計。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語法分析方法的文法

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

3、公開發(fā)表的規(guī)范書寫）。時間安排：設計安排一周：周1、周2：完成系統(tǒng)分析及設計。周3、周4：完成程序調(diào)試及測試。周5：撰寫課程設計報告。設計驗收安排：設計周的星期五第1節(jié)課開始到實驗室進行上機驗收。設計報告書收取時間：設計周的次周星期一上午10點。指導教師簽名： 2009年 11月 23日系主任（或責任教師）簽名： 2009年 11月 23日1.系統(tǒng)描述 自定義while循環(huán)句型的文法及其屬性文法，并用lr法為該文法設計、編制、調(diào)試一個語法及語義分析程序，并在過程中實現(xiàn)詞法分析、語法分析，最終以三地址碼的形式將形成的中間代碼輸出。2.文法及屬性文法的描述21 文法的描述該文法的產(chǎn)生式如下所示：s

4、-while(a)b;a-cdcc-a|b d- =| b-a=e b-b; e-efe e-(e) e-a|b f-+|-|*|/ 其中while、( 、) 、 、 、；、a 、b、=、=、+、-、*、/ 均為終結(jié)符，而s、a、b、c、d、e、f這些大寫字母均為非終結(jié)符。d表示比較運算符，f表示算術運算符。22 屬性文法的描述對該文法的屬性文法描述如下：(1) s-while(a)b; prinf(if a goto b else goto next)(2) a-cdc printf(a.val = c1.val d c2.val) (3) c-a|b c.val = a | b(4) d-

5、 =| d.val = =| (5) b-a=e b.val =a.val = e.val (6) b-b; printf(b = i1.val t i2.val)(7) e-efe printf(e.val = e1.val f e2.val) (8) e-(e) printf(e.place=e1.place)(9) e-a|b e.val = a | b(10)f-+|-|*|/ f.val = +|-|*|/ 3. 語法分析方法描述及語法分析表設計3.1語法分析方法的描述3.1.1 lr分析法基本概述lr分析法的歸約過程是規(guī)范推導的逆過程，所以lr分析過程是一種規(guī)范歸約過程。lr分析法

6、正是給出一種能根據(jù)當前分析棧中的符號串(通常以狀態(tài)表示)和向右順序查看輸入串的k個(k0)符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能唯一地確定句柄3.1.2 lr分析器分析過程1.首先將初始狀態(tài) s0及句子的左界符#分別壓入狀態(tài)棧和符號棧中。2.設在分析中的某一步，分析棧及余留的輸入串為如下格局： s0s1 sm ai ai+1an #x1 xm 則用棧頂狀態(tài)sm和當前掃描符 ai組成符號對（ sm, ai)去查分析動作表，根據(jù)actionsm, ai的指示完成相應的分析動作。表中每一表元素所規(guī)定的動作僅能是下列四種動作之一：（1） actionsm, ai=

7、sm+1 （移進）表明句柄尚未在棧頂形成，此時正期待移進輸入符號以便形成句柄。故將當前的輸入符號和表元素sm+1分別壓入棧中（2） actionsm, ai= rj (歸約）表明此時應按文法的第j個產(chǎn)生式a xm-k+1xm-k+2 xm 進行歸約。即棧頂符號串xm-k+1xm-k+2 xm已成為當前句型的句柄。所謂按第j個產(chǎn)生式歸約，就是將分析棧中從頂向下的k個符號退棧，然后將文法符號a壓入符號棧中。然后以（ sm-k,a)去查狀態(tài)轉(zhuǎn)移表，設gotosm-k,a= sl ,則將此新狀態(tài)壓入狀態(tài)棧中。（3） actionsm, ai=acc （接受）表明當前的輸入串已被成功地分析完畢，應停止分

8、析器的工作。（4） actionsm, ai=error（空白）。 表明當前的輸入串中含有錯誤，也應終止當前的分析工作。轉(zhuǎn)出錯處理3. 重復上述第2步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)”或“出錯狀態(tài)“為止。3.2 lr分析表設計構(gòu)造3.2.1 已定義文法的dfa如圖3.2.13.2.2 文法的分析表見表3.2.2分析表注釋：a代表 a|b+代表 +|-|*|/=代表 =|a|bef（e;f)e)(a|befa|b|w (a)b;a-cdcc-a|bi4: c- a|bi6: s-w (b)ei5: a-cdcd-|cdcc- a|bi20: e-efee-(e)e-efee-a|bi14: b

9、-a=ee-(e)e-efee-a|bi21: e-efei22: e- (e)i13: b-a=ei16: e-efef-+|-|*|/ i15: b-a=ei18: e-a|bi17: e- (e)e-(e)e-efee-a|bsw(a|bb;e;（=efcai8: a-cdci0: s-ss -w(a)b;i2: s-w (a)b;i1:s-si9:s-w (a)b;i10:s-w (a) b;i11:s-w (a) b;b-a=eb-b;i12:s-w (a) b;b-b;i24:s-w(a)b;b-b;i25：s-w(a)b;i23:e- (e)圖3.2.1： 文法的dfa分析表的a

10、ction部分狀態(tài)w（）；as流程圖如下：5.2 語法分析語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。流程圖如下：輸入串#cic1sp#xisi總 控 程 序輸出action表goto表棧結(jié)束其中sp為棧頂指針，si為狀態(tài)棧，xi為文法符號棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關系gotosi,x=sj確定，改關系式是指當前棧頂狀態(tài)為si遇到當前文法符號為x時應轉(zhuǎn)向狀態(tài)sj。x為終結(jié)符或非終結(jié)符。5.3 語法制導翻譯在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應的語義子程序（或語義規(guī)則描述的語義動作）進行翻譯。屬性文法的每個符

11、號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由于屬性類型不同，屬性域存放的內(nèi)容就要根據(jù)屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向?qū)傩灾档闹羔?。對于綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛?cè)霔r為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。6 詳細的算法描述主要是詞法分析與lr語法分析部分（包含主體程序干，對于調(diào)用的函數(shù)略去）詞法分析主體：int cifa()o

12、fstream fout;fout.open(詞法分析.txt,ios:out);if(!fout)cout詞法分析文件打開失敗！endl;fout.close();/將詞法分析文件置空ifstream fin;fin.open(源文件.txt);if(!fin)cout打開源文件失敗!endl;/源文件打開char temp120;for(int i=0;i20;i+)temp1i=0;/temp1用來記錄非符號串且初始值均置空char temp2;i=0;while(!fin.eof()&temp2!=)fin.get(temp2);if(isfuhao(temp2)/當讀入的是符號時，分

13、析temp1 if(temp10!=0) analysis(temp1);fuhao(temp2);/判斷是那種符號i=0; for(int i=0;i20;i+) temp1i=0;/temp1置空elsetemp1i=temp2;i+; fin.close();cout文件 詞法分析 導入完成！endl;cout是否轉(zhuǎn)化為含有雙符號的詞法分析文件？(yes-1,no-0)i;if(i)change();cout文件 詞法分析2 已導入完成！n;zhuangtai *temp;temp=top;while(temp!=null)coutnnext;coutnow analysis ww,wh

14、ile)=0) push(2);p=p-next;break;case(1):if(strcmp(p-w,)=0) pop(1);push(0);break;case(2):if(strcmp(p-w,()=0) push(3);p=p-next;break;case(3):if(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(4);p=p-next;break;case(4):pop(1);n=top-n;if(n=3) push(5);break; if(n=7) push(8);break;case(5):if(strcmp(p-d,:運算符)=

15、0) push(6);p=p-next;break;case(6):pop(1);push(7);p=p-next;break;case(7): if(strcmp(p-w,)=0) push(8);break;case(8):pop(3);push(9);break;case(9):if(strcmp(p-w,)=0) push(10);p=p-next;break;case(10):if(strcmp(p-w,)=0) push(11);p=p-next;break;case(11):/if(strcmp(p-w,;)=0) push(12);break; if(strcmp(p-d,:為

16、標示符)=0) push(13);p=p-next;break; case(12): if(strcmp(p-w,;)=0) push(24);p=p-next;break;case(13):if(strcmp(p-w,=)=0) push(14);p=p-next;break;case(14):if(strcmp(p-w,()=0) push(17);p=p-next;break;if(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(18);p=p-next;break;case(15): pop(3);if(top-n=11) push(12);b

17、reak;case(16):/if(strcmp(p-d,:為運算符)=0)if(strcmp(p-d,:運算符)=0)push(19);p=p-next;break;case(17):if(strcmp(p-w,()=0) push(17);p=p-next;break;if(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(18);p=p-next;break;case(18):pop(1);n=top-n;if(strcmp(p-w,)=0)&(n=20) push(21);break;if(strcmp(p-w,;)=0)&(n=20) push

18、(21);break;if(n=14)&(strcmp(p-d,:運算符)=0) push(16);break;if(n=14)&(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(15);break;if(strcmp(p-d,:運算符)=0)&(n=17) push(16);break;if(strcmp(p-w,)=0&(n=17) push(21);break;if(strcmp(p-d,:運算符)=0)&(n=20) push(16);break;case(19):pop(1);if(top-n=16) push(20);break;case(

19、20):if(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(18);p=p-next;break;if(strcmp(p-w,()=0) push(17);p=p-next;break; case(21):pop(3);n=top-n;if(strcmp(p-w,)=0&(n=17) push(22);break;if(strcmp(p-w,;)=0)&(n=20) push(21);break;if(strcmp(p-d,:運算符)=0)&(n=20) push(16);break;if(strcmp(p-w,)=0)&(n=20) push(21

20、);break; if(n=14)&(strcmp(p-w,;)=0) push(15);break;if(n=14)&(strcmp(p-d,:運算符)=0) push(16);break;if(n=14)&(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(15);break;if(strcmp(p-d,:運算符)=0)&(n=17) push(16);break;case(22):if(strcmp(p-w,)=0) push(23);p=p-next;break;case(23):pop(3); n=top-n;if(strcmp(p-w,)=0

21、&(n=17) push(22);break;if(strcmp(p-w,;)=0)&(n=20) push(21);break;if(strcmp(p-d,:運算符)=0)&(n=20) push(16);break;if(strcmp(p-w,)=0)&(n=20) push(21);break;if(n=14)&(strcmp(p-d,:運算符)=0) push(16);break;if(n=14)&(strcmp(p-d,:為標示符)=0|strcmp(p-d,:為常數(shù))=0) push(15);break;if(strcmp(p-d,:運算符)=0)&(n=17) push(16);break;case(24): if(strcmp(p-d,:為標示符)=0)|(strcmp(p-d,:為標示符)=0)pop(2);push(13);p=p-next;break;if(strcmp(p-w,)=0) push(25);break;case(25):pop(8);push(1);break;return p;7 軟件的測試方法和測試結(jié)果運行界面及結(jié)果顯示：語法分析過程中狀態(tài)棧與符號棧情況：源文件：詞法分析結(jié)果：三地址輸出