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

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

2、分析結(jié)果進(jìn)行輸出，要求輸出結(jié)果是三地址形式的。2 文法及屬性文法的描述21文法描述語(yǔ)句 > := while (< 條件表達(dá)式 > (< 賦值語(yǔ)句 > | 語(yǔ)句 > <條件表達(dá)式> := (<標(biāo)識(shí)符>|<無(wú)符號(hào)整數(shù)>）<條件運(yùn)算符> (<標(biāo)識(shí)符>|<無(wú)符號(hào)整數(shù)><標(biāo)識(shí)符> := <字母> (<字母>|<數(shù)字><條件運(yùn)算符> := > | < | = <無(wú)符號(hào)整數(shù)> := <數(shù)字>（<數(shù)字

3、><賦值語(yǔ)句> := <標(biāo)識(shí)符>=(<標(biāo)識(shí)符> | <數(shù)字> <算術(shù)運(yùn)算符> (<標(biāo)識(shí)符> | <數(shù)字><算術(shù)運(yùn)算符> := + | - | * | / <賦值語(yǔ)句> := <標(biāo)識(shí)符>=<標(biāo)識(shí)符> | <數(shù)字>22遞歸文法while語(yǔ)句文法：S -> while (B S | i=EB -> E relop Erelop -> < | = | >E -> E+E | E-E | E*E | E/E | (E |

4、 i | n在編寫程序的時(shí)候用到的是遞歸下降法，而遞歸下降法對(duì)文法的要求是不能包含左遞歸，對(duì)上述的文法進(jìn)行消除左遞歸之后，得到如下的遞歸文法：S -> while (B S | i=EB -> E relop Erelop -> < | = | >E -> (EF | 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.ne

5、xt:=S.begin;S.code:=gen(S.begin, : | B.code |gen(S.true, : | S1.code | gen(goto,S.begin | gen(B.false, : | gen(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;r

6、elop.code:=gen(<|gen(=|gen(>E -> (E1FE.place:=newlabel;E.code:=E1.code | F.code |gen(E.place := ,(, E1.place , , F.place;E -> iFE.palce:=newlabel;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

7、.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 -> *EF1F.place:=newlabel;F.code:=E.code | F1.code |gen(F.place:= * , E.place , F1.place;F -> /EF1F

8、.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 語(yǔ)法分析方法描述按照遞歸下降分析技術(shù)，遞歸下降識(shí)別程序是由一組子程序組成，每個(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ì)的文

9、法根據(jù)遞歸下降分析技術(shù)對(duì)文法的要求改為非左遞歸的文法。程序中5個(gè)子程序，其中S 是開(kāi)始符號(hào)，也是遞歸下降分析的入口，通過(guò)調(diào)用int Getsymbol(對(duì)輸入的字符串進(jìn)行單詞分析，并返回當(dāng)前所分析到的單詞，然后在遞歸語(yǔ)法分析中根據(jù)這個(gè)單詞分析下一步要執(zhí)行的子程序。4 中間代碼形式的描述41三地址代碼在本程序中用到了三地址語(yǔ)句的輸出包括以下的種類：賦值語(yǔ)句：x:= y op z復(fù)制語(yǔ)句：x:= y條件轉(zhuǎn)移語(yǔ)句：if x relop y goto L 例如，本程序中語(yǔ)句while (B S ,可以輸出三地址代碼為：if B goto L else goto Lnext；而E -> (EF可以

10、輸出三地址代碼為：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 -> >relop:= >E -> (EFE1:= (E2 FE -> iFE:= I FE -> nFE:= n FF -> +EFF1:= +E F2F -> -EFF

11、1:= -E F2F -> *EFF1:= *E F2F -> /EFF1:= /E F2F ->F:= 圖2 三地址代碼5 概要設(shè)計(jì)51簡(jiǎn)要分析遞歸下降分析技術(shù)就是通過(guò)對(duì)每個(gè)非終結(jié)符編寫一個(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)的單詞類型。單詞類型主要包括變量，關(guān)鍵字，常量，各種符號(hào)等，每種符號(hào)都是一種類型。在語(yǔ)法分析程序中，根據(jù)詞法得到的結(jié)果，進(jìn)行判斷是否是當(dāng)前需要的單詞類型，如果不是就說(shuō)明輸入字符串不能由該文法推導(dǎo)出來(lái)；如

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

13、n( 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=i F(;else if(re=n F(;void F( re=Getsymbol(;if(re=+ E(; F(;else if(re=- E(; F(;else if(

14、re=* E(; F(;else if(re=/ E(; F(;6 詳細(xì)的算法描述（流程圖或偽代碼）關(guān)閉文件6 1main( 主函數(shù)的算法描述 圖3 mian(流程圖主程序執(zhí)行時(shí)首先會(huì)測(cè)試input.txt文件是否存在，因?yàn)槌绦蚓褪峭ㄟ^(guò)該文件得到需要進(jìn)行遞歸下降分析方法分析的輸入符號(hào)串；然后建立output.txt文件，問(wèn)以后的輸出結(jié)果做基礎(chǔ)；接著調(diào)用遞歸下降分析法的入口程序S(來(lái)開(kāi)始對(duì)文件中的輸入字符串進(jìn)行詞法，語(yǔ)法和語(yǔ)義分析；最后關(guān)閉文件結(jié)束程序。62Getsymbol(子程序的算法描述Int Getsymbol(sym=fgetc(intput; /取當(dāng)前文件指針指向的字符While(s

15、ym不為空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ù)字，并保存到數(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是<）返回11；Else

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

17、e=變量 /執(zhí)行S->i = E re=Getsymbol(; /取下一個(gè)字符的機(jī)內(nèi)碼If(re=等號(hào)調(diào)用E(；ElseERROR(；該程序就是對(duì)通過(guò)Getsymbol(詞法分析程序得到的單詞，進(jìn)行不同的程序語(yǔ)句執(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(和relop(子程序的算法描述在B(子程序中，不用判斷任何的單詞，就依次調(diào)用E(，relop(，E(，執(zhí)行B->E relop EVoid relop( re=Getsymbol(; /取下一個(gè)

18、字符的機(jī)內(nèi)碼If(sym=大于號(hào) ； /執(zhí)行relop-><Else if(sym=等于號(hào) ；/執(zhí)行relop->=Else if(syn=小于號(hào) ； /執(zhí)行relop->>ElseERROR(；在relop程序中就主要上判斷當(dāng)前取得的單詞是不是條件運(yùn)算符。65 E(子程序的算法描述Void E( re=Getsymbol(; /取下一個(gè)字符的機(jī)內(nèi)碼if(re=左括號(hào) /執(zhí)行E->(EF E(；re=Getsymbol(; /取下一個(gè)字符的機(jī)內(nèi)碼if(re=右括號(hào)F(；Else if(re=變量 /執(zhí)行E->iFF(；Else if(re=常量 /執(zhí)行

19、E->nFF(；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(合起來(lái)就是一個(gè)完整的可遞歸的算術(shù)操作運(yùn)算，但由于遞歸下降分析方法不能含有左遞歸文法，所以消去左遞歸后就成了兩個(gè)子程序。7 軟件的測(cè)試方法和測(cè)試結(jié)果由于該程序是用遞歸下降分析法來(lái)編寫的，根據(jù)文法可以知道它可以

20、對(duì)while語(yǔ)句進(jìn)行嵌套，條件判斷，賦值語(yǔ)句等的語(yǔ)句進(jìn)行分析。而且賦值語(yǔ)句也可以嵌套。根據(jù)這些，我們?cè)谶x擇測(cè)試用例的時(shí)候就要選擇比較典型的，盡量找到文法中有但程序中沒(méi)能很好實(shí)現(xiàn)的地方。下面就用到了幾個(gè)典型的用例：輸入字符串：while (n<10 a=(b+c*d;測(cè)試分析：這個(gè)輸入字符串是正確的，是最簡(jiǎn)單的while語(yǔ)句測(cè)試結(jié)果：圖4 輸出結(jié)果輸入字符串：whil (n<10 a=b+c;測(cè)試分析：該字符串不符合本程序的文法，其中是while出錯(cuò)測(cè)試結(jié)果：圖5 輸出結(jié)果輸入字符串：while (tomn<10 while (tomm<10 toma=(tomb+c23

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