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

1、目錄1系統(tǒng)描述 .21.1目的 .21.2設(shè)計內(nèi)容： .21.3翻譯過程 .21.4初始條件： .31.5開發(fā)平臺 .32文法及屬性文法的描述 .33語法分析表設(shè)計 .43.1 LR 分析概述 .43.2 LR(0) 分析表 .53.3LR 語法分析過程的設(shè)計思想及算法 .743.4翻譯方法 .8中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計.85簡要的分析與概要設(shè)計 .96詳細(xì)的算法描述 .96.1main 函數(shù) .106.2詞法分析 .1076.3語法分析 .12測試方法和測試結(jié)果 .137.1測試過程 .137.2測試結(jié)論 .148研制報告 .148.1研制過程 .148.2本設(shè)計的評價 .

2、1598.3個人心得體會 .15參考文獻 .16本科生課程設(shè)計成績評定表 .17FOR循環(huán)語句的翻譯程序設(shè)計 LR 方法 、輸出四元式1 系統(tǒng)描述1.1 目的通過設(shè)計、編制、調(diào)試一個FOR 循環(huán)語句的語法及語義分析程序，加深對語法及語義分析原理的理解， 實現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析，并且實現(xiàn)對單詞序列的語法分析、語義分析以及中間代碼生成。1.2 設(shè)計內(nèi)容：本設(shè)計按照要求設(shè)計出for 語句的簡單文法， 并使用 LR 分析法對用戶輸入的程序進行分析和翻譯。對下列正確的程序輸入：for(i=0;i<10;i+)m=m+i;結(jié)果程序要對該輸入進行詞法分析，然后利用LR 分析法對詞法

3、分析后得到的單詞序列進行語法分析，經(jīng)過語法制導(dǎo)翻譯顯示出等價的四元式表示的中間代碼。對于錯誤的程序輸入，如：for(i=0;i<10)m=m+i;結(jié)果程序要指出程序出錯。1.3 翻譯過程詞法分析：詞法分析是編制一個讀單詞的過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標(biāo)識符、常數(shù)、運算符、分隔符五大類。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。程序語言的單詞符號一般分為五種：關(guān)鍵字（保留字/基本字） if 、while 、begin ；標(biāo)識符：常量名、變量名 ；常數(shù)： 34、56.78、true、a、；運算符： +、-、* 、/、and、or、.、；界限符：，

