1、目錄1 系統描述（問題域描述）21.1目的21.2設計步驟21.3系統體系結構描述22 文法及屬性文法的描述32.1文法32.2屬性文法33 語法分析方法描述及語法分析表設計53.1語法分析方法53.2語法分析表設計64中間代碼形式的描述及中間代碼序列的結構設計64.1中間代碼形式描述64.2中間代碼序列的結構設計75 編譯系統的概要設計75.1系統分析75.1.1詞法分析75.1.2語法分析85.1.3中間代碼生成85.2概要設計95.2.1系統總體設計圖95.2.2數據結構96 詳細的算法描述（流程圖或偽代碼）106.1詞法分析106.2語法分析117 軟件的測試方法和測試結果127.1軟

2、件測試方法127.2測試結果127.2.1簡單for循環語句（無嵌套）127.2.2 for循環嵌套語句148 研制報告168.1研制過程168.2對本設計特點和不足的評價168.3收獲與體會179 參考文獻（按公開發表的規范書寫）17FOR循環語句的翻譯程序設計（遞歸下降法、輸出四元式）1 系統描述（問題域描述）1.1目的通過設計、編輯、調試和運行一個 對for 循環語句進行詞法分析、語法及語義分析的編譯程序，并通過對實驗用例的測試來更加深刻的理解語言編譯的過程和原理。從而達到在理論學習的基礎上，對本課程有一個更深的掌握。1.2設計步驟對循環語句：for表達式；循環條件；表達式賦值語句（賦值

3、語句中可以嵌套更多的for循環語句）（1） 設計符合自身語法分析方法要求的文法和屬性文法。 （2） 設計對for循環語句進行詞法分析的函數，輸出單詞序列。（3） 設計遞歸下降法對文法進行語法分析。（4） 對源文件進行語法分析同時對源文件進行語義處理。（5） 設計中間代碼格式并輸出四位置中間代碼到文件中保存。 （6） 對源文件中的錯誤進行輸出。1.3系統體系結構描述源文件詞法分析語法分析中間代碼文件管理 本系統包括兩大部分：詞法分析和語法分析；系統中還包含了一個文件管理的連接件，實現對詞法分析結果和中間代碼的輸出保存功能。2 文法及屬性文法的描述2.1文法文法是用于描述語言的語法結構的形式規則（

4、即語法規則）。這些規則必須是準確的、易于理解的以及有相當強的描述能力。由這種規則所產生的程序語言應有利于句子分析和翻譯，而且，最好能通過這些規則自動產生有效的語法分析程序。for 循環語句的文法如下所示：1)S->for(W)Sx 2)W->A;W13)W1->B;W2 4)W2->A5)Sx->Ax 6)Sx->Am7)Am->AmAx 8)Am->Ax2.2屬性文法遞歸下降法的屬性文法是在上下文無關文法的基礎上，為每個文法符號（終結符或者非終結符）配備若干相關的“值”（與文法符號相關的屬性）。 在一個屬性文法中，對應于每個產生式 Aa 都有一

5、套與之相關聯的語義規則，每規則的形式為：b:=f（c1，c2，ck）。其中 f 是一個函數，b和c1，c2，ck是該產生式的文法符號的屬性。并有如下規則：（1）如果b 是 A 的一個屬性，c1，c2，ck 是產生式右邊文法符號的屬性或A的其他屬性，則稱b是A的綜合屬性。（2）如果b是產生式右部某文法符號X的一個屬性，并且c1，c2，ck 是A或產生式右邊任何文法符號的屬性，則稱b是文法符號X的繼承屬性。for循環語句的屬性文法為：產生式屬性文法S->for(W)Sxemit(1);/生成最后一個jumpbackpatch(nextstat,LastGotoAddress);/回填最后ju

6、mp;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.cod

7、eBegin ;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.Fa

8、lseOrEnd = 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)

9、;/輸出賦值語句E->EoperT(oper為+-*/)emit(oper , E , T , temp);/輸出表達式3 語法分析方法描述及語法分析表設計3.1語法分析方法遞歸下降分析方法是一種自頂向下語法分析方法，其目的是從文法的開始符號開始，根據輸入字符串進行最左推導，試圖推導出給定的字符串。或者說，從根節點（文法開始符號）開始，自上而下，從左到右地為輸入字符串建立一棵語法樹，并以預先確定的順序創建語法樹的節點。遞歸下降分析法可能需要回溯，即需要重復地掃描輸入。遞歸子程序法的實現思想是對應每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的串，當某非終結符的產生式有

