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

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

2、><p>　　專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級 11203070A </p><p>　　學(xué)生姓名 學(xué)號11203070237 </p><p>　　指導(dǎo)教師 黃賢英 職稱 教授 </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 國內(nèi)外研究現(xiàn)狀1</p><p>　　1.3 研究目的與研究內(nèi)容2</p><p>　　2 開發(fā)技術(shù)與原理簡介3</p><p>　　2.1 原理簡介3</p><p>　　2.2 開發(fā)技術(shù)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 適合教學(xué)9</p><p>　　3.2.3 高效準(zhǔn)確的算法設(shè)計(jì)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)的結(jié)構(gòu)分析10</p><p>　　3.4.2 miniC語言分析10</p><p>　　3.4.3 系統(tǒng)功能分析11</p><p><b>　　4 總體設(shè)計(jì)12</b></p><p

8、>　　4.1 系統(tǒng)整體結(jié)構(gòu)設(shè)計(jì)12</p><p>　　4.2 系統(tǒng)模塊化設(shè)計(jì)與調(diào)用關(guān)系12</p><p><b>　　5 詳細(xì)設(shè)計(jì)14</b></p><p>　　5.1 詞法分析14</p><p>　　5.1.1 miniC語言的詞法分析14</p><p>　　5.1.2

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

10、;　　5.2.1 語法分析功能結(jié)構(gòu)圖25</p><p>　　5.2.2 miniC語言結(jié)構(gòu)文法定義25</p><p>　　5.2.3miniC表達(dá)式文法定義32</p><p>　　5.2.4 預(yù)測分析法（語法分析方案一）38</p><p>　　5.2.5 遞歸下降進(jìn)行語法分析（語法分析方案二）43</p>&

11、lt;p>　　5.2.6 遞歸下降與LL(1)預(yù)測分析法混合使用（語法分析方案三）43</p><p>　　5.2.7 遞歸下降與LL(1)預(yù)測分析法混合使用（語法分析方案四）44</p><p>　　5.2.8 文法改進(jìn)后的LL(1)預(yù)測分析（語法分析方案五）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)化算法設(shè)計(jì)57</p><p>　　5.5 目標(biāo)代碼生成58</p><p>　　5.5.1 目標(biāo)代碼生成階段設(shè)計(jì)思路58</p><p>　　5.5.2 中間代碼翻譯為目標(biāo)代碼規(guī)則58</p><p>　　5.6 平臺編譯60</p><p

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

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

16、2 功能與核心程序?qū)?yīng)規(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)測試源碼設(shè)計(jì)72</p><p>　　7.4 測試結(jié)果72</

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

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

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

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

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

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

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

24、理地使用了軟件設(shè)計(jì)模式，系統(tǒng)具有良好的可擴(kuò)展性，對于編譯原理理論的研究和相關(guān)算法的開發(fā)和改進(jìn)都有很大的幫助。該系統(tǒng)性能穩(wěn)定、有一套完整異常處理方案、可以實(shí)現(xiàn)用戶需求的所有功能。該論文詳細(xì)的介紹了miniC編譯原理可視化系統(tǒng)開發(fā)的理論依據(jù)，使用的工具，設(shè)計(jì)方法，面向?qū)ο蟮念惤Y(jié)構(gòu)等內(nèi)容，有助于該系統(tǒng)的使用和改進(jìn)。</p><p>　　關(guān)鍵詞：編譯 輔助教學(xué) 可視化 系統(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>　　隨著當(dāng)前計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)行業(yè)的飛速發(fā)展，物聯(lián)網(wǎng)產(chǎn)品的需求日益增多，計(jì)算機(jī)產(chǎn)品與計(jì)算機(jī)服務(wù)已經(jīng)被廣大用戶接受并逐漸形成一種依賴。編譯原理作為一門計(jì)算機(jī)科學(xué)與技術(shù)的專業(yè)的基礎(chǔ)學(xué)科，它的學(xué)習(xí)難度較大，但是對于計(jì)算機(jī)專業(yè)的學(xué)生來說非常重要。不論是物聯(lián)網(wǎng)產(chǎn)品還是互聯(lián)網(wǎng)服務(wù)，都離不開計(jì)算機(jī)專業(yè)工程師的不斷努力，隨著計(jì)算機(jī)新技術(shù)的層出不窮和處理器

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

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

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

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

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

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

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

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

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

43、>　　miniC編譯過程可視化系統(tǒng)是一個具有用戶操作界面的系統(tǒng)，在開發(fā)過程中需要將核心算法和界面分開。該系統(tǒng)使用C++編程語言并結(jié)合STL類庫開發(fā)出系統(tǒng)相關(guān)功能的核心代碼，使用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程序的設(shè)計(jì)與開發(fā)。該系統(tǒng)需要使用C++語言設(shè)計(jì)核心算法程序并使用C#語言設(shè)計(jì)圖形用戶界面程序，Visual Studio 2015支持這兩種語言的程序開發(fā)設(shè)計(jì)，恰巧滿足了系統(tǒng)的開發(fā)需要，同時也避免了使用多款I(lǐng)DE開發(fā)程序間不兼容情況的發(fā)生。MASM的功能是將適用于Windows平臺

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

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

