賦值語(yǔ)句的遞歸下降翻譯程序設(shè)計(jì)2

1、賦值語(yǔ)句的遞歸下降翻譯程序設(shè)計(jì)1 引言遞歸下降法是語(yǔ)法分析中最易懂的一種方法。它的主要原理是，對(duì)每個(gè)非終極符按其產(chǎn)生式結(jié)構(gòu)構(gòu)造相應(yīng)語(yǔ)法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過(guò)程調(diào)用命令。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，所以稱(chēng)這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎是一致的。本文將采用這種方法對(duì)賦值語(yǔ)句進(jìn)行翻譯，并得到逆波蘭式的中間代碼結(jié)果。另外我還完成了對(duì)逆波蘭式的中間代碼翻譯執(zhí)行的程序。1.1 逆波蘭式簡(jiǎn)介在通常的表達(dá)式中，二元運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，所以，這種表示法也稱(chēng)為中綴表示。對(duì)中綴表達(dá)式的計(jì)值，并非按運(yùn)算符出現(xiàn)的自然順序來(lái)

2、執(zhí)行其中的各個(gè)運(yùn)算，而是根據(jù)算符間的優(yōu)先關(guān)系來(lái)確定運(yùn)算的次序，此外，還應(yīng)顧及括號(hào)規(guī)則。因此，要從中綴表達(dá)式直接產(chǎn)生目標(biāo)代碼一般比較麻煩。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱(chēng)為后綴表示。這種表示法的一個(gè)特點(diǎn)是，表達(dá)式中各個(gè)運(yùn)算是按運(yùn)算符出現(xiàn)的順序進(jìn)行的，故無(wú)須使用括號(hào)來(lái)指示運(yùn)算順序，因而又稱(chēng)為無(wú)括號(hào)式。下面我們對(duì)照地給出一些表達(dá)式的兩種表示：中綴表示后綴表示A+BAB+（1）A+B*CABC*+（2）(A+B)*(C+D)AB+CD+*（3）x/yz-d*exyz/de*-（4）(a=0b>3)(ex

3、<>y)a0=b3>exy<>（5）從上面的例子可以看出：(1) 在兩種表示中，運(yùn)算對(duì)象出現(xiàn)的順序相同；(2) 在后綴表示中，運(yùn)算符按實(shí)際計(jì)算順序從左到右排列，且每一運(yùn)算符總是跟在其運(yùn)算對(duì)象之后。 順便提及，Lukasiewicz原來(lái)提出的是前綴表示，即把每一運(yùn)算符置于其運(yùn)算對(duì)象之前。例如，中綴式a+b和(a+b)/c相應(yīng)的前綴表示分別為+ab和/+abc。因此，為了區(qū)分前綴和后綴表示，通常將后綴表示稱(chēng)為逆波蘭表示。因前綴表示并不常用，所以有時(shí)也將后綴表示就稱(chēng)為波蘭表示。2 需求分析本課程設(shè)計(jì)的目的是為了實(shí)現(xiàn)賦值語(yǔ)句的遞歸下降翻譯程序設(shè)計(jì)，并給出對(duì)應(yīng)的逆波蘭式中間

4、代碼。賦值語(yǔ)句:= 標(biāo)識(shí)符 ：= 算術(shù)表達(dá)式算術(shù)表達(dá)式的文法：算術(shù)表達(dá)式項(xiàng)加法運(yùn)算符項(xiàng)項(xiàng) 因子乘法運(yùn)算符因子因子 標(biāo)識(shí)符無(wú)符號(hào)整數(shù)（表達(dá)式）加法運(yùn)算符 乘法運(yùn)算符 設(shè)計(jì)賦值語(yǔ)句文法，給出該文法的屬性文法，用遞歸下降分析法實(shí)現(xiàn)對(duì)賦值語(yǔ)句的翻譯，給出翻譯的逆波蘭式結(jié)果。3 總體設(shè)計(jì)本文采用用遞歸下降分析法實(shí)現(xiàn)對(duì)賦值語(yǔ)句的翻譯，并給出翻譯的逆波蘭式結(jié)果。3.1 設(shè)計(jì)原則設(shè)計(jì)賦值語(yǔ)句文法，給出該文法的屬性文法，用遞歸下降分析法實(shí)現(xiàn)對(duì)賦值語(yǔ)句的翻譯，給出翻譯的逆波蘭式結(jié)果。按照遞歸下降分析技術(shù)，遞歸下降識(shí)別程序是由一組子程序組成，每個(gè)子程序?qū)?yīng)于一個(gè)非終結(jié)符號(hào)。該子程序處理相應(yīng)句型中相對(duì)于此非終結(jié)符號(hào)的