10、多個候選式時，能夠按照LL（1）形式唯一地確定選擇某個候選式進行推導，因此首先要消除左遞歸。由于遞歸下降法對每個過程可能存在直接或間接的遞歸調用，所以對某個過程在退出之前可能又要被調用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復。由于遞歸過程是遵循先進后出規律，通常開辟棧來處理。遞歸調用的語法調用關系圖如下圖所示：遞歸調用的語法調用關系圖3.2語法分析表設計在對for循環語句進行翻譯時，涉及到對賦值表達式和布爾表達式語句的翻譯。在文法的描述中給出了算術運算符、關系運算符和邏輯運算符之間的優先級關系，其結合性由下表所示：優先級操作符類型操作對象的個數結合性1（）邏輯運算符左&

11、gt;右2!邏輯非運算符單目運算符右>左3*,/算術運算符雙目運算符左>右4+，-算術運算符雙目運算符左>右5<,<=,>,>=關系運算符雙目運算符左>右6=,!=關系運算符雙目運算符左>右7&&邏輯與運算符雙目運算符左>右8|邏輯或運算符雙目運算符左>右9=賦值運算符雙目運算符右>左4中間代碼形式的描述及中間代碼序列的結構設計4.1中間代碼形式描述常見的中間代碼形式有逆波蘭記號，三元式，四元式和樹形表示。本課程設計輸出的中間代碼的表示方法是四元式。四元式是一種更接近目標代碼的中間代碼形式。由于這種形式的中

12、間代碼便于優化處理，因此，在目前許多編譯程序中得到了廣泛的應用。 四元式實際上是一種“三位置語句”的等價表示。它的一般形式為： (op,arg1,arg2,result) 其中，op為一個二元 (也可是一元或零元)運算符；arg1,arg2分別為它的兩個運算 (或操作)對象，它們可以是變量、常數或系統定義的臨時變量名；運算的結果將放入result中。需要指出的是，每個四元式只能有一個運算符，所以，一個復雜的表達式須由多個四元式構成的序列來表示。例如，表達式A+B*C可寫為序列 T1=B*C T2=A+T1 其中，T1，T2是編譯系統所產生的臨時變量名。當op為一元、零元運算符 (如無條件轉移)

13、時，arg2甚至arg1應缺省，即result=op arg1或 op result ；對應的一般形式為： (op,arg1,result) 或 (op,result) 4.2中間代碼序列的結構設計對于循環語句：for（語句1；語句2；語句3）表達式，的中間代碼序列的結構為：5 編譯系統的概要設計5.1系統分析5.1.1詞法分析對源程序流進行掃描，每識別出一個單詞，若是標識符，則到符號表中查找，如果符號表中沒有此標識符的記錄，那么將此標識符插入符號表。最后按照單詞其所屬的類別，把類標識返回，作為語法分析階段的輸入。5.1.2語法分析由文法開始符號對應的子程序控制 for循環語句各個模塊的執行順

14、序，并由文法開始符號對應的子程序遞歸調用其他的子程序，對各個模塊采用自頂向下，自左至右的推導方法完成對輸入字符進行匹配的工作，試圖推導出與輸入符號串一致的文法的句子。5.1.3中間代碼生成控制代碼的輸出形式，以四元式形式輸出中間代碼5.2概要設計5.2.1系統總體設計圖5.2.2數據結構這次課程設計中，在詞法分析階段，用一個KeyWord.txt文件存放所有的關鍵字，用一個結構體數組tableword table_word100來存放詞法分析所輸出的單詞序列，并將單詞序列輸出到文件word.txt中。 在語法分析過程中，同樣使用一個結構體數組item siyuanshi100來存放語法分析輸出

15、的中間代碼四元式，并將結果輸出到siyuanshi.txt中。KEYIDID ID ID數組tablewordlexptrtokenforEOSiEOShowEOSareEOSyouEOS字符串數組table_word定義字符表的數據結構如下：struct tablewordstring word;int type;/1表示ID，2表示數值常量，3表示字符常量，0表示其它;/*為符號表分配一個存儲空間*/tableword table_word100;int tableword_length=0;int word_now=0;/*保存將要輸出的四元式信息*/struct itemstring

16、text;/四元式內容;item siyuanshi100;6 詳細的算法描述（流程圖或偽代碼）6.1詞法分析/詞法分析相關函數（1）bool Keyword(char c,string *KEYWORD,int KNLength,ifstream &infile);/*對字符進行關鍵詞的判斷，將字符與關鍵詞一個一個進行比較，如果比較成功，則返回真；如果比較到文件末尾，還未成功，則返回假。*/（2）bool Identify(char c,ifstream &infile,string &strtemp);/對字符進行標示符的判斷（3）bool ConstChar(ch

17、ar c,ifstream &infile);/對字符進行字符串常量的判斷（）bool ConstNum(char c,ifstream &infile);/對字符進行常數的判斷（）bool Operator(char c,ifstream &infile);/對字符進行運算符的判斷（）bool Delimiter(char c );/對字符進行界符的判斷（）int classfify(char c);/對字符進行類型判斷，相應返回類型號（）int classify_num(char c);/對讀入的數字字符進行分類詞法分析流程圖6.2語法分析/語法語義函數，每個函數對

