minic編譯過程可視化系統(tǒng)的設計與實現(xiàn)——畢業(yè)論文

1、<p>　　編號 </p><p><b>　　畢業(yè)設計（論文）</b></p><p>　　題目 miniC編譯過程可視化系統(tǒng) </p><p>　　的設計與實現(xiàn) </p><p>　　二級學院 計算機科學與工程 </p

2、><p>　　專 業(yè) 計算機科學與技術 </p><p>　　班 級 11203070A </p><p>　　學生姓名 學號11203070237 </p><p>　　指導教師 黃賢英 職稱 教授 </p><p>　　時 間

3、 2016.6 </p><p><b>　　目 錄</b></p><p><b>　　摘 要I</b></p><p>　　AbstractIII</p><p><b>　　1 緒論1</b></p><p>

4、;　　1.1 課題背景1</p><p>　　1.2 國內外研究現(xiàn)狀1</p><p>　　1.3 研究目的與研究內容2</p><p>　　2 開發(fā)技術與原理簡介3</p><p>　　2.1 原理簡介3</p><p>　　2.2 開發(fā)技術3</p><p><b>　

5、　3 需求分析5</b></p><p>　　3.1 miniC語言定義5</p><p>　　3.1.1 miniC語言字符集的定義5</p><p>　　3.1.2 miniC語言單詞的定義5</p><p>　　3.1.3 miniC語法規(guī)則定義6</p><p>　　3.2 功能需求9&

6、lt;/p><p>　　3.2.1 可視化界面9</p><p>　　3.2.2 適合教學9</p><p>　　3.2.3 高效準確的算法設計9</p><p>　　3.2.4 系統(tǒng)功能需求9</p><p>　　3.2.5 完整的系統(tǒng)功能10</p><p>　　3.3 其它需求10

7、</p><p>　　3.4 需求分析10</p><p>　　3.4.1 系統(tǒng)的結構分析10</p><p>　　3.4.2 miniC語言分析10</p><p>　　3.4.3 系統(tǒng)功能分析11</p><p><b>　　4 總體設計12</b></p><p

8、>　　4.1 系統(tǒng)整體結構設計12</p><p>　　4.2 系統(tǒng)模塊化設計與調用關系12</p><p><b>　　5 詳細設計14</b></p><p>　　5.1 詞法分析14</p><p>　　5.1.1 miniC語言的詞法分析14</p><p>　　5.1.2

9、 miniC語言詞法分析狀態(tài)轉化圖設計19</p><p>　　5.1.3 詞法分析數(shù)據(jù)結構設計22</p><p>　　5.1.4 miniC語言詞法分析核心程序設計23</p><p>　　5.1.5 正規(guī)式->NFA->DFA功能24</p><p>　　5.2 語法分析25</p><p>

10、;　　5.2.1 語法分析功能結構圖25</p><p>　　5.2.2 miniC語言結構文法定義25</p><p>　　5.2.3miniC表達式文法定義32</p><p>　　5.2.4 預測分析法（語法分析方案一）38</p><p>　　5.2.5 遞歸下降進行語法分析（語法分析方案二）43</p>&

11、lt;p>　　5.2.6 遞歸下降與LL(1)預測分析法混合使用（語法分析方案三）43</p><p>　　5.2.7 遞歸下降與LL(1)預測分析法混合使用（語法分析方案四）44</p><p>　　5.2.8 文法改進后的LL(1)預測分析（語法分析方案五）44</p><p>　　5.3 語義分析及中間代碼生成45</p><

12、p>　　5.3.1 中間代碼四元式格式定義45</p><p>　　5.3.2 語義分析階段出現(xiàn)的錯誤46</p><p>　　5.3.3文法與中間代碼的翻譯規(guī)則46</p><p>　　5.4 代碼優(yōu)化56</p><p>　　5.4.1 代碼優(yōu)化原理56</p><p>　　5.4.2 代碼優(yōu)化規(guī)

13、則56</p><p>　　5.4.3 代碼優(yōu)化算法設計57</p><p>　　5.5 目標代碼生成58</p><p>　　5.5.1 目標代碼生成階段設計思路58</p><p>　　5.5.2 中間代碼翻譯為目標代碼規(guī)則58</p><p>　　5.6 平臺編譯60</p><p

14、>　　5.6.1 平臺編譯技術介紹60</p><p>　　5.6.2 MASM工具介紹61</p><p><b>　　6系統(tǒng)實現(xiàn)62</b></p><p>　　6.1 詞法分析階段核心程序實現(xiàn)62</p><p>　　6.2 語法分析階段核心程序實現(xiàn)63</p><p>　

15、　6.3 語義分析及中間代碼生成階段核心程序實現(xiàn)65</p><p>　　6.4 代碼優(yōu)化階段核心程序實現(xiàn)67</p><p>　　6.5 目標代碼生成階段核心程序實現(xiàn)68</p><p>　　6.6 用戶操作界面功能實現(xiàn)68</p><p>　　6.6.1 用戶操作界面設計68</p><p>　　6.6.

16、2 功能與核心程序對應規(guī)則69</p><p><b>　　7系統(tǒng)測試71</b></p><p>　　7.1 系統(tǒng)測試環(huán)境搭建71</p><p>　　7.2 系統(tǒng)功能測試方法71</p><p>　　7.3 系統(tǒng)測試源碼設計72</p><p>　　7.4 測試結果72</

17、p><p>　　7.4.1 用戶界面72</p><p>　　7.4.2 詞法分析功能73</p><p>　　7.4.3 語法分析（LL1預測分析，不分析全局變量）功能74</p><p>　　7.4.4 語法分析（遞歸下降+LL1分析函數(shù)體）功能74</p><p>　　7.4.5 語法分析（遞歸下降+LL1分

18、析表達式）功能75</p><p>　　7.4.6 語法分析（完全遞歸下降分析）功能76</p><p>　　7.4.7 語法分析（LL1預測分析，使用新文法）功能76</p><p>　　7.4.8 語義分析及中間代碼生成功能77</p><p>　　7.4.9 代碼優(yōu)化功能78</p><p>　　7.4

