武漢理工大學(xué) DO-WHILE語(yǔ)句的翻譯分析程序設(shè)計(jì) ———遞歸下降法、輸出四元式

1、武漢理工大學(xué)編譯原理課程設(shè)計(jì)說(shuō)明書(shū)DO-WHILE語(yǔ)句的翻譯分析程序設(shè)計(jì) 遞歸下降法、輸出四元式1問(wèn)題描述1.1問(wèn)題描述 設(shè)計(jì)一個(gè)DO-WHILE循環(huán)語(yǔ)句的詞法語(yǔ)法及語(yǔ)義分析程序，語(yǔ)法分析選擇遞歸下降法，采用用語(yǔ)法制導(dǎo)翻譯輸出中間代碼四元式。1.2主要任務(wù)通過(guò)設(shè)計(jì)、編制、調(diào)試一個(gè)DO-WHILE循環(huán)語(yǔ)句的語(yǔ)法及語(yǔ)義分析程序，加深對(duì)語(yǔ)法及語(yǔ)義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。首先寫(xiě)出一個(gè)能識(shí)別DO-WHILE循環(huán)語(yǔ)句的文法，通過(guò)消除左遞歸使它符合LL(1)即遞歸下降法的要求，然后按照這個(gè)文法編寫(xiě)一個(gè)集詞法分析，語(yǔ)法分析和語(yǔ)義分析為一體的程序，該程序首先可以檢查輸入語(yǔ)句

2、是否符合詞法要求，若符合則繼續(xù)識(shí)別輸入的語(yǔ)句是否符合DO-WHILE語(yǔ)句的文法，若符合則進(jìn)行語(yǔ)義分析，輸出用四地址代碼表示的中間代碼。1.3測(cè)試數(shù)據(jù)編寫(xiě)好源代碼后，進(jìn)行調(diào)試，根據(jù)程序要求進(jìn)輸入一小段程序，進(jìn)行詞法、語(yǔ)法的分析，給出分析結(jié)果。2文法及屬性文法的描述2.1文法的描述用擴(kuò)充巴科斯-瑙爾范式（EBNF）給出的while循環(huán)語(yǔ)句的文法描述，如下：<while語(yǔ)句> :=do (<條件語(yǔ)句>) while <賦值語(yǔ)句> <條件語(yǔ)句> := <表達(dá)式><條件運(yùn)算符> <表達(dá)式><條件運(yùn)算符> :=

3、 > | < | = | >= | <=<表達(dá)式> := <表達(dá)式> + <表達(dá)式2> | <表達(dá)式> - <表達(dá)式2> | <表達(dá)式2> <表達(dá)式2>:=<表達(dá)式2> * <表達(dá)式3> |<表達(dá)式2> / <表達(dá)式3> | <表達(dá)式3><表達(dá)式3>:=(<表達(dá)式>) | <標(biāo)識(shí)符>|<數(shù)字><賦值語(yǔ)句>:=<標(biāo)識(shí)符>=<表達(dá)式>； 2.2 DO

4、-while循環(huán)語(yǔ)句文法的描述產(chǎn)生式為S-> do E while A，為便于語(yǔ)法制導(dǎo)翻譯將其改寫(xiě)如下： 文法G(s)如下： S->DGWE （意思是do G while E） G->c=R R->dTe|d T->+|-|*|/ E->aFb F-> >|=|<2.3 DO-WHILE循環(huán)語(yǔ)句的屬性文法產(chǎn)生式語(yǔ)義規(guī)則Sdo E while A S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin:E。codegen(E

5、.true:) S1.codegen(goto S.begin)3.語(yǔ)法分析方法及中間代碼形式的描述 3.1語(yǔ)法分析方法 遞歸下降程序是由一組子程序組成，每個(gè)子程序?qū)?yīng)于一個(gè)非終結(jié)(S,A,B,C,D,E,F,G,H)。每個(gè)子程序處理相應(yīng)句型中相對(duì)于此非終結(jié)符號(hào)的產(chǎn)生式。在定義文法時(shí)，是遞歸定義的，所以這些子程序也是遞歸的。當(dāng)一個(gè)子程序調(diào)用另一個(gè)子程序時(shí)，原子程序順序執(zhí)行語(yǔ)句，即總是先執(zhí)行被調(diào)用的子程序，然后再執(zhí)行后繼的程序。程序中9個(gè)子程序，其中S 是開(kāi)始符號(hào)，也是遞歸下降分析的入口，通過(guò)調(diào)用詞法分析器進(jìn)行單詞分析，并通過(guò)word=l.Yufa_Queue.front()來(lái)得到當(dāng)前所分析到的

