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

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

2、分析結(jié)果進(jìn)行輸出，要求輸出結(jié)果是三地址形式的。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在編寫程序的時(shí)候用到的是遞歸下降法，而遞歸下降法對(duì)文法的要求是不能包含左遞歸，對(duì)上述的文法進(jìn)行消除左遞歸之后，得到如下的遞歸文法：S - w

3、hile (B) S | i=EB - E relop Erelop - E - (E)F | iF | nFF - +EF | -EF | *EF | /EF | 23屬性文法的描述產(chǎn)生式屬性文法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 語法分析方法描述按照遞歸下降分析技術(shù)，遞歸下降識(shí)別程序是

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

8、輸出包括以下的種類：賦值語句：x:= y op z復(fù)制語句：x:= y條件轉(zhuǎn)移語句：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 概要設(shè)計(jì)51簡要分析遞歸下降分析技術(shù)就是通過對(duì)每個(gè)非終結(jié)符編寫一個(gè)子程序來實(shí)現(xiàn)它的操作，然后通過遞歸的調(diào)用來實(shí)現(xiàn)對(duì)輸入字符串的分析，這其中還包括對(duì)輸入字符串的詞法分析。在詞法分析的時(shí)，得到的字符單詞要和關(guān)鍵字比較，看是否是關(guān)鍵字，根據(jù)比較結(jié)果進(jìn)行返回相應(yīng)的單詞類型。單詞類型主要包括變量，關(guān)鍵字，常量，各種符號(hào)等，每種符號(hào)都是一種類型。在

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

11、析。主程序main()主要就是進(jìn)行各種變量的初始化，調(diào)用遞歸分析程序的入口子程序。子程序間的嵌套關(guān)系如下：void main() S(); void Getsymbol() void ERROR() void S() re=Getsymbol(); if(re=while(關(guān)鍵字) 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 詳細(xì)的算法描述（流程圖或偽代碼）初始化各變量打開文件調(diào)用S()子程序關(guān)閉文件61main()主函數(shù)的算法描述圖3 mian()流程圖主程序執(zhí)行時(shí)首先會(huì)測(cè)試input.txt文件是否存在，因?yàn)槌绦蚓褪峭ㄟ^該文件得到需要進(jìn)行遞歸下降分析方法分析的輸入符號(hào)串；然后建立output.txt文件，問以后的輸出結(jié)果做基礎(chǔ)；接著調(diào)用遞歸

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

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

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

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

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

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

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