5、產(chǎn)生式。3.1.1 文法賦值語(yǔ)句:= 標(biāo)識(shí)符 ：= 算術(shù)表達(dá)式算術(shù)表達(dá)式的文法：算術(shù)表達(dá)式項(xiàng)加法運(yùn)算符項(xiàng)項(xiàng) 因子乘法運(yùn)算符因子因子 標(biāo)識(shí)符無(wú)符號(hào)整數(shù)（表達(dá)式）加法運(yùn)算符 乘法運(yùn)算符 3.1.2 屬性文法的設(shè)計(jì)下面，我們按照以上文法，說(shuō)明如何按語(yǔ)法制導(dǎo)翻譯方法將簡(jiǎn)單算術(shù)表達(dá)式翻譯成為后綴式。為了突出翻譯的重點(diǎn)，這里不過(guò)多地涉及某些語(yǔ)義處理細(xì)節(jié)，屬性文法中只給出了語(yǔ)義規(guī)則。產(chǎn)生式屬性文法賦值語(yǔ)句:= 標(biāo)識(shí)符 ：= 算術(shù)表達(dá)式POST=標(biāo)識(shí)符&算術(shù)表達(dá)式&=算術(shù)表達(dá)式項(xiàng)加法運(yùn)算符項(xiàng)POST=項(xiàng)&項(xiàng)&加法運(yùn)算符項(xiàng) 因子乘法運(yùn)算符因子POST=因子&因子&

6、乘法運(yùn)算符因子 標(biāo)識(shí)符無(wú)符號(hào)整數(shù)（表達(dá)式）POST=標(biāo)識(shí)符無(wú)符號(hào)整數(shù)表達(dá)式在屬性文法中，POST就是我們要得到的逆波蘭式?！?amp;”表示各個(gè)逆波蘭式的連接。3.2 數(shù)據(jù)結(jié)構(gòu)和模塊說(shuō)明3.2.1 主函數(shù)圖1 主函數(shù)流程圖3.2.2 語(yǔ)義分析函數(shù)本函數(shù)的功能是實(shí)現(xiàn)對(duì)賦值語(yǔ)句的語(yǔ)義分析。最后得到對(duì)應(yīng)的逆波蘭式結(jié)果。圖2 語(yǔ)義分析函數(shù)流程圖3.2.3 語(yǔ)句函數(shù)本函數(shù)實(shí)現(xiàn)了對(duì)語(yǔ)句的分析，結(jié)果返回的也是逆波蘭式。圖3 語(yǔ)句函數(shù)3.2.4 賦值語(yǔ)句函數(shù)賦值語(yǔ)句的產(chǎn)生式如下：賦值語(yǔ)句:= 標(biāo)識(shí)符 ：= 算術(shù)表達(dá)式本函數(shù)的功能是將其轉(zhuǎn)化為對(duì)應(yīng)的逆波蘭式：POST=標(biāo)識(shí)符&算術(shù)表達(dá)式&=圖4