4、； （）/* 。語法分析：語法分析是編譯程序的核心部分 ,其主要任務(wù)是確定語法結(jié)構(gòu) , 檢查語法錯誤，報告錯誤的性質(zhì)和位置，并進行適當(dāng)?shù)募m錯工作。此次設(shè)計中語法分析中主要通過 LR 分析表對語法分析處理過程進行控制，使四元式翻譯的工作有條不紊的進行，同時識別語法分析中的語法錯誤。中間代碼生成：為了使編譯程序有較高的目標(biāo)程序質(zhì)量，或要求從編譯程序邏輯結(jié)構(gòu)上把與機器無關(guān)和與機器有關(guān)的工作明顯的分開來時，許多編譯程序都采用了某種復(fù)雜性介于源程序語言和機器語言之間的中間語言。常用的幾種中間語言有: 逆波蘭式、四元式、三元式、樹表示。本課程設(shè)計主要實現(xiàn)四元式的生成。1.4 初始條件：理論：掌握一種計算機

5、高級語言的使用。學(xué)完編譯課程，掌握詞法分析程序設(shè)計方法， LR 語法分析方法，以及語法制導(dǎo)的翻譯和中間代碼生成技術(shù)。實踐工具和環(huán)境：計算機實驗室提供計算機及軟件環(huán)境。1. 5 開發(fā)平臺所使用的系統(tǒng)： Windows XP程序開發(fā)工具： Visual C+ 6.0程序設(shè)計語言：C+ 。2 文法及屬性文法的描述按照設(shè)計要求，設(shè)計出的For 語句的符合簡單優(yōu)先定義的文法規(guī)則及相關(guān)的語義規(guī)則如下：產(chǎn)生式語義規(guī)則S f ( E ; F ; G ) H ;gotoS f ( E ; X ; Y ) H ;gotoEid= cid.value=c.value;Fid<cIf id.value>=

6、c.valuegoto over ;Gid + +id.value=id.value+1 ;Xid> cIf id.value<=c.valuegoto over ;Yid id.value=id.value-1;H123123id= id+ idid .value= id .value + id.valueHid 1 = id 2 + cid 1.value= id 2 .value + c .valueHid 1 = c+ id 2id 1 .value= c.value + id2 .value其中產(chǎn)生式規(guī)則中的符號：c 表示常數(shù) const， f 表示關(guān)鍵字 for， i

7、表示一般標(biāo)識符id3 語法分析表設(shè)計3.1 LR 分析概述一個 LR 分析器由 3 個部分組成：總控程序，也可以稱為驅(qū)動程序。對所有的LR 分析器總控程序都是相同的。分析表或分析函數(shù)。不同的文法分析表將不同，同一個文法采用的LR 分析器不同時，分析表也不同，分析表又可分為動作（ACTION ）表和狀態(tài)轉(zhuǎn)換（ GOTO）表兩個部分，他們都可用二維數(shù)組表示。分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧。它們均是先進后出棧。分析器的動作由棧頂狀態(tài)和相應(yīng)的狀態(tài)棧所決定（ LR （0）分析器不需向前查看輸入符號）。LR 分析器工作過程示意圖如下圖所示：輸入串 XXX .#SnXn.SP.總控程序輸出.S1X1S

8、0X0ACTIONGOTO 表表其中 SP 為棧指針 ,Si 為狀態(tài)棧， Xi 為文法符號棧。 狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系 GOTOSi,X=Sj 確定，該關(guān)系式是指當(dāng)棧頂狀態(tài)為 Si 遇到當(dāng)前文法符號為 X 時應(yīng)轉(zhuǎn)向狀態(tài) Sj。 X 為終結(jié)符或非終結(jié)符。ACTIONSi,a 規(guī)定了棧頂狀態(tài)為Si 時遇到輸入符號a 應(yīng)執(zhí)行的動作。動作有 4 種可能：移進：檔 Sj=GOTOSi,a 成立，則把 Sj 移入到狀態(tài)棧，把 a 移入到文法符號棧。其中 i,j 表示狀態(tài)號。歸約：檔在棧頂形成句柄為 時，則用 歸約為相應(yīng)的非終結(jié)符 A ，即當(dāng)文法中有 A 的產(chǎn)生式，而 的長度為 r（即 | |=r），則從狀態(tài)

9、棧和文法符號棧中自棧頂向下去掉 r 個符號，即棧指針 SP 減去 r。并把 A 一如文法符號棧內(nèi)，再把滿足 Sj=GOTOSi,A 的狀態(tài)移進狀態(tài)棧，其中Si 為修改指針后的棧頂狀態(tài)。接受 acc：當(dāng)歸約到文法符號棧中只剩文法的開始符號S 時，并且輸入符號串已結(jié)束即當(dāng)前輸入符是 #，則為分析成功。報錯：當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入串不是該文法能接受的句子3.2 LR(0) 分析表根據(jù)上述文法構(gòu)造的有窮自動機和根據(jù)有窮自動機構(gòu)造的LR(0)分析表有窮自動機：>15c21id10<14c20H0S1F8;12G16)222630;3336c43f

10、idid37+40id422( 3E 4; 6X9id17+23+ 27id;1331=34c38+41id445= 7c11idY18)242832;3539idH19_25_29 LR(0)分析表：ACTIONGOTOf(;)id=c<+>-#SEFGXYH0S211acc2S33S544S65S76S10897S118S129S1310S14S1511R3R3R3R3R3R3R3R3R3R3R3R3R3R312S171613S191814S2015S2116S2217S2318S2419S2520R4R4R4R4R4R4R4R4R4R4R4R4R4R421R6R6R6R6R6

11、R6R6R6R6R6R6R6R6R622S2623S2724S2825S2926S313027R5R5R5R5R5R5R5R5R5R5R5R5R5R528S313229R7R7R7R7R7R7R7R7R7R7R7R7R7R730S3331S3432S3533S3634S37S3835S3936R1R1R1R1R1R1R1R1R1R1R1R1R1R137S4038S4139R2R2R2R2R2R2R2R2R2R2R2R2R2R240S4241S4442R8R8R8R8R8R8R8R8R8R8R8R8R8R843R9R9R9R9R9R9R9R9R9R9R9R9R9R944R10R10R10R10R

12、10R10R10R10R10R10R10R10R10R10其中， S 表示移進且下一狀態(tài)為S 的下標(biāo)； R 表示歸約，歸約所用的產(chǎn)生式為 R 的下標(biāo)相對應(yīng)的產(chǎn)生式;空白表示沒有相應(yīng)的關(guān)系即出錯。3.3 LR語法分析過程的設(shè)計思想及算法3.4翻譯方法設(shè)計中，使用語法制導(dǎo)翻譯方法。所謂語法制導(dǎo)的翻譯方法是指：按照給定的語法，對單詞符號串進行語法分析，并構(gòu)造出語法分析樹，語法分析過程中根據(jù)需要構(gòu)造屬性依賴圖，然后遍歷語法樹并在語法樹的各個節(jié)點處，按語義規(guī)則進行計算，并生成中間代碼。所謂屬性依賴圖是一個有向圖，用于描述分析樹中的屬性和屬性間的相互依賴關(guān)系。4 中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計

13、本次設(shè)計，使用的中間代碼為四元式（即三地址碼） 。四元式的四個組成成分：算符 op，第一和第二運算對象ARG1 和 ARG2，及運算結(jié)果RESULT。例如對語句：for(i=0;i<10;i+)emp=temp+i;等價的四元式表示如下：（1）(=,0,， i)（2）if i>=10 goto over（3）（ +，temp， i ， t）（4）（ =，t， temp）（5）（ +，i， 1， i）（6）goto （2）（7）over設(shè)計并生成的結(jié)果程序，最終需要將用戶輸入的程序經(jīng)過詞法分析和語法分析，生成如上所述的四元式表示的中間代碼形式。5 簡要的分析與概要設(shè)計程序由詞法分析和

14、語法分析兩部分構(gòu)成：詞法分析程序， 以用戶輸入的字符串為輸入，判斷輸入是否包含非法字符，若字符完全合法，分析結(jié)果是，將標(biāo)識符、常量、其他合法單詞的類別和值保存在輸入流中，做為語法分析的輸入。為了有效地編寫詞法分析程序，首先應(yīng)構(gòu)造出程序流程圖，然后根據(jù)流程圖編寫程序。語法分析，以詞法分析結(jié)果作為輸入，驗證，輸入流中各種符號是否符合語法規(guī)則。若不符合，顯示出錯信息，否則，在分析過后顯示與輸入程序等價的中間代碼。同樣需要構(gòu)造語法分析的程序流程圖。6 詳細(xì)的算法描述程序包括三個文件：詞法分析.cpp 和 for 循環(huán)翻譯 .cpp。其中 for 循環(huán)語句翻譯 .cpp 中含有 main 函數(shù)，作為程序

15、的入口，在main 函數(shù)中接受用戶輸入的程序流，并保存在一個string 對象中，然后調(diào)用詞法分析.cpp 中的voidgetSym(string &s,int &i) 對程序流進行詞法分析分離出單詞符號，再調(diào)用語法分析 .cpp 文件中的 void gramCheck()函數(shù)對單詞符號輸入流進行語法分析和語義分析，并生成四元式形式的中間代碼。函數(shù) void getSym(string &s,int &i) 調(diào)用 getchar 函數(shù)獲得輸入流中的符號進行分析，如得到的是標(biāo)識符，則調(diào)用 outsym 函數(shù)分別普通標(biāo)識符和關(guān)鍵字。函數(shù) gramCheck()調(diào)用函

16、數(shù) priCmp 比較符號棧和輸入流中的兩個符號的優(yōu)先級關(guān)系。程序中的函數(shù)調(diào)用關(guān)系如，圖1：圖 1 for 循環(huán)語句翻譯程序函數(shù)調(diào)用關(guān)系圖Maingetlinegetsymactiongotopoppushgetcharoutsym6.1main函數(shù)Main() 函數(shù)主要代碼和相關(guān)解釋如下：int main()Int r;string s;/用于保存輸入程序的字符串cout<<" 輸入for循環(huán)語句："<<endl;/ 提示用戶輸入程序getline(cin,s);/接受用戶輸入并保存在s 中g(shù)etSym(s,i);r=nodeSize;for(i=

17、0;i<r;i+)/ 調(diào)用詞法分析程序sti=nodei.type;/將此法分析的結(jié)果保存到數(shù)組中語法分析；中間代碼生成；6.2 詞法分析在文件“詞法分析.cpp”中編寫詞法分析程序，文件中主要包含一個結(jié)構(gòu)體 struct symNode，一個結(jié)構(gòu)體數(shù)組 symNode node100，取字符函數(shù) void getChar(string &s,int &i)ch=si;i+; ，取單詞函數(shù) void getSym(string &s,int &i) ，程序中數(shù)據(jù)結(jié)構(gòu)和各函數(shù)具體功能如下：（1）定義結(jié)構(gòu)體：struct symNodeint type;str

18、ing sValue;int eValue;此結(jié)構(gòu)體用來保存詞法分析后，各種單詞的信息。Type 表示單詞的類別，各符號對應(yīng)的類別值見表1，如果單詞是常量， eValue 則保存該常量的值，如果單詞是標(biāo)識符， sValue 則保存該標(biāo)識符的值。（2）數(shù)組 symNode node100，用來保存單詞輸入流作為語法分析的輸入流；int position=0; position 保存數(shù)組 node 中將要輸入的單詞的位置，初值為 0。（3）函數(shù) void getSym(string &s,int &i); 用來作詞法分析， s 存儲用戶的輸入程序， i 用來保存當(dāng)前應(yīng)該取字符的位置

19、。（4）函數(shù)void getChar(string &s,int &i)ch=si;i+;用來取字符串 s 中第 i 個字符。（5）函數(shù) void outSym(string s); 區(qū)分 s 是關(guān)鍵字還是普通標(biāo)識符。詞法分析程序的具體算法描述： getChar()函數(shù)從串 s 里面取字符，直到遇到非空字符，如果已到達串尾，詞法分析結(jié)束。 getSym（）判斷所取的字符是字母開頭，還是以數(shù)字開頭，還是其他合法字符；如果以字母開頭，則開始保存為標(biāo)識符，繼續(xù)取字符直到遇到非字母非數(shù)字字符；如果以數(shù)字開頭則保存為整數(shù)常量，繼續(xù)取字符直到遇到非數(shù)字字符；其他字符則保存為相應(yīng)類別。所有的

20、單詞分離后保存到數(shù)組symNode node100中。詞法分析程序所輸出的單詞符號常常采用以下二元式表示：（單詞種別，單詞自身的值）。單詞的種別是語法分析需要的信息，而單詞自身的值則是編譯其他階段所需要的信息。詞法分析的流程圖，如圖2：圖 2 詞法分析流程圖開始輸入串末尾NYYgetcharCh=空YN結(jié)束Ch=string sCh=保存 s 的類型Ys=s+chA-Z orNA-Z和值getchar0-9NYCh=Yint temp保存 temp 的類Temp=temp*10+Ch=0-9Nint(ch)-480-9型和值Ngetchar其他合法Y保存其他符號字符？的類型和值N出錯6.3語法

21、分析在文件“ for 循環(huán)翻譯 .cpp”中編寫語法分析程序。程序中各函數(shù)具體功能解釋如下：int Initstack(stack &s)：初始化棧；int push(stack &s,char e) ：將要入棧的元素壓入棧中； char pop(stack &s,char *e) ：將要出棧的元素彈出棧；int action(int m,int n,char a)：對照 LR 分析表，判斷輸入的字符需要移進還是歸約；int go(int m,int n,char a) ：對照 LR 分析表，判斷需要歸約的字符串所對應(yīng)的產(chǎn)生式；在 main 函數(shù)中利用switch()

22、語句來實現(xiàn)歸約。7 測試方法和測試結(jié)果7.1 測試過程針對所設(shè)計的關(guān)于for 循環(huán)語句的翻譯程序，分別用正確的程序和有錯誤的程序進行測試，測試出結(jié)果程序的可用性和健壯性。測試中分別使用了兩個合法程序和兩個非法程序，對結(jié)果程序進行測試，具體的測試程序、測試過程和測試結(jié)果如下： for 循環(huán)語句語法分析過程：合法程序 1:for(i=0;i<10;i+) m=m+i;合法程序 2：for(j=1000;j >100;j -)t=t+j;非法程序：for(i=0;i<20) m=m+i;7.2測試結(jié)論經(jīng)過測試，可以得知，結(jié)果程序能達到預(yù)計的要求：對合法程序進行詞法分析和簡單優(yōu)先的語

23、法分析，并生成四元式表示的中間代碼；對于錯誤的程序輸入，結(jié)果程序能夠判斷其出錯。存在問題：對于錯誤的程序輸入，結(jié)果程序不能給出錯誤的位置。對于含有非法輸入符號的程序，結(jié)果程序沒有很好地處理，程序健壯性不強。8 研制報告8.1 研制過程在課程設(shè)計期間，通過閱讀大量相關(guān)書籍，利用網(wǎng)絡(luò)查找各種資料，根據(jù)相關(guān)知識，寫出了符合簡單優(yōu)先語法規(guī)則的關(guān)于for 語句的屬性文法。獲得語法規(guī)則的屬性文法后，對程序進行了概要設(shè)計，將程序大致分為詞法分析和語法分析兩個模塊，并且設(shè)計出文法對應(yīng)的符號優(yōu)先關(guān)系表。詞法分析負(fù)責(zé)對輸入串進行單詞識別，并保存單詞各信息，作為語法分析和翻譯的輸入。語法分析負(fù)責(zé)對輸入流中的單詞進行

24、分析，檢驗是否符合所寫的語法規(guī)則，并對其進行初步翻譯。概要設(shè)計后，對兩個模塊分別進行了詳細(xì)設(shè)計，并利用詞法分析流程圖和語法分析流程圖，設(shè)計程序的大致流程，并具體到各函數(shù)的設(shè)計。通過對程序進行了詳細(xì)設(shè)計，得到了程序大致流程， 并根據(jù)流程進行編碼，編碼過程中，出現(xiàn)了一些語法和語義上錯誤，通過調(diào)試和修改，使得程序成功運行。設(shè)計測試方法和測試用程序，并對程序進行了測試。8.2 本設(shè)計的評價此次設(shè)計對for 語句進行了全面詞法分析和語法分析，并得到了用于分析for 語句的結(jié)果程序。結(jié)果程序能對用戶輸入的程序代碼進行分析，判斷是否存在詞法錯誤和語法錯誤，如果出現(xiàn)錯誤，向用戶給出提示，如果沒有錯誤，則生成于

25、輸入程序等價的中間代碼，方便后續(xù)編譯過程工作。但是結(jié)果程序也存在很多不足：對于非法的輸入，無法給出錯誤的位置。對非法輸入考慮不全面，對某些非法輸入無法給出錯誤信息，另外屬性文法不完善，程序中的使用的某些判斷方法，只適合于本次設(shè)計使用的文法，實用性不強。8.3 個人心得體會本課程設(shè)計是for循環(huán)語句的翻譯程序，包括詞法分析部分、語法分析部分和中間代碼生成部分。詞法分析階段是編譯過程的第一個階段，是編譯的基礎(chǔ)。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，即對構(gòu)成源程序的字符流進行掃描然后根據(jù)構(gòu)詞規(guī)則識別單詞( 也稱單詞符號或符號 )。 語法分析部分采用 LR 分析方法進行語法分析，判斷給出的符號串是否為該文法識別的句子。中間代碼生成器部分主要實現(xiàn)四元式的生成，將用中綴式表示的算術(shù)表達式轉(zhuǎn)換為用四元式表示的算術(shù)表達式。在整個編譯器設(shè)計過程中，遇到了很多意想不到的困難，其主要原因是對各個部分要實現(xiàn)的功能考慮不夠周全，典型的如在詞法分析的設(shè)計中，當(dāng)前待分析字符串為“ a>+” , 當(dāng)前字符為 >，此時，分析器到底是將其分析為大于關(guān)系運算符還是大于等