1、武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課內(nèi)實踐報告學(xué) 號： 0121210340314課內(nèi)實踐報告課程名稱 編譯原理設(shè)計題目WHILE循環(huán)語句的翻譯程序設(shè)計(遞歸下降法，輸出四元式)學(xué) 院 計算機科學(xué)與技術(shù)專業(yè)班級計算機1203班姓 名 閔丹楓指導(dǎo)教師林 泓2014年12月 8日課程設(shè)計任務(wù)書學(xué)生姓名： 閔丹楓 專業(yè)班級： 計算機1203班 指導(dǎo)教師： 林 泓 工作單位：計算機科學(xué)與技術(shù)學(xué)院 題目: WHILE循環(huán)語句的翻譯程序設(shè)計（遞歸下降法、輸出四元式）初始條件：理論：學(xué)完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設(shè)計。要求完成的主要任務(wù):

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

3、方法和測試結(jié)果；8 研制報告（研制過程，本設(shè)計的評價、特點、不足、收獲與體會等）；9 參考文獻（按公開發(fā)表的規(guī)范書寫）。時間安排：設(shè)計安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計。周3、周4：完成程序調(diào)試及測試。周5：撰寫課程設(shè)計報告。設(shè)計驗收安排：設(shè)計周的星期五第1節(jié)課開始到實驗室進行上機驗收。設(shè)計報告書收取時間：設(shè)計周的次周星期一上午10點。指導(dǎo)教師簽名： 2014年 9月 1日系主任（或責(zé)任教師）簽名： 2014年 月 日 WHILE循環(huán)語句的翻譯程序設(shè)計（遞歸下降法、輸出四元式）一 系統(tǒng)描述1.1問題描述設(shè)計一個WHILE布爾表達式DO賦值語句循環(huán)語句的詞法語法及語義分析程序，語法分析選擇

4、遞歸下降法，采用用語法制導(dǎo)翻譯輸出中間代碼四元式。1.2主要任務(wù)設(shè)計一個能識別while循環(huán)語句的文法，消除左遞歸，使文法符合LL(1)文法。利用遞歸下降法編寫一個集詞法分析，語法分析和語義分析為一體的程序。該程序首先可以檢查輸入語句是否符合詞法要求，若符合則繼續(xù)識別輸入的語句是否符合while語句的文法，若符合則進行語義分析，輸出用四地址代碼表示的中間代碼。二 文法及屬性文法的描述2.1 文法的描述 擴充巴科斯-瑙爾范式（EBNF）： := while () do := := + | - | := * | / | :=() | |:=；根據(jù)以上寫出來的While循環(huán)語句的文法表示如下：1.

5、S - while (A) do B2. A - CDC3. D - | = | = | C+E | C-E | E5. E - E*F | E/F | E6. F - (C) | i | n對以上文法消除左遞歸，最后得到的文法為：1. S-while (A) do B 2. A-CDC3. D- | = | = | EG 5. G-+EG | -EG | 6. E-FH 7. H-*FH | / FH | 8. F-(C) | i | n 9. B-i=C；2.1 屬性文法的描述(1)任一非終結(jié)符B都不是左遞歸的，否則會產(chǎn)生死循環(huán)。(2)對A的任意兩個右部i , j ,有：first(i)f

6、irst(j)=， First(i)表i所能導(dǎo)出串的第一個符號的集合。顯然，每個i的first(i)是互不相同的，否則則無法判斷應(yīng)執(zhí)行哪個(i )。產(chǎn)生式 語義規(guī)則S-while (A) do B S.first:=newtemp; S.second:=newtemp;A.true:=newtemp;emit（A.false:=S.second;S1.second:=S.first; S.place:=(S.begin, :) | B.place |printf(S.true, :) |S1.place | printf(goto,S.begin) | printf(B.false, :) |