19、.10 目標代碼生成功能78</p><p>　　7.4.11 平臺編譯并運行程序79</p><p>　　7.5 測試分析80</p><p><b>　　8總結81</b></p><p><b>　　致謝82</b></p><p><b>　　參

20、考文獻83</b></p><p><b>　　文獻綜述84</b></p><p><b>　　摘 要</b></p><p>　　miniC編譯過程可視化系統(tǒng)是基于計算機科學與技術專業(yè)的基礎學科編譯原理相關理論設計開發(fā)的，該系統(tǒng)涉及到編譯原理中詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化和目標

21、代碼生成五個階段的功能和相關算法的實現(xiàn)，并將每個階段的分析過程通過圖表的形式展示出來。該系統(tǒng)具有輔助教學功能，可以幫助高校計算機專業(yè)的學生更形象的理解編譯原理這門課程；miniC編譯過程可視化系統(tǒng)是一個完整的編譯系統(tǒng)，可以提供給計算機程序設計初學者作為編譯工具使用；該系統(tǒng)還可以應用到編譯器軟件的開發(fā)設計中，有助于編譯軟件的發(fā)展，以適應當前各類計算機編程語言、各種處理器和操作系統(tǒng)的發(fā)展需要。</p><p>　　m

22、iniC編譯過程可視化系統(tǒng)是一款集輔助教學、程序設計、工業(yè)開發(fā)為一體的計算機工具軟件。通過使用CppSTL和C#DotNet技術相結合進行開發(fā)，該系統(tǒng)處理問題更加高效、應用更加靈活、可擴展性比較高。該系統(tǒng)實現(xiàn)了將編譯原理五個階段中的處理步驟、設計的算法、應用的原理通過圖表的形式形象的展示出來，并對每個階段的功能以多種方案的形式進行設計。該系統(tǒng)可以遍歷源程序以狀態(tài)轉換圖方式進行詞法分析，可以完成從正規(guī)式到NFA再到DFA之間的轉換并以圖形

23、形式表示，對語法分析按照LL(1)預測分析法和遞歸下降分析法相結合實現(xiàn)五種分析方案，可以進行語義分析并生成與源程序等價的中間代碼并進行優(yōu)化，可以在Windows平臺生成匯編代碼并編譯為可執(zhí)行程序進行執(zhí)行。該系統(tǒng)對編譯原理的相關理論深度實現(xiàn)，并可以作為一個完整的系統(tǒng)使用。</p><p>　　miniC編譯過程可視化系統(tǒng)對于編譯原理各個階段的經(jīng)典算法都有相關的實現(xiàn)，該系統(tǒng)在開發(fā)過程中遵循軟件工程開發(fā)的一般方法，并合

24、理地使用了軟件設計模式，系統(tǒng)具有良好的可擴展性，對于編譯原理理論的研究和相關算法的開發(fā)和改進都有很大的幫助。該系統(tǒng)性能穩(wěn)定、有一套完整異常處理方案、可以實現(xiàn)用戶需求的所有功能。該論文詳細的介紹了miniC編譯原理可視化系統(tǒng)開發(fā)的理論依據(jù)，使用的工具，設計方法，面向對象的類結構等內容，有助于該系統(tǒng)的使用和改進。</p><p>　　關鍵詞：編譯 輔助教學 可視化 系統(tǒng) 算法</p><p>

25、<b>　　Abstract</b></p><p>　　MiniC compilation process visualization system is based on the basic course of computer science and technology professional compiler principle theory in the design and

26、development, the system relates to compilation principle of lexical analysis, syntax analysis, semantic analysis and intermediate code generation, code optimization and target code generation implementation of the functi

27、on of five stages and the associated algorithm and the analysis process of each stage in the form of chart showi</p><p>　　MiniC compiler process visualization system is a set of auxiliary teaching, programmi

28、ng, industrial development as one of the computer tools software. By using the combination of CppSTL and C#DotNet technology, the system is more efficient and more flexible and scalable. The system realizes will compile

29、principle of five stages of processing steps and design algorithms, application of the principle of image in the form of charts show out, and the function of each stage in the form of various sch</p><p>　　Co

30、mpile the miniC process visualization system for compiling principle for the various stages of the classical algorithm are related to the realization of, the system in the development process followed the general method

31、of software engineering development and reasonably used software design pattern, the system has good scalability, the compiler for the development and the improvement of the theory research and the related algorithm have

32、 great help. The performance of the system is stable, ther</p><p>　　Key words: compiler assisted teaching visualization system algorithm</p><p><b>　　1 緒論</b></p><p>

33、<b>　　1.1 課題背景</b></p><p>　　隨著當前計算機技術和互聯(lián)網(wǎng)行業(yè)的飛速發(fā)展，物聯(lián)網(wǎng)產(chǎn)品的需求日益增多，計算機產(chǎn)品與計算機服務已經(jīng)被廣大用戶接受并逐漸形成一種依賴。編譯原理作為一門計算機科學與技術的專業(yè)的基礎學科，它的學習難度較大，但是對于計算機專業(yè)的學生來說非常重要。不論是物聯(lián)網(wǎng)產(chǎn)品還是互聯(lián)網(wǎng)服務，都離不開計算機專業(yè)工程師的不斷努力，隨著計算機新技術的層出不窮和處理器

34、的更新?lián)Q代，計算機編程語言的多種多樣，對于計算機學習者和IT行業(yè)從業(yè)者來說難度也日益增大。對于他們來說，不斷地去學習新技術，才能保證自己不被淘汰，但是學習的速度遠不及新技術的更新速度，尤其是編程語言的更新。因此編譯原理這門基礎學科就起到了重要的作用，編譯原理不僅是一套理論，更多的涉及到編程語言、操作系統(tǒng)、微處理器技術等方面的內容。為了適應當前教學需求，設計一個編譯原理課程學習輔助教學系統(tǒng)是很有必要的。因此該系統(tǒng)：編譯原理可視化系統(tǒng)有利于

