編譯原理

定　價(jià)：￥55.00

作　者：	（美）Alfred V. Aho等著；李建中，姜守旭譯；李建中譯
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：	計(jì)算機(jī)科學(xué)叢書
標(biāo)　簽：	編譯原理

購(gòu)買這本書可以去

ISBN：	9787111123491	出版時(shí)間：	2003-08-01	包裝：	膠版紙
開本：	26cm	頁(yè)數(shù)：	524	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)分析、類型檢查、運(yùn)行環(huán)境、中間代碼生成、代碼生成、代碼優(yōu)化等，并在最后兩章中討論了實(shí)現(xiàn)編譯器的一些編程問(wèn)題和幾個(gè)編譯器實(shí)例，每章都提供了大量的練習(xí)和參考文獻(xiàn)。本書從介紹編譯的原理性概念開始，然后通過(guò)構(gòu)建一個(gè)簡(jiǎn)單的一遍編譯器來(lái)逐一解釋這些概念。本書是編譯原理課程的經(jīng)典教材，作者曾多次使用本書的內(nèi)容在貝爾實(shí)驗(yàn)室、哥倫比亞大學(xué)、普林斯頓大學(xué)和斯坦福大學(xué)向本科生和研究生講授初等及高等編譯課程。本書作者AlfredV．Aho、RaviSethi和JeffreyD．Ullman是世界著名的計(jì)算機(jī)科學(xué)家，他們?cè)谟?jì)算機(jī)科學(xué)理論、數(shù)據(jù)庫(kù)等很多領(lǐng)域都做出了杰出貢獻(xiàn)。本書是編譯領(lǐng)域無(wú)可替代的經(jīng)典著作，被廣大計(jì)算機(jī)專業(yè)人士譽(yù)為“龍書”。本書一直被世界各地的著名高等院校和科研機(jī)構(gòu)（如貝爾實(shí)驗(yàn)室、哥倫比亞大學(xué)、普林斯頓大學(xué)和斯坦福大學(xué)等）廣泛用作本科生和研究生編譯原理與技術(shù)課程的教材，本書對(duì)我國(guó)計(jì)算機(jī)教育界也具有重大影響。書中深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)分析、類型檢查、運(yùn)行環(huán)境、中間代碼生成、代碼生成、代碼優(yōu)化等，并在最后兩章中討論了實(shí)現(xiàn)編譯器的一些編程問(wèn)題和幾個(gè)編譯器實(shí)例，而且每章都提供了大量的練習(xí)和參考文獻(xiàn)。本書可以作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生編譯原理與技術(shù)課程的教材，也可以作為計(jì)算機(jī)技術(shù)人員必讀的專業(yè)參考書之一。讀大師名著，做IT精英

作者簡(jiǎn)介

　　AlfredV.Aho于普林斯頓大學(xué)獲得博士學(xué)位，現(xiàn)任貝爾實(shí)驗(yàn)室基礎(chǔ)科學(xué)研究院副院長(zhǎng)、計(jì)算機(jī)科學(xué)研究中心主任。在貝爾實(shí)驗(yàn)室主要負(fù)責(zé)計(jì)算科學(xué)和軟件研究工作，已經(jīng)出版多本算法、數(shù)據(jù)結(jié)構(gòu)、編譯器、數(shù)據(jù)庫(kù)系統(tǒng)及計(jì)算機(jī)科學(xué)基礎(chǔ)等方面的經(jīng)典著相關(guān)圖書C++語(yǔ)言的設(shè)計(jì)和演化離散數(shù)學(xué)導(dǎo)學(xué)數(shù)據(jù)庫(kù)設(shè)計(jì)教程（第２版）信息論、編碼與密碼學(xué)軟件需求3D游戲卷1實(shí)時(shí)渲染與軟件技術(shù)現(xiàn)代信息檢索CAXA數(shù)控銑CAD/CAM技術(shù)C語(yǔ)言的科學(xué)和藝術(shù)計(jì)算機(jī)視覺(jué)UNIX系統(tǒng)編程信息系統(tǒng)原理：原書第6版并行程序設(shè)計(jì)數(shù)據(jù)庫(kù)與事務(wù)處理計(jì)算機(jī)科學(xué)概論（原書第2版）人工智能：英文可擴(kuò)展并行計(jì)算技術(shù)、結(jié)構(gòu)與編程數(shù)據(jù)庫(kù)原理、編程與性能Java面向?qū)ο蟪绦蛟O(shè)計(jì)教程嵌入式微控制器C++編程思想。第2卷：實(shí)用編程技術(shù)微機(jī)接口技術(shù)實(shí)驗(yàn)教程數(shù)據(jù)倉(cāng)庫(kù)（原書第3版）神經(jīng)網(wǎng)絡(luò)原理（原書第２版）并行計(jì)算導(dǎo)論（原書第2版）組合數(shù)學(xué)（原書第4版）JAVA編程思想（第2版）數(shù)據(jù)庫(kù)系統(tǒng)導(dǎo)論3D游戲卷2動(dòng)畫與高級(jí)實(shí)時(shí)渲染技術(shù)數(shù)字圖像處理疑難解析操作系統(tǒng)現(xiàn)代操作系統(tǒng)（第2版）計(jì)算機(jī)網(wǎng)絡(luò)：自頂向下方法與Internet特色（原書第3版）高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)方案（原書第3版）3D計(jì)算機(jī)圖形學(xué)（原書第3版）C程序設(shè)計(jì)語(yǔ)言（第2版·新版）習(xí)題解答計(jì)算機(jī)網(wǎng)絡(luò)與因特網(wǎng)（原書第4版）模式分析的核方法

