【導(dǎo)讀】作源語(yǔ)言）書(shū)寫(xiě)的程序翻譯成另一種語(yǔ)言的等價(jià)的程序。編譯過(guò)程劃分了詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代。另外兩個(gè)重要的工作：表格處理和出錯(cuò)處理。與上述六個(gè)階級(jí)都有聯(lián)系。

　　

【正文】 N Y N Y Y N N Y N Y Programme() 調(diào)用主函數(shù)部分Main_Function() Const_Declaration()。 常量說(shuō)明處理 Var_Declaration() 變量說(shuō)明處理 Sub_Function() 測(cè)試 ch 是否為開(kāi)始符？ 出錯(cuò) 處理 在 TABLE 表中登記過(guò)程名 遞歸調(diào)用Programme() 取單詞 Get_Next_Token() 在 TABLE 表中返填子程序入口 生成開(kāi)辟數(shù)據(jù)段指令： int 0 A 調(diào)用語(yǔ)句處理過(guò)程 生成退出數(shù)據(jù)段的指令 OPR 0 0 測(cè)試 ch 是否為語(yǔ)句后跟符 出錯(cuò)處理 調(diào)用列目標(biāo)程序過(guò)程 返回 第 18 頁(yè) 共 41 頁(yè) 4． 3 語(yǔ)法分析概要設(shè)計(jì) 語(yǔ)法分析是編譯過(guò)程的核心部分，語(yǔ)法分析的任務(wù)是：按照文法，從源程序符號(hào)串中識(shí)別出各類(lèi)語(yǔ)法成分，同時(shí)進(jìn)行語(yǔ)法檢查，為語(yǔ)義分析和代碼生成做準(zhǔn)備。語(yǔ)法分析設(shè)計(jì)采用遞歸下降分析法，遞歸下降分析技術(shù)是一種無(wú)回溯的自頂向下分析 技術(shù)，它的實(shí)現(xiàn)思想是：讓一個(gè)識(shí)別符程序由一組子程序組成，其中每一個(gè)子程序?qū)?yīng)于文法的一個(gè)非終結(jié)符；根據(jù)文法的遞歸定義，這些子程序往往是遞歸子程序。這種技術(shù)稱(chēng)為遞歸下降技術(shù)，相應(yīng)的識(shí)別程序稱(chēng)為遞歸下降識(shí)別程序。在遞歸下降識(shí)別程序中的每一個(gè)子程序都對(duì)應(yīng)于文法的一個(gè)非終結(jié)符，更確切地說(shuō)為各個(gè)非終結(jié)符設(shè)計(jì)一個(gè)子程序，每一個(gè)子程序分析相對(duì)于相應(yīng)非終結(jié)符短語(yǔ)。例如，當(dāng)進(jìn)入關(guān)于非終結(jié)符號(hào)〈語(yǔ)句〉的遞歸子程序時(shí)，便期待句子中出現(xiàn)相對(duì)于〈語(yǔ)句〉的短語(yǔ)，這時(shí)必要的是讓識(shí)別程序邏輯知道句子中正期待短語(yǔ)的位置。遞歸下降分析技術(shù)是面 向目標(biāo)的，這個(gè)目標(biāo)是子程序所相應(yīng)的非終結(jié)符號(hào)，也是預(yù)測(cè)的，預(yù)言能找到這個(gè)相對(duì)于該非終結(jié)符號(hào)的短語(yǔ)。 C 語(yǔ)言的語(yǔ)法分析 EBNF 如下： 程序 [宏定義 ][頭文件 ]主函數(shù)（ main） [子函數(shù) ] 主函數(shù) (main) [變量說(shuō)明部分 ][常量說(shuō)明部分 ][子函數(shù)調(diào)用 ]語(yǔ)句 常量說(shuō)明部分 CONST常量定義 {， 常量定義 }； 常量定義 標(biāo)識(shí)符 =整型常量 整型常量 [+|]數(shù)字 {數(shù)字 } 變量說(shuō)明部分 類(lèi)型說(shuō)明 標(biāo)識(shí)符 {， 標(biāo)識(shí)符 }； 類(lèi)型說(shuō)明 int| flaot|double|char 標(biāo)識(shí)符 字母 {字母 | 數(shù)字 } 語(yǔ)句 賦值語(yǔ)句 |條件語(yǔ)句 |循環(huán)語(yǔ)句 |子函數(shù)調(diào)用語(yǔ)句 |輸入語(yǔ)句 |輸出語(yǔ)句 賦值語(yǔ)句 標(biāo)識(shí)符 =表達(dá)式 條件 表達(dá)式 關(guān)系運(yùn)算符 表達(dá)式 |！ 表達(dá)式 循環(huán)語(yǔ)句 FOR 循環(huán)語(yǔ)句 |WHILE 循環(huán)語(yǔ)句 |DOWHILE 循環(huán)語(yǔ)句 FOR 循 環(huán)語(yǔ)句 for‘（’ [賦值語(yǔ)句 ]‘； ‘[表達(dá)式 ]’； ‘[條件語(yǔ)句 ]’）‘ WHILE 循環(huán)語(yǔ)句 while‘(?條件 ‘)‘語(yǔ)句 dowhile 循環(huán)語(yǔ)句 do‘{?語(yǔ)句 ‘}‘while‘(?條件 ‘)‘ 函數(shù)調(diào)用語(yǔ)句 函數(shù)名 ‘（’ [變量說(shuō)明 ]‘）’ 輸入語(yǔ)句 scanf‘(?輸入類(lèi)型聲明 ‘，’‘ amp?！畼?biāo)識(shí)符 ’ )‘’；‘ 輸出語(yǔ)句 printf‘(?輸出類(lèi)型聲明 ‘，’ 標(biāo)識(shí)符 ’ )‘’；‘ 輸出類(lèi)型聲明 %d|%c|%s 表達(dá)式 [+|]項(xiàng) 加減法運(yùn)算符 項(xiàng) 項(xiàng) 因子 乘除法運(yùn)算符 因子 因子 標(biāo)識(shí)符 |無(wú)符號(hào)整數(shù) |‘（‘ 表達(dá)式 ’）‘ 加減法運(yùn)算符 +| 乘除法運(yùn)算符 *|/ 關(guān)系運(yùn)算符 ==||=||=|!= 條件語(yǔ)句 if條件 語(yǔ)句 else語(yǔ)句 字母 a|b|?? |A|B|?? |Z 數(shù)字 0|1|?? |9 用 C 語(yǔ)言實(shí)現(xiàn)遞歸下降分析程序如 下 ： void Error(){…} main( ) 第 19 頁(yè) 共 41 頁(yè) { Constant（） 。 Variable()； Call_sentence()； Sentence()。 } Constant（） /*常量說(shuō)明部分 */ { if(const) { Constant_define()。 } } Constant_define() /*常量定義 */ { Identifer（）； Integer_content()。 /*整型常量 */ } Variable() /*變量說(shuō)明部分 */ { if(類(lèi)型說(shuō)明 ) 定義標(biāo)識(shí)符； } Sentence() /*語(yǔ)句 */ { if(!Set_value_sentence()) if(!Condition_sentence()) if(!Circle_sentence()) if(!Call_sentence()) if(!printf) if(!scanf) return Error()。 } Set_value_sentence() { Identifer（）； /*標(biāo)識(shí)符 */ Expression（）； /*表達(dá)式 */ } Condition () /*條件 */ { Expression（）； Relation_symbol()。 /*關(guān)系運(yùn)算符 */ Expression（）； } 第 20 頁(yè) 共 41 頁(yè) Circle_sentence() /*循環(huán)語(yǔ)句 */ { for 語(yǔ)句（）； while 語(yǔ)句（）； dowhile 語(yǔ)句（）； } Call_sentence() /*函數(shù)調(diào)用語(yǔ)句 */ { Function_Identifer（）； /*函數(shù)名 */ } Expression（） /*表達(dá)式 */ { if(+|) Item()。 Math_ symbol()。 /*算數(shù)運(yùn)算符 */ Item()。 } Item() /*項(xiàng) */ { Factor()。 Math_ symbol()。 Factor()。 } Factor() /*因子 */ { Identifer（）； Integer。 If(?(?) Expression（） 。 If(?)‘) Get_next_word()。 } Math_ symbol() { if(Math_ symbol()) Get_next_word()。 } Relation_symbol()。 { if(Relation_symbol()) Get_next_word()。 } Condition_sentence () /*條件語(yǔ)句 */ { 第 21 頁(yè) 共 41 頁(yè) if(if){ if(?(?) Expression（） 。 if(?)‘) Sentence ()。 } if(else) Sentence ()。 } 目標(biāo)代碼的分析 代碼生成概要： ? 代碼生成的基礎(chǔ)是用目標(biāo)代碼段系統(tǒng)地替換 AST 的結(jié)點(diǎn)和子樹(shù)，用這種方法可以保持語(yǔ)義緊接著是一個(gè)線(xiàn)性代階段，從重寫(xiě)的 AST 產(chǎn)生一個(gè)線(xiàn)性指令序列。 ? 替換過(guò)程被 稱(chēng)為樹(shù)重寫(xiě)。線(xiàn)性化由目標(biāo)代碼段和數(shù)據(jù)流和控制流需求控制。 ? 代碼生成中的三個(gè)主要問(wèn)題是代碼選擇、寄存器分配和指令排序。 ? 一般情況下，發(fā)現(xiàn)最優(yōu)組合是 NP完全的。有三個(gè)方法簡(jiǎn)化代碼生成問(wèn)： 1每次只考慮 AST 的一小部分； 2 簡(jiǎn)化目標(biāo)機(jī)； 3限制代碼段之間的接口。 ? 代碼生成分三個(gè)階段進(jìn)行： 1 預(yù)處理，通過(guò)程序轉(zhuǎn)換，有些 AST 結(jié)點(diǎn)模式被其他AST 結(jié)點(diǎn)模式替換； 2 正確代碼生成，通過(guò)樹(shù)重寫(xiě)，所有 AST 結(jié)點(diǎn)模式被目標(biāo)代碼序列替換； 3 后處理，通過(guò)窺孔優(yōu)化，有些目標(biāo)代碼序列被其他目標(biāo)代碼序列替換。 ? 預(yù)處理和后處理可能反復(fù)執(zhí)行 ? 得到代碼 最簡(jiǎn)單的方法是為 AST 的每個(gè)結(jié)點(diǎn)生成代碼段，由迭代解釋程序?yàn)槠鋱?zhí)行。如果目標(biāo)代碼為 C 或 C++，所有優(yōu)化都可能留給 C 或 C++編譯程序。這個(gè)過(guò)程用最小的投入使解釋程序變?yōu)榫幾g程序。 ? 可以生成對(duì)庫(kù)中簡(jiǎn)單拷貝的例程調(diào)用，而不是多次重復(fù)一個(gè)代碼段，這可以相當(dāng)可觀地減小目標(biāo)代碼的長(zhǎng)度。這個(gè)技術(shù)被稱(chēng)為線(xiàn)程代碼。目標(biāo)代碼長(zhǎng)度的減少對(duì)嵌入式系統(tǒng)可能是重要的。 ? 通過(guò)將庫(kù)例程編號(hào)并且將程序存儲(chǔ)為這些編號(hào)數(shù)的一個(gè)列表可以大大減小目標(biāo)代碼長(zhǎng)度。所有目標(biāo)機(jī)依賴(lài)現(xiàn)在集中于庫(kù)例程中。 ? 在其他方向，每一個(gè)重復(fù)的代碼段可能在它們的上下文中被部 分求值，從而導(dǎo)致更有效的代碼。 ? 在簡(jiǎn)單代碼生成中，為每個(gè)可能的結(jié)點(diǎn)類(lèi)型選擇了到目標(biāo)代碼的固定翻譯。這些翻譯基于共同的接口規(guī)定。 ? 簡(jiǎn)單代碼生成只需局部判定，因此尤其適合窄編譯程序。 ? 寄存器機(jī)的簡(jiǎn)單代碼生成用機(jī)器指令重寫(xiě)每個(gè)表達(dá)式結(jié)點(diǎn)，這滿(mǎn)足了代碼選擇的需要。接口規(guī)定是：一條指令的輸出寄存器必要性須即用作父母指令的輸入寄存器。 ? 寄存器機(jī)上的表達(dá)式的代碼可以通過(guò)深度優(yōu)先遞歸訪問(wèn)生成，這滿(mǎn)足了指令排序的需要。遞歸例程攜帶兩個(gè)額外的參數(shù)，結(jié)果必須傳入其中的寄存器和空閑寄存器集，這滿(mǎn)足了寄存器分配的需要。 ? 因?yàn)槊總€(gè)沒(méi)有 處理的操作數(shù)都占用了一個(gè)寄存器，為需要最多寄存器的操作數(shù)首先編譯代碼是有利的。這要求可以在深度優(yōu)先訪問(wèn)中計(jì)算結(jié)點(diǎn)的權(quán)。 ? 當(dāng)一個(gè)表達(dá)式需要的寄存器多于可用的寄存器時(shí)，我們需要溢出一個(gè)和多個(gè)寄存 第 22 頁(yè) 共 41 頁(yè) 器至存儲(chǔ)器。沒(méi)有最好的寄存器溢出技術(shù)，除非進(jìn)行全面的研究。因此我們求助于啟發(fā)式算法。 ? 在一個(gè)啟發(fā)式算法中，我們分離出可以用可用寄存器編譯的最大子表達(dá)式，編譯它們，將結(jié)果存儲(chǔ)進(jìn)臨時(shí)變量。變減小了原始樹(shù)，我們對(duì)其重復(fù)這個(gè)過(guò)程。 ? 機(jī)器寄存器被編譯程序設(shè)計(jì)者分為四組：為管理目的所需的、為參數(shù)傳遞保留的、為表達(dá)式求值保留的和用于存 儲(chǔ)局部變量的。通常情況下，每個(gè)集合的大小是固定，并且有些集合可能是空的。 ? 通常情況下，為局部變量保留的寄存器集比候選集要小。啟發(fā)式算法包括先來(lái)先服務(wù)、來(lái)自程序員的寄存器提示以及從靜態(tài)或動(dòng)態(tài)簡(jiǎn)要表得的使用計(jì)數(shù)。更高級(jí)的啟發(fā)算法使用圖著色。 ? 棧上的編譯用符號(hào)解釋的編譯有些類(lèi)似于符號(hào)解釋。在后者中，我們保持符號(hào)表示法，但現(xiàn)在我們包括棧和寄存器，更重要的是，這一次，表示法中的信息必須精確。這種表示法被稱(chēng)為寄變描述符。 ? 如果結(jié)點(diǎn)的效果可以精確存儲(chǔ)于寄變描述符中，我們就這樣做。沒(méi)有為結(jié)點(diǎn)生成代碼，但其語(yǔ)義保留在寄變描述 符中：舊寄變描述 +結(jié)點(diǎn) ? 如呆結(jié)點(diǎn)的效果使我們不能精確地在寄變描述符中保留信息，我們生成代碼以獲得效果并且在寄變描述符中記錄結(jié)果。因此語(yǔ)義被保留于結(jié)點(diǎn)的重寫(xiě)中。 ? 如果從活躍分析中得到可用信息，當(dāng)離開(kāi)其活躍范圍時(shí)，我們可以從寄變描述符中刪除關(guān)于變量的所有信息。 ? 基本塊為控制圖的最大部分，它不包含分裂和結(jié)合。基本塊是從標(biāo)號(hào)或從例程的開(kāi)頭開(kāi)始，正好在轉(zhuǎn)移或類(lèi)轉(zhuǎn)移結(jié)點(diǎn)、標(biāo)號(hào)或例程的結(jié)尾結(jié)束。它只包含表達(dá)式和賦值。 ? 基本塊的概念從對(duì)控制流的關(guān)注中分離出對(duì)表達(dá)式和賦值的整齊序列的代碼生成的關(guān)注。這種分離對(duì)窄編譯程序尤其有 用，因?yàn)樗试S它們?yōu)楸磉_(dá)式序列做優(yōu)化代碼生成。 ? 基本塊的代碼生成分兩步進(jìn)行。首先將控制流圖轉(zhuǎn)換成依賴(lài)圖，它是一“ dag” ，即有向非循環(huán)圖。然后我們重寫(xiě)依賴(lài)圖至代碼。收益在于比起控制流圖，依賴(lài)圖對(duì)指令順序限制較少。 ? 基本塊的依賴(lài)圖由兩種依賴(lài)組成：表達(dá)式中通過(guò)操作數(shù)的數(shù)據(jù)依賴(lài)以及通過(guò)變量的數(shù)據(jù)依賴(lài)，這些變量的賦值中得到它們的值并且它們的值在且 中被繼續(xù)使用。最終的數(shù)據(jù)依賴(lài)是那些在基本塊后仍被需要的值，這些值稱(chēng)為基本塊的根。 ? 強(qiáng)調(diào)這些數(shù)據(jù)依賴(lài)并且移除其他的控制流依賴(lài)產(chǎn)生了一個(gè)粗糙的數(shù)據(jù)依賴(lài)圖，它可以通過(guò)旁路賦值并 且只保留那些從根可達(dá)的結(jié)點(diǎn)而被簡(jiǎn)化。這個(gè)圖是 dag,即有向非循環(huán)圖。