1、學 號： 課內實踐報告課程名稱 編譯原理設計題目WHILE循環語句的翻譯程序設計(遞歸下降法，輸出四元式)學 院 計算機科學與技術專業班級計算機1203班姓 名 閔丹楓指導教師林 泓2014年12月 8日課程設計任務書學生姓名： 閔丹楓 專業班級： 計算機1203班 指導教師： 林 泓 工作單位：計算機科學與技術學院 題目: WHILE循環語句的翻譯程序設計（遞歸下降法、輸出四元式）初始條件：理論：學完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環境。如果自己有計算機可以在其上進行設計。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要

2、求）（1） 寫出符合給定的語法分析方法的文法及屬性文法。（2） 完成題目要求的中間代碼四元式的描述。（3） 寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設計。（4） 編制好分析程序后，設計若干用例，上機測試并通過所設計的分析程序。（5） 設計報告格式按附件要求書寫。課程設計報告書正文的內容應包括：1 系統描述（問題域描述）；2 文法及屬性文法的描述；3 語法分析方法描述及語法分析表設計；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結構設計；5 編譯系統的概要設計；6 詳細的算法描述（流程圖或偽代碼）；7 軟件的測試方法和測試結果；8 研制報告（研制過程，本設計的評價、特點

3、、不足、收獲與體會等）；9 參考文獻（按公開發表的規范書寫）。時間安排：設計安排一周：周1、周2：完成系統分析及設計。周3、周4：完成程序調試及測試。周5：撰寫課程設計報告。設計驗收安排：設計周的星期五第1節課開始到實驗室進行上機驗收。設計報告書收取時間：設計周的次周星期一上午10點。指導教師簽名： 2014年 9月 1日系主任（或責任教師）簽名： 2014年 月 日 WHILE循環語句的翻譯程序設計（遞歸下降法、輸出四元式）一 系統描述1.1問題描述設計一個WHILE布爾表達式DO賦值語句循環語句的詞法語法及語義分析程序，語法分析選擇遞歸下降法，采用用語法制導翻譯輸出中間代碼四元式。1.2主

4、要任務設計一個能識別while循環語句的文法，消除左遞歸，使文法符合LL(1)文法。利用遞歸下降法編寫一個集詞法分析，語法分析和語義分析為一體的程序。該程序首先可以檢查輸入語句是否符合詞法要求，若符合則繼續識別輸入的語句是否符合while語句的文法，若符合則進行語義分析，輸出用四地址代碼表示的中間代碼。二 文法及屬性文法的描述2.1 文法的描述 擴充巴科斯-瑙爾范式（EBNF）：<while語句> := while (<條件語句>) do <賦值語句> <條件語句> := <表達式><條件運算符> <表達式>

5、<表達式> := <表達式> + <表達式2> | <表達式> - <表達式2> | <表達式2> <表達式2>:=<表達式2> * <表達式3> |<表達式2> / <表達式3> | <表達式3><表達式3>:=(<表達式>) | <標識符>|<數字><賦值語句>:=<標識符>=<表達式>；根據以上寫出來的While循環語句的文法表示如下：1. S -> whi

6、le (A) do B2. A -> CDC3. D -> > | = | < | >= |<=4. C -> 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-> > | = | < | >= | <= 4. C->EG 5. G->+EG | -EG | 6. E->FH 7. H->*FH | / FH |

7、 8. F->(C) | i | n 9. B->i=C；2.1 屬性文法的描述(1)任一非終結符B都不是左遞歸的，否則會產生死循環。(2)對A的任意兩個右部i , j ,有：first(i)first(j)=， First(i)表i所能導出串的第一個符號的集合。顯然，每個i的first(i)是互不相同的，否則則無法判斷應執行哪個(i )。產生式 語義規則S->while (A) do B S.first:=newtemp; S.second:=newtemp;A.true:=newtemp;emit（A.false:=S.second;S1.second:=S.first;

8、 S.place:=(S.begin, :) | B.place |printf(S.true, :) |S1.place | printf(goto,S.begin) | printf(B.false, :) | 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:

9、=newtemp ;Emit(D.Place':=''<').D-> = D.place:=newtemp ;Emit(D.Place':=''=').D-> >= D.place:=newtemp ;Emit(D.Place':=''>=').D-> <= D.place:=newtemp ;Emit(D.Place':=''<=')C->EG C.Place:=newtemp;Em