35、學生學習編譯原理課程，理解計算機編程語言與微處理器的工作原理。隨著嵌入式設備需求增加，處理器的應用更加廣泛，每一款處理都會對應一套編譯系統(tǒng)，編譯軟件變得非常重要，該系統(tǒng)有利于編譯軟件的發(fā)展，有利于國產(chǎn)軟件的發(fā)展。</p><p>　　1.2 國內外研究現(xiàn)狀</p><p>　　編譯原理的研究在國外已經(jīng)非常成熟了，而且還有很多優(yōu)秀的產(chǎn)品，例如微軟的Microsoft Visual Studi

36、o，GUN中的GCC等，這些都是適用于C語言、C++語言程序設計的編譯器，這類編譯器是將源程序編譯鏈接為可執(zhí)行程序在指定處理器上運行。另外還有Sun公司開發(fā)的Java語言以及其編譯器javac命令集和解釋器java命令集，這類編譯系統(tǒng)是將編譯前端和編譯后端分開，通過Java字節(jié)碼（即編譯原理中的中間代碼）做為中間鍵來完成程序功能，使得Java開發(fā)出的程序不受操作系統(tǒng)和處理器的影響。還有JavaScript、Python這些解釋型語言，使

37、用它們編寫的程序不需要編譯為中間代碼或可執(zhí)行文件，而是使用系統(tǒng)程序對這些程序逐行解釋執(zhí)行。但是，國內幾乎沒有太多的編譯軟件產(chǎn)品，除了軍用的一些編譯器外，商業(yè)使用的編譯器幾乎全部為國外的產(chǎn)品。計算機科學與技術專業(yè)中的編譯原理這門課程相對比較復雜，因此大部分學生學習起來會比較困難，只有極少部分的學生學的還不錯，但也只局限于理論層面。編譯原理課程的學習需要借助輔助教學軟件來完成，但是國內的輔助教學軟件的發(fā)展還比較落后，輔助教學軟件的應用不是很

38、廣泛。</p><p>　　1.3 研究目的與研究內容</p><p>　　通過對編譯原理的研究，有助于編譯原理課程的學習，改善該課程的教學質量，促進編譯原理理論的研究和發(fā)展。通過圖形化界面將編譯原理各個階段的分析過程顯示出來，有助于理解編譯原理各個階段的工作原理。編譯原理五個分析過程都涉及到大量的算法，該系統(tǒng)可以將算法的分析過程通過一定的形式表示處理，有助于對編譯算法的研究和改進。編譯器

39、是計算機中至關重要的一款系統(tǒng)軟件，它是軟件開發(fā)人員和計算機操作系統(tǒng)交互的工具。一款優(yōu)秀的編譯軟件有利于軟件開發(fā)人員更好的工作。但是，當前國內開發(fā)人員使用的編譯軟件大部分都是國外軟件。編譯軟件成為國產(chǎn)軟件發(fā)展的瓶頸，編譯原理也是國內技術瓶頸，因此該系統(tǒng)對于發(fā)展國產(chǎn)編譯軟件具有一定的促進作用。該系統(tǒng)實現(xiàn)從詞法分析到目標代碼生成五個階段的編譯前端和編譯后端的功能，并且可以實現(xiàn)運行程序和顯示程序的結果等功能，該系統(tǒng)實現(xiàn)了編譯原理大部分功能，基本

40、上是一個完整的軟件系統(tǒng)。在該系統(tǒng)的基礎上可以進一步的深入研究編譯原理和研發(fā)出適合國內軟件開發(fā)人員的編譯工具軟件。該畢業(yè)設計研究的主要內容是編譯原理的相關理論，包括編譯過程各階段的算法實現(xiàn)，編程語言的字符集、構詞規(guī)則、語法結構以及與匯編語言的轉換</p><p>　　2 開發(fā)技術與原理簡介</p><p><b>　　2.1 原理簡介</b></p>&l

41、t;p>　　miniC編譯過程可視化系統(tǒng)開發(fā)過程中涉及到的理論基本都來自編譯原理中的相關理論。詞法分析需要根據(jù)相關語言的構詞規(guī)則設計出詞法的狀態(tài)轉換圖，然后按照詞法的狀態(tài)轉換圖設計出詞法分析的核心算法。語法分析應用LL(1)預測分析法和遞歸下降分析法內容設計出語法分析功能，該部分包括文法的設計、存儲和處理，獲取文法的首終結符集，獲取文法的后隨符號集，構造LL(1)預測分析表，設計預測分析核心算法等。語義分析及中間代碼生成按照語法制

42、導翻譯方法分析沒有語法錯誤的Token串，生成規(guī)范的四元式形式的中間代碼。代碼優(yōu)化針對中間代碼生成過程中由于每個部分存在的chain而產(chǎn)生的空跳轉和相鄰跳轉造成的中間代碼冗余進行優(yōu)化。目標代碼生成需要將中間代碼根據(jù)相應操作系統(tǒng)和處理器適用的匯編格式轉換為匯編代碼。最后平臺使用MASM工具協(xié)助完成系統(tǒng)功能。</p><p><b>　　2.2 開發(fā)技術</b></p><p

43、>　　miniC編譯過程可視化系統(tǒng)是一個具有用戶操作界面的系統(tǒng)，在開發(fā)過程中需要將核心算法和界面分開。該系統(tǒng)使用C++編程語言并結合STL類庫開發(fā)出系統(tǒng)相關功能的核心代碼，使用C#語言開發(fā)用戶操作界面，最后通過Windows平臺下的BAT腳本將核心代碼和用戶界面整合在一起。</p><p><b>　　系統(tǒng)開發(fā)工具</b></p><p>　　該系統(tǒng)使用到的開發(fā)

