【正文】 return outer_scope_。 std::vectorSymbolTable* inner_scopes_。 Symbol* operator[] (const std::stringamp。 lexeme) const。 lexeme, TokenTag tag)。 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 20 bool Insert(Symbol* symbol)。 通過詞素獲取相應(yīng)的符號(hào)，由重載運(yùn)算符 []實(shí)現(xiàn)。 在符號(hào)表中插入新項(xiàng)有兩種方式。指針 outer_scope_指向外部作用域符號(hào)表。符號(hào)由類 Symbol 實(shí)現(xiàn)。符號(hào)表可以實(shí)現(xiàn)為線性表和哈希表，線性表雖然容易實(shí)現(xiàn)，但表很大時(shí)性能會(huì)很差，所以本設(shè)計(jì)采用哈希表。所以在此 不是創(chuàng)建一種新的語(yǔ)言，而是以此子語(yǔ)言為例編寫一個(gè)編譯器前端。 // if 塊中定義的變量 x, 它會(huì)將外部作用域中 x 覆蓋。 // 嵌套作用域中的定義的 x,它會(huì)將外部作用域中 x 覆蓋。 // 嵌套塊，產(chǎn)生一個(gè)新的內(nèi)部作用域?？墒?，在函數(shù)內(nèi)部， 可以自由嵌套作用域。 所以應(yīng)該注意定義函數(shù)的順序，當(dāng) 定義了很多相互調(diào)用的函數(shù) ，會(huì)使程序變得復(fù)雜 。 可以自定義函數(shù)。 readStr(char buffer[], int bufferSize)。 printChar(char c)。 printStr(string)。運(yùn)算符本身不出現(xiàn)在代碼中，布爾表達(dá)式的值是通過代碼序列中的位置來表示的。amp。 布爾表達(dá)式中不支持短路代碼。 字面值 ? 整型，如： 2343， 123 ? 字符串， 如：“ Hi， my name is XiKangjie\n” ? 字符， 如： ’a’, ‘\n’ 表達(dá)式 表達(dá)式中只支持以下運(yùn)算符： +， ，后綴 ++和 ， *， /， %， ， =， ， =， ==， ||， amp。另外，如果超過了數(shù)組的長(zhǎng)度，調(diào)用函數(shù)的棧結(jié)構(gòu)將會(huì)被破壞 。 只支持靜態(tài)數(shù)組。 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 17 3 設(shè)計(jì)與實(shí)現(xiàn) C 子語(yǔ)言 本設(shè)計(jì)將一個(gè)用 C 子語(yǔ)言編寫的源程序翻譯成中間代碼，該Ｃ子語(yǔ)言描述如下： 數(shù)據(jù)類型 該 子語(yǔ)言支持兩種數(shù)據(jù)類型： ? int： 32 位有符號(hào)整型。 在考慮第一個(gè)聲明之前， offset 被設(shè)置為 0。一般情況下，字符類型（ char）占用一個(gè)字節(jié)，整型（ int）占用 4 個(gè)字節(jié)。比如，將整數(shù)相加的指令往往希望整數(shù)能夠?qū)R（ aligned），也就是說，希望它們被放在內(nèi)存中特定的位置上，比如地址能夠被 4 整除的位置上。名字的類型和相對(duì)地址信息保存在相應(yīng)的符號(hào)表?xiàng)l目中 [12]。 前端 詞法分析器 語(yǔ)法分析器 中間代碼生成器 符號(hào)表 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 16 局部變量名的存儲(chǔ)布局 從變量類型可以知道該變量在運(yùn)行時(shí)刻需要的內(nèi)存數(shù)量。 } return float(c) / b // 此處的 b 為參數(shù) b。 c = a + b。 { int b = 100。 float foo(int a, float b) { int c。 ? 函數(shù)作用域：每個(gè)變量在函數(shù)內(nèi)部定義。 char c。 作用域 在靜態(tài)類型編程語(yǔ)言中，變量在使用之前必須聲明，聲明提供了變量的類型。 圖 符號(hào)表 符號(hào)表通常用哈希表實(shí)現(xiàn)。在基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 15 本設(shè)計(jì)中，由語(yǔ)法分析器來創(chuàng)建這些條目。如果新的名字出現(xiàn)或關(guān)于一個(gè)已存在名字新的信息出新，要對(duì)符號(hào)表進(jìn)行更新。編譯器用符號(hào)表跟蹤作用域及名字綁定的相關(guān)信息。 以上只是列舉了一些簡(jiǎn)單情況下的示例，對(duì)于復(fù)雜的源程序，翻譯成的四元式集是以上常見四元式結(jié)構(gòu)組合的結(jié)果。 c = add(a, b)。 ? 函數(shù)調(diào)用 int add(int a, int b) { return a + b。 default: a = a + 2。 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 13 ? switch 語(yǔ)句 switch(i) { case 1: a = a + 1。 ? while 語(yǔ)句 while(a b) a = a + 1。 else c = b。 i++ ) body = (=, 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:, _, _, _) 每個(gè) for 語(yǔ)句會(huì)產(chǎn)生四個(gè)標(biāo)號(hào)，一個(gè)表示類似“ i = 0”的初始化，一個(gè)表示類似“ i ３”的條件判斷，一個(gè)表示 body,一個(gè)表示類似“ i++”的表達(dá)式。 ? for 循環(huán) for(i = 0。 ? 條件跳轉(zhuǎn) (, i, 5, tmp1) // 條件 (jtrue, jump_address, tmp1, _) // 表示如果 tmp1 為真則跳轉(zhuǎn)。 ? 聲明 int a, b = 無 int a=5 = (=, 5, _, a) 聲明時(shí)可以進(jìn)行初始化。 a b = (, a, b, tmp) ? 一元運(yùn)算 a = (, a, _, tmp) 下劃線表示空。 四元式由如下成分組成： 中間代碼 目標(biāo)代碼分析器 1 目標(biāo)代碼分析器 2 目標(biāo)代碼 2 目標(biāo)代碼 1 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 10 ? 操作符 ? 操作數(shù)，即兩個(gè)操作數(shù) ? 結(jié)果，存儲(chǔ)運(yùn)算結(jié)果 （ operator, arg1, arg2, result） 一個(gè)簡(jiǎn)單的表達(dá)式可以用一個(gè)四元式表示： b + c = (+, b, c, tmp1) 稍微復(fù)雜的表達(dá)式可以由一個(gè)四元式集合表示，臨時(shí)變量存儲(chǔ)中間結(jié)果。 四元式 在四元式中，所有的操作都可以歸約為一元或二元操作。因此需要一種接近匯編語(yǔ)言的中間代碼，它支持機(jī)器無關(guān)級(jí)的優(yōu)化。 在后綴表達(dá)式中，任何語(yǔ)句表示都可以不使用括號(hào)，如： a * (9 + d) = a9d+* 后綴表達(dá)式 計(jì)算 可以通過棧來實(shí)現(xiàn)。 中間代碼可以是不同的語(yǔ)言，它由編譯器的設(shè)計(jì)者決定。中間代碼是機(jī)器無關(guān)的，但是它們接近機(jī)器指令。另外，很容易對(duì)中間代碼進(jìn)行優(yōu)化，優(yōu)化也是與機(jī)器無關(guān)的 [9]。中間代碼是跟目標(biāo)機(jī)器無關(guān)的，所以相同的中間代碼可以在目標(biāo)語(yǔ)言之間共享（如圖 ）。 factor ? digit | (expr) 現(xiàn)在考慮具有最高優(yōu)先級(jí)的二目運(yùn)算符 *和 /。 先考慮“ + * /”這四個(gè)常用運(yùn)算符之間的優(yōu)先級(jí)關(guān)系： 左結(jié)合： + 左結(jié)合： * / 創(chuàng)建兩個(gè)非終結(jié)符 expr 和 term， expr 對(duì)應(yīng)于“左結(jié)合： +”， term 對(duì)應(yīng)于“左結(jié)合：*/”，并使用另一個(gè)非終結(jié)符號(hào) factor 來表示表達(dá)式中的基本單元。該表達(dá)式可有兩種不同的翻譯，即（ 5 +２） * 3 或 5 + (2 * 3)。 stmt()。 optExpr()。 accept(‘?！?。 optExpr()。每個(gè)非終結(jié)符都產(chǎn)生一個(gè)對(duì)相應(yīng)過程的調(diào)用： 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 8 accept(for)。 expr。 在分析過程的開始，首先調(diào)用文法的開始非終結(jié)符號(hào) stmt 對(duì)應(yīng)的過程，根據(jù)相應(yīng)的語(yǔ)法規(guī)則，調(diào)用相應(yīng)的處理過程。過程 accept(t)將它的參數(shù) t 和向前看符號(hào)比較，如果匹配就前進(jìn)到下一個(gè)輸入終結(jié)符號(hào)。該分析器中還包括一個(gè)額外的過程 accept。 else report(?syntax error?)。 } } void optExpr() { if(curToken == expr) accept(expr)。 break。 break。 accept(‘)’)。 accept(‘?！?。 optExpr()。 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 7 case for: accept(for)。 stmt()。 accept(expr)。 case if: accept(if)。’)。 optExpr) stmt | other optExpr ? ε | expr 則預(yù)測(cè)分析器如下所示： void stmt() { switch(curToken) { case expr: accept(expr)。 | if(expr) stmt | for(optExpr。在預(yù)測(cè)分析法中，各個(gè)非終結(jié)符號(hào)對(duì)應(yīng)的過程中的控制流可以由向前看符號(hào)無二義性地 確定，在分析輸入串時(shí)出現(xiàn)的過程調(diào)用序列隱式地定義了該輸入串的一棵 語(yǔ)法樹 [8]。 為文法的每個(gè)非終結(jié)符都創(chuàng)建一個(gè)相應(yīng)的 過程。本設(shè)計(jì)語(yǔ)法分析采用遞歸下降分析法。 LR 分析法表示對(duì)輸入串從左到右掃描，構(gòu)造最右推導(dǎo)的逆過程。 LL(1)文法表示對(duì)輸入串從左到右掃描，進(jìn)行最左推導(dǎo)，分析時(shí)每步向前查看一個(gè)字符。自頂向下方法可以較容易地手工構(gòu)造出高效的語(yǔ)法分析器。 大多數(shù)分析方法都可以歸為以下兩類：自頂向下方法和自底向上方法。 語(yǔ)法分析 語(yǔ)法分析是分析如何根據(jù) 一個(gè)文法生成一個(gè)終結(jié)符號(hào)串的過程。圖 給出了幾個(gè)有限自動(dòng)機(jī)的例子。 } 詞法分析器將產(chǎn)生如下 tokens： INT ID(match) LPAREN CHAR STAR ID(str) RPAREN LBRACE IF LPAREN BANG ID(strncmp) LPAREN ID(str) COMMA STRING(0) COMMA NUM(1) RPAREN RPAREN RETURN REAL(0) SEMI RBRAC EOF 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 5 確定有限自動(dòng)機(jī) 確定有限自動(dòng)機(jī)可用來實(shí)現(xiàn)詞法分析器。 在詞法分析器中，詞法單元（ token）通常包含以下幾種類型： ? 標(biāo)識(shí) 符 ? 保留字（如：“ if”，“ while”等） ? 數(shù)值常量（如：整數(shù)，實(shí)數(shù)等） ? 字符串常量 ? 簡(jiǎn)單符號(hào)（運(yùn)算符如：“ +”，“ ”等，分隔符如：“；”，“，”等） ? 多重符號(hào)（運(yùn)算符如“ +=”，“ ++”等） 這些詞法單元將用于下一階段語(yǔ)法分析。 圖 編譯器前端 源代碼 目標(biāo)代碼 源代碼分析器 目標(biāo)代碼生成器 t1 = c t2 = b * t1 t3 = t1 + t2 t4 = t3 源代碼 前端 t1 = c t2 = b * t1 t3 = t1 + t2 t4 = t3 詞法分析器 語(yǔ)法分析器 中間代碼生成器 基于 GUI 的交互式編譯系統(tǒng)之中間代碼生成器的設(shè)計(jì)與實(shí)現(xiàn) 4 詞法分析 詞法分析器以字符流作為輸入， 刪除單詞之間的空白符和注釋（程序中每一部分都有可能出現(xiàn)空白和注釋）并 生成一系列的名字 、關(guān)鍵字和標(biāo)點(diǎn)符號(hào)。本設(shè)計(jì)要實(shí)現(xiàn)的正是 編譯器的前端。 圖 編譯器結(jié)構(gòu) 源代碼分析器不依賴于機(jī)器，然而 目標(biāo)代碼生成器需要針對(duì)不同的機(jī)器類型生成不同的代碼，因此是依賴于機(jī)器的。 （ 1） 源代碼分析器：它將輸入的源代碼看作是一個(gè)字符串，然后將其翻譯成有意義的符號(hào)（變量，值，操作符等）。 return b。機(jī)器碼是計(jì)算機(jī)可以執(zhí)行的一系列指令 [4]。本設(shè)計(jì)可以報(bào)告出錯(cuò)誤是什么及錯(cuò)誤在源程序的行號(hào)和列號(hào)。詞法分析階段可以檢測(cè)出來自輸入的字符串不能形成語(yǔ)言的任何單詞符號(hào)（ token）。編譯 器可以使用的中間代碼有多種形式，對(duì)于本設(shè)計(jì)，采用 簡(jiǎn)單的四元式。這種實(shí)現(xiàn)要更容易 合理些。 中間代碼（ intermediate code, IC）是一種抽 象機(jī)器語(yǔ)言，它可以表示目標(biāo)機(jī)的操作而不需太多涉及與機(jī)器相關(guān)的細(xì)節(jié)， 而且，它也獨(dú)立于源語(yǔ)言的細(xì)節(jié) [3]。假設(shè)需要 這樣一個(gè)編譯器：它可以編譯 N 種不同的源語(yǔ)言，然后 為 M 臺(tái)不同的目標(biāo)機(jī)生成 代碼。對(duì)于本設(shè)計(jì)， 采用的是自頂向