7、 printf(goto Lnext);）A-CDCA.place:=newpemt;emit(A.place:=C1.place D.place C2.place).D- D.place:=newtemp ;Emit(D.Place:=).D- D.place:=newtemp ;Emit(D.Place:= =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=EG C.Place:=newtemp;Emit(C.Place:=

8、E.Place G.place)G-+EG G.Place:=newtemp;Emit(G1.Place:=+E.Place G2.place)G-EG G.Place:=newtemp;Emit(G1.Place:=-E.Place G2.place)G-G.Place:=newtemp;Emit(G.Place:=H-*FH H.Place:=newtemp;Emit(H1.Place:=*F.Place H2.place)H- /FHH.Place:=newtemp;Emit(H1.Place:=+F.Place H2.place)H-G.Place:=newtemp;Emit(H1.P

9、lace:=+E.Place H2.place)F-(C) F.Place:=C.PlaceB-i=C;p:=lookup()If p!=nil thenEmit(p:=C.PlaceElse error)三 語法分析方法描述31 語法分析方法描述 遞歸下降法是一種比較簡單直觀，易于構(gòu)造的語法分析方法。他要求文法滿足LL（1）文法，他的設(shè)計思想是對應(yīng)文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的單詞（或串），當某非終結(jié)符的產(chǎn)生式有多個候選時，能夠按LL（1）形式可唯一地確定選擇某個候選進行推導(dǎo)。它的優(yōu)點是簡單直觀，易于構(gòu)造，很多編譯系統(tǒng)所實現(xiàn)缺點是對文法

10、要求很高，由于遞歸調(diào)用多，影響分析器的效率。遞歸下降程序是由一組子程序組成，每個子程序?qū)?yīng)于一個非終結(jié)(S,A,B,C,D,E,F,G,H)。每個子程序處理相應(yīng)句型中相對于此非終結(jié)符號的產(chǎn)生式。在定義文法時，是遞歸定義的，所以這些子程序也是遞歸的。當一個子程序調(diào)用另一個子程序時，原子程序順序執(zhí)行語句，即總是先執(zhí)行被調(diào)用的子程序，然后再執(zhí)行后繼的程序。程序中9個子程序，其中S 是開始符號，也是遞歸下降分析的入口，通過調(diào)用詞法分析器進行單詞分析，并通過word=l.Yufa_Queue.front()來得到當前所分析到的單詞，然后在遞歸語法分析中根據(jù)這個單詞分析下一步要執(zhí)行的子程序。其中要注意的是

11、，當子程序G()和H()中出現(xiàn)匹配的是空字符串時，不做單詞處理，該所取得的單詞，應(yīng)該為下一個匹配產(chǎn)生做準備。32 遞歸下降法實現(xiàn)的原理設(shè)A是一個非終結(jié)符：A1 A2 An則寫 (A) if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示調(diào)用處理符號串i的子程序。對A的任一右部i 設(shè)為： i = y1 y2 yn則定義( i) begin(y1);(y2);(yn) end其中yj可分為下列兩種情況（j=1,n):1) yjVT,則 (

12、yj) if char yj then ERROR else READ(char)2) yjVN,則(yj)表示調(diào)用關(guān)于yj的遞歸子程序。四中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計4.1四元式形式 中間代碼為四元式，按照要求，要輸出四元式一個四元式是一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為oparg1arg2及result。域op包含一個代表運算符的內(nèi)部碼。語句while ab do a=a+b的四元式輸出:1 ( , a , b , 3 ) 2 ( j , _ , _ ,6 ) 3 ( + , a , b , n ) 4 ( = , n , _ , a ) 5 ( j , _ , _ ,

13、 1) 6五 編譯系統(tǒng)的概要設(shè)計5.1全局程序的概要設(shè)計 遞歸下降分析技術(shù)就是通過對每個非終結(jié)符編寫一個子程序來實現(xiàn)它的操作，然后通過遞歸的調(diào)用來實現(xiàn)對輸入字符串的分析，這其中還包括對輸入字符串的詞法分析。在詞法分析的時，得到的字符單詞要和關(guān)鍵字比較，看是否是關(guān)鍵字，根據(jù)比較結(jié)果進行返回相應(yīng)的單詞類型。單詞類型主要包括界限符，關(guān)鍵字，常量，標識符，運算符等，每種符號都是一種類型。在語法分析程序中，根據(jù)詞法得到的結(jié)果，進行判斷是否是當前需要的單詞類型，如果不是就說明輸入字符串不能由該文法推導(dǎo)出來；如果是當前需要的類型，就相應(yīng)得做該單詞類型分支程序。根據(jù)文法可以得到這個遞歸下降程序可以分析whil

14、e語句，在文法的開始符號S開始進行遞歸調(diào)用，因此這個文法的遞歸中就要考慮到調(diào)用以及遞歸。在遞歸子程序中，在嵌套調(diào)用其他子程序時都是有一定條件的，當滿足這個條件的時候該程序可以按照滿足的條件執(zhí)行下去，當沒有滿足程序中的條件時就會顯示語法錯誤。5.2詞法分析詞法分析程序的任務(wù)是：從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號的中間程序。詞法分析檢查的錯誤主要是挑出源程序中出現(xiàn)的非法符號。所謂非法符號是指不是程序設(shè)計語言中允許出現(xiàn)的符號，就像自然語句中的錯字。5.3遞歸下降翻譯器的設(shè)計對每個非終結(jié)符A構(gòu)造一個函數(shù)過程，對A的每個繼承屬性設(shè)置一個形式參數(shù)

15、，函數(shù)的返回值為A的綜合屬性，A對應(yīng)的函數(shù)過程中，為出現(xiàn)在A的產(chǎn)生式中的每一個文法符號的每一個屬性都設(shè)置一個局部變量。非終結(jié)符A對應(yīng)的函數(shù)過程中，根據(jù)當前的輸入符號決定使用哪個產(chǎn)生式候選。每個產(chǎn)生式對應(yīng)的程序代碼中，按照從左到右的次序，對于單詞符號，非3：終結(jié)符和語義動作分別做以下工作。1. 對于帶有綜合屬性x的終結(jié)符X，把x的值存入為X，x設(shè)置的變量中。然后產(chǎn)生一個匹配X的調(diào)用，并繼續(xù)讀入一個輸入符號。2. 對于每個非終結(jié)符號B，產(chǎn)生一個右邊帶有函數(shù)調(diào)用的賦值語句c=B(b1,b2,，bk)3. 對于語義動作，把動作的代碼抄進分析器中，用代表屬性的變量來代替對應(yīng)屬性的每一次引用。5.4語法制

