賦值語句的遞歸下降翻譯程序設計2

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

2、執(zhí)行其中的各個運算，而是根據(jù)算符間的優(yōu)先關系來確定運算的次序，此外，還應顧及括號規(guī)則。因此，要從中綴表達式直接產(chǎn)生目標代碼一般比較麻煩。波蘭邏輯學家J.Lukasiewicz于1929年提出了另一種表示表達式的方法。按此方法，每一運算符都置于其運算對象之后，故稱為后綴表示。這種表示法的一個特點是，表達式中各個運算是按運算符出現(xiàn)的順序進行的，故無須使用括號來指示運算順序，因而又稱為無括號式。下面我們對照地給出一些表達式的兩種表示：中綴表示后綴表示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) 在兩種表示中，運算對象出現(xiàn)的順序相同；(2) 在后綴表示中，運算符按實際計算順序從左到右排列，且每一運算符總是跟在其運算對象之后。 順便提及，Lukasiewicz原來提出的是前綴表示，即把每一運算符置于其運算對象之前。例如，中綴式a+b和(a+b)/c相應的前綴表示分別為+ab和/+abc。因此，為了區(qū)分前綴和后綴表示，通常將后綴表示稱為逆波蘭表示。因前綴表示并不常用，所以有時也將后綴表示就稱為波蘭表示。2 需求分析本課程設計的目的是為了實現(xiàn)賦值語句的遞歸下降翻譯程序設計，并給出對應的逆波蘭式中間

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

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

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

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

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 語句函數(shù)string yucu()string temp=statement();while(syn=26)temp+="n"+statement();return (string)temp;4.3 賦值語句函數(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 表達式函數(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 項函數(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 對目標代碼的翻譯函數(shù)這里只給出了關鍵的代碼：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+自帶的功能對源代碼進行了調(diào)試，直至沒有語法錯誤和語義錯誤。6 軟件的測試方法和結(jié)果采用文本文件輸入源代碼，然后程序通過讀取文本文件中的源代碼，進行語義分析，最后輸出逆波蘭式的中間代碼結(jié)果。本文一共測試了三組典型數(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 測試結(jié)果另外本文還實現(xiàn)了對逆波蘭式的翻譯結(jié)果。計算出了在程序中的每個變量的值。圖9 命令行方式執(zhí)行圖10 對逆波蘭式的翻譯執(zhí)行結(jié)果7 有關技術(shù)的討論在對賦值語句的翻譯過程中，我只是實現(xiàn)了對語句的翻譯，并給出逆波蘭式。而實際有用的還必須要能計算出運行的結(jié)果，也就是能夠達到計算出變量數(shù)值的結(jié)果。8 收獲與體會在本課程設計的過程中，我學習到了好多書本上學不到的東西，真正體會到了編譯

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