6、單詞，然后在遞歸語(yǔ)法分析中根據(jù)這個(gè)單詞分析下一步要執(zhí)行的子程序。其中要注意的是，當(dāng)子程序G()和H()中出現(xiàn)匹配的是空字符串時(shí)，不做單詞處理，該所取得的單詞，應(yīng)該為下一個(gè)匹配產(chǎn)生做準(zhǔn)備。 它的優(yōu)點(diǎn)是簡(jiǎn)單直觀，易于構(gòu)造，很多編譯系統(tǒng)所實(shí)現(xiàn)。缺點(diǎn)是對(duì)文法要求很高，由于遞歸調(diào)用多，影響分析器的效率。 其文法可以表示為： ETE+T TFT*F Fi（E） 可以用語(yǔ)法圖來(lái)表示語(yǔ)言的文法，如圖：+TTE*FFTE)(iF3.2中間代碼形式描述 中間代碼采用四元式輸出，一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱(chēng)為oparg1arg2及result。域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼。語(yǔ)句do c=

7、a+b while a<b的四元式輸出形式如下： 100 ( + , a , b , T ) 101 ( = , T , - , c ) 102 ( j<, a , b , 100 ) 4簡(jiǎn)要的分析與概要設(shè)計(jì)4.1全局程序概要設(shè)計(jì) 遞歸下降分析技術(shù)就是通過(guò)對(duì)每個(gè)非終結(jié)符編寫(xiě)一個(gè)子程序來(lái)實(shí)現(xiàn)它的操作，然后通過(guò)遞歸的調(diào)用來(lái)實(shí)現(xiàn)對(duì)輸入字符串的分析，這其中還包括對(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ù)詞法得到的

8、結(jié)果，進(jìn)行判斷是否是當(dāng)前需要的單詞類(lèi)型，如果不是就說(shuō)明輸入字符串不能由該文法推導(dǎo)出來(lái)；如果是當(dāng)前需要的類(lèi)型，就相應(yīng)得做該單詞類(lèi)型分支程序。 根據(jù)文法可以得到這個(gè)遞歸下降程序可以分析while語(yǔ)句，在文法的開(kāi)始符號(hào)S開(kāi)始進(jìn)行遞歸調(diào)用，因此這個(gè)文法的遞歸中就要考慮到調(diào)用以及遞歸。在遞歸子程序中，在嵌套調(diào)用其他子程序時(shí)都是有一定條件的，當(dāng)滿足這個(gè)條件的時(shí)候該程序可以按照滿足的條件執(zhí)行下去，當(dāng)沒(méi)有滿足程序中的條件時(shí)就會(huì)顯示語(yǔ)法錯(cuò)誤。 4.2詞法分析 詞法分析程序的任務(wù)是：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)的單詞符號(hào)，把作為字符串的源程序改造成為單詞符號(hào)的中間程序。詞法分析檢查的錯(cuò)誤主要是挑

9、出源程序中出現(xiàn)的非法符號(hào)。所謂非法符號(hào)是指不是程序設(shè)計(jì)語(yǔ)言中允許出現(xiàn)的符號(hào)，就像自然語(yǔ)句中的錯(cuò)字。 4.3遞歸下降翻譯器的設(shè)計(jì)1. 對(duì)每個(gè)非終結(jié)符A構(gòu)造一個(gè)函數(shù)過(guò)程，對(duì)A的每個(gè)繼承屬性設(shè)置一個(gè)形式參數(shù)，函數(shù)的返回值為A的綜合屬性，A對(duì)應(yīng)的函數(shù)過(guò)程中，為出現(xiàn)在A的產(chǎn)生式中的每一個(gè)文法符號(hào)的每一個(gè)屬性都設(shè)置一個(gè)局部變量。2. 非終結(jié)符A對(duì)應(yīng)的函數(shù)過(guò)程中，根據(jù)當(dāng)前的輸入符號(hào)決定使用哪個(gè)產(chǎn)生式候選。3. 每個(gè)產(chǎn)生式對(duì)應(yīng)的程序代碼中，按照從左到右的次序，對(duì)于單詞符號(hào)，非終結(jié)符和語(yǔ)義動(dòng)作分別做以下工作。（1）對(duì)于帶有綜合屬性x的終結(jié)符X，把x的值存入為X，x設(shè)置的變量中。然后產(chǎn)生一個(gè)匹配X的調(diào)用，并繼續(xù)讀