16、導(dǎo)翻譯在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動作）進行翻譯。屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由于屬性類型不同，屬性域存放的內(nèi)容就要根據(jù)屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向?qū)傩灾档闹羔槨τ诰C合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛?cè)霔r為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應(yīng)的屬性值，即在成為棧頂時，繼承屬性的屬性域必須

17、有值。六 詳細的算法描述S()W()EF()D()G()R()T()方法和變量的定義#define MAX 100int m = 0, sum = 0;/sum用于計算運算符的個數(shù) m用于標記輸入表達式中字符的個數(shù)char JG = A;char strMAX; /用于存賦值表達式int token = 0; /左括號的標志int sign = 0;char whi5 = w, h, i, l, e ; /檢查關(guān)鍵字whilestring getsentence(); /獲取表達式void anlyse(string temp); /while語句遞歸分析bool Judge_W(char *

18、ch); /判斷whilevoid Do_E(string temp); /Evoid Do_F(string temp); /F void Do_G(string temp); / Gvoid change(int e); /用于更改計算后數(shù)組中的值void chengchuchuli(int i, int m); /對賦值語句進行乘除處理便于輸出四元式 void jiajianchuli(int j, int m); /對賦值語句進行加減處理四元式void siyuanshi(); /用于處理賦值語句輸出四元式void anlyse(string temp)char *wh = new c

19、har5;int s_length = temp.size() + 1;char *str = new chars_length;for (; sign 5; sign+)whsign = tempsign;if (Judge_W(wh)if (tempsign = ()sign+;Do_E(temp);做W（）：bool Judge_W(char *ch) bool flag = true;for (int i = 0; i 5; i+)if (chi != whii)flag = false;cout while關(guān)鍵字輸入錯誤！ aFbif (tempsign = a & tempsign

20、 A & tempsign = Z)cout ( ;sign+;Do_F(temp);elsecout （）中含有非法字符！ | =void Do_F(string temp) /F - | =int f_sign = sign;if (tempf_sign = )if (tempf_sign + 1 = =)cout tempf_sign + 1= a & tempf_sign + 2 A & tempf_sign + 2 = Z)cout tempf_sign tempf_sign + 1 , tempf_sign - 1 , tempf_sign + 2 ,sign) = a & tem

21、pf_sign + 1 A & tempf_sign + 1 = Z)cout tempf_sign , tempf_sign - 1 , tempf_sign + 1 ,sign) endl;sign+;sign+;if (tempsign = ) & tempsign + 1 = )sign = sign + 2;Do_G(temp);elsecout ()中存在符號錯誤 c=Rvoid Do_G(string temp) /G- c=R 賦值表達式int pMAX;int len = temp.size() + 1;char ch = a;int c = -1, q = 0;while

22、(tempsign != ; & sign len)ch = tempsign;strm+ = ch;if (ch = = | ch = + | ch = - | ch = * | ch = /) sum+;else if (ch = ()p+c = m - 1;else if (ch = )q = m - 1;chengchuchuli(pc, q);/從左括號處理到又括號jiajianchuli(pc, q);JG = (char)(int)JG-;strpc = strm - 1 = JG;c-;JG = (char)(int)JG+;sign+;cout str endl;siyuan

23、shi();if (tempsign != ;) cout 前缺少 “;” endl;if (temptemp.size()-1 != ) cout 缺少“” = A&ch = Z)for (int l = 0; l= A&stre = Z)for (int i = 0; im; i+)if (stri = stre)stri = JG;void chengchuchuli(int i, int m)i+;for (; i = m - 1; i+)/處理乘除運算if (stri = * | stri = /)cout ( stri stri - 1 stri + 1 JG ) endl;cha

24、nge(i - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;void jiajianchuli(int j, int m)j+;for (; j = m - 1; j+)/處理加減運算if (strj = + | strj = -)cout ( strj strj - 1 strj + 1 JG ) endl;change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;void siyuanshi()for (int i = 0; i =

25、 m - 1; i+)/處理乘除運算if (stri = * | stri = /)cout ( stri stri - 1 stri + 1 JG ) endl;change(i - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;for (int j = 0; j = m - 1; j+)/處理加減運算if (strj = + | strj = -)cout ( strj strj - 1 strj + 1 JG ) endl;change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;for (int k = 0; k = m - 1; k+)/處理賦值運算if (strk = =)JG = (char)(int)-JG;cout ( strk strk + 1 strk - 1 ) b）z=x+y;測試結(jié)果如下：輸入while(ab)z=x+y*c; 測試結(jié)果如下輸入wh(ab)z=y; 結(jié)果為