44、工具為Visual Studio 2015和MASM。Visual Studio 2015作為Windows平臺下多種編程語言的開發(fā)工具非常適合Windows程序的設計與開發(fā)。該系統(tǒng)需要使用C++語言設計核心算法程序并使用C#語言設計圖形用戶界面程序，Visual Studio 2015支持這兩種語言的程序開發(fā)設計，恰巧滿足了系統(tǒng)的開發(fā)需要，同時也避免了使用多款IDE開發(fā)程序間不兼容情況的發(fā)生。MASM的功能是將適用于Windows平臺

45、下的匯編程序編譯鏈接為可執(zhí)行程序，這也是該系統(tǒng)比較重要的一個功能。目標代碼生成階段生成出Windows平臺下的匯編代碼，這樣保證了與該系統(tǒng)運行平臺的一致性，避免了生成其它平臺下的匯編代碼時增加系統(tǒng)測試難度情況的發(fā)生。</p><p><b>　　系統(tǒng)開發(fā)技術</b></p><p>　　該系統(tǒng)使用的開發(fā)技術為C++ STL和C# Winform。C++語言對于字符處理

46、有很好的支持。在C++中ASCII表中的字符存儲需要一個字節(jié)的空間，中文字符存儲需要兩個字節(jié)的空間。該系統(tǒng)的字符集為ASCII表中的字符，而中文字符只會出現(xiàn)在源程序的注釋中不進行分析處理。其它的編程語言，例如C#、Java，統(tǒng)一將字符存儲在兩個字節(jié)的空間中，這樣就對字符處理造成一定的麻煩，同時也增大了程序運行的體積。在使用C++進行核心算法程序設計時，該系統(tǒng)使用STL標準模板庫減少了鏈表和字符串處理的難度，提高了系統(tǒng)的開發(fā)效率。圖形用戶

47、界面使用C#Winform進行設計開發(fā)。Winform開發(fā)相比于MFC開發(fā)更加高效，簡單，更利于維護。</p><p><b>　　3 需求分析</b></p><p>　　3.1 miniC語言定義</p><p>　　3.1.1 miniC語言字符集的定義</p><p>　　字符集定義了miniC語言可識別的全部符

48、號，用來判斷某一符號是否為非法字符。</p><p>　　(1)<字符集> -> <字母> | <數(shù)字> | <特殊符號></p><p>　　釋義：字符集由字母、數(shù)字及一些特殊符號構成。</p><p>　　(2)<字母> -> a|b|c···|z|A|B|C&

49、#183;··|Z</p><p>　　釋義：字母由ASCII碼表中所有的大寫字母和小寫字母構成。</p><p>　　(3)<數(shù)字> -> 0|1|2|3···|9</p><p>　　釋義：數(shù)字由ASCII碼表中0~9所有的數(shù)字構成。</p><p>　　(4)<特

50、殊符號> -> +|-|*|/|=|</p><p>　　釋義：miniC語言中只用使用 這些特殊符號，其他符號均認為是異常字符。</p><p>　　3.1.2 miniC語言單詞的定義</p><p>　　(1)<單詞> -> <關鍵詞> | <標識符> | <常量> | <運算符>

51、 | <界符></p><p>　　釋義：miniC語言中的單詞可分為關鍵詞、標識符、常量、運算符和界符共5類單詞。</p><p>　　(2)<關鍵詞> -> auto | break | case | char | const | continue | default | do | double | else | enum | extern | float

52、 | for | goto | if | inline | int | long | register | restrict | return | short | signed | sizeof | static | struct | switch | typedef | union | unsigned | void | volatile | while | _bool | _Complex | _Imaginary | true |

53、 false | print | scan</p><p>　　釋義：miniC語言中一共有41個關鍵詞。</p><p>　　(3)<標識符> -> <_下劃線> | <字母> | <標識符><字母> | <標識符><數(shù)字></p><p>　　釋義：標識符有下劃線和字母開頭

54、，后面可以為數(shù)字或字母。</p><p>　　(4)<常量> -> <整型常量> | <浮點型常量> | <字符常量> | <字符串常量> | <布爾常量></p><p>　　釋義：常量由整型常量、浮點型常量、字符常量、字符串常量和布爾常量構成。</p><p>　　3.1.3 mini

55、C語法規(guī)則定義</p><p>　　(1)S –> $ | FunctionDefinition </p><p>　　| FunctionImplement </p><p>　　| GlobalVariableDefinition</p><p>　　釋義：預處理之后的源程序由函數(shù)聲明、函數(shù)實現(xiàn)、全局變量定義，并且開始符號可以推導出

56、空。</p><p>　　(2)FunctionDefinition -> MemoryType DataType Id ( ParameterList ) ;</p><p>　　釋義：函數(shù)定義依次由存儲類別、數(shù)據(jù)類型、函數(shù)名、小括號內的形參表列及分號順序構成。</p><p>　　(3)FunctionImplement -> MemoryType

57、DataType Id ( ParameterList ) { FunctionBody }</p><p>　　釋義：函數(shù)實現(xiàn)依次由存儲類別、數(shù)據(jù)類型、函數(shù)名、小括號內的形參表列及大括號內的函數(shù)體順序構成。</p><p>　　(4)GlobalVariableDefinition -> MemoryType DataType VariableList ;</p>&

58、lt;p>　　釋義：全局變量定義依次由存儲類別、數(shù)據(jù)類型、變量列表及分號順序構成。</p><p>　　(5)MemoryType -> auto | static | register | extern | $</p><p>　　釋義：存儲類別由auto、static、register和extern組成，存儲類別可以為空。</p><p>　　(6)

59、DataType -> int | char | float | double</p><p>　　釋義：數(shù)據(jù)類型有int、char、float和double構成。</p><p>　　(7)VariableList –> VariableData | VariableList , VariableData</p><p>　　釋義：變量列表規(guī)則：變量名

60、 ( = 表達式 ) [ , 變量名 ( = 表達式 ) … ]。</p><p>　　(8)VariableData -> variableName | variableName = Express</p><p>　　釋義：變量列表項可以由變量名等于表達式或單獨一個變量名構成。</p><p>　　(9)ParameterList -> $ | Pa