7、賦值語(yǔ)句函數(shù)3.2.5 表達(dá)式函數(shù)表達(dá)式的產(chǎn)生式如下：算術(shù)表達(dá)式項(xiàng)加法運(yùn)算符項(xiàng)本函數(shù)的功能是將其轉(zhuǎn)化為對(duì)應(yīng)的逆波蘭式：POST=項(xiàng)&項(xiàng)&加法運(yùn)算符圖5 表達(dá)式函數(shù)3.2.6 項(xiàng)函數(shù)項(xiàng)的產(chǎn)生式如下：項(xiàng) 因子乘法運(yùn)算符因子本函數(shù)的功能是將其轉(zhuǎn)化為對(duì)應(yīng)的逆波蘭式：POST=因子&因子&乘法運(yùn)算符圖6 項(xiàng)函數(shù)3.2.7 因子函數(shù)因子的產(chǎn)生式如下：因子 標(biāo)識(shí)符無(wú)符號(hào)整數(shù)（表達(dá)式）本函數(shù)的功能是將其轉(zhuǎn)化為對(duì)應(yīng)的逆波蘭式：POST=標(biāo)識(shí)符無(wú)符號(hào)整數(shù)表達(dá)式圖7 因子函數(shù)3.3 開(kāi)發(fā)工具的選擇操作系統(tǒng)：windows XP內(nèi)存：1G平臺(tái)：VC+ 6.04 詳細(xì)的算法設(shè)計(jì)4.1 語(yǔ)

8、義分析函數(shù)string lrparser()string temp=""scaner();kk=0;if(syn=1)temp=yucu();if(syn=6)scaner();if(syn=0 && kk=0)cout<<"分析成功！"<<endl;elseif(kk=0)cout<<"error:lost end "<<endl;kk=1;elsecout<<"error: can't find begin"<<en

9、dl;kk=1;return (string)temp;4.2 語(yǔ)句函數(shù)string yucu()string temp=statement();while(syn=26)temp+="n"+statement();return (string)temp;4.3 賦值語(yǔ)句函數(shù)string statement()string ID,eplace,temp;scaner();if(syn=10)ID=token;scaner();if(syn=18)eplace=expression();temp=ID+" "+eplace+" = "e

10、lsecout<<"error:lost :="<<endl;kk=1;elsecout<<"lost ID"<<endl;kk=1;return (string)temp;4.4 表達(dá)式函數(shù)string expression()string ag1,ag2,temp;int tpsyn;ag1=term();temp=ag1;while(syn=13 | syn=14)tpsyn=syn;ag2=term();string aa=(tpsyn=13)?"+":"-"

11、temp+=" "+ag2+" "+aa+" "return (string)temp;4.5 項(xiàng)函數(shù)string term()string ag1,ag2,temp;int tpsyn;ag1=factor();temp=ag1;scaner();while(syn=15 | syn=16)tpsyn=syn;ag2=factor();string aa=(tpsyn=15)?"*":"/"temp+=" "+ag2+" "+aa+" &quo

12、t;scaner();return (string)temp;4.6 因子函數(shù)string factor()scaner();string fplace=""if(syn=10)return token;else if(syn=11)sprintf(temp,"%d",sum);return (string)temp;else if(syn=27)fplace=expression();if(syn=28)return fplace;else cout<<"error: without ) "<<endl;kk

