WHILE循環(huán)語句的翻譯程序設計

1、WHILE循環(huán)語句的翻譯程序設計（遞歸下降法、輸出三地址表示）1 系統(tǒng)描述按照課程設計的要求，寫一個能識別while循環(huán)語句的文法，通過一定的變換使它符合遞歸下降法的要求，然后按照這個文法編寫一個程序，該程序能識別輸入的語句是否符合while語句的文法，或者能不能通過文法的開始符號推導出該語句。該程序應該包括詞法分析器，能對輸入的語句進行詞法分析，然后再對結果進行語法分析。詞法分析器應能識別關鍵字，標示符，常量，操作符等。該程序的語法分析器能對輸入的語法進行分析，判斷輸入語句能否滿足while循環(huán)語句的文法。通過遞歸下降的方法對語句進行分析，看能否通過開始符號推導出來。該程序的語義分析器就是對

2、分析結果進行輸出，要求輸出結果是三地址形式的。2 文法及屬性文法的描述21文法描述 := while () ( | ) := (|） (|) := (|) := | | = := （) := =( | ) ( | ) := + | - | * | / := = | 22遞歸文法while語句文法：S - while (B) S | i=EB - E relop Erelop - E - E+E | E-E | E*E | E/E | (E) | i | n在編寫程序的時候用到的是遞歸下降法，而遞歸下降法對文法的要求是不能包含左遞歸，對上述的文法進行消除左遞歸之后，得到如下的遞歸文法：S - w

3、hile (B) S | i=EB - E relop Erelop - E - (E)F | iF | nFF - +EF | -EF | *EF | /EF | 23屬性文法的描述產生式屬性文法S - while (B) S1S.begin:=newlabel;S.next:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin, :) | B.code |gen(S.true, :) | S1.code | gen(goto,S.begin) | gen(B.false, :) | g

4、en(goto Lnext);B - E1 relop E2B.place:=newlabel;B.code:=E1.code | relop.code |E2.code |gen(B.place := , E1.place , relop. place , E2.place);relop - relop.place:=newlabel;relop.code:=gen();E - (E1)FE.place:=newlabel;E.code:=E1.code | F.code |gen(E.place := ,(, E1.place , ), F.place);E - iFE.palce:=ne

5、wlabel;E.code:=i.code | F.code | gen(E.palce := ,i.place , F.place);E - nFE.place:=newlabel;E.code:=n.code | F.code | gen(E.place := , n.place , F.place);F - +EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= + , E.place , F1.place);F - -EF1F.place:=newlabel;F.code:=E.code | F1.code | ge

6、n(F.place:= - , E.place , F1.place);F - *EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= * , E.place , F1.place);F - /EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= / , E.place , F1.place);F - F.place:=newlabel;F.code:=gen(F.code:= );圖1 屬性文法3 語法分析方法描述按照遞歸下降分析技術，遞歸下降識別程序是

7、由一組子程序組成，每個子程序對應于一個非終結符號。該子程序處理相應句型中相對于此非終結符號的產生式。在定義文法時，是遞歸定義的，所以這些子程序也是遞歸的。當一個子程序調用另一個子程序時，總是先執(zhí)行被調用的子程序，然后再執(zhí)行后繼的程序。在本程序中，首先要做的就是將設計的文法根據(jù)遞歸下降分析技術對文法的要求改為非左遞歸的文法。程序中5個子程序，其中S 是開始符號，也是遞歸下降分析的入口，通過調用int Getsymbol()對輸入的字符串進行單詞分析，并返回當前所分析到的單詞，然后在遞歸語法分析中根據(jù)這個單詞分析下一步要執(zhí)行的子程序。4 中間代碼形式的描述41三地址代碼在本程序中用到了三地址語句的

8、輸出包括以下的種類：賦值語句：x:= y op z復制語句：x:= y條件轉移語句：if x relop y goto L 例如，本程序中語句while (B) S ,可以輸出三地址代碼為：if B goto L else goto Lnext；而E - (E)F可以輸出三地址代碼為：E1:= (E2) F。42本程序中的三地址代碼 S - while (B) SL0:=if (B) goto L1 else goto LnextS - i=EL:= i=EB - E relop EB:= E1 relop E2relop - relop:= =relop:= =relop - relop:=