61、rameterData | ParameterList , ParameterData</p><p>　　釋義：形參表列規(guī)則為：數(shù)據(jù)類型 ( 參數(shù)名 ) [ , 數(shù)據(jù)類型 ( 參數(shù)名 ) … ]，parameterName為參數(shù)名。</p><p>　　(10)ParameterData -> DataType | DataType parameterName</p>

62、<p>　　釋義：形參表列項由數(shù)據(jù)類型加參數(shù)名或單獨一個參數(shù)名構成。</p><p>　　(11)FunctionBody -> $ | RunStatement FunctionBody</p><p>　　釋義：函數(shù)體由N個執(zhí)行語句構成，N>=0。</p><p>　　(12)RunStatement -> Express ; &l

63、t;/p><p>　　| MemoryType DataType VariableList ;</p><p>　　| if ( Express ) StatementBody</p><p>　　| if ( Express ) StatementBody1 else StatementBody2</p><p>　　| while ( Exp

64、ress ) StatementBody</p><p>　　| do StatementBody while ( Express ) ;</p><p>　　| for ( Express1 , Express2 , Express3 ) StatementBody</p><p><b>　　| break ;</b></p>

65、<p>　　| continue ;</p><p>　　| return Express ;</p><p>　　| print ( String ) ;</p><p>　　| print ( Express ) ;</p><p>　　| scan ( id ) ;</p><p>　　釋義：執(zhí)行語句

66、可以是表達式、局部變量定義、if語句、if-else語句、while循環(huán)語句、do-while循環(huán)語句、for循環(huán)語句、break跳出循環(huán)語句、continue終止當前循環(huán)語句、return返回語句、print控制臺打印語句以及scan控制臺輸入語句構成。</p><p>　　(13)StatementBody -> RunStatement | { RunStatement* }</p>&

67、lt;p>　　釋義：執(zhí)行語句體可以是單獨一條執(zhí)行語句或是大括號內N條執(zhí)行語句構成，N>=0。</p><p>　　(14)Express -> EqualExprress</p><p>　　釋義：在miniC語言中賦值表達式、布爾表達式、關系表達式和算術表達式統(tǒng)一按照表達式來處理不再區(qū)分，表達式間根據(jù)運算符的優(yōu)先級從低到高的順序依次推導生成。</p>&l

68、t;p>　　(15)EqualExpress -> BoolExpress | EqualExpress Ao BoolExpress</p><p>　　釋義：賦值表達式由賦值運算符加上布爾表達式或者是單獨一個布爾表達式構成，在miniC語言中存在連等操作。</p><p>　　(16)Ao -> = | += | -= | *= | /=</p><

69、;p>　　釋義：賦值運算符由=、+=、-=、*=和/=構成。</p><p>　　(17)BoolExpress -> BoolTerm | BoolExpress ||[或] BoolTerm</p><p>　　釋義：布爾表達式由邏輯或運算符加上布爾項或者是單獨一個布爾項構成。</p><p>　　(18)BoolTerm -> Relatio

70、nExpress | BoolTerm && RelationExpress</p><p>　　釋義：布爾項由邏輯與運算符加上關系表達式或者是單獨一個關系表達式構成。</p><p>　　(19)RelationExpress -> ArithmeticExpress</p><p>　　| ArithmeticExpress != Ari

71、thmeticExpress</p><p>　　| ArithmeticExpress == ArithmeticExpress</p><p>　　| ArithmeticExpress < ArithmeticExpress</p><p>　　| ArithmeticExpress > ArithmeticExpress</p>&

72、lt;p>　　| ArithmeticExpress <= ArithmeticExpress</p><p>　　| ArithmeticExpress >= ArithmeticExpress</p><p>　　釋義：關系表達式由兩個算術表達式進行關系運算或者是單獨一個算術表達式構成。</p><p>　　(20)ArithmeticExpr

73、ess -> ArithmeticTerm</p><p>　　| ArithmeticExpress + ArithmeticTerm</p><p>　　| ArithmeticExpress – ArithmeticTerm</p><p>　　釋義：算術表達式由加、減運算符加上算術表項或者是單獨一個算術表項構成。</p><p>

74、;　　(21)ArithmeticTerm -> ArithmeticFactor</p><p>　　| ArithmeticTerm * ArithmeticFactor</p><p>　　| ArithmeticTerm / ArithmeticFactor</p><p>　　| ArithmeticTerm % ArithmeticFactor&l

75、t;/p><p>　　釋義：算術表項由乘、除、取余運算符加上算術因子或者是單獨一個算術因子構成。</p><p>　　(22)ArithmeticFactor -> ArithmeticAel</p><p>　　| ! ArithmeticAel</p><p>　　釋義：算術因子由邏輯非運算符加上算術原子或者是單獨一個算術原子構成。&l

76、t;/p><p>　　(23)ArithmeticAel -> ( BoolExpress )</p><p><b>　　| Root</b></p><p>　　釋義：算術原子由小括號內的布爾表達式或者是算術根構成。</p><p>　　(24)Root -> id | 整型[八進制、十進制、十六進制] |

77、浮點型[小數(shù)、指數(shù)] | BOOL | 字符型</p><p>　　釋義：算術根由標識符、整型常量[八進制、十進制、十六進制]、浮點型常量[小數(shù)、指數(shù)]、布爾常量及字符型常量構成。</p><p>　　(25)BOOL -> true | false</p><p>　　釋義：布爾常量由true、false構成。</p><p><

78、;b>　　3.2 功能需求</b></p><p>　　3.2.1 可視化界面</p><p>　　該系統(tǒng)需要對編譯過程中的抽象處理通過圖形用戶界面的形式展示給用戶，因此需要界面優(yōu)化，操作簡單，核心算法高效準確，需要對用戶的錯誤操作做出提示，對用戶編寫的源代碼提供各部分功能的異常處理。</p><p>　　3.2.2 適合教學</p>

