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

17/17目錄1系統(tǒng)描述（問題域描述） 21.1目的 21.2設計步驟 21.3系統(tǒng)體系結構描述 22文法及屬性文法的描述 32.1文法 32.2屬性文法 33語法分析方法描述及語法分析表設計 53.1語法分析方法 53.2語法分析表設計 64中間代碼形式的描述及中間代碼序列的結構設計 64.1中間代碼形式描述 64.2中間代碼序列的結構設計 75編譯系統(tǒng)的概要設計 75.1系統(tǒng)分析 75.1.1詞法分析 75.1.2語法分析 85.1.3中間代碼生成 85.2概要設計 95.2.1系統(tǒng)總體設計圖 95.2.2數(shù)據(jù)結構 96詳細的算法描述（流程圖或偽代碼） 106.1詞法分析 106.2語法分析 117軟件的測試方法和測試結果 127.1軟件測試方法 127.2測試結果 127.2.1簡單for循環(huán)語句（無嵌套） 127.2.2for循環(huán)嵌套語句 148研制報告 168.1研制過程 168.2對本設計特點和不足的評價 168.3收獲與體會 179參考文獻（按公開發(fā)表的規(guī)范書寫） 17

FOR循環(huán)語句的翻譯程序設計（遞歸下降法、輸出四元式）1系統(tǒng)描述（問題域描述）1.1目的通過設計、編輯、調(diào)試和運行一個對for循環(huán)語句進行詞法分析、語法及語義分析的編譯程序，并通過對實驗用例的測試來更加深刻的理解語言編譯的過程和原理。從而達到在理論學習的基礎上，對本課程有一個更深的掌握。1.2設計步驟對循環(huán)語句：for〈表達式；循環(huán)條件；表達式〉賦值語句（賦值語句中可以嵌套更多的for循環(huán)語句）（1）設計符合自身語法分析方法要求的文法和屬性文法。（2）設計對for循環(huán)語句進行詞法分析的函數(shù)，輸出單詞序列。（3）設計遞歸下降法對文法進行語法分析。（4）對源文件進行語法分析同時對源文件進行語義處理。（5）設計中間代碼格式并輸出四地址中間代碼到文件中保存。（6）對源文件中的錯誤進行輸出。1.3系統(tǒng)體系結構描述源文件源文件詞法分析語法分析中間代碼文件管理本系統(tǒng)包括兩大部分：詞法分析和語法分析；系統(tǒng)中還包含了一個文件管理的連接件，實現(xiàn)對詞法分析結果和中間代碼的輸出保存功能。2文法及屬性文法的描述2.1文法文法是用于描述語言的語法結構的形式規(guī)章（即語法規(guī)章）。這些規(guī)章必須是精確的、易于理解的以及有相當強的描述能力。由這種規(guī)章所產(chǎn)生的程序語言應有利于句子分析和翻譯，而且，最好能通過這些規(guī)章自動產(chǎn)生有效的語法分析程序。for循環(huán)語句的文法如下所示：1)S->for(W)Sx2)W->A;W13)W1->B;W24)W2->A5)Sx->Ax6)Sx->{Am}7)Am->AmAx8)Am->Ax2.2屬性文法遞歸下降法的屬性文法是在上下文無關文法的基礎上，為每個文法符號（終結符或者非終結符）配備若干相關的“值”（與文法符號相關的屬性）。在一個屬性文法中，對應于每個產(chǎn)生式A→a都有一套與之相關聯(lián)的語義規(guī)章，每規(guī)章的形式為：b:=f（c1，c2，…，ck）。其中f是一個函數(shù)，b和c1，c2，…，ck是該產(chǎn)生式的文法符號的屬性。并有如下規(guī)章：（1）如果b是A的一個屬性，c1，c2…，ck是產(chǎn)生式右邊文法符號的屬性或A的其他屬性，則稱b是A的綜合屬性。（2）如果b是產(chǎn)生式右部某文法符號X的一個屬性，并且c1，c2…，ck是A或產(chǎn)生式右邊任何文法符號的屬性，則稱b是文法符號X的繼承屬性。for循環(huán)語句的屬性文法為：產(chǎn)生式屬性文法S->for(W)Sxemit(1);//生成最后一個jumpbackpatch(nextstat,LastGotoAddress);//回填最后jump;backpatch(W.FalseOrEnd,nextstat);//B為假跳到最后一個語句W1->B;W2backpatch(B.TrueOrChain,W2.TrueOrChain);backpatch(W2.FalseOrEnd,B.codeBegin);W2->Aemit(4);//輸出跳轉W2.TrueOrChain=nextstat;W2.FalseOrEnd=nextstat-1;Sx->{Am}去掉{}B->B1||Lbackpatch(B1.FalseOrEnd,L.codeBegin);//回填B.codeBegin=B1.codeBegin;B.TrueOrChain=chainMerge(B1.TrueOrChain,L.TrueOrChain);B.FalseOrEnd=L.FalseOrEnd;LastGotoAddress=nextstat;//記錄最后jump回填地址B->LLastGotoAddress=nextstat;//記錄最后jump回填地址L->L1&&Mbackpatch(L1.TrueOrChain,M.codeBegin);//回填L.codeBegin=L1.codeBegin;L.TrueOrChain=M.TrueOrChain;L.FalseOrEnd=chainMerge(L1.FalseOrEnd,M.FalseOrEnd);M->!M1M.TrueOrChain=M1.FalseOrEnd;M.FalseOrEnd=M1。TrueOrChainM.codeBegin=M1.codeBegin;K->idScidK.TrueOrChain=nextstat;K.codeBegin=nextstat;K.FalseOrEnd=nextstat+1;emit(J+Sc,id,id,);//輸出跳轉語句emit(jump,-,-,);A->id=Eemit(E,-,-,id);//輸出賦值語句E->EoperT(oper為+-*/)emit(oper,E,T,temp);//輸出表達式3語法分析方法描述及語法分析表設計3.1語法分析方法遞歸下降分析方法是一種自頂向下語法分析方法，其目的是從文法的開頭符號開頭，依據(jù)輸入字符串進行最左推導，試圖推導出給定的字符串。或者說，從根節(jié)點（文法開頭符號）開頭，自上而下，從左到右地為輸入字符串建立一棵語法樹，并以預先確定的挨次創(chuàng)建語法樹的節(jié)點。遞歸下降分析法可能需要回溯，即需要重復地掃描輸入。遞歸子程序法的實現(xiàn)思想是對應每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的串，當某非終結符的產(chǎn)生式有多個候選式時，能夠依據(jù)LL（1）形式唯一地確定選擇某個候選式進行推導，因此首先要消除左遞歸。由于遞歸下降法對每個過程可能存在直接或間接的遞歸調(diào)用，所以對某個過程在退出之前可能又要被調(diào)用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復。由于遞歸過程是遵循先進后出規(guī)律，通常開辟棧來處理。遞歸調(diào)用的語法調(diào)用關系圖如下圖所示：遞歸調(diào)用的語法調(diào)用關系圖3.2語法分析表設計在對for循環(huán)語句進行翻譯時，涉及到對賦值表達式和布爾表達式語句的翻譯。在文法的描述中給出了算術運算符、關系運算符和規(guī)律運算符之間的優(yōu)先級關系，其結合性由下表所示：優(yōu)先級操作符類型操作對象的個數(shù)結合性1（）規(guī)律運算符——左—>右2!規(guī)律非運算符單目運算符右—>左3*,/算術運算符雙目運算符左—>右4+，-算術運算符雙目運算符左—>右5<,<=,>,>=關系運算符雙目運算符左—>右6==,!=關系運算符雙目運算符左—>右7&&規(guī)律與運算符雙目運算符左—>右8||規(guī)律或運算符雙目運算符左—>右9=賦值運算符雙目運算符右—>左4中間代碼形式的描述及中間代碼序列的結構設計4.1中間代碼形式描述常見的中間代碼形式有逆波蘭記號，三元式，四元式和樹形表示。本課程設計輸出的中間代碼的表示方法是四元式。四元式是一種更接近目標代碼的中間代碼形式。由于這種形式的中間代碼便于優(yōu)化處理，因此，在目前很多編譯程序中得到了廣泛的應用。四元式實際上是一種“三地址語句”的等價表示。它的一般形式為：(op,arg1,arg2,result)其中，op為一個二元(也可是一元或零元)運算符；arg1,arg2分別為它的兩個運算(或操作)對象，它們可以是變量、常數(shù)或系統(tǒng)定義的臨時變量名；運算的結果將放入result中。需要指出的是，每個四元式只能有一個運算符，所以，一個簡單的表達式須由多個四元式構成的序列來表示。例如，表達式A+B*C可寫為序列T1∶=B*CT2∶=A+T1其中，T1，T2是編譯系統(tǒng)所產(chǎn)生的臨時變量名。當op為一元、零元運算符(如無條件轉移)時，arg2甚至arg1應缺省，即result∶=oparg1或opresult；對應的一般形式為：(op,arg1,,result)或(op,,,result)4.2中間代碼序列的結構設計對于循環(huán)語句：for（語句1；語句2；語句3）{表達式}，的中間代碼序列的結構為：5編譯系統(tǒng)的概要設計5.1系統(tǒng)分析5.1.1詞法分析對源程序流進行掃描，每識別出一個單詞，若是標識符，則到符號表中查找，如果符號表中沒有此標識符的記錄，那么將此標識符插入符號表。最后依據(jù)單詞其所屬的類別，把類標識返回，作為語法分析階段的輸入。5.1.2語法分析由文法開頭符號對應的子程序掌握for循環(huán)語句各個模塊的執(zhí)行挨次，并由文法開頭符號對應的子程序遞歸調(diào)用其他的子程序，對各個模塊接受自頂向下，自左至右的推導方法完成對輸入字符進行匹配的工作，試圖推導出與輸入符號串全都的文法的句子。5.1.3中間代碼生成掌握代碼的輸出形式，以四元式形式輸出中間代碼5.2概要設計5.2.1系統(tǒng)總體設計圖5.2.2數(shù)據(jù)結構這次課程設計中，在詞法分析階段，用一個KeyWord.txt文件存放全部的關鍵字，用一個結構體數(shù)組tablewordtable_word[100]來存放詞法分析所輸出的單詞序列，并將單詞序列輸出到文件word.txt中。在語法分析過程中，同樣使用一個結構體數(shù)組itemsiyuanshi[100]來存放語法分析輸出的中間代碼——四元式，并將結果輸出到siyuanshi.txt中。KEYKEYIDIDIDID數(shù)組tablewordlexptrtokenforEOSiEOShowEOSareEOSyouEOS字符串數(shù)組table_word定義字符表的數(shù)據(jù)結構如下：structtableword{ stringword; inttype;//1表示ID，2表示數(shù)值常量，3表示字符常量，0表示其它};/*為符號表安排一個存儲空間*/tablewordtable_word[100];inttableword_length=0;intword_now=0;/*保存將要輸出的四元式信息*/structitem{ stringtext;//四元式內(nèi)容};itemsiyuanshi[100];6簡略的算法描述（流程圖或偽代碼）6.1詞法分析//詞法分析相關函數(shù)（1）boolKeyword(charc,string*KEYWORD,intKNLength,ifstream&infile);/*對字符進行關鍵詞的推斷，將字符與關鍵詞一個一個進行比較，如果比較成功，則返回真；如果比較到文件末尾，還未成功，則返回假。*/（2）boolIdentify(charc,ifstream&in&strtemp);//對字符進行標示符的推斷（3）boolConstChar(charc,ifstream&infile);//對字符進行字符串常量的推斷（）boolConstNum(charc,ifstream&infile);//對字符進行常數(shù)的推斷（）boolOperator(charc,ifstream&infile);//對字符進行運算符的推斷（）boolDelimiter(charc);//對字符進行界符的推斷（）intclassfify(charc);//對字符進行類型推斷，相應返回類型號（）intclassify_num(charc);//對讀入的數(shù)字字符進行分類詞法分析流程圖6.2語法分析//語法語義函數(shù)，每個函數(shù)對應產(chǎn)生式的一個非終結符，從上到下進行遞歸調(diào)用，直到推出相應的終結符串。receive（）函數(shù)是對字符進行相應入棧出棧操作。emit()函數(shù)則是將產(chǎn)生的四元式中間代碼輸入到數(shù)組中。voidS(tableword&word);voidA(tableword&word);voidE(tableword&word);voidD(tableword&word);voidO(tableword&word);voidP(tableword&word);voidG(tableword&word);voidB(tableword&word);voidS1(tableword&word);voidX(tableword&word);voidE1(tableword&word);voidT(tableword&word);voidT1(tableword&word);voidF(tableword&word);voidreceive(tableword&word,stringtemp,inttype);voidemit(introw,stringstrtemp);7軟件的測試方法和測試結果7.1軟件測試方法由于本程序在設計上考慮到for循環(huán)語句的多種表現(xiàn)形式，如for嵌套的方式，條件語句的表述等，所以在理論上能完成的功能很全，因此為了測試程序在實際應用中能否完成這些功能，我設計了兩種測試途徑：(1)輸入最簡潔的for循環(huán)語句（無嵌套）(2)實現(xiàn)簡潔for嵌套，可包括多個賦值語句7.2測試結果7.2.1簡潔for循環(huán)語句（無嵌套）簡潔for循環(huán)語句的輸入文件如下圖所示：編譯運行如下圖所示：輸出詞法分析的單詞序列：輸出語法語義分析之后的四元式中間代碼：7.2.2for循環(huán)嵌套語句for循環(huán)嵌套語句的測試用例輸入文件：詞法分析后輸出的單詞序列文件：輸出語法語義分析之后的四元式中間代碼：8研制報告8.1研制過程作為一名計算機科學與技術專業(yè)大三的同學，我覺得能做類似的課程設計是十分有意義。它對我們的能力的提升很有好處。在已度過的大三的時間里我們大多數(shù)接觸的是專業(yè)基礎課。我們在課堂上掌握的僅僅是專業(yè)基礎課的理論面，如何把我們所學到的專業(yè)基礎理論運用到實踐中？課程設計為我們供應了良好的平臺。課程設計是培育同學綜合運用所學知識發(fā)現(xiàn)提出分析和解決實際問題熬煉實踐能力的重要環(huán)節(jié)是對同學實際工作能力的簡略訓練和考察過程.回顧起此次for循環(huán)課程設計，我感慨頗多，的確，從考察到定稿，從理論到實踐，在這一個多星期的日子里，可以說是苦多于甜，但是我學到了很多很多的的東西，不僅鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。在本次課程設計中，我先是簡略了解了各種文法，然后進行了自己的文法的設計，將二者結合起來，作出一個自己的文法，然后我開頭設計一些基本的構件并描述出它們的簡略接口功能，接口設計好之后，下一步便是進行類接口的實現(xiàn)了，最關鍵的一步是總控程序的設計，對其他構件類的調(diào)用。在以上功能完成之后，我們便開頭遍程了。最后，進行調(diào)試。至此，我的for語法分析及翻譯系統(tǒng)出爐了，余下的工作便是進一步的完善系統(tǒng)功能。8.2對本設計特點和不足的評價本程序?qū)崿F(xiàn)的功能有：簡潔for循環(huán)，for循環(huán)嵌套，賦值語句，多個賦值語句（用分號隔開成語句），能完成的計算功能有布爾表達式，基本的四則運算，能將各個功能結合起來形成for循環(huán)，賦值語句，布爾表達式，空語句的復合消失。for語句的實現(xiàn)上，通過將之分解成三個表達式來分別調(diào)用，直接對應接口，使得代碼冗余大大減小。for語句的分隔符是接受‘[’，’]’來代替了小括號，避開了回溯所帶來的算法效率低問題。在詞法分析階段，區(qū)分一元和二元操作符的方法是：當取得的第一個字符為一元操作符時，連續(xù)取下一個字符，若仍為操作符，則返回宏定義的標號，若不是操作符則將其放回，返回一元操作符的標號。在詞法分析階段在每一個類型推斷中都需要進行放回操作。對語法分析，詞法分析，四元式輸出分離設計，同步掌握，使得代碼更敏捷，結構更緊湊，不必要對中間結果進行大量重復的存儲后，然后逐一檢索后使用。由于沒有對中間結果