9、 E - (E)FE1:= (E2) FE - iFE:= I FE - nFE:= n FF - +EFF1:= +E F2F - -EFF1:= -E F2F - *EFF1:= *E F2F - /EFF1:= /E F2F -F:= 圖2 三地址代碼5 概要設計51簡要分析遞歸下降分析技術就是通過對每個非終結符編寫一個子程序來實現(xiàn)它的操作，然后通過遞歸的調用來實現(xiàn)對輸入字符串的分析，這其中還包括對輸入字符串的詞法分析。在詞法分析的時，得到的字符單詞要和關鍵字比較，看是否是關鍵字，根據(jù)比較結果進行返回相應的單詞類型。單詞類型主要包括變量，關鍵字，常量，各種符號等，每種符號都是一種類型。在

10、語法分析程序中，根據(jù)詞法得到的結果，進行判斷是否是當前需要的單詞類型，如果不是就說明輸入字符串不能由該文法推導出來；如果是當前需要的類型，就相應得做該單詞類型分支程序。根據(jù)文法可以得到這個遞歸下降程序可以分析包含有while嵌套的語句，在文法的開始符號S中就嵌套了S本身，因此這個文法的遞歸中就要考慮到while的自身嵌套。在遞歸子程序中，在嵌套調用其他子程序時都是有一定條件的，當滿足這個條件的時候該程序可以按照滿足的條件執(zhí)行下去，當沒有滿足程序中的條件時就會報錯。52程序的概要設計在本程序中，Getsymbol()子程序就是對當前輸入的字符串進行詞法分析，包括對變量，常量，關鍵字，各種符號的分