79、<p>　　該系統(tǒng)能夠輸出miniC語言編譯各個階段的中間結果和最終結果。有編譯各階段的多種算法展示，可以作為編譯原理課程的教學輔助系統(tǒng)。</p><p>　　3.2.3 高效準確的算法設計</p><p>　　該系統(tǒng)是針對miniC語言進行編譯處理，并得到各個部分的分析結果，需要對編譯過程的每個部分設計出相應的算法實現(xiàn)其功能，為了使系統(tǒng)穩(wěn)定、高效、容錯性高，必須設計出準確高效

80、的算法結構，算法中不能包含死循環(huán)導致系統(tǒng)崩潰。</p><p>　　3.2.4 系統(tǒng)功能需求</p><p>　　詞法分析：要求對mimiC語言進行單詞的識別，通過程序作圖方式展示正規(guī)式到有窮自動機轉換的算法。</p><p>　　語法分析：對詞法分析階段生成的Token串進行語法結構分析，至少使用2種語法分析算法完成語法分析功能。</p><p

81、>　　語義分析及中間代碼生成：要求使用語法指導的語義分析方法進行該階段的分析，輸出語義分析錯誤，生成中間代碼和函數(shù)聲明與實現(xiàn)、變量定義相關數(shù)據(jù)結構。</p><p>　　代碼優(yōu)化：尋找至少一種代碼優(yōu)化方法，實現(xiàn)代碼優(yōu)化的目的，提高代碼的運行效率。</p><p>　　目標代碼生成：選擇當前任意一個操作系統(tǒng)平臺，生成符合該平臺的匯編代碼或可執(zhí)行程序，能夠在該平臺執(zhí)行出miniC語言的運

82、行結果。</p><p>　　3.2.5 完整的系統(tǒng)功能</p><p>　　該系統(tǒng)是針對miniC語言這門自定義的編程語言進行編譯，涉及到編譯過程中詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化和目標代碼生成五部分</p><p><b>　　3.3 其它需求</b></p><p>　　該系統(tǒng)需要在Window

83、s平臺下穩(wěn)定運行，各部分功能的響應度高，可以在Intel X86處理器上執(zhí)行相應程序。</p><p><b>　　3.4 需求分析</b></p><p>　　3.4.1 系統(tǒng)的結構分析</p><p>　　該系統(tǒng)的功能是實現(xiàn)編譯原理可視化，將編譯過程中的詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化、目標代碼生成的五部分分析過程通過可

84、視化界面展現(xiàn)出來。該系統(tǒng)需要對編譯過程的五部分逐一分析，并將分析結果保存在文件或數(shù)據(jù)庫中。系統(tǒng)的圖像化界面會將分析結果從文件或數(shù)據(jù)庫中讀取出來并顯示。</p><p>　　3.4.2 miniC語言分析</p><p>　　設計編程語言：每一款編譯軟件都是針對一種特定的語言進行分析處理的，在設計編譯軟件之前需要先設計編程語言。該系統(tǒng)是針對miniC語言進行編譯，miniC語言是非常接近C語

85、言的一種自定義語言，但miniC語言不涉及C語言中的指針和數(shù)組相關文法。設計完成miniC語言后就可以進行系統(tǒng)的整體設計了。</p><p>　　3.4.3 系統(tǒng)功能分析</p><p>　　詞法分析階段：該階段需要對源文件進行分析識別，通常使用狀態(tài)轉化圖法進行詞法分析的識別。識別出的單詞以Token串的形式保存在文件或數(shù)據(jù)庫中，Token類通常包含的屬性為編號、內容、類別、是否識別錯誤等

86、。該階段需要先設計出識別單詞的狀態(tài)換圖，然后根據(jù)狀態(tài)轉換圖實現(xiàn)詞法分析的核心算法。</p><p>　　語法分析階段：該階段需要以詞法分析階段的結果Token串為基礎進行語法分析，判斷源代碼是否存在語法錯誤。語法分析算法有很多，但任何一種分析方法都是基于miniC語言的文法，因此在實現(xiàn)語法分析之前需要先根據(jù)miniC語言的語法規(guī)則設計出相應的文法，然后使用LL1預測分析法和遞歸下降分析法完成語法分析的規(guī)則。結果以

87、分析表的方式保存。</p><p>　　詞法分析和中間代碼生成階段：該階段一般使用的實現(xiàn)方法是遞歸下降法，該系統(tǒng)同樣也是使用遞歸下降法進行分析實現(xiàn)的，結果采用四元式和符號表的方式保存。</p><p>　　代碼優(yōu)化階段：代碼優(yōu)化是對源代碼或上一階段生成的中間代碼進行等價變換，使優(yōu)化的程序生成更加簡潔和高效的代碼。該階段會根據(jù)中間代碼生成階段的規(guī)則進行優(yōu)化，修改、刪除中間代碼中無效的跳轉。&

88、lt;/p><p>　　目標代碼生成階段：該階段是將中間代碼結合相應的平臺轉換為匯編代碼。</p><p>　　平臺編譯階段：該系統(tǒng)設計在Windows平臺上，需要結合Windows和對應處理器生成可以在該平臺下直接運行的程序。</p><p><b>　　4 總體設計</b></p><p>　　4.1 系統(tǒng)整體結構設計&

89、lt;/p><p>　　miniC編譯過程可視化系統(tǒng)包含五方面的功能：詞法分析功能、語法分析功能、語義分析及中間代碼生成功能和目標代碼生成五個核心功能，如圖4-1所示。這些功能也與編譯原理的分析過程一一對應。每個功能模塊下面還會提供多個解決方案，給用戶的使用提供更多的選擇。</p><p>　　圖4-1 系統(tǒng)整體架構圖</p><p>　　4.2 系統(tǒng)模塊化設計與調用關