47、界面使用C#Winform進(jìn)行設(shè)計(jì)開發(fā)。Winform開發(fā)相比于MFC開發(fā)更加高效，簡單，更利于維護(hù)。</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ù)字及一些特殊符號構(gòu)成。</p><p>　　(2)<字母> -> a|b|c···|z|A|B|C&

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

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

51、 | <界符></p><p>　　釋義：miniC語言中的單詞可分為關(guān)鍵詞、標(biāo)識符、常量、運(yùn)算符和界符共5類單詞。</p><p>　　(2)<關(guān)鍵詞> -> 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個關(guān)鍵詞。</p><p>　　(3)<標(biāo)識符> -> <_下劃線> | <字母> | <標(biāo)識符><字母> | <標(biāo)識符><數(shù)字></p><p>　　釋義：標(biāo)識符有下劃線和字母開頭

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

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

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

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

58、lt;p>　　釋義：全局變量定義依次由存儲類別、數(shù)據(jù)類型、變量列表及分號順序構(gòu)成。</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構(gòu)成。</p><p>　　(7)VariableList –> VariableData | VariableList , VariableData</p><p>　　釋義：變量列表規(guī)則：變量名

60、 ( = 表達(dá)式 ) [ , 變量名 ( = 表達(dá)式 ) … ]。</p><p>　　(8)VariableData -> variableName | variableName = Express</p><p>　　釋義：變量列表項(xiàng)可以由變量名等于表達(dá)式或單獨(dú)一個變量名構(gòu)成。</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>　　釋義：形參表列項(xiàng)由數(shù)據(jù)類型加參數(shù)名或單獨(dú)一個參數(shù)名構(gòu)成。</p><p>　　(11)FunctionBody -> $ | RunStatement FunctionBody</p><p>　　釋義：函數(shù)體由N個執(zhí)行語句構(gòu)成，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、可以是表達(dá)式、局部變量定義、if語句、if-else語句、while循環(huán)語句、do-while循環(huán)語句、for循環(huán)語句、break跳出循環(huán)語句、continue終止當(dāng)前循環(huán)語句、return返回語句、print控制臺打印語句以及scan控制臺輸入語句構(gòu)成。</p><p>　　(13)StatementBody -> RunStatement | { RunStatement* }</p>&

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

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

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

70、nExpress | BoolTerm && RelationExpress</p><p>　　釋義：布爾項(xiàng)由邏輯與運(yùn)算符加上關(guān)系表達(dá)式或者是單獨(dú)一個關(guān)系表達(dá)式構(gòu)成。</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>　　釋義：關(guān)系表達(dá)式由兩個算術(shù)表達(dá)式進(jìn)行關(guān)系運(yùn)算或者是單獨(dú)一個算術(shù)表達(dá)式構(gòu)成。</p><p>　　(20)ArithmeticExpr

73、ess -> ArithmeticTerm</p><p>　　| ArithmeticExpress + ArithmeticTerm</p><p>　　| ArithmeticExpress – ArithmeticTerm</p><p>　　釋義：算術(shù)表達(dá)式由加、減運(yùn)算符加上算術(shù)表項(xiàng)或者是單獨(dú)一個算術(shù)表項(xiàng)構(gòu)成。</p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

92、.1 miniC語言的詞法分析</p><p>　　(1)miniC語言單詞規(guī)則研究與設(shè)計(jì)</p><p>　　在miniC語言中單詞基本上都是由ASCII碼表中的部分字符構(gòu)成，其他字符（比如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)在源程序中，在設(shè)計(jì)詞法分析規(guī)則時，將這些系統(tǒng)操作字符忽略掉，不再分析識別。</p><p>　　AS

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

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

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]點(diǎn)號（或英文句號）</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]點(diǎn)好 異常字符處理</p><p><b>　　[123]左大括號</b></p><p><b>　　[125]右大括號</b></p><p>　　[126]波浪符號 （面向?qū)ο蟮奈鰳?gòu)

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

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

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

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

103、gt;<p>　　這些字符可以構(gòu)成用戶定義變量和數(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)轉(zhuǎn)化圖設(shè)計(jì)</p><p>　　詞法分析階段通常使用狀態(tài)轉(zhuǎn)換圖的方法完成詞法分析核心程序設(shè)計(jì)。以miniC語言字符集和單詞構(gòu)造規(guī)則的定義為基礎(chǔ)，設(shè)計(jì)出適用于miniC語言詞法分析的狀態(tài)轉(zhuǎn)換圖，如圖5-1~圖5-15所示。</p><p>　　(1

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

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

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

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

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

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

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

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

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

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

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

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

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