10、入一個(gè)輸入符號(hào)。（2）對(duì)于每個(gè)非終結(jié)符號(hào)B，產(chǎn)生一個(gè)右邊帶有函數(shù)調(diào)用的賦值語(yǔ)句c=B(b1,b2,，bk)（3）對(duì)于語(yǔ)義動(dòng)作，把動(dòng)作的代碼抄進(jìn)分析器中，用代表屬性的變量來(lái)代替對(duì)應(yīng)屬性的每一次引用。 4.4語(yǔ)法制導(dǎo)翻譯在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（或語(yǔ)義規(guī)則描述的語(yǔ)義動(dòng)作）進(jìn)行翻譯。屬性文法的每個(gè)符號(hào)有屬性，所以每個(gè)符號(hào)入棧時(shí)，必須連屬性一起入棧，這樣，棧符號(hào)就由文法符號(hào)及存放該符號(hào)屬性的域所組成。由于屬性類(lèi)型不同，屬性域存放的內(nèi)容就要根據(jù)屬性的類(lèi)型來(lái)定。有的可能直接存放屬性值，也有的存放的是指向?qū)傩灾档闹羔?。?duì)于綜合屬性，其屬性域不存放其屬性值，而是存

11、放一個(gè)指針，指向存貯該屬性值的單元。對(duì)于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛?cè)霔r(shí)為空，但是在該棧符號(hào)變成棧頂符號(hào)之前的某一時(shí)刻，它們必須接受相應(yīng)的屬性值，即在成為棧頂時(shí)，繼承屬性的屬性域必須有值。5測(cè)試方法和測(cè)試結(jié)果5.1測(cè)試方法 編寫(xiě)好源程序，連接運(yùn)行無(wú)誤后，用幾個(gè)簡(jiǎn)單的while語(yǔ)句檢測(cè)其正確性，如：輸入do-while語(yǔ)句：Wa<bDa=a+b#，看其輸出結(jié)果是否與我們所預(yù)期的結(jié)果一致，如果不一致，則需對(duì)源程序進(jìn)行檢查修正，我們可以用逐步調(diào)試的方法來(lái)對(duì)源程序進(jìn)行跟蹤分析，找出出錯(cuò)的地方和原因，在對(duì)其進(jìn)行修改，重新調(diào)試運(yùn)行，直到輸出正確的結(jié)果為止。若輸出結(jié)果正確，

12、還要多用幾個(gè)while語(yǔ)句對(duì)其進(jìn)行檢測(cè)，直到所有輸出結(jié)果正確。5.2測(cè)試結(jié)果測(cè)試結(jié)果如下：6經(jīng)驗(yàn)與體會(huì)在做本次實(shí)驗(yàn)之前我對(duì)LL(1)文法的構(gòu)成,遞歸下降原理不是很了解,在查閱了相關(guān)資料后,對(duì)此有了深入了解.在整個(gè)設(shè)計(jì)過(guò)程中,將詞法分析做為一個(gè)單獨(dú)的模塊,它可以被任何語(yǔ)法分析調(diào)用,提高獨(dú)立性.并且在編程之前就已經(jīng)將程序的概要設(shè)計(jì)都做出來(lái)了，所以在編寫(xiě)程序的時(shí)候相對(duì)比較容易。詞法分析，語(yǔ)法分析都是很容易的，只要理解了分析方法的實(shí)現(xiàn)原理，編寫(xiě)程序判斷輸入字符串是否滿足給定的文法是比較簡(jiǎn)單的。本次的設(shè)計(jì)的不足主要體現(xiàn)在以下幾個(gè)方面，首先，因?yàn)榍皫状蔚膶?shí)驗(yàn)都沒(méi)有把詞法分析器編出來(lái)，因此程序中我沒(méi)有采用詞

