畢業(yè)設計（論文）-基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現.doc

基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現摘要本設計實現了一個編譯器前端，它將一個用C語言的子語言編寫的源程序翻譯成中間代碼。詞法分析器、語法分析器、中間代碼生成器均是采用C+語言手動書寫完成，未采用自動生成器，GUI采用Win32 API實現以保證輕快的運行速度及良好的系統(tǒng)性能，編輯控件采用Scintilla。詞法分析器采用確定有限自動機實現，語法分析器是一個遞歸下降分析器，中間代碼生成器輸出的中間代碼以四元式形式表示。本設計實現的編譯器前端，運行在Windows平臺下，Windows系統(tǒng)版本為Windows XP、Windows 7或更高版本。本設計提供了一個可工作的界面友好的編譯器前端，可以用來理解編譯原理及解釋怎樣用一種語言如C+實現編譯器前端，以供學習和教學所用。關鍵詞：編譯器前端；GUI；C+Design & Implementation of Intermediate Code Generator of Interactive Compilation System Based GUIAbstractThis final project implements a compiler front-end, it translates source programs written in a subset of the C language into intermediate code. The lexer、parser and intermediate code generator are all hand-written in C+, no auto lexer or parser are used, GUI is implemented in Win32 API for fast running speed and high performance, and edit control uses Scintilla. The lexer is implemented in Deterministic finite automata,the parser is a recursive-descent parser, the intermediate codes are represented in quadruple。The compiler front-endruns on the Windows platform, Windows system version is Windows XP, Windows 7 or later.This project provide a working and user interface friendly compiler front-end, which can be used to demonstrate compiler principle and how compilers can be implementedin a language such as C+, for learning and teaching.Keywords: compiler front-end; GUI; C+目錄1 緒論12 基本原理32.1 詞法分析42.1.1 詞法分析結果42.1.2 確定有限自動機52.2 語法分析52.2.1 遞歸下降分析法62.2.2 運算符的優(yōu)先級82.3 中間代碼生成92.3.1 四元式92.3.2 四元式的常見結構102.4 符號表142.4.1 作用域152.4.2 局部變量名的存儲布局163 設計與實現173.1 C子語言173.1.1數據類型173.1.2 字面值173.1.3 表達式173.1.4 語句183.1.5 函數183.2 符號表193.3 詞法分析器243.4 語法分析器263.5 中間代碼生成器283.6 GUI304 測試36總結41參考文獻42致謝43附錄源程序44附件1：開題報告（文獻綜述）附件2：譯文及原文影印件1 緒論很少有人去自己編寫或修改編譯器，那么為什么要去實現編譯器前端呢？很重要的一點就是，理解計算機程序怎樣被編譯以及執(zhí)行，可以幫助任何程序員理解他們寫的代碼是怎樣驅動計算機的，從而幫助他們寫出更快、更高效的程序。編譯原理經過多年發(fā)展已日趨成熟，然而現代很多跟編譯原理相關的教材，內容陳舊落后，比如以Fortran或Pascal等過時語言為例進行分析講解，或者全書充滿晦澀難懂的定理公式，不能以直觀的方式進行闡述，致使學生望而生畏。本設計用C+語言實現了一個編譯器前端，它將一個用C子語言編寫的源程序翻譯成中間代碼，擁有友好直觀的交互式圖形界面，有助于對編譯原理的理解，可用于學習及教學。在一段程序可以執(zhí)行之前，首先需要把它翻譯成一種其能夠被計算機接受的形式，完成這項翻譯工作的程序稱為編譯器（compiler）1。簡單而言，編譯器是一個程序，它將使用源語言編寫的程序轉換成另一種目標語言。在轉換階段很重要的一部分是報告用戶當前源程序的錯誤。為了將源程序從一種語言翻譯成另一種語言，編譯器必須首先把程序的各種成分拆開，并搞清其結構和含義，然后再把這些成分組合成有意義的計算機能識別的語言。編譯器的前端進行詞法分析、語法分析和語義分析，并且產生中間代碼，即進行分析。編譯器的后端對中間代碼進行優(yōu)化并將中間代碼翻譯成機器語言，即進行組合。詞法分析的任務是：對源程序進行從左到右逐個字符地掃描，產生一個個獨立的單詞符號（token）。詞法分析是編譯的基礎。語法分析的任務是：在詞法分析識別出一系列單詞符號的基礎上，分析并判定源程序的結構是否符合語法規(guī)則。語法分析可以粗略地分為兩類，一類是自頂向下，一類是自底向上2。對于本設計，采用的是自頂向下進行分析。語法分析得到語法樹，盡管可以直接將語法樹轉換成目標機器代碼，但這樣做不利于可移植性和模塊化設計。假設需要這樣一個編譯器：它可以編譯N種不同的源語言，然后為M臺不同的目標機生成代碼。理論上，這是N*M個編譯器，如圖1.1(a)，但實現這么多的編譯器是需要花費大量的人力物力。中間代碼（intermediate code, IC）是一種抽象機器語言，它可以表示目標機的操作而不需太多涉及與機器相關的細節(jié)，而且，它也獨立于源語言的細節(jié)3。一個可移植的編譯器如圖1.1(b)所示，它先將源語言轉換成中間代碼，然后再將中間代碼轉化成目標機器語言，這樣便只需要實現N個前端和M個后端。這種實現要更容易合理些。即使在只需實現一個前端和一個后端的情況下，好的中間代碼也利于將系統(tǒng)模塊化，使得編譯器前端不會因機器相關的細節(jié)而復雜化，編譯器后端不會因源語言的特殊信息而干擾。編譯器可以使用的中間代碼有多種形式，對于本設計，采用簡單的四元式。IC(a) (b)圖1.1 面向5種語言并支持4種目標機的編譯器：（a）沒有IC，（b）有IC編譯器的每個階段都可能遇到錯誤，如果編譯器在遇到第一個錯誤時就停止運行，對于修正程序肯定起不到多大幫助作用。詞法分析階段可以檢測出來自輸入的字符串不能形成語言的任何單詞符號（token）。語法分析階段可以檢測出違反語言語法的單詞符號串。本設計可以報告出錯誤是什么及錯誤在源程序的行號和列號。2基本原理一個編譯器是一個計算機程序，它可以把用某種高級語言寫的源代碼轉換成另一種形式，典型的形式是機器碼。機器碼是計算機可以執(zhí)行的一系列指令4。int max(int a, int b)if(a b)return a;return b;一個編譯器由有兩部分組成，如圖2.1所示。（1）源代碼分析器：它將輸入的源代碼看作是一個字符串，然后將其翻譯成有意義的符號（變量，值，操作符等）。（2）目標代碼生成器：它將源代碼分析器的結果轉換成可執(zhí)行代碼。t1 = -ct2 = b * t1t3 = t1 + t2t4 = t3目標代碼源代碼目標代碼生成器源代碼分析器圖2.1 編譯器結構源代碼分析器不依賴于機器，然而目標代碼生成器需要針對不同的機器類型生成不同的代碼，因此是依賴于機器的。源代碼分析器經常被稱作編譯器的前端，目標代碼生成器被稱作后端。本設計要實現的正是編譯器的前端。編譯器的前端又分為三個階段，如圖2.2所示。t1 = -ct2 = b * t1t3 = t1 + t2t4 = t3前端源代碼中間代碼生成器語法分析器詞法分析器圖2.2 編譯器前端2.1 詞法分析詞法分析器以字符流作為輸入，刪除單詞之間的空白符和注釋（程序中每一部分都有可能出現空白和注釋）并生成一系列的名字、關鍵字和標點符號。如果讓語法分析器來處理它們就會使得語法分析過于復雜，結構也不清晰，這便是將詞法分析成為一個獨立階段，從語法分析中分離出去的主要原因5。在詞法分析器中，詞法單元（token）通常包含以下幾種類型： 標識符 保留字（如：“if”，“while”等） 數值常量（如：整數，實數等） 字符串常量 簡單符號（運算符如：“+”，“-”等，分隔符如：“；”，“，”等） 多重符號（運算符如“+=”，“+”等）這些詞法單元將用于下一階段語法分析。2.1.1 詞法分析結果對于下面一段程序：int match(char* str)/ find a zeroif(!strncmp(str, “0”, 1)return 0;詞法分析器將產生如下tokens：INTID(match)LPARENCHARSTARID(str)RPARENLBRACEIFLPARENBANGID(strncmp) LPAREN ID(str) COMMA STRING(0) COMMANUM(1)RPAREN RPAREN RETURN REAL(0)SEMIRBRACEOF2.1.2 確定有限自動機確定有限自動機可用來實現詞法分析器。有限自動機包括一個有限狀態(tài)集合和一些從一個狀態(tài)通往另一狀態(tài)的邊，每條邊上標有一個符號；其中一個狀態(tài)是初態(tài)，某些狀態(tài)是終態(tài)6。圖2.3給出了幾個有限自動機的例子。if312IFa-z0-910-92120-9IDNUM圖2.3 詞法單詞的有限自動機在確定有限自動機中，不會有從同一狀態(tài)發(fā)出的兩條邊標記有相同的符號，確定有限自動機以如下方式接受或拒絕一個字符串：從初始狀態(tài)出發(fā)，對于輸入串中的每個字符，自動機都將沿著一條確定的邊到達另一狀態(tài)，這條邊必須是標有輸入字符的邊，對n個字符的字符串進行了n次狀態(tài)轉換后，如果自動機到達了一個終態(tài)，自動機將接受該字符串，若到達的不是終態(tài)，或者找不到與輸入字符相匹配的邊，那么自動機將拒絕接受該字符串7。2.2 語法分析語法分析是分析如何根據一個文法生成一個終結符號串的過程。一種語言的識別器是一個程序，它把輸入看作一個字符串x，如果x是該語言的一個句子，則回答是，否則回答否。大多數分析方法都可以歸為以下兩類：自頂向下方法和自底向上方法。在自頂向下語法分析器中，構造過程從根結點開始，逐步向葉子節(jié)點方向進行，直至推出句子。自頂向下方法可以較容易地手工構造出高效的語法分析器。在自底向上語法分析器中，逐步對輸入串進行歸約，直至文法的開始符號，即從葉子節(jié)點開始，逐步向上歸約，直至語法樹的根節(jié)點。LL(1)文法表示對輸入串從左到右掃描，進行最左推導，分析時每步向前查看一個字符。LL(1)分析法需要消除左遞歸和克服回溯。LR分析法表示對輸入串從左到右掃描，構造最右推導的逆過程。LR分析法若采取手工構造，工作量非常大。本設計語法分析采用遞歸下降分析法。2.2.1 遞歸下降分析法遞歸下降分析方法是一種不帶回溯的自頂向下語法分析方法，它使用一組遞歸過程來處理輸入。為文法的每個非終結符都創(chuàng)建一個相應的過程。遞歸下降分析法的一種簡單形式是預測分析法。在預測分析法中，各個非終結符號對應的過程中的控制流可以由向前看符號無二義性地確定，在分析輸入串時出現的過程調用序列隱式地定義了該輸入串的一棵語法樹8。假設用預測分析法分析以下文法(黑體字符序列被視為一個單元，也就是單個終結符號)：stmtexpr;|if(expr) stmt|for(optExpr; optExpr; optExpr) stmt|otheroptExpr|expr則預測分析器如下所示：void stmt() switch(curToken) caseexpr:accept(expr); accept(;);break;case if:accept(if); accept(); accept(expr); accept(); stmt();break;casefor:accept(for); accept();optExpr(); accept(;); optExpr(); accept(;) optExpr();accept(); stmt(); break;case other:accept(other); break;default:report(“syntax error”);voidoptExpr() if(curToken = expr)accept(expr);voidaccept(terminal t) if(curToken = t)curToken = nextTerminal;elsereport(“syntax error”);該預測分析器中包含了兩個過程stmt()和optExpr()，分別對應于文法中非終結符號stmt和optExpr。該分析器中還包括一個額外的過程accept。這個額外的過程用來簡化stmt和optExpr()的代碼。過程accept(t)將它的參數t和向前看符號比較，如果匹配就前進到下一個輸入終結符號。因此，accept改變了全局變量curToken的值，該變量存儲了當前正被掃描的輸入終結符號。在分析過程的開始，首先調用文法的開始非終結符號stmt對應的過程，根據相應的語法規(guī)則，調用相應的處理過程。例如在處理“for(expr; expr; expr) other”輸入時，curToken被初始化為第一個終結符號for。每個非終結符都產生一個對相應過程的調用：accept(for); accept();optExpr(); accept(;); optExpr(); accept(;); optExpr();accept(); stmt();2.2.2 運算符的優(yōu)先級考慮表達式5 + 2 * 3。該表達式可有兩種不同的翻譯，即（5 +）* 3或5 + (2 * 3)。因此當多種運算符出現時，需要給出一些規(guī)則來確定運算符之間的相對優(yōu)先關系。先考慮“+ - * /”這四個常用運算符之間的優(yōu)先級關系：左結合：+ -左結合：* /創(chuàng)建兩個非終結符expr和term，expr對應于“左結合：+-”，term對應于“左結合：*/”，并使用另一個非終結符號factor來表示表達式中的基本單元。當前，表達式中基本單元是數字位和帶括號的表達式。factor digit | (expr)現在考慮具有最高優(yōu)先級的二目運算符*和/。由于這些運算符是左結合的，因此其產生式和左結合列表的產生式類似：termterm * factor|term / factor|factor類似的，expr生成由加減運算符分隔的term列表：exprexpr + term|expr term|term因此最終得到的文法是：exprexpr + term | expr term | termtermterm * factor | term / factor | factorfactordigit | (expr)2.3 中間代碼生成目標代碼1目標代碼分析器1中間代碼目標代碼分析器2目標代碼2圖2.4 中間代碼經常會有這種情況，編譯器需要為幾個目標機器生成機器碼或匯編程序。中間代碼是跟目標機器無關的，所以相同的中間代碼可以在目標語言之間共享（如圖2.4）。那么為一臺新的機器開發(fā)編譯器時就可以減少工作量。另外，很容易對中間代碼進行優(yōu)化，優(yōu)化也是與機器無關的9。中間代碼生成階段將語法樹翻譯成中間語言表示形式。中間代碼是機器無關的，但是它們接近機器指令。源程序通過中間代碼生成器翻譯成等價的中間語言。中間代碼可以是不同的語言，它由編譯器的設計者決定。語法樹可以作為中間語言，后綴表達式可以作為中間語言，三地址代碼（四元式）也可以作為中間語言。在后綴表達式中，任何語句表示都可以不使用括號，如：a * (9 + d) = a9d+*后綴表達式計算可以通過棧來實現。然而使用后綴表達式有很多不利的地方，如后綴表達式生成的匯編代碼包含冗余的操作；這些操作只能在匯編代碼中進行優(yōu)化，而不是在中間代碼中；優(yōu)化需要針對特定的目標機器。因此需要一種接近匯編語言的中間代碼，它支持機器無關級的優(yōu)化。所以本設計采用四元式。2.3.1 四元式在四元式中，所有的操作都可以歸約為一元或二元操作。這種中間代碼可以看成是一系列的執(zhí)行步驟，每步的執(zhí)行結果存儲在臨時變量中10。四元式由如下成分組成： 操作符 操作數，即兩個操作數 結果，存儲運算結果（operator, arg1, arg2, result）一個簡單的表達式可以用一個四元式表示：b + c = (+, b, c, tmp1)稍微復雜的表達式可以由一個四元式集合表示，臨時變量存儲中間結果。a * (5 + d)= (+, 5, d ,tmp1)(*, a, tmp1, tmp2)2.3.2 四元式的常見結構 算術運算和布爾表達式a + b = (+, a, b, tmp1)a * (b + c) = (+, b, c, tmp1), (*, a, tmp1, tmp2)按照運算順序，先計算括號中的表達式“b + c”，運算結果保存在臨時變量tmp1中，然后計算a * tmp1。a ( (-, a, _, tmp)下劃線表示空。 賦值a = a + b = (+, a, b, tmp), (=, tmp, _, a)本設計的賦值運算只支持簡單賦值，不支持連續(xù)賦值，如a = b = 0。 聲明int a, b=無int a=5 = (=, 5, _, a)聲明時可以進行初始化。 數組引用a = xi = (=, xi, _, a)xi = a = (=, a, _, xi) 無條件跳轉(jmp, jump_address, _, _)jump_address表示跳轉目標地址，在本設計中是一個目標標號。 條件跳轉(, i, 5, tmp1)/ 條件(jtrue, jump_address, tmp1, _)/ 表示如果tmp1為真則跳轉。注：是條件調轉還是無條件調轉，由arg2決定。 for循環(huán)for(i = 0; i (=, 0, _, i)/ 初始化(label_0:, _, _, _)(, i, 3, temp_0)/ 條件(jtrue, label_1, temp_0, _)(jmp, label_3, _, _)(label_1:,_, _,_)body of loop.(label_2:,_,_, _)(+, i, 1, i)/ 迭代(jmp, label_0, _, _)(label_3:,_,_,_)每個for語句會產生四個標號，一個表示類似“i = 0”的初始化，一個表示類似“i ”的條件判斷，一個表示body,一個表示類似“i+”的表達式。 if-else語句if(a (, a, b, temp_0)(jtrue, label_1, temp_0, _)(jmp, label_0, _, _)(label_1:,_,_, _)(=, a, _, c)(jmp, label_2, _, _)(label_0:,_,_, _)(=, b, _, c)(label_2:,_,_,_)一個if-else語句會產生3個標號，一個表示條件為真時的執(zhí)行語句，一個表示條件為假的執(zhí)行語句，一個表示跳出if-else語句。 while語句while(a (label_0:, _, _,_)(, a, b, temp_0)(jtrue, label_1, temp_0, _)(jmp, label_2, _, _)(label_1:,_,_, _)(+, a, 1, temp_1)(=, temp_1, _, a)(jmp, label_0, _, _)(label_2:,_,_,_)每個while語句產生3個標號，一個表示類似“a = 0”的初始化，一個表示類似“a (jmp, label_0, _, _)(label_3:, _, _, _)(+, a, 1, temp_0)(=, temp_0, _, a)(jmp, label_2, _, _)(label_1:, _, _, _)(+, a, 2, temp_1)(=, temp_1, _, a)(jmp, label_2, _, _)(label_0:, _, _, _)(=, i, 1, temp_2)(jtrue, label_3, temp_2, _)(jmp, label_1, _, _)(label_2:, _, _, _)每個switch語句會針對相應的case和default產生標號，同時，還會產生跳出switch的標號。 函數調用int add(int a, int b)return a + b;void main()int a = 1, b = 1, c;c = add(a, b);=(add:, _, _, _)(enter, 16, _, _)(+, a, b, temp_0)(return, temp_0, _, _)(return, _, _, _)(main:, _, _, _)(enter, 16, _, _)(=, 1, _, a)(=, 1, _, b)(param, b, _, _)(param, a, _, _)(call, add, _, temp_1)(incStackPtr, 8, _, _)(=, temp_1, _, c)(return, _, _, _)每個函數調用會針對主調函數和被調函數產生相應的標號。以上只是列舉了一些簡單情況下的示例，對于復雜的源程序，翻譯成的四元式集是以上常見四元式結構組合的結果。2.4符號表符號表是一種供編譯器用于保存有關源程序構造的各種信息的數據結構，這些信息在編譯器的分析階段被逐步收集并放入符號表11。編譯器用符號表跟蹤作用域及名字綁定的相關信息。在源程序中每次遇到名字都會去搜索符號表。如果新的名字出現或關于一個已存在名字新的信息出新，要對符號表進行更新。符號表條目可在詞法分析階段、語法分析階段和語義分析階段創(chuàng)建（如圖2.5）。在本設計中，由語法分析器來創(chuàng)建這些條目。因為相對于詞法分析器而言，語法分析器知道一個程序的語法結構，它可以更好地區(qū)分一個詞法單元的實際意義，因此常更適合創(chuàng)建符號表條目。前端詞法分析器中間代碼生成器語法分析器符號表圖2.5 符號表符號表通常用哈希表實現。KEY：詞素（lexeme），VALUE：符號（symbol）。2.4.1 作用域在靜態(tài)類型編程語言中，變量在使用之前必須聲明，聲明提供了變量的類型。如：int a; char c;通常，聲明只在它的作用域內有效。 函數作用域：每個變量在函數內部定義。 塊作用域：變量只在代碼塊內有效。float foo(int a, float b)int c;/ c為局部作用域中變量。 int b = 100;/ 塊作用域中定義的b將參數b覆蓋。c = a + b;/ 將參數a的值與新定義的b值之和賦值給c。return float(c) / b/ 此處的b為參數b。為防止引用變量產生沖突，須為每個作用域設置一個符號表。2.4.2 局部變量名的存儲布局從變量類型可以知道該變量在運行時刻需要的內存數量。在編譯時刻，可以使用這些數量為每個名字分配一個相對地址。名字的類型和相對地址信息保存在相應的符號表條目中12。數據對象的存儲布局受目標機器的尋址約束的影響。比如，將整數相加的指令往往希望整數能夠對齊（aligned），也就是說，希望它們被放在內存中特定的位置上，比如地址能夠被4整除的位置上。類型的寬度（width）是指該類型的一個對象所需的存儲單元的數量。一般情況下，字符類型（char）占用一個字節(jié)，整型（int）占用4個字節(jié)?？梢允褂靡粋€變量，比如offset，來跟蹤下一個可用的相對地址。在考慮第一個聲明之前，offset被設置為0。每處理一個變量x時，x被加入符號表，它的相對地址被設置為offset的當前值，隨后，x類型的寬度被加到offset上。3設計與實現3.1 C子語言本設計將一個用C子語言編寫的源程序翻譯成中間代碼，該子語言描述如下：3.1.1數據類型該子語言支持兩種數據類型： int：32位有符號整型。 char: 8位無符號整型。只支持靜態(tài)數組。如果傳遞一個數組給函數，數組將會以指針形式傳遞，所以對于數組的任何更改，將會影響調用函數傳遞的數組。另外，如果超過了數組的長度，調用函數的棧結構將會被破壞。每個作用域中的局部變量應該在該作用域塊的開始即任何其他語句之前進行聲明，就像以前的C98標準那樣。3.1.2 字面值 整型，如：2343， -123 字符串，如：“Hi， my name is XiKangjien” 字符，如：a, n3.1.3 表達式表達式中只支持以下運算符：+，-，后綴+和-，*，/，%，=，=，|，&布爾表達式中不支持短路代碼。在短路代碼中，布爾運算符&、|和！被翻譯成跳轉指令。運算符本身不出現在代碼中，布爾表達式的值是通過代碼序列中的位置來表示的。3.1.4 語句 if-else語句 switch語句 while語句 do-while語句 for語句 break和continue語句3.1.5 函數有幾個內建的函數用來基本的輸入輸出，它們是：- printStr(char str); printStr(string);在標準輸出中打印一個以null結尾的字符串。- printChar(char c);- printInt(int n);- readStr(char buffer, int bufferSize);- readInt(int n)這些函數會調用標準C輸入輸出函數，如printf和scanf，另外，這些函數名被視為關鍵字，所以它們是該語言語法的一部分?？梢宰远x函數。但是，需要知道這里不支持函數的前向聲明：int f(int x);所以應該注意定義函數的順序，當定義了很多相互調用的函數，會使程序變得復雜。另外，本子語言盡可能合理地去實現作用域，局部變量的作用域和生存周期就像C語言那樣，但是沒有全局作用域，也就是說不能定義全局變量。可是，在函數內部，可以自由嵌套作用域。比如：void foo()int x, y;/ 嵌套塊，產生一個新的內部作用域。int x; / 嵌套作用域中的定義的x,它會將外部作用域中x覆蓋。if (true)int x; / if塊中定義的變量x,它會將外部作用域中x覆蓋。在這個子語言中有很多的限制，比如沒有類型檢測，只有少量的語義分析等等。所以在此不是創(chuàng)建一種新的語言，而是以此子語言為例編寫一個編譯器前端。3.2 符號表一個符號表必須允許添加新項，查找已存在項，支持在編譯期間動態(tài)增長符號表。符號表可以實現為線性表和哈希表，線性表雖然容易實現，但表很大時性能會很差，所以本設計采用哈希表。本設計的符號表由類SymbolTable實現，其內部存儲結構由哈希表實現（這里使用標準容器unordered_map），KEY代表詞素（lexeme），VALUE代表與該詞素對應的符號（Symbol）。符號由類Symbol實現。由于作用域可以嵌套，同時又要為每個作用域創(chuàng)建一個符號表，所以在類SymbolTable中，容器inner_scopes_存儲嵌套的內部作用域，容器中的每個元素為指向內部作用域符號表的指針。指針outer_scope_指向外部作用域符號表。在創(chuàng)建一個符號表時，要為其傳遞外部作用域符號表參數，若當前創(chuàng)建的符號表為根符號表，則默認為其傳遞參數NULL。在符號表中插入新項有兩種方式。一是插入Symbol，二是插入詞素和詞法單元標記。通過詞素獲取相應的符號，由重載運算符實現。class SymbolTablepublic:SymbolTable(SymbolTable* prev = NULL) : outer_scope_(prev) SymbolTable();bool Insert(Symbol* symbol);bool Insert(const std:string& lexeme, TokenTag tag);bool IsInCurrentScope(const std:string& lexeme) const;/ 重載了運算符，可以直接通過symboltablekey來獲取value。Symbol* operator (const std:string& key);std:vector inner_scopes_;/ 內部作用域指針。SymbolTable* outer() return outer_scope_; private:SymbolTable* outer_scope_;/ 指向外部作用域/ 用哈希map存儲符號表。std:unordered_map table_;類Symbol表示符號表的符號，它也是類VariableSymbol和類FunctionSymbol的基類。一個符號由詞素和相應的詞法單元標記組成，一個用于關鍵字if的符號對象可以通過以下語句創(chuàng)建：Symbol symbol_if(“if”, IF);class Symbolpublic:Symbol(const std:string& lexeme, TokenTag tag) : lexeme_(lexeme),token_tag_(tag) virtual Symbol() std:string lexeme() const return lexeme_; TokenTag token_tag() const return token_tag_; bool IsKeyword() const;private:std:string lexeme_;/ 詞素。TokenTag token_tag_;/ 詞法單元標記，表示詞法單元的屬性。;類VariableSymbol表示變量符號，用來存儲變量信息。offset_表示變量的偏移量，與變量在內存的布局有關；width_表示變量類型的寬度；size_表示變量占用的字節(jié)數；is_array_表示變量是否是數組；data_type_表示變量的類型，DataType是一個枚舉類型，其中有三個元素，VOID_TYPE、INT_TYPE和CHAR_TYPE；kind_表示變量的種類，VariableKind是一個枚舉類型，其中有兩個元素，LOCAL表示變量是局部變量，ARGUMENT表示變量是參數。class VariableSymbol : public Symbolpublic:VariableSymbol(const std:string& identifier) : Symbol(identifier, ID) private:unsigned int offset_;/偏移量，即相對位置。unsigned intwidth_;/ 變量類型的寬度，即占用的字節(jié)數。unsigned int size_;/ 整個符號占用的字節(jié)數。bool is_array_;/ 當前符號是否是數組。DataType data_type_;/ 數據類型，可以為int、char或void。VariableKind kind_;/ 變量的種類，可以為局部變量或參數變量。;enum DataTypeINT_TYPE,CHAR_TYPE,VOID_TYPE;enum VariableKindLOCAL,ARGUMENT;類FunctionSymbol表示函數符號，用來存儲函數信息。包括函數標示符，返回類型及參數信息。class FunctionSymbol : public Symbolpublic:FunctionSymbol(const std:string& identifier, DataType return_type): Symbol(identifier, ID), return_type_(return_type) DataType return_type() const return return_type_; std:vector parameters_;/ 參數列表。private:DataType return_type_;/ 函數的返回類型。;類Parameter保存函數的參數信息。包括參數的標示符，類型，是否是數組。class Parameterpublic:Parameter(DataType type, const std:string& identifier, bool is_array): type_(type), identifier_(identifier), is_array_(is_array) DataType type() const return type_; std:string identifier() const return identifier_; bool is_array() const return is_array_; private:DataType type_;/ 參數的類型。std:string identifier_;/ 參數的名字。bool is_array_;/ 參數是否為數組。;每個Token有個Tag變量，表示詞素的屬性，用于做出語法分析決定。用枚舉類型TokenTag實現。枚舉類型TokenTag的每個元素與編程語言上下文中的符號意義無關。在詞法分析階段，符號所代表的具體意義尚未知曉，在語法分析階段，才確定符號的具體意義。比如，符號“*”叫做“ASTERISK”或者“STAR”。它可以表示不同的語言元素，比如可能是一個指針，或者乘號。所以在枚舉變量TokenTag中，把“*”叫做“ASTERISK”，直到語法分析階段才能從上下文解析出其具體意義。enum TokenTagEND_OF_FILE = EOF,PLUS = (int)+,MINUS = (int)-,ASTERISK = (int)*,FORWARD_SLASH = (int)/,PERCENT = (int)%,EQUAL = (int)=,LESS = (int),OPEN_BRACE = (int),CLOSE_BRACE = (int),OPEN_PAREN = (int)(,CLOSE_PAREN = (int),OPEN_BRACKET = (int),CLOSE_BRACKET = (int),COMMA = (int),COLON = (int):,SEMICOLON = (int);,EXCLAMATION = (int)!,LESS_OR_EQUAL = 400,GREATER_OR_EQUAL = 401,EQUAL_EQUAL = 402,NOT_EQUAL = 403,OR = 404,AND = 405,PLUS_PLUS = 406,MINUS_MINUS = 407,ID = 256,NUM_LITERAL = 257,STRING_LITERAL = 258,/ 保留關鍵字。VOID = 300,INT,CHAR,IF,ELSE,FOR,DO,WHILE,SWITCH,CASE,DEFAULT,RETURN,BREAK,CONTINUE,PRINT_INT,PRINT_STR,PRINT_CHAR,READ_INT,READ_STR,GOTO;3.3 詞法分析器詞法分析器的實現按照2.1.2節(jié)原理。狀態(tài)轉換圖用來跟蹤掃描器讀入的當前查看字符。隨著字符的讀入，從一個狀態(tài)轉換到另一個狀態(tài)。當進入一個狀態(tài)，緊接著讀入下一個字符如果有一條從當前狀態(tài)發(fā)出的邊且其上標志的字符和讀入的字符相匹配，然后轉向改變指向的下一個狀態(tài)，否則報告錯誤。詞法分析器由類Lexer實現，可用通過GetNextToken()獲取下一個Token，或者通過PeekNextToken()查看下一個Token。核心算法在Scan()中實現，忽略注釋和空白符，分析出以下類型的Token： 算術運算符：+ - * / % +