圖書目錄

出版者的話 專家指導(dǎo)委員會(huì) 譯者序 前言 第1章編譯簡(jiǎn)介 1 1.1 編譯器 1 1.1.1 編譯的分析-綜合模型 1 1.1.2 編譯器的前驅(qū)與后繼 3 1.2 源程序分析 3 1.2.1 詞法分析 3 1.2.2 語(yǔ)法分析 3 1.2.3 語(yǔ)義分析 5 1.2.4 文本格式器中的分析 5 1.3 編譯器的各階段 6 1.3.1 符號(hào)表管理 7 1.3.2 錯(cuò)誤檢測(cè)與報(bào)告 7 1.3.3 各分析階段 7 1.3.4 中間代碼生成 9 1.3.5 代碼優(yōu)化 9 1.3.6 代碼生成 10 1.4 編譯器的伙伴 10 1.4.1 預(yù)處理器 10 1.4.2 匯編器 11 1.4.3 兩遍匯編 12 1.4.4 裝配器和連接編輯器 12 1.5 編譯器各階段的分組 13 1.5.1 前端與后端 13 1.5.2 編譯器的遍 13 1.5.3 減少編譯的遍數(shù) 14 1.6 編譯器的構(gòu)造工具 14 參考文獻(xiàn)注釋 15 第2章簡(jiǎn)單的一遍編譯器 17 2.1 概述 17 2.2 語(yǔ)法定義 17 2.2.1 分析樹 19 2.2.2 二義性 20 2.2.3 操作符的結(jié)合規(guī)則 20 2.2.4 操作符的優(yōu)先級(jí) 21 2.3 語(yǔ)法制導(dǎo)翻譯 22 2.3.1 后綴表示 22 2.3.2 語(yǔ)法制導(dǎo)定義 22 2.3.3 綜合屬性 23 2.3.4 深度優(yōu)先遍歷 24 2.3.5 翻譯模式 25 2.3.6 翻譯的輸出 25 2.4 語(yǔ)法分析 26 2.4.1 自頂向下語(yǔ)法分析 27 2.4.2 預(yù)測(cè)分析法 29 2.4.3 何時(shí)使用產(chǎn)生式 30 2.4.4 設(shè)計(jì)一個(gè)預(yù)測(cè)語(yǔ)法分析器 30 2.4.5 左遞歸 31 2.5 簡(jiǎn)單表達(dá)式的翻譯器 32 2.5.1 抽象語(yǔ)法和具體語(yǔ)法 32 2.5.2 調(diào)整翻譯模式 33 2.5.3 非終結(jié)符expr. term 和rest 的過(guò)程 33 2.5.4 翻譯器的優(yōu)化 35 2.5.5 完整程序 35 2.6 詞法分析 37 2.6.1 剔除空白符和注釋 37 2.6.2 常數(shù) 37 2.6.3 識(shí)別標(biāo)識(shí)符和關(guān)鍵字 37 2.6.4 詞法分析器的接口 38 2.6.5 詞法分析器 38 2.7 符號(hào)表 40 2.7.1 符號(hào)表接口 40 2.7.2 處理保留的關(guān)鍵字 41 2.7.3 符號(hào)表的實(shí)現(xiàn)方法 41 2.8 抽象堆棧機(jī) 42 2.8.1 算術(shù)指令 42 2.8.2 左值和右值 43 2.8.3 堆棧操作 43 2.8.4 表達(dá)式的翻譯 43 2.8.5 控制流 44 2.8.6 語(yǔ)句的翻譯 44 2.8.7 輸出一個(gè)翻譯 45 2.9 技術(shù)的綜合 46 2.9.1 翻譯器的描述 46 2.9.2 詞法分析器模塊lexer.c 47 2.9.3 語(yǔ)法分析器模塊parser.c 48 2.9.4 輸出模塊emitter.c 48 2.9.5 符號(hào)表模塊symbol.c和init.c 48 2.9.6 錯(cuò)誤處理模塊error.c 48 2.9.7 編譯器的建立 48 2.9.8 程序清單 49 練習(xí) 53 編程練習(xí) 54 參考文獻(xiàn)注釋 55 第3章詞法分析 57 3.1 詞法分析器的作用 57 3.1.1 詞法分析中的問(wèn)題 58 3.1.2 記號(hào). 模式. 詞素 58 3.1.3 記號(hào)的屬性 59 3.1.4 詞法錯(cuò)誤 60 3.2 輸入緩沖 60 3.2.1 雙緩沖區(qū) 61 3.2.2 標(biāo)志 62 3.3 記號(hào)的描述 62 3.3.1 串和語(yǔ)言 62 3.3.2 語(yǔ)言上的運(yùn)算 63 3.3.3 正規(guī)表達(dá)式 64 3.3.4 正規(guī)定義 65 3.3.5 縮寫表示法 66 3.3.6 非正規(guī)集 66 3.4 記號(hào)的識(shí)別 67 3.4.1 狀態(tài)轉(zhuǎn)換圖 68 3.4.2 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 70 3.5 詞法分析器描述語(yǔ)言 72 3.5.1 Lex說(shuō)明 72 3.5.2 超前掃描操作 75 3.6 有窮自動(dòng)機(jī) 76 3.6.1 不確定的有窮自動(dòng)機(jī) 77 3.6.2 確定的有窮自動(dòng)機(jī) 78 3.6.3 從NFA到DFA的變換 79 3.7 從正規(guī)表達(dá)式到NFA 81 3.7.1 從正規(guī)表達(dá)式構(gòu)造NFA 81 3.7.2 NFA的雙堆棧模擬 84 3.7.3 時(shí)間空間的權(quán)衡 85 3.8 設(shè)計(jì)詞法分析器的生成器 85 3.8.1 基于NFA的模式匹配 86 3.8.2 詞法分析器的DFA 88 3.8.3 實(shí)現(xiàn)超前掃描操作 88 3.9 基于DFA的模式匹配器的優(yōu)化 89 3.9.1 NFA的重要狀態(tài) 89 3.9.2 從正規(guī)表達(dá)式到DFA 89 3.9.3 最小化DFA的狀態(tài)數(shù) 93 3.9.4 詞法分析器的狀態(tài)最小化 95 3.9.5 表壓縮方法 95 練習(xí) 97 編程練習(xí) 103 參考文獻(xiàn)注釋 103 第4章語(yǔ)法分析 105 4.1 語(yǔ)法分析器的作用 105 4.1.1 語(yǔ)法錯(cuò)誤的處理 106 4.1.2 錯(cuò)誤恢復(fù)策略 108 4.2 上下文無(wú)關(guān)文法 109 4.2.1 符號(hào)的使用約定 110 4.2.2 推導(dǎo) 110 4.2.3 分析樹和推導(dǎo) 112 4.2.4 二義性 113 4.3 文法的編寫 113 4.3.1 正規(guī)表達(dá)式和上下文無(wú)關(guān)文法的 比較 114 4.3.2 驗(yàn)證文法所產(chǎn)生的語(yǔ)言 114 4.3.3 消除二義性 115 4.3.4 消除左遞歸 116 4.3.5 提取左因子 117 4.3.6 非上下文無(wú)關(guān)語(yǔ)言的結(jié)構(gòu) 118 4.4 自頂向下語(yǔ)法分析 120 4.4.1 遞歸下降語(yǔ)法分析法 120 4.4.2 預(yù)測(cè)語(yǔ)法分析器 121 4.4.3 預(yù)測(cè)語(yǔ)法分析器的狀態(tài)轉(zhuǎn)換圖 121 4.4.4 非遞歸的預(yù)測(cè)分析 123 4.4.5 FIRST和FOLLOW 124 4.4.6 預(yù)測(cè)分析表的構(gòu)造 125 4.4.7 LL(1)文法 126 4.4.8 預(yù)測(cè)分析的錯(cuò)誤恢復(fù) 127 4.5 自底向上語(yǔ)法分析 128 4.5.1 句柄 129 4.5.2 句柄裁剪 130 4.5.3 用棧實(shí)現(xiàn)移動(dòng)歸約分析 131 4.5.4 活前綴 133 4.5.5 移動(dòng)歸約分析過(guò)程中的沖突 133 4.6 算符優(yōu)先分析法 134 4.6.1 使用算符優(yōu)先關(guān)系 135 4.6.2 從結(jié)合律和優(yōu)先級(jí)獲得算符優(yōu)先 關(guān)系 136 4.6.3 處理一元操作符 137 4.6.4 優(yōu)先函數(shù) 137 4.6.5 算符優(yōu)先分析中的錯(cuò)誤恢復(fù) 139 4.7 LR語(yǔ)法分析器 142 4.7.1 LR語(yǔ)法分析算法 142 4.7.2 LR文法 145 4.7.3 構(gòu)造SLR語(yǔ)法分析表 146 4.7.4 構(gòu)造規(guī)范LR語(yǔ)法分析表 151 4.7.5 構(gòu)造LALR語(yǔ)法分析表 155 4.7.6 LALR語(yǔ)法分析表的有效構(gòu)造 方法 158 4.7.7 LR語(yǔ)法分析表的壓縮 161 4.8 二義文法的應(yīng)用 163 4.8.1 使用優(yōu)先級(jí)和結(jié)合規(guī)則來(lái)解決分析 動(dòng)作的沖突 163 4.8.2 懸空else的二義性 164 4.8.3 特例產(chǎn)生式引起的二義性 165 4.8.4 LR語(yǔ)法分析中的錯(cuò)誤恢復(fù) 167 4.9 語(yǔ)法分析器的生成器 168 4.9.1 語(yǔ)法分析器的生成器Yacc 169 4.9.2 用Yacc處理二義文法 171 4.9.3 用Lex建立Yacc的詞法分析器 173 4.9.4 Yacc的錯(cuò)誤恢復(fù) 174 練習(xí) 174 參考文獻(xiàn)注釋 182 第5章語(yǔ)法制導(dǎo)翻譯 185 5.1 語(yǔ)法制導(dǎo)定義 185 5.1.1 語(yǔ)法制導(dǎo)定義的形式 186 5.1.2 綜合屬性 186 5.1.3 繼承屬性 187 5.1.4 依賴圖 187 5.1.5 計(jì)算順序 189 5.2 語(yǔ)法樹的構(gòu)造 189 5.2.1 語(yǔ)法樹 190 5.2.2 構(gòu)造表達(dá)式的語(yǔ)法樹 190 5.2.3 構(gòu)造語(yǔ)法樹的語(yǔ)法制導(dǎo)定義 191 5.2.4 表達(dá)式的無(wú)環(huán)有向圖 192 5.3 自底向上計(jì)算S屬性定義 194 5.4 L屬性定義 195 5.4.1 L屬性定義 196 5.4.2 翻譯模式 196 5.5 自頂向下翻譯 198 5.5.1 從翻譯模式中消除左遞歸 198 5.5.2 預(yù)測(cè)翻譯器的設(shè)計(jì) 201 5.6 自底向上計(jì)算繼承屬性 202 5.6.1 刪除嵌入在翻譯模式中的動(dòng)作 202 5.6.2 分析棧中的繼承屬性 203 5.6.3 模擬繼承屬性的計(jì)算 204 5.6.4 用綜合屬性代替繼承屬性 206 5.6.5 一個(gè)難計(jì)算的語(yǔ)法制導(dǎo)定義 207 5.7 遞歸計(jì)算 207 5.7.1 從左到右遍歷 207 5.7.2 其他遍歷方法 208 5.8 編譯時(shí)屬性值的空間分配 209 5.8.1 在編譯時(shí)為屬性分配空間 209 5.8.2 避免復(fù)制 211 5.9 編譯器構(gòu)造時(shí)的空間分配 211 5.9.1 從文法中預(yù)知生存期 212 5.9.2 不相重疊的生存期 214 5.10 語(yǔ)法制導(dǎo)定義的分析 215 5.10.1 屬性的遞歸計(jì)算 216 5.10.2 強(qiáng)無(wú)環(huán)的語(yǔ)法制導(dǎo)定義 216 5.10.3 環(huán)形檢測(cè) 217 練習(xí) 219 參考文獻(xiàn)注釋 221 第6章類型檢查 223 6.1 類型系統(tǒng) 224 6.1.1 類型表達(dá)式 224 6.1.2 類型系統(tǒng) 225 6.1.3 靜態(tài)和動(dòng)態(tài)類型檢查 226 6.1.4 錯(cuò)誤恢復(fù) 226 6.2 一個(gè)簡(jiǎn)單的類型檢查器的說(shuō)明 226 6.2.1 一種簡(jiǎn)單語(yǔ)言 226 6.2.2 表達(dá)式的類型檢查 227 6.2.3 語(yǔ)句的類型檢查 228 6.2.4 函數(shù)的類型檢查 228 6.3 類型表達(dá)式的等價(jià) 229 6.3.1 類型表達(dá)式的結(jié)構(gòu)等價(jià) 229 6.3.2 類型表達(dá)式的名字 231 6.3.3 類型表示中的環(huán) 232 6.4 類型轉(zhuǎn)換 233 6.5 函數(shù)和運(yùn)算符的重載 234 6.5.1 子表達(dá)式的可能類型的集合 235 6.5.2 縮小可能類型的集合 236 6.6 多態(tài)函數(shù) 237 6.6.1 為什么要使用多態(tài)函數(shù) 237 6.6.2 類型變量 238 6.6.3 包含多態(tài)函數(shù)的語(yǔ)言 239 6.6.4 代換. 實(shí)例和合一 240 6.6.5 多態(tài)函數(shù)的檢查 241 6.7 合一算法 244 練習(xí) 247 參考文獻(xiàn)注釋 251 第7章運(yùn)行時(shí)環(huán)境 253 7.1 源語(yǔ)言問(wèn)題 253 7.1.1 過(guò)程 253 7.1.2 活動(dòng)樹 253 7.1.3 控制棧 255 7.1.4 聲明的作用域 256 7.1.5 名字的綁定 256 7.1.6 一些問(wèn)題 257 7.2 存儲(chǔ)組織 257 7.2.1 運(yùn)行時(shí)內(nèi)存的劃分 257 7.2.2 活動(dòng)記錄 258 7.2.3 編譯時(shí)的局部數(shù)據(jù)布局 259 7.3 存儲(chǔ)分配策略 260 7.3.1 靜態(tài)存儲(chǔ)分配 260 7.3.2 棧式存儲(chǔ)分配 262 7.3.3 懸空引用 265 7.3.4 堆式存儲(chǔ)分配 265 7.4 對(duì)非局部名字的訪問(wèn) 266 7.4.1 程序塊 267 7.4.2 無(wú)嵌套過(guò)程的詞法作用域 268 7.4.3 包含嵌套過(guò)程的詞法作用域 269 7.4.4 動(dòng)態(tài)作用域 274 7.5 參數(shù)傳遞 275 7.5.1 傳值調(diào)用 275 7.5.2 引用調(diào)用 276 7.5.3 復(fù)制-恢復(fù) 277 7.5.4 傳名調(diào)用 277 7.6 符號(hào)表 278 7.6.1 符號(hào)表表項(xiàng) 278 7.6.2 名字中的字符 279 7.6.3 存儲(chǔ)分配信息 280 7.6.4 符號(hào)表的線性表數(shù)據(jù)結(jié)構(gòu) 280 7.6.5 散列表 281 7.6.6 表示作用域的信息 283 7.7 支持動(dòng)態(tài)存儲(chǔ)分配的語(yǔ)言措施 285 7.7.1 垃圾單元 285 7.7.2 懸空引用 286 7.8 動(dòng)態(tài)存儲(chǔ)分配技術(shù) 287 7.8.1 固定塊的顯式分配 287 7.8.2 變長(zhǎng)塊的顯式分配 287 7.8.3 隱式存儲(chǔ)釋放 288 7.9 Fortran語(yǔ)言的存儲(chǔ)分配 288 7.9.1 COMMON區(qū)域中的數(shù)據(jù) 289 7.9.2 一個(gè)簡(jiǎn)單的等價(jià)算法 290 7.9.3 Fortran語(yǔ)言的等價(jià)算法 292 7.9.4 映射數(shù)據(jù)區(qū) 294 練習(xí) 294 參考文獻(xiàn)注釋 298 第8章中間代碼生成 299 8.1 中間語(yǔ)言 299 8.1.1 圖表示 299 8.1.2 三地址碼 300 8.1.3 三地址語(yǔ)句的類型 301 8.1.4 語(yǔ)法制導(dǎo)翻譯生成三地址碼 302 8.1.5 三地址語(yǔ)句的實(shí)現(xiàn) 303 8.1.6 表示方法比較：間址的使用 305 8.2 聲明語(yǔ)句 305 8.2.1 過(guò)程中的聲明語(yǔ)句 305 8.2.2 跟蹤作用域信息 306 8.2.3 記錄中的域名 308 8.3 賦值語(yǔ)句 309 8.3.1 符號(hào)表中的名字 309 8.3.2 臨時(shí)名字的重用 310 8.3.3 尋址數(shù)組元素 311 8.3.4 數(shù)組元素尋址的翻譯模式 312 8.3.5 賦值語(yǔ)句中的類型轉(zhuǎn)換 314 8.3.6 記錄域的訪問(wèn) 315 8.4 布爾表達(dá)式 315 8.4.1 翻譯布爾表達(dá)式的方法 316 8.4.2 數(shù)值表示 316 8.4.3 短路代碼 317 8.4.4 控制流語(yǔ)句 317 8.4.5 布爾表達(dá)式的控制流翻譯 319 8.4.6 混合模式的布爾表達(dá)式 321 8.5 case語(yǔ)句 321 8.6 回填 323 8.6.1 布爾表達(dá)式 323 8.6.2 控制流語(yǔ)句 326 8.6.3 翻譯的實(shí)現(xiàn)方案 326 8.6.4 標(biāo)號(hào)和goto 327 8.7 過(guò)程調(diào)用 328 8.7.1 調(diào)用序列 328 8.7.2 一個(gè)簡(jiǎn)單的例子 328 練習(xí) 329 參考文獻(xiàn)注釋 331 第9章代碼生成 333 9.1 代碼生成器設(shè)計(jì)中的問(wèn)題 333 9.1.1 代碼生成器的輸入 333 9.1.2 目標(biāo)程序 334 9.1.3 存儲(chǔ)管理 334 9.1.4 指令選擇 334 9.1.5 寄存器分配 335 9.1.6 計(jì)算次序的選擇 336 9.1.7 代碼生成方法 336 9.2 目標(biāo)機(jī)器 336 9.3 運(yùn)行時(shí)存儲(chǔ)管理 338 9.3.1 靜態(tài)分配 339 9.3.2 棧式分配 340 9.3.3 名字的運(yùn)行地址 342 9.4 基本塊和流圖 343 9.4.1 基本塊 343 9.4.2 基本塊的變換 344 9.4.3 保結(jié)構(gòu)變換 344 9.4.4 代數(shù)變換 345 9.4.5 流圖 345 9.4.6 基本塊的表示 345 9.4.7 循環(huán) 346 9.5 下次引用信息 346 9.5.1 計(jì)算下次引用信息 346 9.5.2 臨時(shí)名字的存儲(chǔ)分配 347 9.6 一個(gè)簡(jiǎn)單的代碼生成器 347 9.6.1 寄存器描述符和地址描述符 348 9.6.2 代碼生成算法 348 9.6.3 函數(shù)getreg 349 9.6.4 為其他類型的語(yǔ)句生成代碼 350 9.6.5 條件語(yǔ)句 351 9.7 寄存器分配與指派 351 9.7.1 全局寄存器分配 352 9.7.2 引用計(jì)數(shù) 352 9.7.3 外層循環(huán)的寄存器指派 353 9.7.4 圖染色法寄存器分配 354 9.8 基本塊的dag表示法 354 9.8.1 dag的構(gòu)造 355 9.8.2 dag的應(yīng)用 357 9.8.3 數(shù)組. 指針和過(guò)程調(diào)用 358 9.9 窺孔優(yōu)化 359 9.9.1 冗余加載與保存 360 9.9.2 不可達(dá)代碼 360 9.9.3 控制流優(yōu)化 361 9.9.4 代數(shù)化簡(jiǎn) 361 9.9.5 強(qiáng)度削弱 361 9.9.6 機(jī)器語(yǔ)言的使用 362 9.10 從dag生成代碼 362 9.10.1 重排序 362 9.10.2 對(duì)dag的啟發(fā)式排序 362 9.10.3 樹的最優(yōu)排序 363 9.10.4 標(biāo)記算法 364 9.10.5 從標(biāo)記樹中產(chǎn)生代碼 364 9.10.6 多寄存器操作 367 9.10.7 代數(shù)性質(zhì) 367 9.10.8 公共子表達(dá)式 368 9.11 動(dòng)態(tài)規(guī)劃代碼生成算法 368 9.11.1 一種寄存器計(jì)算機(jī) 368 9.11.2 動(dòng)態(tài)規(guī)劃的原理 369 9.11.3 鄰近計(jì)算 369 9.11.4 動(dòng)態(tài)規(guī)劃算法 369 9.12 代碼生成器的生成器 371 9.12.1 采用重寫樹技術(shù)的代碼生成 371 9.12.2 借助語(yǔ)法分析的模式匹配 375 9.12.3 用于語(yǔ)義檢查的例程 376 練習(xí) 376 參考文獻(xiàn)注釋 378 第10章代碼優(yōu)化 381 10.1 引言 381 10.1.1 代碼改進(jìn)變換的準(zhǔn)則 381 10.1.2 性能的提高 382 10.1.3 優(yōu)化編譯器的組織 383 10.2 優(yōu)化的主要種類 384 10.2.1 保持功能變換 385 10.2.2 公共子表達(dá)式 386 10.2.3 復(fù)制傳播 387 10.2.4 無(wú)用代碼刪除 387 10.2.5 循環(huán)優(yōu)化 388 10.2.6 代碼外提 388 10.2.7 歸納變量和強(qiáng)度削弱 388 10.3 基本塊的優(yōu)化 390 10.4 流圖中的循環(huán) 392 10.4.1 支配節(jié)點(diǎn) 392 10.4.2 自然循環(huán) 393 10.4.3 內(nèi)循環(huán) 393 10.4.4 前置首節(jié)點(diǎn) 394 10.4.5 可約流圖 394 10.5 全局?jǐn)?shù)據(jù)流分析介紹 395 10.5.1 點(diǎn)和路徑 396 10.5.2 到達(dá)定義 396 10.5.3 結(jié)構(gòu)化程序的數(shù)據(jù)流分析 397 10.5.4 對(duì)數(shù)據(jù)流信息的保守估計(jì) 399 10.5.5 in 和 out 的計(jì)算 400 10.5.6 處理循環(huán) 401 10.5.7 集合的表示 402 10.5.8 局部到達(dá)定義 403 10.5.9 引用-定義鏈 404 10.5.10 計(jì)算順序 404 10.5.11 一般控制流 404 10.6 數(shù)據(jù)流方程的迭代解 405 10.6.1 到達(dá)定義的迭代算法 406 10.6.2 可用表達(dá)式 408 10.6.3 活躍變量分析 410 10.6.4 定義-引用鏈 411 10.7 代碼改進(jìn)變換 412 10.7.1 全局公共子表達(dá)式刪除 412 10.7.2 復(fù)制傳播 413 10.7.3 循環(huán)不變計(jì)算的檢測(cè) 415 10.7.4 代碼外提 415 10.7.5 可選的代碼外提方案 417 10.7.6 代碼外提后對(duì)數(shù)據(jù)流信息的 維護(hù) 418 10.7.7 歸納變量刪除 418 10.7.8 帶有循環(huán)不變表達(dá)式的歸納 變量 421 10.8 處理別名 422 10.8.1 一種簡(jiǎn)單的指針語(yǔ)言 422 10.8.2 指針賦值的作用 422 10.8.3 利用指針信息 424 10.8.4 過(guò)程間的數(shù)據(jù)流分析 425 10.8.5 帶有過(guò)程調(diào)用的代碼模型 425 10.8.6 別名的計(jì)算 426 10.8.7 存在過(guò)程調(diào)用時(shí)的數(shù)據(jù)流分析 427 10.8.8 change信息的用途 428 10.9 結(jié)構(gòu)化流圖的數(shù)據(jù)流分析 429 10.9.1 深度優(yōu)先搜索 429 10.9.2 流圖的深度優(yōu)先表示中的邊 431 10.9.3 流圖的深度 431 10.9.4 區(qū)間 432 10.9.5 區(qū)間劃分 432 10.9.6 區(qū)間圖 433 10.9.7 節(jié)點(diǎn)分裂 433 10.9.8 T1-T2 分析 434 10.9.9 區(qū)域 434 10.9.10 尋找支配節(jié)點(diǎn) 435 10.10 高效數(shù)據(jù)流算法 436 10.10.1 迭代算法中的深度優(yōu)先順序 436 10.10.2 基于結(jié)構(gòu)的數(shù)據(jù)流分析 437 10.10.3 對(duì)基于結(jié)構(gòu)的算法的一些速度上 的改進(jìn) 440 10.10.4 處理不可約流圖 441 10.11 一個(gè)數(shù)據(jù)流分析工具 441 10.11.1 數(shù)據(jù)流分析框架 442 10.11.2 數(shù)據(jù)流分析框架的公理 443 10.11.3 單調(diào)性和分配性 444 10.11.4 數(shù)據(jù)流問(wèn)題的聚合路徑解 447 10.11.5 流問(wèn)題的保守解 447 10.11.6 通用框架的迭代算法 448 10.11.7 一個(gè)數(shù)據(jù)流分析工具 448 10.11.8 算法10.18的性質(zhì) 449 10.11.9 算法10.18的收斂性 449 10.11.10 初始化的修正 450 10.12 類型估計(jì) 450 10.12.1 處理無(wú)窮類型集 451 10.12.2 一個(gè)簡(jiǎn)單的類型系統(tǒng) 452 10.12.3 前向方案 452 10.12.4 后向方案 453 10.13 優(yōu)化代碼的符號(hào)調(diào)試 455 10.13.1 基本塊中變量值的推斷 456 10.13.2 全局優(yōu)化的影響 459 10.13.3 歸納變量刪除 459 10.13.4 全局公共子表達(dá)式刪除 459 10.13.5 代碼外提 459 練習(xí) 460 參考文獻(xiàn)注釋 465 第11章編寫一個(gè)編譯器 469 11.1 編譯器設(shè)計(jì) 469 11.1.1 源語(yǔ)言問(wèn)題 469 11.1.2 目標(biāo)語(yǔ)言問(wèn)題 469 11.1.3 性能標(biāo)準(zhǔn) 469 11.2 編譯器開發(fā)方法 470 11.3 編譯器開發(fā)環(huán)境 472 11.4 測(cè)試與維護(hù) 474 第12章編譯器實(shí)例 475 12.1 數(shù)學(xué)排版預(yù)處理器EQN 475 12.2 Pascal編譯器 475 12.3 C編譯器 476 12.4 Fortran H編譯器 477 12.4.1 Fortran H中的代碼優(yōu)化 478 12.4.2 代數(shù)優(yōu)化 478 12.4.3 寄存器優(yōu)化 478 12.5 BLISS/11編譯器 479 12.6 Modula-2優(yōu)化編譯器 480 附錄一個(gè)程序設(shè)計(jì)項(xiàng)目 483 參考文獻(xiàn) 489 索引 511