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

基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn)基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn)摘要本設(shè)計(jì)實(shí)現(xiàn)了一個編譯器前端，它將一個用C語言的子語言編寫的源程序翻譯成中間代碼。詞法分析器、語法分析器、中間代碼生成器均是采用C+語言手動書寫完成，未采用自動生成器，GUI采用Win32 API實(shí)現(xiàn)以保證輕快的運(yùn)行速度及良好的系統(tǒng)性能，編輯控件采用Scintilla。詞法分析器采用確定有限自動機(jī)實(shí)現(xiàn)，語法分析器是一個遞歸下降分析器，中間代碼生成器輸出的中間代碼以四元式形式表示。本設(shè)計(jì)實(shí)現(xiàn)的編譯器前端，運(yùn)行在Windows平臺下，Windows系統(tǒng)版本為Windows XP、Windows 7或更高版本。本設(shè)計(jì)提供了一個可工作的界面友好的編譯器前端，可以用來理解編譯原理及解釋怎樣用一種語言如C+實(shí)現(xiàn)編譯器前端，以供學(xué)習(xí)和教學(xué)所用。關(guān)鍵詞：編譯器前端；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 詞法分析結(jié)果42.1.2 確定有限自動機(jī)52.2 語法分析52.2.1 遞歸下降分析法62.2.2 運(yùn)算符的優(yōu)先級82.3 中間代碼生成92.3.1 四元式92.3.2 四元式的常見結(jié)構(gòu)102.4 符號表142.4.1 作用域152.4.2 局部變量名的存儲布局163 設(shè)計(jì)與實(shí)現(xiàn)173.1 C子語言173.1.1數(shù)據(jù)類型173.1.2 字面值173.1.3 表達(dá)式173.1.4 語句183.1.5 函數(shù)183.2 符號表193.3 詞法分析器243.4 語法分析器263.5 中間代碼生成器283.6 GUI304 測試36總結(jié)41參考文獻(xiàn)42致謝43附錄源程序44附件1：開題報(bào)告（文獻(xiàn)綜述）附件2：譯文及原文影印件1 緒論很少有人去自己編寫或修改編譯器，那么為什么要去實(shí)現(xiàn)編譯器前端呢？很重要的一點(diǎn)就是，理解計(jì)算機(jī)程序怎樣被編譯以及執(zhí)行，可以幫助任何程序員理解他們寫的代碼是怎樣驅(qū)動計(jì)算機(jī)的，從而幫助他們寫出更快、更高效的程序。編譯原理經(jīng)過多年發(fā)展已日趨成熟，然而現(xiàn)代很多跟編譯原理相關(guān)的教材，內(nèi)容陳舊落后，比如以Fortran或Pascal等過時語言為例進(jìn)行分析講解，或者全書充滿晦澀難懂的定理公式，不能以直觀的方式進(jìn)行闡述，致使學(xué)生望而生畏。本設(shè)計(jì)用C+語言實(shí)現(xiàn)了一個編譯器前端，它將一個用C子語言編寫的源程序翻譯成中間代碼，擁有友好直觀的交互式圖形界面，有助于對編譯原理的理解，可用于學(xué)習(xí)及教學(xué)。在一段程序可以執(zhí)行之前，首先需要把它翻譯成一種其能夠被計(jì)算機(jī)接受的形式，完成這項(xiàng)翻譯工作的程序稱為編譯器（compiler）1。簡單而言，編譯器是一個程序，它將使用源語言編寫的程序轉(zhuǎn)換成另一種目標(biāo)語言。在轉(zhuǎn)換階段很重要的一部分是報(bào)告用戶當(dāng)前源程序的錯誤。為了將源程序從一種語言翻譯成另一種語言，編譯器必須首先把程序的各種成分拆開，并搞清其結(jié)構(gòu)和含義，然后再把這些成分組合成有意義的計(jì)算機(jī)能識別的語言。編譯器的前端進(jìn)行詞法分析、語法分析和語義分析，并且產(chǎn)生中間代碼，即進(jìn)行分析。編譯器的后端對中間代碼進(jìn)行優(yōu)化并將中間代碼翻譯成機(jī)器語言，即進(jìn)行組合。詞法分析的任務(wù)是：對源程序進(jìn)行從左到右逐個字符地掃描，產(chǎn)生一個個獨(dú)立的單詞符號（token）。詞法分析是編譯的基礎(chǔ)。語法分析的任務(wù)是：在詞法分析識別出一系列單詞符號的基礎(chǔ)上，分析并判定源程序的結(jié)構(gòu)是否符合語法規(guī)則。語法分析可以粗略地分為兩類，一類是自頂向下，一類是自底向上2。對于本設(shè)計(jì)，采用的是自頂向下進(jìn)行分析。語法分析得到語法樹，盡管可以直接將語法樹轉(zhuǎn)換成目標(biāo)機(jī)器代碼，但這樣做不利于可移植性和模塊化設(shè)計(jì)。假設(shè)需要這樣一個編譯器：它可以編譯N種不同的源語言，然后為M臺不同的目標(biāo)機(jī)生成代碼。理論上，這是N*M個編譯器，如圖1.1(a)，但實(shí)現(xiàn)這么多的編譯器是需要花費(fèi)大量的人力物力。中間代碼（intermediate code, IC）是一種抽象機(jī)器語言，它可以表示目標(biāo)機(jī)的操作而不需太多涉及與機(jī)器相關(guān)的細(xì)節(jié)，而且，它也獨(dú)立于源語言的細(xì)節(jié)3。一個可移植的編譯器如圖1.1(b)所示，它先將源語言轉(zhuǎn)換成中間代碼，然后再將中間代碼轉(zhuǎn)化成目標(biāo)機(jī)器語言，這樣便只需要實(shí)現(xiàn)N個前端和M個后端。這種實(shí)現(xiàn)要更容易合理些。即使在只需實(shí)現(xiàn)一個前端和一個后端的情況下，好的中間代碼也利于將系統(tǒng)模塊化，使得編譯器前端不會因機(jī)器相關(guān)的細(xì)節(jié)而復(fù)雜化，編譯器后端不會因源語言的特殊信息而干擾。編譯器可以使用的中間代碼有多種形式，對于本設(shè)計(jì)，采用簡單的四元式。IC(a) (b)圖1.1 面向5種語言并支持4種目標(biāo)機(jī)的編譯器：（a）沒有IC，（b）有IC編譯器的每個階段都可能遇到錯誤，如果編譯器在遇到第一個錯誤時就停止運(yùn)行，對于修正程序肯定起不到多大幫助作用。詞法分析階段可以檢測出來自輸入的字符串不能形成語言的任何單詞符號（token）。語法分析階段可以檢測出違反語言語法的單詞符號串。本設(shè)計(jì)可以報(bào)告出錯誤是什么及錯誤在源程序的行號和列號。2基本原理一個編譯器是一個計(jì)算機(jī)程序，它可以把用某種高級語言寫的源代碼轉(zhuǎn)換成另一種形式，典型的形式是機(jī)器碼。機(jī)器碼是計(jì)算機(jī)可以執(zhí)行的一系列指令4。int max(int a, int b)if(a b)return a;return b;一個編譯器由有兩部分組成，如圖2.1所示。（1）源代碼分析器：它將輸入的源代碼看作是一個字符串，然后將其翻譯成有意義的符號（變量，值，操作符等）。（2）目標(biāo)代碼生成器：它將源代碼分析器的結(jié)果轉(zhuǎn)換成可執(zhí)行代碼。t1 = -ct2 = b * t1t3 = t1 + t2t4 = t3目標(biāo)代碼源代碼目標(biāo)代碼生成器源代碼分析器圖2.1 編譯器結(jié)構(gòu)源代碼分析器不依賴于機(jī)器，然而目標(biāo)代碼生成器需要針對不同的機(jī)器類型生成不同的代碼，因此是依賴于機(jī)器的。源代碼分析器經(jīng)常被稱作編譯器的前端，目標(biāo)代碼生成器被稱作后端。本設(shè)計(jì)要實(shí)現(xiàn)的正是編譯器的前端。編譯器的前端又分為三個階段，如圖2.2所示。t1 = -ct2 = b * t1t3 = t1 + t2t4 = t3前端源代碼中間代碼生成器語法分析器詞法分析器圖2.2 編譯器前端2.1 詞法分析詞法分析器以字符流作為輸入，刪除單詞之間的空白符和注釋（程序中每一部分都有可能出現(xiàn)空白和注釋）并生成一系列的名字、關(guān)鍵字和標(biāo)點(diǎn)符號。如果讓語法分析器來處理它們就會使得語法分析過于復(fù)雜，結(jié)構(gòu)也不清晰，這便是將詞法分析成為一個獨(dú)立階段，從語法分析中分離出去的主要原因5。在詞法分析器中，詞法單元（token）通常包含以下幾種類型： 標(biāo)識符 保留字（如：“if”，“while”等） 數(shù)值常量（如：整數(shù)，實(shí)數(shù)等） 字符串常量 簡單符號（運(yùn)算符如：“+”，“-”等，分隔符如：“；”，“，”等） 多重符號（運(yùn)算符如“+=”，“+”等）這些詞法單元將用于下一階段語法分析。2.1.1 詞法分析結(jié)果對于下面一段程序：int match(char* str)/ find a zeroif(!strncmp(str, “0”, 1)return 0;詞法分析器將產(chǎn)生如下tokens：INTID(match)LPARENCHARSTARID(str)RPARENLBRACEIFLPARENBANGID(strncmp) LPAREN ID(str) COMMA STRING(0) COMMANUM(1)RPAREN RPAREN RETURN REAL(0)SEMIRBRACEOF2.1.2 確定有限自動機(jī)確定有限自動機(jī)可用來實(shí)現(xiàn)詞法分析器。有限自動機(jī)包括一個有限狀態(tài)集合和一些從一個狀態(tài)通往另一狀態(tài)的邊，每條邊上標(biāo)有一個符號；其中一個狀態(tài)是初態(tài)，某些狀態(tài)是終態(tài)6。圖2.3給出了幾個有限自動機(jī)的例子。if312IFa-z0-910-92120-9IDNUM圖2.3 詞法單詞的有限自動機(jī)在確定有限自動機(jī)中，不會有從同一狀態(tài)發(fā)出的兩條邊標(biāo)記有相同的符號，確定有限自動機(jī)以如下方式接受或拒絕一個字符串：從初始狀態(tài)出發(fā)，對于輸入串中的每個字符，自動機(jī)都將沿著一條確定的邊到達(dá)另一狀態(tài)，這條邊必須是標(biāo)有輸入字符的邊，對n個字符的字符串進(jìn)行了n次狀態(tài)轉(zhuǎn)換后，如果自動機(jī)到達(dá)了一個終態(tài)，自動機(jī)將接受該字符串，若到達(dá)的不是終態(tài)，或者找不到與輸入字符相匹配的邊，那么自動機(jī)將拒絕接受該字符串7。2.2 語法分析語法分析是分析如何根據(jù)一個文法生成一個終結(jié)符號串的過程。一種語言的識別器是一個程序，它把輸入看作一個字符串x，如果x是該語言的一個句子，則回答是，否則回答否。大多數(shù)分析方法都可以歸為以下兩類：自頂向下方法和自底向上方法。在自頂向下語法分析器中，構(gòu)造過程從根結(jié)點(diǎn)開始，逐步向葉子節(jié)點(diǎn)方向進(jìn)行，直至推出句子。自頂向下方法可以較容易地手工構(gòu)造出高效的語法分析器。在自底向上語法分析器中，逐步對輸入串進(jìn)行歸約，直至文法的開始符號，即從葉子節(jié)點(diǎn)開始，逐步向上歸約，直至語法樹的根節(jié)點(diǎn)。LL(1)文法表示對輸入串從左到右掃描，進(jìn)行最左推導(dǎo)，分析時每步向前查看一個字符。LL(1)分析法需要消除左遞歸和克服回溯。LR分析法表示對輸入串從左到右掃描，構(gòu)造最右推導(dǎo)的逆過程。LR分析法若采取手工構(gòu)造，工作量非常大。本設(shè)計(jì)語法分析采用遞歸下降分析法。2.2.1 遞歸下降分析法遞歸下降分析方法是一種不帶回溯的自頂向下語法分析方法，它使用一組遞歸過程來處理輸入。為文法的每個非終結(jié)符都創(chuàng)建一個相應(yīng)的過程。遞歸下降分析法的一種簡單形式是預(yù)測分析法。在預(yù)測分析法中，各個非終結(jié)符號對應(yīng)的過程中的控制流可以由向前看符號無二義性地確定，在分析輸入串時出現(xiàn)的過程調(diào)用序列隱式地定義了該輸入串的一棵語法樹8。假設(shè)用預(yù)測分析法分析以下文法(黑體字符序列被視為一個單元，也就是單個終結(jié)符號)：stmtexpr;|if(expr) stmt|for(optExpr; optExpr; optExpr) stmt|otheroptExpr|expr則預(yù)測分析器如下所示：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”);該預(yù)測分析器中包含了兩個過程stmt()和optExpr()，分別對應(yīng)于文法中非終結(jié)符號stmt和optExpr。該分析器中還包括一個額外的過程accept。這個額外的過程用來簡化stmt和optExpr()的代碼。過程accept(t)將它的參數(shù)t和向前看符號比較，如果匹配就前進(jìn)到下一個輸入終結(jié)符號。因此，accept改變了全局變量curToken的值，該變量存儲了當(dāng)前正被掃描的輸入終結(jié)符號。在分析過程的開始，首先調(diào)用文法的開始非終結(jié)符號stmt對應(yīng)的過程，根據(jù)相應(yīng)的語法規(guī)則，調(diào)用相應(yīng)的處理過程。例如在處理“for(expr; expr; expr) other”輸入時，curToken被初始化為第一個終結(jié)符號for。每個非終結(jié)符都產(chǎn)生一個對相應(yīng)過程的調(diào)用：accept(for); accept();optExpr(); accept(;); optExpr(); accept(;); optExpr();accept(); stmt();2.2.2 運(yùn)算符的優(yōu)先級考慮表達(dá)式5 + 2 * 3。該表達(dá)式可有兩種不同的翻譯，即（5 +）* 3或5 + (2 * 3)。因此當(dāng)多種運(yùn)算符出現(xiàn)時，需要給出一些規(guī)則來確定運(yùn)算符之間的相對優(yōu)先關(guān)系。先考慮“+ - * /”這四個常用運(yùn)算符之間的優(yōu)先級關(guān)系：左結(jié)合：+ -左結(jié)合：* /創(chuàng)建兩個非終結(jié)符expr和term，expr對應(yīng)于“左結(jié)合：+-”，term對應(yīng)于“左結(jié)合：*/”，并使用另一個非終結(jié)符號factor來表示表達(dá)式中的基本單元。當(dāng)前，表達(dá)式中基本單元是數(shù)字位和帶括號的表達(dá)式。factor digit | (expr)現(xiàn)在考慮具有最高優(yōu)先級的二目運(yùn)算符*和/。由于這些運(yùn)算符是左結(jié)合的，因此其產(chǎn)生式和左結(jié)合列表的產(chǎn)生式類似：termterm * factor|term / factor|factor類似的，expr生成由加減運(yùn)算符分隔的term列表：exprexpr + term|expr term|term因此最終得到的文法是：exprexpr + term | expr term | termtermterm * factor | term / factor | factorfactordigit | (expr)2.3 中間代碼生成目標(biāo)代碼1目標(biāo)代碼分析器1中間代碼目標(biāo)代碼分析器2目標(biāo)代碼2圖2.4 中間代碼經(jīng)常會有這種情況，編譯器需要為幾個目標(biāo)機(jī)器生成機(jī)器碼或匯編程序。中間代碼是跟目標(biāo)機(jī)器無關(guān)的，所以相同的中間代碼可以在目標(biāo)語言之間共享（如圖2.4）。那么為一臺新的機(jī)器開發(fā)編譯器時就可以減少工作量。另外，很容易對中間代碼進(jìn)行優(yōu)化，優(yōu)化也是與機(jī)器無關(guān)的9。中間代碼生成階段將語法樹翻譯成中間語言表示形式。中間代碼是機(jī)器無關(guān)的，但是它們接近機(jī)器指令。源程序通過中間代碼生成器翻譯成等價的中間語言。中間代碼可以是不同的語言，它由編譯器的設(shè)計(jì)者決定。語法樹可以作為中間語言，后綴表達(dá)式可以作為中間語言，三地址代碼（四元式）也可以作為中間語言。在后綴表達(dá)式中，任何語句表示都可以不使用括號，如：a * (9 + d) = a9d+*后綴表達(dá)式計(jì)算可以通過棧來實(shí)現(xiàn)。然而使用后綴表達(dá)式有很多不利的地方，如后綴表達(dá)式生成的匯編代碼包含冗余的操作；這些操作只能在匯編代碼中進(jìn)行優(yōu)化，而不是在中間代碼中；優(yōu)化需要針對特定的目標(biāo)機(jī)器。因此需要一種接近匯編語言的中間代碼，它支持機(jī)器無關(guān)級的優(yōu)化。所以本設(shè)計(jì)采用四元式。2.3.1 四元式在四元式中，所有的操作都可以歸約為一元或二元操作。這種中間代碼可以看成是一系列的執(zhí)行步驟，每步的執(zhí)行結(jié)果存儲在臨時變量中10。四元式由如下成分組成： 操作符 操作數(shù)，即兩個操作數(shù) 結(jié)果，存儲運(yùn)算結(jié)果（operator, arg1, arg2, result）一個簡單的表達(dá)式可以用一個四元式表示：b + c = (+, b, c, tmp1)稍微復(fù)雜的表達(dá)式可以由一個四元式集合表示，臨時變量存儲中間結(jié)果。a * (5 + d)= (+, 5, d ,tmp1)(*, a, tmp1, tmp2)2.3.2 四元式的常見結(jié)構(gòu) 算術(shù)運(yùn)算和布爾表達(dá)式a + b = (+, a, b, tmp1)a * (b + c) = (+, b, c, tmp1), (*, a, tmp1, tmp2)按照運(yùn)算順序，先計(jì)算括號中的表達(dá)式“b + c”，運(yùn)算結(jié)果保存在臨時變量tmp1中，然后計(jì)算a * tmp1。a ( (-, a, _, tmp)下劃線表示空。 賦值a = a + b = (+, a, b, tmp), (=, tmp, _, a)本設(shè)計(jì)的賦值運(yùn)算只支持簡單賦值，不支持連續(xù)賦值，如a = b = 0。 聲明int a, b=無int a=5 = (=, 5, _, a)聲明時可以進(jìn)行初始化。 數(shù)組引用a = xi = (=, xi, _, a)xi = a = (=, a, _, xi) 無條件跳轉(zhuǎn)(jmp, jump_address, _, _)jump_address表示跳轉(zhuǎn)目標(biāo)地址，在本設(shè)計(jì)中是一個目標(biāo)標(biāo)號。 條件跳轉(zhuǎn)(, i, 5, tmp1)/ 條件(jtrue, jump_address, tmp1, _)/ 表示如果tmp1為真則跳轉(zhuǎn)。注：是條件調(diào)轉(zhuǎn)還是無條件調(diào)轉(zhuǎn)，由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語句會產(chǎn)生四個標(biāo)號，一個表示類似“i = 0”的初始化，一個表示類似“i ”的條件判斷，一個表示body,一個表示類似“i+”的表達(dá)式。 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語句會產(chǎn)生3個標(biāo)號，一個表示條件為真時的執(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語句產(chǎn)生3個標(biāo)號，一個表示類似“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語句會針對相應(yīng)的case和default產(chǎn)生標(biāo)號，同時，還會產(chǎn)生跳出switch的標(biāo)號。 函數(shù)調(diào)用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, _, _, _)每個函數(shù)調(diào)用會針對主調(diào)函數(shù)和被調(diào)函數(shù)產(chǎn)生相應(yīng)的標(biāo)號。以上只是列舉了一些簡單情況下的示例，對于復(fù)雜的源程序，翻譯成的四元式集是以上常見四元式結(jié)構(gòu)組合的結(jié)果。2.4符號表符號表是一種供編譯器用于保存有關(guān)源程序構(gòu)造的各種信息的數(shù)據(jù)結(jié)構(gòu)，這些信息在編譯器的分析階段被逐步收集并放入符號表11。編譯器用符號表跟蹤作用域及名字綁定的相關(guān)信息。在源程序中每次遇到名字都會去搜索符號表。如果新的名字出現(xiàn)或關(guān)于一個已存在名字新的信息出新，要對符號表進(jìn)行更新。符號表?xiàng)l目可在詞法分析階段、語法分析階段和語義分析階段創(chuàng)建（如圖2.5）。在本設(shè)計(jì)中，由語法分析器來創(chuàng)建這些條目。因?yàn)橄鄬τ谠~法分析器而言，語法分析器知道一個程序的語法結(jié)構(gòu)，它可以更好地區(qū)分一個詞法單元的實(shí)際意義，因此常更適合創(chuàng)建符號表?xiàng)l目。前端詞法分析器中間代碼生成器語法分析器符號表圖2.5 符號表符號表通常用哈希表實(shí)現(xiàn)。KEY：詞素（lexeme），VALUE：符號（symbol）。2.4.1 作用域在靜態(tài)類型編程語言中，變量在使用之前必須聲明，聲明提供了變量的類型。如：int a; char c;通常，聲明只在它的作用域內(nèi)有效。 函數(shù)作用域：每個變量在函數(shù)內(nèi)部定義。 塊作用域：變量只在代碼塊內(nèi)有效。float foo(int a, float b)int c;/ c為局部作用域中變量。 int b = 100;/ 塊作用域中定義的b將參數(shù)b覆蓋。c = a + b;/ 將參數(shù)a的值與新定義的b值之和賦值給c。return float(c) / b/ 此處的b為參數(shù)b。為防止引用變量產(chǎn)生沖突，須為每個作用域設(shè)置一個符號表。2.4.2 局部變量名的存儲布局從變量類型可以知道該變量在運(yùn)行時刻需要的內(nèi)存數(shù)量。在編譯時刻，可以使用這些數(shù)量為每個名字分配一個相對地址。名字的類型和相對地址信息保存在相應(yīng)的符號表?xiàng)l目中12。數(shù)據(jù)對象的存儲布局受目標(biāo)機(jī)器的尋址約束的影響。比如，將整數(shù)相加的指令往往希望整數(shù)能夠?qū)R（aligned），也就是說，希望它們被放在內(nèi)存中特定的位置上，比如地址能夠被4整除的位置上。類型的寬度（width）是指該類型的一個對象所需的存儲單元的數(shù)量。一般情況下，字符類型（char）占用一個字節(jié)，整型（int）占用4個字節(jié)?？梢允褂靡粋€變量，比如offset，來跟蹤下一個可用的相對地址。在考慮第一個聲明之前，offset被設(shè)置為0。每處理一個變量x時，x被加入符號表，它的相對地址被設(shè)置為offset的當(dāng)前值，隨后，x類型的寬度被加到offset上。3設(shè)計(jì)與實(shí)現(xiàn)3.1 C子語言本設(shè)計(jì)將一個用C子語言編寫的源程序翻譯成中間代碼，該子語言描述如下：3.1.1數(shù)據(jù)類型該子語言支持兩種數(shù)據(jù)類型： int：32位有符號整型。 char: 8位無符號整型。只支持靜態(tài)數(shù)組。如果傳遞一個數(shù)組給函數(shù)，數(shù)組將會以指針形式傳遞，所以對于數(shù)組的任何更改，將會影響調(diào)用函數(shù)傳遞的數(shù)組。另外，如果超過了數(shù)組的長度，調(diào)用函數(shù)的棧結(jié)構(gòu)將會被破壞。每個作用域中的局部變量應(yīng)該在該作用域塊的開始即任何其他語句之前進(jìn)行聲明，就像以前的C98標(biāo)準(zhǔn)那樣。3.1.2 字面值 整型，如：2343， -123 字符串，如：“Hi， my name is XiKangjien” 字符，如：a, n3.1.3 表達(dá)式表達(dá)式中只支持以下運(yùn)算符：+，-，后綴+和-，*，/，%，=，=，|，&布爾表達(dá)式中不支持短路代碼。在短路代碼中，布爾運(yùn)算符&、|和！被翻譯成跳轉(zhuǎn)指令。運(yùn)算符本身不出現(xiàn)在代碼中，布爾表達(dá)式的值是通過代碼序列中的位置來表示的。3.1.4 語句 if-else語句 switch語句 while語句 do-while語句 for語句 break和continue語句3.1.5 函數(shù)有幾個內(nèi)建的函數(shù)用來基本的輸入輸出，它們是：- printStr(char str); printStr(string);在標(biāo)準(zhǔn)輸出中打印一個以null結(jié)尾的字符串。- printChar(char c);- printInt(int n);- readStr(char buffer, int bufferSize);- readInt(int n)這些函數(shù)會調(diào)用標(biāo)準(zhǔn)C輸入輸出函數(shù)，如printf和scanf，另外，這些函數(shù)名被視為關(guān)鍵字，所以它們是該語言語法的一部分。可以自定義函數(shù)。但是，需要知道這里不支持函數(shù)的前向聲明：int f(int x);所以應(yīng)該注意定義函數(shù)的順序，當(dāng)定義了很多相互調(diào)用的函數(shù)，會使程序變得復(fù)雜。另外，本子語言盡可能合理地去實(shí)現(xiàn)作用域，局部變量的作用域和生存周期就像C語言那樣，但是沒有全局作用域，也就是說不能定義全局變量?？墒?，在函數(shù)內(nèi)部，可以自由嵌套作用域。比如：void foo()int x, y;/ 嵌套塊，產(chǎn)生一個新的內(nèi)部作用域。int x; / 嵌套作用域中的定義的x,它會將外部作用域中x覆蓋。if (true)int x; / if塊中定義的變量x,它會將外部作用域中x覆蓋。在這個子語言中有很多的限制，比如沒有類型檢測，只有少量的語義分析等等。所以在此不是創(chuàng)建一種新的語言，而是以此子語言為例編寫一個編譯器前端。3.2 符號表一個符號表必須允許添加新項(xiàng)，查找已存在項(xiàng)，支持在編譯期間動態(tài)增長符號表。符號表可以實(shí)現(xiàn)為線性表和哈希表，線性表雖然容易實(shí)現(xiàn)，但表很大時性能會很差，所以本設(shè)計(jì)采用哈希表。本設(shè)計(jì)的符號表由類SymbolTable實(shí)現(xiàn)，其內(nèi)部存儲結(jié)構(gòu)由哈希表實(shí)現(xiàn)（這里使用標(biāo)準(zhǔn)容器unordered_map），KEY代表詞素（lexeme），VALUE代表與該詞素對應(yīng)的符號（Symbol）。符號由類Symbol實(shí)現(xiàn)。由于作用域可以嵌套，同時又要為每個作用域創(chuàng)建一個符號表，所以在類SymbolTable中，容器inner_scopes_存儲嵌套的內(nèi)部作用域，容器中的每個元素為指向內(nèi)部作用域符號表的指針。指針outer_scope_指向外部作用域符號表。在創(chuàng)建一個符號表時，要為其傳遞外部作用域符號表參數(shù)，若當(dāng)前創(chuàng)建的符號表為根符號表，則默認(rèn)為其傳遞參數(shù)NULL。在符號表中插入新項(xiàng)有兩種方式。一是插入Symbol，二是插入詞素和詞法單元標(biāo)記。通過詞素獲取相應(yīng)的符號，由重載運(yùn)算符實(shí)現(xiàn)。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;/ 重載了運(yùn)算符，可以直接通過symboltablekey來獲取value。Symbol* operator (const std:string& key);std:vector inner_scopes_;/ 內(nèi)部作用域指針。SymbolTable* outer() return outer_scope_; private:SymbolTable* outer_scope_;/ 指向外部作用域/ 用哈希map存儲符號表。std:unordered_map table_;類Symbol表示符號表的符號，它也是類VariableSymbol和類FunctionSymbol的基類。一個符號由詞素和相應(yīng)的詞法單元標(biāo)記組成，一個用于關(guān)鍵字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_;/ 詞法單元標(biāo)記，表示詞法單元的屬性。;類VariableSymbol表示變量符號，用來存儲變量信息。offset_表示變量的偏移量，與變量在內(nèi)存的布局有關(guān)；width_表示變量類型的寬度；size_表示變量占用的字節(jié)數(shù)；is_array_表示變量是否是數(shù)組；data_type_表示變量的類型，DataType是一個枚舉類型，其中有三個元素，VOID_TYPE、INT_TYPE和CHAR_TYPE；kind_表示變量的種類，VariableKind是一個枚舉類型，其中有兩個元素，LOCAL表示變量是局部變量，ARGUMENT表示變量是參數(shù)。class VariableSymbol : public Symbolpublic:VariableSymbol(const std:string& identifier) : Symbol(identifier, ID) private:unsigned int offset_;/偏移量，即相對位置。unsigned intwidth_;/ 變量類型的寬度，即占用的字節(jié)數(shù)。unsigned int size_;/ 整個符號占用的字節(jié)數(shù)。bool is_array_;/ 當(dāng)前符號是否是數(shù)組。DataType data_type_;/ 數(shù)據(jù)類型，可以為int、char或void。VariableKind kind_;/ 變量的種類，可以為局部變量或參數(shù)變量。;enum DataTypeINT_TYPE,CHAR_TYPE,VOID_TYPE;enum VariableKindLOCAL,ARGUMENT;類FunctionSymbol表示函數(shù)符號，用來存儲函數(shù)信息。包括函數(shù)標(biāo)示符，返回類型及參數(shù)信息。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_;/ 參數(shù)列表。private:DataType return_type_;/ 函數(shù)的返回類型。;類Parameter保存函數(shù)的參數(shù)信息。包括參數(shù)的標(biāo)示符，類型，是否是數(shù)組。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_;/ 參數(shù)的類型。std:string identifier_;/ 參數(shù)的名字。bool is_array_;/ 參數(shù)是否為數(shù)組。;每個Token有個Tag變量，表示詞素的屬性，用于做出語法分析決定。用枚舉類型TokenTag實(shí)現(xiàn)。枚舉類型TokenTag的每個元素與編程語言上下文中的符號意義無關(guān)。在詞法分析階段，符號所代表的具體意義尚未知曉，在語法分析階段，才確定符號的具體意義。比如，符號“*”叫做“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,/ 保留關(guān)鍵字。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 詞法分析器詞法分析器的實(shí)現(xiàn)按照2.1.2節(jié)原理。狀態(tài)轉(zhuǎn)換圖用來跟蹤掃描器讀入的當(dāng)前查看字符。隨著字符的讀入，從一個狀態(tài)轉(zhuǎn)換到另一個狀態(tài)。當(dāng)進(jìn)入一個狀態(tài)，緊接著讀入下一個字符如果有一條從當(dāng)前狀態(tài)發(fā)出的邊且其上標(biāo)志的字符和讀入的字符相匹配，然后轉(zhuǎn)向改變指向的下一個狀態(tài)，否則報(bào)告錯誤。詞法分析器由類Lexer實(shí)現(xiàn)，可用通過GetNextToken()獲取下一個Token，或者通過PeekNextToken()查看下一個Token。核心算法在Scan()中實(shí)現(xiàn)，忽略注釋和空白符，分析出以下類型的Token： 算術(shù)運(yùn)算符：+ - * / % +