1、武漢理工大學編譯原理課程設計說明書DO-WHIL語句的翻譯分析程序設計遞歸下降法、輸出四元式1問題描述i.i問題描述設計一個DO-WHILE循環語句的詞法、語法及語義分析程序，語法分析選擇遞歸下降法，采用用語法制導翻譯輸出中間代碼四元式。1.2主要任務通過設計、編制、調試一個 DO-WHILE循環語句的語法及語義分析程序，加深對語法及 語義分析原理的理解，并實現詞法分析程序對單詞序列的詞法檢查和分析。首先寫出一個能識別DO-WHILE循環語句的文法，通過消除左遞歸使它符合LL（1）即遞歸 下降法的要求，然后按照這個文法編寫一個集詞法分析，語法分析和語義分析為一體的程序， 該程序首先可以檢查輸入

2、語句是否符合詞法要求，若符合則繼續識別輸入的語句是否符合 DO-WHILE語句的文法，若符合則進行語義分析，輸出用四地址代碼表示的中間代碼。1.3測試數據編寫好源代碼后，進行調試，根據程序要求進輸入一小段程序，進行詞法、語法的分析， 給出分析結果。2文法及屬性文法的描述2.1文法的描述用擴充巴科斯-瑙爾范式（EBNF）給出的while循環語句的文法描述，如下：vwhile語句 :=do （條件語句） while 賦值語句 條件語句 := 表達式 條件運算符 表達式條件運算符 := | | = | = | =表達式 := 表達式 + 表達式2 | 表達式 - 表達式2 | 表達式2表達式2:=表

3、達式2 * 表達式3 |表達式2 / 表達式3 | 表達式3表達式3:=（表達式）| 標識符|數字<賦值語句 >:=< 標識符 >=<表達式>2.2 DO-while循環語句文法的描述產生式為S-> do E while A，為便于語法制導翻譯將其改寫如下: 文法G(s)如下：S->DGWE(意思是 do G while E)G->c=RR->dTe|dT->+|-|*|/E->aFbF-> >|=|<2.3 DO-WHILE循環語句的屬性文法產生式語義規則St do E while AS.begi n:

4、=n ewlabel;E.true:=newlabel;E.false:=S .n ext;S1. next:=S.beg in;S.code:=gen(S.beginII E。： 'ode IIge n(E.true'll： S1)ode IIgen( goto S.begin)3.語法分析方法及中間代碼形式的描述3.1語法分析方法遞歸下降程序是由一組子程序組成，每個子程序對應于一個非終結 (S,A,B,C,D,E,F,GH)。每個子程序處理相應句型中相對于此非終結符號的產生式。在定義文法 時，是遞歸定義的，所以這些子程序也是遞歸的。當一個子程序調用另一個子程序時，原子程 序

5、順序執行語句，即總是先執行被調用的子程序，然后再執行后繼的程序。程序中9個子程序， 其中S是開始符號，也是遞歸下降分析的入口，通過調用詞法分析器進行單詞分析，并通過 word=I.Yufa_Queue.fro nt()來得到當前所分析到的單詞，然后在遞歸語法分析中根據這個單詞分 析下一步要執行的子程序。其中要注意的是，當子程序G()和H()中出現匹配的是空字符串時，不做單詞處理，該所取得的單詞，應該為下一個匹配產生做準備。它的優點是簡單直觀，易于構造，很多編譯系統所實現。缺點是對文法要求很高，由于 遞歸調用多，影響分析器的效率。其文法可以表示為：E T | E+TT F | T*FF i |

6、( E)可以用語法圖來表示語言的文法，如圖：3.2中間代碼形式描述中間代碼采用四元式輸出，一個四元式是一個帶有四個域的記錄結構，這四個域分別稱為op、arg1、arg2及result。域op包含一個代表運算符的內部碼。語句do c=a+b while a<b的四元式輸出形式如下：100 ( + , a , b , T )101 ( = , T , - , c )102 ( j<, a , b , 100 )4 簡要的分析與概要設計4.1全局程序概要設計遞歸下降分析技術就是通過對每個非終結符編寫一個子程序來實現它的操作，然后通過遞歸的調用來實現對輸入字符串的分析， 這其中還包括對輸入

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

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

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

10、個符號有屬性，所以每個符號入棧時， 必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由于屬性類 型不同，屬性域存放的內容就要根據屬性的類型來定。有的可能直接存放屬性值，也有的存放 的是指向屬性值的指針。對于綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向 存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧 時為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成 為棧頂時，繼承屬性的屬性域必須有值。5測試方法和測試結果5.1測試方法編寫好源程序，連接運行無誤后，用幾個簡單的while語句檢測其正確性，如：