18、應產生式的一個非終結符，從上到下進行遞歸調用，直到推出相應的終結符串。receive（）函數是對字符進行相應入棧出棧操作。emit()函數則是將產生的四元式中間代碼輸入到數組中。void S(tableword &word);void A(tableword &word);void E(tableword &word);void D(tableword &word);void O(tableword &word);void P(tableword &word);void G(tableword &word);void B(tablewor

19、d &word);void S1(tableword &word);void X(tableword &word);void E1(tableword &word);void T(tableword &word);void T1(tableword &word);void F(tableword &word);void receive(tableword &word,string temp,int type);void emit(int row,string strtemp);7 軟件的測試方法和測試結果7.1軟件測試方法由于本程

20、序在設計上考慮到for循環語句的多種表現形式，如for嵌套的方式，條件語句的表述等，所以在理論上能完成的功能很全，因此為了測試程序在實際應用中能否完成這些功能，我設計了兩種測試途徑：(1)輸入最簡單的for循環語句（無嵌套）(2)實現簡單for嵌套，可包括多個賦值語句7.2測試結果7.2.1簡單for循環語句（無嵌套）簡單for循環語句的輸入文件如下圖所示：編譯運行如下圖所示：輸出詞法分析的單詞序列：輸出語法語義分析之后的四元式中間代碼：7.2.2 for循環嵌套語句for循環嵌套語句的測試用例輸入文件：詞法分析后輸出的單詞序列文件：輸出語法語義分析之后的四元式中間代碼：8 研制報告8.1研制

21、過程作為一名計算機科學與技術專業大三的學生，我覺得能做類似的課程設計是十分有意義。它對我們的能力的提升很有好處。 在已度過的大三的時間里我們大多數接觸的是專業基礎課。我們在課堂上掌握的僅僅是專業基礎課的理論面，如何把我們所學到的專業基礎理論運用到實踐中？課程設計為我們提供了良好的平臺。課程設計是培養學生綜合運用所學知識發現提出分析和解決實際問題鍛煉實踐能力的重要環節是對學生實際工作能力的具體訓練和考察過程. 回顧起此次 for循環課程設計，我感慨頗多，的確，從考察到定稿，從理論到實踐，在這一個多星期的日子里，可以說是苦多于甜，但是我學到了很多很多的的東西，不僅鞏固了以前所學過的知識，而且學到了

22、很多在書本上所沒有學到過的知識。在本次課程設計中，我先是具體了解了各種文法，然后進行了自己的文法的設計，將二者結合起來，作出一個自己的文法，然后我開始設計一些基本的構件并描述出它們的具體接口功能，接口設計好之后，下一步便是進行類接口的實現了，最關鍵的一步是總控程序的設計，對其他構件類的調用。在以上功能完成之后，我們便開始遍程了。最后，進行調試。至此，我的for語法分析及翻譯系統出爐了，余下的工作便是進一步的完善系統功能。8.2對本設計特點和不足的評價本程序實現的功能有：簡單for循環，for循環嵌套，賦值語句，多個賦值語句（用分號隔開成語句），能完成的計算功能有布爾表達式，基本的四則運算，能將

23、各個功能結合起來形成for循環，賦值語句，布爾表達式，空語句的復合出現。for語句的實現上，通過將之分解成三個表達式來分別調用，直接對應接口，使得代碼冗余大大減小。for語句的分隔符是采用，來代替了小括號，避免了回溯所帶來的算法效率低問題。在詞法分析階段，區分一元和二元操作符的方法是：當取得的第一個字符為一元操作符時，繼續取下一個字符，若仍為操作符，則返回宏定義的標號，若不是操作符則將其放回，返回一元操作符的標號。在詞法分析階段在每一個類型判斷中都需要進行放回操作。對語法分析，詞法分析，四元式輸出分離設計，同步控制，使得代碼更靈活，結構更緊湊，不必要對中間結果進行大量重復的存儲后，然后逐一檢索后使用。由于沒有對中間結果進行存儲，造成語法上的某些錯誤處理不是很方便等缺點。不過這個缺點并非先天性的，可以通過冗余的存儲中間結果來克服。同時，這個功能可以作為編譯是的一個開關選項，當編譯過程中為了追求效率時，不打開冗余存儲開關(相當于gcc中的-On型開關)，當為了檢測更多的錯誤時