前言 教學(xué)建議 第1章 引論 1 1.1 編譯概述 1 1.2 編譯的過程 2 1.2.1 高級語言程序的處理過程 2 1.2.2 編譯的過程 3 1.3 編譯程序的生成 7 1.3.1 編譯程序的組合方式 7 1.3.2 編譯程序的生成方式 9 1.4 基本知識 11 1.4.1 形式語言 11 1.4.2 文法 14 1.5 練習(xí) 24 第2章 詞法分析 26 2.1 詞法分析概述 26 2.2 單詞的表示 27 2.2.1 單詞的種別 27 2.2.2 屬性 28 2.3 單詞的形式描述 29 2.3.1 正規(guī)式描述 30 2.3.2 正規(guī)文法描述 32 2.3.3 正規(guī)式與正規(guī)文法的等價性 33 2.4 有窮自動機 38 2.4.1 不確定的有窮自動機 38 2.4.2 確定的有窮自動機 40 2.4.3 NFA與DFA的等價性 41 2.4.4 DFA的化簡 45 2.4.5 正規(guī)式和FA的等價性 47 2.4.6 正規(guī)文法和FA的等價性 53 2.5 詞法分析程序的構(gòu)造 56 2.5.1 單詞識別程序的構(gòu)造 56 2.5.2 詞法分析程序的自動生成工具LEX簡介 59 2.6 練習(xí) 62 第3章 自頂向下的語法分析法 64 3.1 語法分析概述 64 3.2 自頂向下語法分析的實現(xiàn) 65 3.2.1 推導(dǎo)樹與語法樹 65 3.2.2 二義性 66 3.2.3 確定與不確定的自頂向下語法分析 67 3.3 確定的自頂向下的語法分析條件 70 3.3.1 LL(1)文法 70 3.3.2 非LL(1)文法到LL(1)文法的等價變換 75 3.4 自頂向下語法分析程序的構(gòu)造 80 3.4.1 預(yù)測分析法 80 3.4.2 遞歸下降分析法 83 3.5 練習(xí) 85 第4章 自底向上的語法分析法 88 4.1 自底向上語法分析的實現(xiàn) 88 4.1.1 歸約 88 4.1.2 短語和句柄 90 4.2 簡單優(yōu)先分析法 92 4.2.1 簡單優(yōu)先文法 92 4.2.2 簡單優(yōu)先分析算法 94 4.3 算符優(yōu)先分析法 96 4.3.1 算符優(yōu)先文法 96 4.3.2 算符優(yōu)先分析算法 100 4.3.3 優(yōu)先函數(shù) 103 4.4 練習(xí) 105 第5章 LR分析法 108 5.1 LR分析法概述 108 5.2 LR(0)分析 110 5.2.1 LR(0)項目集規(guī)范族 110 5.2.2 LR(0)文法 116 5.2.3 LR(0)分析器的工作過程 119 5.3 SLR(1)分析 120 5.3.1 SLR(1)文法 120 5.3.2 SLR(1)分析表的構(gòu)造 121 5.4 LR(1)分析 123 5.4.1 LR(1)文法 123 5.4.2 LR(1)項目集規(guī)范族的構(gòu)造 125 5.4.3 LR(1)分析表的構(gòu)造 126 5.5 LALR(1)分析 127 5.5.1 LALR(1)文法 127 5.5.2 LALR(1)分析表的構(gòu)造 128 5.6 語法分析程序的自動生成工具YACC簡介 130 5.6.1 YACC對語言的要求 130 5.6.2 YACC的輸入輸出 130 5.6.3 YACC源程序 131 5.7 練習(xí) 132 第6章 語義分析 135 6.1 語義分析概述 135 6.2 語法制導(dǎo)的語義計算 135 6.2.1 屬性文法 136 6.2.2 語義計算 138 6.3 符號表 140 6.3.1 符號表的概述 140 6.3.2 符號表的定義 141 6.3.3 符號表的組織 145 6.3.4 符號表的管理 153 6.4 練習(xí) 154 第7章 中間代碼生成 156 7.1 中間代碼生成概述 156 7.2 中間代碼 156 7.2.1 逆波蘭式 156 7.2.2 樹代碼 158 7.2.3 三地址碼 159 7.3 自底向上的語法制導(dǎo)翻譯 161 7.3.1 說明語句的翻譯 161 7.3.2 含簡單變量的賦值語句的翻譯 164 7.3.3 含數(shù)組元素的賦值語句的翻譯 167 7.3.4 布爾表達式的翻譯 168 7.3.5 控制語句的翻譯 174 7.3.6 過程調(diào)用 182 7.4 練習(xí) 183 第8章 運行時存儲空間的組織 185 8.1 運行時存儲空間的劃分 185 8.2 數(shù)據(jù)空間的存儲分配策略 186 8.2.1 靜態(tài)存儲分配策略 186 8.2.2 動態(tài)存儲分配策略 186 8.3 棧式存儲分配 190 8.3.1 簡單程序設(shè)計語言的棧式存儲分配 190 8.3.2 嵌套過程語言的棧式存儲分配 193 8.4 練習(xí) 199 第9章 代碼優(yōu)化 201 9.1 代碼優(yōu)化概述 201 9.2 局部優(yōu)化 201 9.2.1 基本塊及其劃分 202 9.2.2 基本塊的優(yōu)化技術(shù) 205 9.2.3 基本塊優(yōu)化技術(shù)的實現(xiàn) 207 9.3 循環(huán)優(yōu)化 212 9.3.1 程序中的循環(huán) 212 9.3.2 循環(huán)的優(yōu)化技術(shù)及其實現(xiàn) 217 9.4 練習(xí) 221 第10章 目標(biāo)代碼生成 224 10.1 目標(biāo)代碼生成概述 224 10.2 模型計算機的指令系統(tǒng) 225 10.2.1 尋址方式 225 10.2.2 指令系統(tǒng) 225 10.3 一種簡單的代碼生成算法 226 10.3.1 寄存器的使用原則 226 10.3.2 待用信息和活躍信息 227 10.3.3 寄存器描述和變量地址描述 231 10.3.4 基本塊的代碼生成算法 231 10.4 DAG的目標(biāo)代碼生成 234 10.5 練習(xí) 235 參考文獻 237