11、析。主程序main()主要就是進行各種變量的初始化，調用遞歸分析程序的入口子程序。子程序間的嵌套關系如下：void main() S(); void Getsymbol() void ERROR() void S() re=Getsymbol(); if(re=while(關鍵字) B(); S();else(re=i(變量) re=Getsymbol(); if(re= =) E(); void B() E(); relop(); E();void E() re=Getsymbol();if(re= ( ) E();re=Getsymbol();if(re=) F();else if(re=

12、i) F();else if(re=n) F();void F() re=Getsymbol();if(re=+) E(); F();else if(re=-) E(); F();else if(re=*) E(); F();else if(re=/) E(); F();6 詳細的算法描述（流程圖或偽代碼）初始化各變量打開文件調用S()子程序關閉文件61main()主函數(shù)的算法描述圖3 mian()流程圖主程序執(zhí)行時首先會測試input.txt文件是否存在，因為程序就是通過該文件得到需要進行遞歸下降分析方法分析的輸入符號串；然后建立output.txt文件，問以后的輸出結果做基礎；接著調用遞歸

13、下降分析法的入口程序S()來開始對文件中的輸入字符串進行詞法，語法和語義分析；最后關閉文件結束程序。62Getsymbol()子程序的算法描述Int Getsymbol()sym=fgetc(intput); /取當前文件指針指向的字符While(sym不為空) if(sym是a-z的字符)將該字符保存在token1數(shù)組中；繼續(xù)取下一個是a-z的字符保存在數(shù)組中；當sym不是字符時，則判斷該數(shù)組中的符號串是不是關鍵字，是就返回16（while的機內碼）；不是就返回13（變量的機內碼）；Else if（sym是0-9之間的數(shù)字）將該數(shù)字保存在token2數(shù)組中；繼續(xù)取下一為0-9的數(shù)字，并保存到

14、數(shù)組中去；當sym不是數(shù)字是，就返回12（常數(shù)的機內碼）；Else if（sym是+）返回4；Else if（sym是-）返回3；Else if（sym是*）返回2；Else if（sym是/）返回1；Else if（sym是）返回9；Else if（sym是；）返回20；該程序就是對輸入串進行分析，分析到不同的數(shù)據(jù)類型就相應返回它的機內碼，這樣方便在語法分析中進行分析。本程序還保存了變量和常量在結構數(shù)組中，方便在語義分析的時候使用。63 S()子程序的算法描述void S()re=Getsymbol(); /取下一個字符的機內碼if(re=關鍵字) /執(zhí)行S-while (B) Sre=Ge

15、tsymbol(); /取下一個字符的機內碼If(re=左括號)調用B()；re=Getsymbol(); /取下一個字符的機內碼if(re=右括號)調用S();Else if(re=變量) /執(zhí)行S-i = E re=Getsymbol(); /取下一個字符的機內碼If(re=等號)調用E()；ElseERROR()；該程序就是對通過Getsymbol()詞法分析程序得到的單詞，進行不同的程序語句執(zhí)行。當?shù)玫搅藈hile是就分析下一個是不是(，是的話就調用B()；否則就出錯。取下一個單詞，是)就調用S()；否則也出錯。當?shù)玫降氖亲兞縤時，去下一個單詞，如果是=就調用E()。64 B()和re

16、lop()子程序的算法描述在B()子程序中，不用判斷任何的單詞，就依次調用E()，relop()，E()，執(zhí)行B-E relop EVoid relop() re=Getsymbol(); /取下一個字符的機內碼 If(sym=大于號) ； /執(zhí)行relop-= Else if(syn=小于號) ； /執(zhí)行relop- Else ERROR()；在relop程序中就主要上判斷當前取得的單詞是不是條件運算符。65 E()子程序的算法描述Void E() re=Getsymbol(); /取下一個字符的機內碼if(re=左括號) /執(zhí)行E-(E)F E()；re=Getsymbol(); /取下一

17、個字符的機內碼if(re=右括號)F()；Else if(re=變量) /執(zhí)行E-iF F()；Else if(re=常量) /執(zhí)行E-nF F()；66 F()子程序算法描述Void F() re=Getsymbol(); /取下一個字符的機內碼 If(re=加號) /執(zhí)行F-+EF E(); F(); Else if(re=減號) /執(zhí)行F-EF E(); F(); Else if(re=乘號) /執(zhí)行F-*EF E(); F(); Else if(re=除號) /執(zhí)行F-/EF E(); F();這個子程序和E()合起來就是一個完整的可遞歸的算術操作運算，但由于遞歸下降分析方法不能含有左

18、遞歸文法，所以消去左遞歸后就成了兩個子程序。7 軟件的測試方法和測試結果由于該程序是用遞歸下降分析法來編寫的，根據(jù)文法可以知道它可以對while語句進行嵌套，條件判斷，賦值語句等的語句進行分析。而且賦值語句也可以嵌套。根據(jù)這些，我們在選擇測試用例的時候就要選擇比較典型的，盡量找到文法中有但程序中沒能很好實現(xiàn)的地方。下面就用到了幾個典型的用例：輸入字符串：while (n10) a=(b+c)*d;測試分析：這個輸入字符串是正確的，是最簡單的while語句測試結果：圖4 輸出結果輸入字符串：whil (n10) a=b+c;測試分析：該字符串不符合本程序的文法，其中是while出錯測試結果：圖5

19、 輸出結果輸入字符串：while (tomn10) while (tomm10) toma=(tomb+c23)*d45;測試分析：該字符串符合文法，它嵌套了while語句，而且變量名包含數(shù)字和字符測試結果：圖6 測試結果輸入字符串：while (tomn10) toma=tomb+c23;測試分析：在嵌套的語句中，第二個while書寫錯誤測試結果：圖7 測試結果8 研制報告這次的課程設計要求比較嚴格，但是題目給得比較早，我在做第一個課程設計的時候就開始了該次課程設計的分析工作。對遞歸下降分析方法的了解，遞歸分析方法的實現(xiàn)原理，三地址輸出等都做了詳細的了解。并且在編程之前就已經將程序的概要設計都做出來了，所以在編寫程序的時候相對比較容易。詞法分析，語法分析都是很容易的，只要你理解了分析方法的實現(xiàn)原理，編寫程序判斷輸入字符串是否滿足給定的文法是比較簡單的。比較麻煩的就是語義分析輸出三地址代碼，由于在遞歸下降分析技術