13、=1; elsecout<<"error: without ( "<<endl;kk=1;return ""4.7 對(duì)目標(biāo)代碼的翻譯函數(shù)這里只給出了關(guān)鍵的代碼：dofin>>word;switch(word0)case '=':ag1=getValue(s.top();s.pop();ags=s.top();s.pop();insertTable(ags,ag1);break;case '+':ag1=getValue(s.top();s.pop();ag2=getValue(s.top

14、();s.pop();s.push(int2str(floor(ag2+ag1);break;case '-':ag1=getValue(s.top();s.pop();ag2=getValue(s.top();s.pop();s.push(int2str(floor(ag2-ag1);break;case '*':ag1=getValue(s.top();s.pop();ag2=getValue(s.top();s.pop();s.push(int2str(floor(ag2*ag1);break;case '/':ag1=getValue(s

15、.top();s.pop();ag2=getValue(s.top();s.pop();if(ag1=0)s.push("9999999");else s.push(int2str(floor(ag2/ag1);break;default:s.push(word);while(!fin.eof();5 軟件調(diào)試使用VC+自帶的功能對(duì)源代碼進(jìn)行了調(diào)試，直至沒(méi)有語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤。6 軟件的測(cè)試方法和結(jié)果采用文本文件輸入源代碼，然后程序通過(guò)讀取文本文件中的源代碼，進(jìn)行語(yǔ)義分析，最后輸出逆波蘭式的中間代碼結(jié)果。本文一共測(cè)試了三組典型數(shù)據(jù)：begin a:=(2+3*4)*4/(3

16、+7) end #begin a:=2+3*4; x:=(a+b)/c end #begin a:=(x*y/(zmvj8969-r)-sdf; x:=(a+b)/c; yue:=123+r +1+2-4 end #圖8 測(cè)試結(jié)果另外本文還實(shí)現(xiàn)了對(duì)逆波蘭式的翻譯結(jié)果。計(jì)算出了在程序中的每個(gè)變量的值。圖9 命令行方式執(zhí)行圖10 對(duì)逆波蘭式的翻譯執(zhí)行結(jié)果7 有關(guān)技術(shù)的討論在對(duì)賦值語(yǔ)句的翻譯過(guò)程中，我只是實(shí)現(xiàn)了對(duì)語(yǔ)句的翻譯，并給出逆波蘭式。而實(shí)際有用的還必須要能計(jì)算出運(yùn)行的結(jié)果，也就是能夠達(dá)到計(jì)算出變量數(shù)值的結(jié)果。8 收獲與體會(huì)在本課程設(shè)計(jì)的過(guò)程中，我學(xué)習(xí)到了好多書(shū)本上學(xué)不到的東西，真正體會(huì)到了編譯

17、原理的強(qiáng)大。也同時(shí)為自己能夠編寫(xiě)出這樣一個(gè)強(qiáng)大的程序而感到欣慰。通過(guò)這次課程設(shè)計(jì)，我體會(huì)到了編譯原理的實(shí)用性,提高了學(xué)習(xí)興趣。同時(shí)這次課程設(shè)計(jì)消除了我對(duì)編譯原理學(xué)習(xí)的畏難情緒. 另外這次課程設(shè)計(jì)使我獲得了對(duì)詞法分析器和語(yǔ)法分析器的感性認(rèn)識(shí),加深了對(duì)理論的理解.在這次編譯原理的課程設(shè)計(jì)中，我采用了遞歸子程序方法進(jìn)行語(yǔ)法分析,對(duì)文法中的每個(gè)非終極符號(hào)按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)的語(yǔ)法分析子程序,完成相應(yīng)的識(shí)別任務(wù)。其中終結(jié)符產(chǎn)生匹配命令，非終結(jié)符則產(chǎn)生調(diào)用命令。因?yàn)槭褂昧诉f歸下降方法,所以程序結(jié)構(gòu)和層次清晰明了,易于手工實(shí)現(xiàn),且時(shí)空效率較高。實(shí)際的語(yǔ)法分析工作,從調(diào)用總程序的分析子程序開(kāi)始，根據(jù)產(chǎn)生式進(jìn)行遞歸調(diào)用各個(gè)分析子程序。另外，我使用了一種簡(jiǎn)單的語(yǔ)義規(guī)則實(shí)現(xiàn)了用遞歸下降分析法實(shí)現(xiàn)了輸出逆波蘭式的目的。不過(guò)這種方法是一種十分有效的方法，可以推廣到while，if等語(yǔ)句，雖然本課程設(shè)計(jì)并沒(méi)有這個(gè)要求。本文還實(shí)現(xiàn)了對(duì)逆波蘭式的翻譯結(jié)果