10、it(C.Place':='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.Plac

11、e':=''*'F.Place H2.place)H-> / FHH.Place:=newtemp;Emit(H1.Place':=''+'F.Place H2.place)H->G.Place:=newtemp;Emit(H1.Place':=''+'E.Place H2.place)F->(C) F.Place:=C.PlaceB->i=C;p:=lookup()If p!=nil thenEmit(p':='C.PlaceElse

12、error)三 語法分析方法描述31 語法分析方法描述 遞歸下降法是一種比較簡單直觀，易于構造的語法分析方法。他要求文法滿足LL（1）文法，他的設計思想是對應文法中每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的單詞（或串），當某非終結符的產生式有多個候選時，能夠按LL（1）形式可唯一地確定選擇某個候選進行推導。它的優點是簡單直觀，易于構造，很多編譯系統所實現缺點是對文法要求很高，由于遞歸調用多，影響分析器的效率。遞歸下降程序是由一組子程序組成，每個子程序對應于一個非終結(S,A,B,C,D,E,F,G,H)。每個子程序處理相應句型中相對于此非終結符號的產生式。在定義文法時

13、，是遞歸定義的，所以這些子程序也是遞歸的。當一個子程序調用另一個子程序時，原子程序順序執行語句，即總是先執行被調用的子程序，然后再執行后繼的程序。程序中9個子程序，其中S 是開始符號，也是遞歸下降分析的入口，通過調用詞法分析器進行單詞分析，并通過word=()來得到當前所分析到的單詞，然后在遞歸語法分析中根據這個單詞分析下一步要執行的子程序。其中要注意的是，當子程序G()和H()中出現匹配的是空字符串時，不做單詞處理，該所取得的單詞，應該為下一個匹配產生做準備。32 遞歸下降法實現的原理設A是一個非終結符：A1 A2 An則寫 (A) Û if charfirst(1 ) then(

14、1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示調用處理符號串i的子程序。對A的任一右部i 設為： i = y1 y2 yn則定義( i) Û begin(y1);(y2);(yn) end其中yj可分為下列兩種情況（j=1,n):1) yjVT,則 ( yj) Û if char yj then ERROR else READ(char)2) yjVN,則(yj)表示調用關于yj的遞歸子程序。四中間代碼形式的描述及中間代碼序列的結構設計4.1四元式形式

15、中間代碼為四元式，按照要求，要輸出四元式一個四元式是一個帶有四個域的記錄結構，這四個域分別稱為oparg1arg2及result。域op包含一個代表運算符的內部碼。語句while a<b do a=a+b的四元式輸出:1 ( <, a , b , 3 ) 2 ( j , _ , _ ,6 ) 3 ( + , a , b , n ) 4 ( = , n , _ , a ) 5 ( j , _ , _ , 1) 6五 編譯系統的概要設計5.1全局程序的概要設計 遞歸下降分析技術就是通過對每個非終結符編寫一個子程序來實現它的操作，然后通過遞歸的調用來實現對輸入字符串的分析，這其中還包括對

16、輸入字符串的詞法分析。在詞法分析的時，得到的字符單詞要和關鍵字比較，看是否是關鍵字，根據比較結果進行返回相應的單詞類型。單詞類型主要包括界限符，關鍵字，常量，標識符，運算符等，每種符號都是一種類型。在語法分析程序中，根據詞法得到的結果，進行判斷是否是當前需要的單詞類型，如果不是就說明輸入字符串不能由該文法推導出來；如果是當前需要的類型，就相應得做該單詞類型分支程序。根據文法可以得到這個遞歸下降程序可以分析while語句，在文法的開始符號S開始進行遞歸調用，因此這個文法的遞歸中就要考慮到調用以及遞歸。在遞歸子程序中，在嵌套調用其他子程序時都是有一定條件的，當滿足這個條件的時候該程序可以按照滿足的

17、條件執行下去，當沒有滿足程序中的條件時就會顯示語法錯誤。5.2詞法分析詞法分析程序的任務是：從左至右逐個字符地對源程序進行掃描，產生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號的中間程序。詞法分析檢查的錯誤主要是挑出源程序中出現的非法符號。所謂非法符號是指不是程序設計語言中允許出現的符號，就像自然語句中的錯字。5.3遞歸下降翻譯器的設計對每個非終結符A構造一個函數過程，對A的每個繼承屬性設置一個形式參數，函數的返回值為A的綜合屬性，A對應的函數過程中，為出現在A的產生式中的每一個文法符號的每一個屬性都設置一個局部變量。非終結符A對應的函數過程中，根據當前的輸入符號決定使用哪個產生式候