90、系</p><p>　　系統(tǒng)分為兩部分，如圖4-2所示。一部分是編譯原理分析的核心程序，用于對編譯過程各個部分進行分析處理；另一部分是圖像化界面，用于顯示分析結果和用戶操作。</p><p>　　編譯原理分析的核心程序與圖形用戶界面分開的好處：1.使系統(tǒng)各部分的分工更加明確，各部分的數(shù)據(jù)結構互相不干擾；2.使系統(tǒng)的可擴展性更高，當系統(tǒng)的可視化界面不僅僅需要在本地顯示，而需要通過網(wǎng)絡協(xié)議演示

91、時，編譯原理的核心程序可以復用，提高了程序的擴展性；3.類似于“前臺”與“后臺”的系統(tǒng)結構設計，有利于后期維護。</p><p>　　圖4-2 系統(tǒng)模塊化設計與數(shù)據(jù)流圖</p><p><b>　　5 詳細設計</b></p><p><b>　　5.1 詞法分析</b></p><p>　　5.1

92、.1 miniC語言的詞法分析</p><p>　　(1)miniC語言單詞規(guī)則研究與設計</p><p>　　在miniC語言中單詞基本上都是由ASCII碼表中的部分字符構成，其他字符（比如Unicode、UTF-8、UTF-16、UTF-32等編碼方式下的字符）在分析過程中均視為意外字符，如果意外字符出現(xiàn)在源程序文件（詞法分析的輸入）的注釋中則忽略該字符，否則按照異常字符處理。<

93、/p><p><b>　　(2)字符分類</b></p><p>　　ASCII碼表中[0-31]字符：這32個字符中只有[9]制表符和[10]回車符可以允許用戶通過鍵盤輸入到源程序文件中存儲，其它的字符均為操作系統(tǒng)提供給用戶的操作字符，因而不會出現(xiàn)在源程序中，在設計詞法分析規(guī)則時，將這些系統(tǒng)操作字符忽略掉，不再分析識別。</p><p>　　AS

94、CII碼表中[32-127]字符：這部分字符中[127]字符無法從鍵盤中輸入，也不再分析；其他字符全部都需要進行分析，根據(jù)這些字符在源程序中作用范圍進行分類，分類分析方式如下：</p><p>　　空界符： [32]空格符，前32個字符中[9]制表符和[10]回車符同樣也是空界符。這類字符在詞法分析過程中作為單詞與單詞之間的分隔符，分隔符不會構成單詞，當在詞法分析過程中遇到這些字符時就說明上一個單詞已經(jīng)分析結束，

95、需要將單詞緩沖區(qū)中的內容保存到Token串中，并清空單詞緩沖區(qū)的內容，進而分析下一個單詞。</p><p>　　實界符（既是分隔符，又是具備一定意義的字符）：</p><p>　　這類字符包括：[34]雙撇號</p><p>　　[35]井號（在預處理階段用到）</p><p>　　[36]$美元符號（在語法分析的文法設計中會用到，在這里當做

96、異常字符處理） 異常字符處理</p><p><b>　　[39]單撇號</b></p><p><b>　　[40]左小括號</b></p><p><b>　　[41]右小括號</b></p><p><b>　　[44]逗號</b></p>

97、;<p>　　[46]點號（或英文句號）</p><p><b>　　[59]分號</b></p><p>　　[64]@符號 異常字符處理</p><p><b>　　[91]左中括號</b></p><p><b>　　[92]反斜杠</b></p>

98、;<p><b>　　[93]右中括號</b></p><p>　　[96]點好 異常字符處理</p><p><b>　　[123]左大括號</b></p><p><b>　　[125]右大括號</b></p><p>　　[126]波浪符號 （面向對象的析構

99、符）</p><p>　　這些字符在詞法分析過程中會單獨構成一個單詞，并且和空界符一樣，也會作為分隔符將前后兩個單詞分開。在這部分中有一些字符為異常字符，當詞法分析程序識別出這些異常字符時會提示錯誤，不在將這些異常字符構造成單詞添加到Token串中，但這些字符會和其他字符一樣起到分隔符的作用。</p><p>　　運算符（在表達式中出現(xiàn)的字符，并且具備一定意義）：</p>&

100、lt;p>　　這類字符包括：[33]邏輯非</p><p><b>　　[37]取余運算符</b></p><p><b>　　[38]地址運算符</b></p><p>　　[42]乘算術運算符</p><p>　　[43]加算術運算符</p><p>　　[45]減

101、算術運算符</p><p>　　[47]除算術運算符</p><p><b>　　[58]冒號</b></p><p>　　[60]小于關系運算符</p><p>　　[61]等于賦值運算符</p><p>　　[62]大于關系運算符</p><p>　　[63]問號（可以

102、和前面的冒號構成“: ?”選擇結構）</p><p><b>　　[94]與運算符</b></p><p><b>　　[124]或運算符</b></p><p><b>　　數(shù)字：0-9</b></p><p>　　這類字符包括：[48]~[57]總共10個字符</p&

103、gt;<p>　　這些字符可以構成用戶定義變量和數(shù)字常量</p><p>　　字母：a-z、A-Z、下劃線</p><p>　　這類字符包括：[65]~[90]、[97]~[122]、[95]</p><p>　　這類字符可以和數(shù)字類字符過程用戶定義變量。</p><p>　　(4)miniC語言單詞的種別碼</p>

104、<p>　　表5-1 miniC語言單詞的種別碼</p><p>　　5.1.2 miniC語言詞法分析狀態(tài)轉化圖設計</p><p>　　詞法分析階段通常使用狀態(tài)轉換圖的方法完成詞法分析核心程序設計。以miniC語言字符集和單詞構造規(guī)則的定義為基礎，設計出適用于miniC語言詞法分析的狀態(tài)轉換圖，如圖5-1~圖5-15所示。</p><p>　　(1

105、)數(shù)字常量識別狀態(tài)轉換圖</p><p>　　圖5-1 處理數(shù)字常量（指數(shù)、小數(shù)、八進制、十進制、十六進制）狀態(tài)轉換</p><p>　　(2)字符常量識別狀態(tài)轉換圖</p><p>　　圖5-2 處理字符常量的狀態(tài)轉換圖</p><p>　　(3)字符串常量識別狀態(tài)轉換圖</p><p>　　圖5-3 處理字符串常量