13、法分析器，只能夠?qū)ξㄒ坏腄a=a+bWa<b#進(jìn)行識(shí)別，同樣后面的語(yǔ)義分析也只能對(duì)這個(gè)起作用；再次，由于我所設(shè)計(jì)的棧中只能一個(gè)字符一個(gè)字符的存放，因此只能用D W分別表示do while；而且我對(duì)語(yǔ)法制導(dǎo)翻譯這一塊很不熟悉，因此我始終不能用程序?qū)崿F(xiàn)語(yǔ)法制導(dǎo)翻譯輸出四元式，于是根據(jù)自己的理解，直接把四元式寫(xiě)了出來(lái)。在這次課程設(shè)計(jì)的過(guò)程中，我也遇到了很多難題。在種種的困難中，我明白了在編寫(xiě)程序時(shí)要有耐心。如果你沒(méi)有耐心，即使再好的思路也不會(huì)得到很好的表達(dá)，特別是在調(diào)試的過(guò)程中，對(duì)于各種各樣的錯(cuò)誤，要特別的有耐心去自習(xí)分析原因，特別是一些基本的語(yǔ)法錯(cuò)誤，不能一看到錯(cuò)誤很多就亂了陣腳，更不能輕易

14、的放棄，半途而廢。 通過(guò)此次課程設(shè)計(jì)，再次對(duì)編譯原理的基礎(chǔ)知識(shí)和一些實(shí)際操作只是有了一定的了解，對(duì)高級(jí)語(yǔ)言在計(jì)算機(jī)上進(jìn)行編譯分析的過(guò)程有了一定的了解。7附錄源代碼： /*文法G(s) s->DGWE G->c=R R->dTe|d T->+|-|*|/ E->aFb F-> >|=|< */#include <stdio.h> #include<dos.h> #include<stdlib.h> #include<string.h>char a50,g5050;char ch;int n1,i1=0

15、,i2=0;int total=0;void S(); void D(); void G(); void W(); void E(); void R(); void T(); void F(); void main() int p,j=0; printf("請(qǐng)輸入do-while語(yǔ)句(D代表do,W代表while),并以#結(jié)束:n");do scanf("%c",&ch); aj=ch; j+; while(ch!='#'); n1=j;ch=a0;S(); printf("n")； if (ch='#

16、') printf("輸出四元式為：n"); p=0; for(;p<i2;p+) printf("10%d %sn",p,gp); /*輸出推導(dǎo)式*/ else printf("errorn"); printf("press any key to continue.n"); getchar(); getchar(); return; printf("n"); printf("press any key to continue.n"); getchar(); g

17、etchar();/*出錯(cuò)情況分析*/void S() printf("%dtS->DGWEn",total);total+; D(); G(); void D() if(ch!='D') printf("有非法字符%c請(qǐng)按回車(chē)返回!",ch); getchar(); getchar(); exit(1); ch=a+i1; void G() int i=i1+1; if(ch!='c'&&ai!='=') printf("有非法字符%c %c請(qǐng)按回車(chē)返回!",ch

18、,ai); getchar(); getchar(); exit(1); printf("%dtG->c=Rn",total);total+; R();void R() int i; i=i1+1;i1=i1+2; ch=ai1; if(ai!='='&&ch!='d') printf("有非法字符%c %c請(qǐng)按回車(chē)返回!",ai,ch); getchar(); getchar(); exit(1); else if(ai1+1='+')|(ai1+1='-')|(ai

19、1+1='*')|(ai1+1='/') printf("%dtR->dTen",total);total+; i2=3; T(); else printf("%dtR->dn",total);total+; i2=2; strcpy(g0,"(=,c,d,_)"); W(); E(); void T() ch=a+i1; switch(ch) case '+': printf("%dtT->+n",total);total+;strcpy(g0,&

20、quot;(+,d,e,T)");strcpy(g1,"(=,c,T,_)");break; case '-': printf("%dtT->-n",total);total+; strcpy(g0,"(-,d,e,T)");strcpy(g1,"(=,c,T,_)");break; case '*': printf("%dtT->*n",total);total+; strcpy(g0,"(*,d,e,T)");strc

21、py(g1,"(=,c,T,_)");break; default: printf("%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請(qǐng)按回車(chē)返回!",ch); getchar(); getchar(); exit(1); void E() ch=a+i1; if(ch!='a') printf("有非法字符%c %c請(qǐng)按回車(chē)返回!",ch); getchar(); getchar(); exit(1); printf("%dtE->aFbn",total);total+; F();void F() int i;ch=a+i1;i=i1+1;if(ai!='b') printf("有非法字符%c請(qǐng)按回車(chē)返回!",ai); getchar(); getchar(); e