18、選。每個產生式對應的程序代碼中，按照從左到右的次序，對于單詞符號，非3：終結符和語義動作分別做以下工作。1. 對于帶有綜合屬性x的終結符X，把x的值存入為X，x設置的變量中。然后產生一個匹配X的調用，并繼續讀入一個輸入符號。2. 對于每個非終結符號B，產生一個右邊帶有函數調用的賦值語句c=B(b1,b2,，bk)3. 對于語義動作，把動作的代碼抄進分析器中，用代表屬性的變量來代替對應屬性的每一次引用。5.4語法制導翻譯在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯。屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣

19、，棧符號就由文法符號及存放該符號屬性的域所組成。由于屬性類型不同，屬性域存放的內容就要根據屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向屬性值的指針。對于綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧時為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。六 詳細的算法描述S()àW()àEàF()àD()àG()àR()àT()方法和變量的定義#define

20、MAX 100int m = 0, sum = 0;/sum用于計算運算符的個數 m用于標記輸入表達式中字符的個數char JG = 'A'char strMAX; /用于存賦值表達式int token = 0; /左括號的標志int sign = 0;char whi5 = 'w', 'h', 'i', 'l', 'e' ; /檢查關鍵字whilestring getsentence(); /獲取表達式void anlyse(string temp); /while語句遞歸分析bool Judge

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

22、h = new char5;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 << "

23、while關鍵字輸入錯誤！" << endl;break;return flag;做E（）：void Do_E(string temp) /E -> aFbif (tempsign >= 'a' && tempsign <= 'z') | (tempsign > 'A' && tempsign <= 'Z')cout << "(" ;sign+;Do_F(temp);elsecout << "（

24、）中含有非法字符！" << endl;做F（） F -> < | = | > | <= | >=void Do_F(string temp) /F -> < | = | > | <= | >=int f_sign = sign;if (tempf_sign = '<' | tempf_sign = '=' | tempf_sign = '>')if (tempf_sign + 1 = '=')cout << tempf_sig

25、n + 1<<","if (tempf_sign + 2 >= 'a' && tempf_sign + 2 <= 'z') | (tempf_sign + 2 > 'A' && tempf_sign + 2 <= 'Z')cout << tempf_sign << tempf_sign + 1 << "," <<tempf_sign - 1 << ",&q

26、uot; << tempf_sign + 2 << ",sign)" << endl;sign = sign + 2;sign+;if (tempsign = ')' && tempsign+1 = '')sign = sign + 2;Do_G(temp);else if (tempf_sign + 1 >= 'a' && tempf_sign + 1 <= 'z') | (tempf_sign + 1 > 'A&#

27、39; && tempf_sign + 1 <= 'Z')cout << tempf_sign << "," << tempf_sign - 1 << "," << tempf_sign + 1 << ",sign)" << endl;sign+;sign+;if (tempsign = ')' && tempsign + 1 = '' )sign = sign +

28、2;Do_G(temp);elsecout << "()中存在符號錯誤" << endl;做Do_G G-> 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 (tempsign != '' && sign < len)ch = tempsign;strm+ = ch;if (ch = '=' |

29、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 <&

30、lt; endl;siyuanshi();if (tempsign != '') cout << "前缺少 “;”" << endl;if (temptemp.size()-1 != '') cout << "缺少“”" << endl;對賦值語句進行四元式輸出：void change(int e)int f = e + 2;char ch = strf;if (ch >= 'A'&&ch <= 'Z')for (i

31、nt l = 0; l<m + 10; l+)if (strl = ch)strl = JG;if (stre >= 'A'&&stre <= 'Z')for (int i = 0; i<m; i+)if (stri = stre)stri = JG;void chengchuchuli(int i, int m)i+;for (; i <= m - 1; i+)/處理乘除運算if (stri = '*' | stri = '/')cout << "("

32、 << stri << " " << stri - 1 << " " << stri + 1 << " " << JG << ")" << endl;change(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+)/

33、處理加減運算if (strj = '+' | strj = '-')cout << "(" << strj << " " << strj - 1 << " " << strj + 1 << " " << JG << ")" << endl;change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG

34、= (char)(int)JG+;void siyuanshi()for (int i = 0; i <= m - 1; i+)/處理乘除運算if (stri = '*' | stri = '/')cout << "(" << stri << " " << stri - 1 << " " << stri + 1 << " " << JG << ")"

35、<< 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 = (