106、的狀態(tài)轉換圖</p><p>　　(4)運算符識別狀態(tài)轉換圖</p><p>　　圖5-4 邏輯非、不等于的狀態(tài)轉換圖</p><p>　　圖5-5 取余、取余等于的狀態(tài)轉換圖</p><p>　　圖5-6 等于、是否等于的狀態(tài)轉換圖圖5-7 位異或、異或等于的狀態(tài)轉換圖</p><p>　　圖5-8 位與、位與等于、

107、邏輯與的狀態(tài)轉換圖</p><p>　　圖5-9 加、加等于、自加的狀態(tài)轉換圖</p><p>　　圖5-10 減、減等于、自減的狀態(tài)轉換圖</p><p>　　圖5-11 位或、位或等于、邏輯或的狀態(tài)轉換圖</p><p>　　圖5-12 小于、小于等于、左移的狀態(tài)轉換圖</p><p>　　圖5-13 大于、大于等

108、于、右移的狀態(tài)轉換圖</p><p>　　圖5-14 乘、乘等于、塊注釋右部的狀態(tài)轉換圖</p><p>　　圖5-15 除、除等于、塊注釋左部、行注釋狀態(tài)轉換圖</p><p>　　5.1.3 詞法分析數(shù)據(jù)結構設計</p><p>　　詞法分析功能將源程序的分析結果保存在一個鏈表中，該鏈表的結點為Token數(shù)據(jù)結構。Token數(shù)據(jù)結構將會在

109、詞法分析階段、語法分析階段和語義分析及中間代碼生成階段中多次使用。Token數(shù)據(jù)結構在該系統(tǒng)中非常重要，承接著編譯前端的各個功能，該數(shù)據(jù)結構的定義如圖5-16所示。</p><p>　　圖5-16 Token數(shù)據(jù)結構定義（C++定義）</p><p>　　類Token定義了Token的屬性和常用方法,該數(shù)據(jù)結構在該系統(tǒng)中非常重要。Token類會在詞法分析整個過程中使用，語法分析使用LL(1

110、)預測分析法時，獲取保存文法、求得First集、Follow集、構造預測分析表以及預測分析核心程序多次使用到，并且還會在語義分析及中間代碼生成階段使用進行相關分析。Token類中的data和type屬性搭配使用會使該系統(tǒng)更簡單、高效。</p><p>　　5.1.4 miniC語言詞法分析核心程序設計</p><p>　　miniC語言詞法分析核心程序是根據(jù)miniC詞法分析狀態(tài)轉換圖的定

111、義來完成的。該核心程序是按照行來分析處理源代碼，如圖5-17所示。該流程圖展示了源程序大致的處理過程，具體的分析處理參照上一節(jié)miniC詞法分析狀態(tài)轉換圖。</p><p>　　圖5-17 miniC詞法分析核心程序流程圖</p><p>　　5.1.5 正規(guī)式->NFA->DFA功能</p><p><b>　　(1)模塊功能概述</b

112、></p><p>　　在詞法分析階段有幾個非常重要的概念，正規(guī)文法、正規(guī)式、有窮自動機，有窮自動機又分為不確定的有窮自動機和確定的有窮自動機。詞法分析階段有相應的算法可以將正規(guī)式轉換為不確定的有窮自動機，將不確定的有窮自動機轉換為確定的有窮自動機。該模塊的功能是按照這些算法將正規(guī)式通過計算機程序分析處理轉換為不確定的有窮自動機，再轉換為確定的有窮自動機，有窮自動機可以通過文本和圖形兩種方式表示，該功能是通

113、過圖形方式表示有窮自動機。</p><p>　　(2)正規(guī)式分析方法</p><p>　　正規(guī)式的規(guī)則大致可以分為五種：</p><p><b>　　e代表一個轉換過程</b></p><p>　　(e)表示將該過程按照一個整體來處理</p><p>　　e1·e2表示e1和e2兩個過程

114、的順序疊加，中間的點號可以省略</p><p>　　e1|e2或的關系，表示e1和e2兩個過程的并行疊加</p><p>　　e*表示e過程重復N次，N大于等于0</p><p>　　正規(guī)式符合上述規(guī)則的同時，還滿足交換律、結合律和分配律這三種代數(shù)規(guī)律。在完成正規(guī)式轉換為有窮自動機功能時，并沒有常規(guī)的計算機算法作為參考設計相應的程序，需要對正規(guī)式分析處理為其它的表示

115、形式才能完成該功能。</p><p>　　通過對多組正規(guī)式分析整理，我們可以得出正規(guī)式的五個規(guī)則附加的權重是不同的。正規(guī)式的規(guī)則按照權重由高到低依次為：(e)、e*、e1|e2、e1·e2、e，我們可以按照正規(guī)式規(guī)則的權重由低到高構造出正規(guī)式分析樹。</p><p>　　(3)構建正規(guī)式分析樹</p><p>　　正規(guī)式分析樹構建步驟：</p>

116、<p>　　1．正規(guī)式分析樹是二叉樹，二叉樹中的每個結點都按照二叉樹來處理。</p><p>　　2．小括號中的內容按照一個整體來處理。</p><p>　　3．正規(guī)式中是否存在|關系，如果存在將正規(guī)是分割成兩個子結點。</p><p>　　4．正規(guī)式中是否存在·關系，如果存在將正規(guī)式分割成兩個子結點。</p><p>

117、;　　5．正規(guī)式中最外層是*關系，將*和元素分開。</p><p>　　6．正規(guī)式最外層是括號，將括號去掉按照正規(guī)式處理。</p><p><b>　　5.2 語法分析</b></p><p>　　5.2.1 語法分析功能結構圖</p><p>　　miniC語言語法分析階段的核心算法有兩種，LL(1)預測分析法和遞歸下