現(xiàn)代編譯程序設(shè)計：中文版

第1章  導(dǎo)論 1                  
 1.1  為什么學(xué)習(xí)編譯程序構(gòu)造 4                  
 1.1.1  編譯程序構(gòu)造是非常成功的 4                  
 1.1.2  編譯程序構(gòu)造的廣泛應(yīng)用 6                  
 1.1.3  編譯程序包含普遍適用的算法 6                  
 1.2  一個簡單的傳統(tǒng)的模塊化編譯程序/解釋程序 6                  
 1.2.1  抽象語法樹 7                  
 1.2.2  范例編譯程序的結(jié)構(gòu) 8                  
 1.2.3  范例編譯程序的語言 9                  
 1.2.4  范例編譯程序的詞法分析 10                  
 1.2.5  范例編譯程序的語法分析 11                  
 1.2.6  范例編譯程序的上下文處理 14                  
 1.2.7  范例編譯程序的代碼生成 14                  
 1.2.8  范例編譯程序的解釋程序 15                  
 1.3  一個更接近于實際的編譯程序的結(jié)構(gòu) 16                  
 1.3.1  結(jié)構(gòu) 17                  
 1.3.2  運行時系統(tǒng) 18                  
 1.3.3  捷徑 18                  
 1.4  編譯程序體系結(jié)構(gòu) 18                  
 1.4.1  編譯程序的寬度 19                  
 1.4.2  誰主控 20                  
 1.5  一個優(yōu)秀編譯程序的特性 22                  
 1.6  可移植性和可重定目標(biāo)性 23                  
 1.7  優(yōu)化的位置和效用 23                  
 1.8  編譯程序構(gòu)造簡史 24                  
 1.8.1  1945~1960年：代碼生成 24                  
 1.8.2  1960~1975年：分析 24                  
 1.8.3  1975年至今：代碼生成和代碼優(yōu)化, 范型 24                  
 1.9  文法 25                  
 1.9.1  文法形式 25                  
 1.9.2  產(chǎn)生式過程 25                  
 1.9.3  文法的擴展形式 27                  
 1.9.4  文法特性 27                  
 1.9.5  文法形式化方法 28                  
 1.10  閉包算法 29                  
 1.10.1  閉包算法的迭代實現(xiàn) 31                  
 1.11  本書使用的概要代碼 33                  
 1.12  小結(jié) 33                  
 第2章  從程序文本到抽象語法樹 38                  
 2.1  從程序文本到記號——詞法結(jié)構(gòu) 41                  
 2.1.1  讀程序文本 41                  
 2.1.2  詞法分析與語法分析 42                  
 2.1.3  正則表達(dá)式和正則描述 43                  
 2.1.4  詞法分析 44                  
 2.1.5  手動產(chǎn)生詞法分析程序 45                  
 2.1.6  自動產(chǎn)生詞法分析程序 50                  
 2.1.7  轉(zhuǎn)換表壓縮 63                  
 2.1.8  詞法分析程序的錯誤處理 68                  
 2.1.9  一個傳統(tǒng)的詞法分析程序產(chǎn)生器——lex 69                  
 2.1.10  記號的詞法識別 70                  
 2.1.11  符號表 72                  
 2.1.12  宏處理和文件包含 76                  
 2.1.13  小結(jié) 80                  
 2.2  從記號到語法樹——語法分析 81                  
 2.2.1  語法分析的兩種方法 82                  
 2.2.2  錯誤檢測和錯誤恢復(fù) 84                  
 2.2.3  手工生成一個自頂向下的語法分析程序 86                  
 2.2.4  自動生成一個自頂向下的語法分析程序 88                  
 2.2.5  自動創(chuàng)建一個自底向上的語法分析程序 111                  
 2.3  小結(jié) 132                  
 第3章  注釋抽象語法樹--上下文 142                  
 3.1  屬性文法 143                  
 3.1.1  依賴圖 146                  
 3.1.2  屬性計算 147                  
 3.1.3  循環(huán)處理 153                  
 3.1.4  屬性分配 158                  
 3.1.5  多次訪問屬性文法 158                  
 3.1.6  屬性文法類型的總結(jié) 167                  
 3.1.7  L-屬性文法 167                  
 3.1.8  S-屬性文法 170                  
 3.1.9  L-屬性文法與S-屬性文法的等價性 171                  
 3.1.10  擴展的文法符號和屬性文法 172                  
 3.1.11  小結(jié) 173                  
 3.2  手工方法 173                  
 3.2.1  線性化AST 174                  
 3.2.2  符號解釋 178                  
 3.2.3  數(shù)據(jù)流方程 184                  
 3.2.4  過程間的數(shù)據(jù)流分析 188                  
 3.2.5  上傳信息流——活躍分析 189                  
 3.2.6  符號解釋和數(shù)據(jù)流方程的比較 194                  
 3.3  小結(jié) 194                  
 第4章  處理中間代碼 202                  
 4.1  解釋 203                  
 4.1.1  遞歸解釋 203                  
 4.1.2  迭代解釋 207                  
 4.2  代碼生成 210                  
 4.2.1  避免完全的代碼生成 213                  
 4.2.2  開始點 214                  
 4.2.3  直接代碼生成 214                  
 4.2.4  簡單代碼生成 218                  
 4.2.5  基本塊的代碼生成 230                  
 4.2.6  BURS代碼生成和動態(tài)程序設(shè)計 241                  
 4.2.7  通過圖著色的寄存器分配 255                  
 4.2.8  超級編譯 259                  
 4.2.9  代碼生成技術(shù)的評價 261                  
 4.2.10  代碼優(yōu)化器的調(diào)試 261                  
 4.2.11  預(yù)處理中間代碼 262                  
 4.2.12  后處理目標(biāo)代碼 265                  
 4.2.13  機器代碼生成 267                  
 4.3  匯編程序. 連接程序和裝入程序 268                  
 4.3.1  匯編程序設(shè)計問題 270                  
 4.3.2  連接程序設(shè)計問題 272                  
 4.4  小結(jié) 273                  
 第5章  存儲管理 283                  
 5.1  顯式回收的數(shù)據(jù)空間分配 284                  
 5.1.1  基本存儲空間分配 285                  
 5.1.2  鏈表 288                  
 5.1.3  可擴展數(shù)組 290                  
 5.2  隱式回收的數(shù)據(jù)空間分配 291                  
 5.2.1  基本垃圾收集算法 291                  
 5.2.2  背景預(yù)備 292                  
 5.2.3  引用計數(shù) 297                  
 5.2.4  標(biāo)記和掃描 300                  
 5.2.5  兩空間復(fù)制 303                  
 5.2.6  緊縮 306                  
 5.2.7  世代垃圾收集 307                  
 5.3  小結(jié) 307                  
 第6章  命令式和面向?qū)ο蟪绦?313                  
 6.1  上下文處理 314                  
 6.1.1  識別 315                  
 6.1.2  類型檢查 321                  
 6.1.3  小結(jié) 328                  
 6.2  源語言數(shù)據(jù)表示和處理 328                  
 6.2.1  基本類型 329                  
 6.2.2  枚舉類型 329                  
 6.2.3  指針類型 329                  
 6.2.4  記錄類型 332                  
 6.2.5  共用體類型 333                  
 6.2.6  數(shù)組類型 334                  
 6.2.7  集合類型 336                  
 6.2.8  例程類型 336                  
 6.2.9  對象類型 337                  
 6.2.10  接口類型 344                  
 6.3  例程及其活動 345                  
 6.3.1  活動記錄 345                  
 6.3.2  例程 347                  
 6.3.3  例程上的操作 348                  
 6.3.4  非嵌套例程 350                  
 6.3.5  嵌套例程 352                  
 6.3.6  Lambda提升 357                  
 6.3.7  迭代器和協(xié)作例程 358                  
 6.4  控制流語句的代碼生成 359                  
 6.4.1  局部控制流 359                  
 6.4.2  例程調(diào)用 366                  
 6.4.3  運行時錯誤處理 372                  
 6.5  模塊的代碼生成 374                  
 6.5.1  名字生成 375                  
 6.5.2  模塊初始化 375                  
 6.5.3  泛型的代碼生成 376                  
 6.6  小結(jié) 377                  
 第7章  函數(shù)式程序 386                  
 7.1  Haskell簡介 387                  
 7.1.1  越位規(guī)則 387                  
 7.1.2  列表 388                  
 7.1.3  列表內(nèi)涵 388                  
 7.1.4  模式匹配 389                  
 7.1.5  多態(tài)類型 390                  
 7.1.6  引用透明性 391                  
 7.1.7  高階函數(shù) 391                  
 7.1.8  惰性計算 392                  
 7.2  編譯函數(shù)式語言 393                  
 7.2.1  函數(shù)核 394                  
 7.3  多態(tài)類型檢查 395                  
 7.3.1  多態(tài)函數(shù)應(yīng)用 396                  
 7.4  脫糖 397                  
 7.4.1  列表的翻譯 397                  
 7.4.2  模式匹配的翻譯 397                  
 7.4.3  列表內(nèi)涵的翻譯 399                  
 7.4.4  嵌套函數(shù)的翻譯 401                  
 7.5  圖歸約 402                  
 7.5.1  歸約順序 405                  
 7.5.2  歸約引擎 406                  
 7.6  函數(shù)核程序的代碼生成 409                  
 7.6.1  避免一些應(yīng)用框架的構(gòu)造 411                  
 7.7  優(yōu)化函數(shù)核 412                  
 7.7.1  嚴(yán)格性分析 413                  
 7.7.2  裝箱分析 417                  
 7.7.3  尾部調(diào)用 417                  
 7.7.4  累加器轉(zhuǎn)換 419                  
 7.7.5  局限性 420                  
 7.8  高級圖處理 421                  
 7.8.1  可變長度結(jié)點 421                  
 7.8.2  指針標(biāo)記 421                  
 7.8.3  聚集結(jié)點分配 421                  
 7.8.4  向量應(yīng)用結(jié)點 422                  
 7.9  小結(jié) 422                  
 第8章  邏輯式程序 427                  
 8.1  邏輯式程序設(shè)計模型 428                  
 8.1.1  構(gòu)建模塊 428                  
 8.1.2  推理機制 430                  
 8.2  解釋的通用實現(xiàn)模型 431                  
 8.2.1  解釋程序指令 432                  
 8.2.2  避免冗余目標(biāo)列表 434                  
 8.2.3  避免復(fù)制目標(biāo)列表尾部 434                  
 8.3  合一 435                  
 8.3.1  結(jié)構(gòu). 列表和集合的合一 435                  
 8.3.2  合一的實現(xiàn) 437                  
 8.3.3  兩個自由變量的合一 440                  
 8.3.4  小結(jié) 441                  
 8.4  編譯的通用實現(xiàn)模型 441                  
 8.4.1  列表程序 442                  
 8.4.2  編譯子句的搜索和合一 444                  
 8.4.3  WAM中的優(yōu)化子句選擇 448                  
 8.4.4  應(yīng)用“cut”機制 450                  
 8.4.5  謂詞assert和retract的實現(xiàn) 452                  
 8.5  合一的編譯代碼 455                  
 8.5.1  WAM中的合一指令 456                  
 8.5.2  通過手工局部計算得到合一指令 457                  
 8.5.3  WAM中的結(jié)構(gòu)合一 462                  
 8.5.4  一種優(yōu)化：讀/寫模式 464                  
 8.5.5  WAM中合一結(jié)構(gòu)的進(jìn)一步優(yōu)化 466                  
 8.5.6  小結(jié) 467                  
 第9章  并行和分布式程序 472                  
 9.1  并行程序設(shè)計模型 474                  
 9.1.1  共享變量和管程 474                  
 9.1.2  消息傳遞模型 476                  
 9.1.3  面向?qū)ο笳Z言 477                  
 9.1.4  Linda元組空間 477                  
 9.1.5  數(shù)據(jù)并行語言 478                  
 9.2  進(jìn)程和線程 479                  
 9.3  共享變量 481                  
 9.3.1  鎖 481                  
 9.3.2  管程 481                  
 9.4  消息傳遞 482                  
 9.4.1  接收方定位 483                  
 9.4.2  編組 483                  
 9.4.3  消息的類型檢查 484                  
 9.4.4  消息選擇 484                  
 9.5  并行的面向?qū)ο笳Z言 485                  
 9.5.1  對象定位 485                  
 9.5.2  對象遷移 486                  
 9.5.3  對象復(fù)制 487                  
 9.6  元組空間 488                  
 9.6.1  避免關(guān)聯(lián)尋址的開銷 488                  
 9.6.2  元組空間的分布實現(xiàn) 490                  
 9.7  自動并行 492                  
 9.7.1  自動地使用并行性 492                  
 9.7.2  數(shù)據(jù)依賴 494                  
 9.7.3  循環(huán)轉(zhuǎn)換 495                  
 9.7.4  分布式存儲器的自動并行 496                  
 9.8  小結(jié) 498                  
 附錄A  一個簡單的面向?qū)ο缶幾g程序/解釋程序 502                  
 附錄B  練習(xí)答案  509                  
 附錄C  參考文獻(xiàn) 519                  
 附錄D  術(shù)語表 527