11、輸入do-while語句：Wa<bDa=a+b#，看其輸出結果是否與我們所預期的結果一致，如果不一致,則需對源程序進行檢查修正，我們可以用逐步調試的方法來對源程序進行跟蹤分析，找出出錯的地方和原因，在對其進行修改，重新調試運行，直到輸出正確的結果為止。若輸出 結果正確，還要多用幾個 while語句對其進行檢測，直到所有輸出結果正確。5.2測試結果測試結果如下:C：U?ersAd rm ini strato rkto pdo_wh il eDe bu gdoi le. ex e6經驗與體會在做本次實驗之前我對 LL(1)文法的構成，遞歸下降原理不是很了解，在查閱了相關資料 后,對此有了深入

12、了解在整個設計過程中，將詞法分析做為一個單獨的模塊，它可以被任何語 法分析調用，提高獨立性并且在編程之前就已經將程序的概要設計都做出來了， 所以在編寫程 序的時候相對比較容易。詞法分析，語法分析都是很容易的，只要理解了分析方法的實現原理，編寫程序判斷輸入字符串是否滿足給定的文法是比較簡單的。本次的設計的不足主要體現在以下幾個方面，首先，因為前幾次的實驗都沒有把詞法分析器編出來，因此程序中我沒有采用詞法分析器，只能夠對唯一的Da=a+bWa<b#進行識別，同樣后面的語義分析也只能對這個起作用；再次，由于我所設計的棧中只能一個字符一個字符的存 放，因此只能用D W分別表示do while;而

13、且我對語法制導翻譯這一塊很不熟悉，因此我始終 不能用程序實現語法制導翻譯輸出四元式，于是根據自己的理解，直接把四元式寫了出來。在這次課程設計的過程中，我也遇到了很多難題。在種種的困難中，我明白了在編寫程序時要有耐心。如果你沒有耐心，即使再好的思路也不會得到很好的表達，特別是在調試的過程 中，對于各種各樣的錯誤，要特別的有耐心去自習分析原因，特別是一些基本的語法錯誤，不 能一看到錯誤很多就亂了陣腳，更不能輕易的放棄，半途而廢。通過此次課程設計，再次對編譯原理的基礎知識和一些實際操作只是有了一定的了解，對高級語言在計算機上進行編譯分析的過程有了一定的了解。7附錄源代碼：/*文法G(s)s->

14、DGWEG->c=RR->dTe|dT->+|-|*|/E->aFbF-> >|=|<*/#in clude <stdio.h>#in clude<dos.h>#in clude<stdlib.h>#i ncludevstri ng.h> char a50,g5050;char ch;int n1,i1=0,i2=0;int total=0;void S();void D();void G();void W();void E();void R();void T();void F();void mai n()in

15、 t p,j=0;printf("請輸入do-while語句(D代表do, W代表while),并以#結束:n");dosea nf("%c",&ch);aj=ch;j+;while(ch!='#');n1=j;ch=a0;S();printf("n")；if (ch='#')printf（"輸出四元式為：n"）;p=o；for(;p<i2;p+)/*輸出推導式*/printf("10%d %sn",p,gp);else prin tf("

16、error n");printf("press any key to continue.n");getchar();getchar();return;prin tf("n");prin tf("press any key to continu e.n");getchar();getchar();/*出錯情況分析*/void S()prin tf("%dtS->DGWEn",total);total+;D();G();void D()if(ch!='D') printf("有

17、非法字符c請按回車返回! ",ch);getchar();getchar();exit(1);ch=a+i1;void G() int i=i1+1;if(ch!='c'&&ai!='=')printf("有非法字符%c %c請按回車返回! ",ch,ai);getchar();getchar();exit(1);prin tf("%dtG->c=Rn",total);total+;R();void R()int i;i=i1+1;i1=i1+2;ch=ai1;if(ai!='=&#

18、39;&&ch!='d')printf("有非法字符%c %c請按回車返回! ",ai,ch);getchar();getchar();exit(1);elseif(ai1+1='+')|(ai1+1='-')|(ai1+1='*')|(ai1+1='/')prin tf("%dtR->dTen",total);total+;i2=3;T();elseprin tf("%dtR->dn",total);total+;i2=2;s

19、trcpy(g0,"(=,c,d,_)");W();E();void T()ch=a+i1;switch(ch)case '+':prin tf("%dtT->+n",total);total+;strcpy(gO,"(+,d,e,T)");strcpy(g1,"(=,c,T,_)");break;case '-':prin tf("%dtT->-n",total);total+; strcpy(gO,"(-,d,e,T)"); s

20、trcpy(g1,"(=,c,T,_)"); break;case '*':prin tf("%dtT->*n",total);total+;strcpy(g0,"(*,d,e,T)");strcpy(g1,"(=,c,T,_)");break;default:prin tf("%dtT->/n",total);total+; strcpy(g0,"(/,d,e,T)"); strcpy(g1,"(=,c,T,_)"); break;W();E();void W()+i1;ch=a+i1;if(ch!=W)printf("有非法字符c請按回車返回! ",ch);getchar();getchar();exit(1);void E()ch=a+i1;if(ch!='a')printf(&quo