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

　　

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