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

第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  一個(gè)簡(jiǎn)單的傳統(tǒng)的模塊化編譯程序/解釋程序 6                  
 1.2.1  抽象語(yǔ)法樹 7                  
 1.2.2  范例編譯程序的結(jié)構(gòu) 8                  
 1.2.3  范例編譯程序的語(yǔ)言 9                  
 1.2.4  范例編譯程序的詞法分析 10                  
 1.2.5  范例編譯程序的語(yǔ)法分析 11                  
 1.2.6  范例編譯程序的上下文處理 14                  
 1.2.7  范例編譯程序的代碼生成 14                  
 1.2.8  范例編譯程序的解釋程序 15                  
 1.3  一個(gè)更接近于實(shí)際的編譯程序的結(jié)構(gòu) 16                  
 1.3.1  結(jié)構(gòu) 17                  
 1.3.2  運(yùn)行時(shí)系統(tǒng) 18                  
 1.3.3  捷徑 18                  
 1.4  編譯程序體系結(jié)構(gòu) 18                  
 1.4.1  編譯程序的寬度 19                  
 1.4.2  誰(shuí)主控 20                  
 1.5  一個(gè)優(yōu)秀編譯程序的特性 22                  
 1.6  可移植性和可重定目標(biāo)性 23                  
 1.7  優(yōu)化的位置和效用 23                  
 1.8  編譯程序構(gòu)造簡(jiǎn)史 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  文法的擴(kuò)展形式 27                  
 1.9.4  文法特性 27                  
 1.9.5  文法形式化方法 28                  
 1.10  閉包算法 29                  
 1.10.1  閉包算法的迭代實(shí)現(xiàn) 31                  
 1.11  本書使用的概要代碼 33                  
 1.12  小結(jié) 33                  
 第2章  從程序文本到抽象語(yǔ)法樹 38                  
 2.1  從程序文本到記號(hào)——詞法結(jié)構(gòu) 41                  
 2.1.1  讀程序文本 41                  
 2.1.2  詞法分析與語(yǔ)法分析 42                  
 2.1.3  正則表達(dá)式和正則描述 43                  
 2.1.4  詞法分析 44                  
 2.1.5  手動(dòng)產(chǎn)生詞法分析程序 45                  
 2.1.6  自動(dòng)產(chǎn)生詞法分析程序 50                  
 2.1.7  轉(zhuǎn)換表壓縮 63                  
 2.1.8  詞法分析程序的錯(cuò)誤處理 68                  
 2.1.9  一個(gè)傳統(tǒng)的詞法分析程序產(chǎn)生器——lex 69                  
 2.1.10  記號(hào)的詞法識(shí)別 70                  
 2.1.11  符號(hào)表 72                  
 2.1.12  宏處理和文件包含 76                  
 2.1.13  小結(jié) 80                  
 2.2  從記號(hào)到語(yǔ)法樹——語(yǔ)法分析 81                  
 2.2.1  語(yǔ)法分析的兩種方法 82                  
 2.2.2  錯(cuò)誤檢測(cè)和錯(cuò)誤恢復(fù) 84                  
 2.2.3  手工生成一個(gè)自頂向下的語(yǔ)法分析程序 86                  
 2.2.4  自動(dòng)生成一個(gè)自頂向下的語(yǔ)法分析程序 88                  
 2.2.5  自動(dòng)創(chuàng)建一個(gè)自底向上的語(yǔ)法分析程序 111                  
 2.3  小結(jié) 132                  
 第3章  注釋抽象語(yǔ)法樹--上下文 142                  
 3.1  屬性文法 143                  
 3.1.1  依賴圖 146                  
 3.1.2  屬性計(jì)算 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-屬性文法的等價(jià)性 171                  
 3.1.10  擴(kuò)展的文法符號(hào)和屬性文法 172                  
 3.1.11  小結(jié) 173                  
 3.2  手工方法 173                  
 3.2.1  線性化AST 174                  
 3.2.2  符號(hào)解釋 178                  
 3.2.3  數(shù)據(jù)流方程 184                  
 3.2.4  過程間的數(shù)據(jù)流分析 188                  
 3.2.5  上傳信息流——活躍分析 189                  
 3.2.6  符號(hào)解釋和數(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  開始點(diǎn) 214                  
 4.2.3  直接代碼生成 214                  
 4.2.4  簡(jiǎn)單代碼生成 218                  
 4.2.5  基本塊的代碼生成 230                  
 4.2.6  BURS代碼生成和動(dòng)態(tài)程序設(shè)計(jì) 241                  
 4.2.7  通過圖著色的寄存器分配 255                  
 4.2.8  超級(jí)編譯 259                  
 4.2.9  代碼生成技術(shù)的評(píng)價(jià) 261                  
 4.2.10  代碼優(yōu)化器的調(diào)試 261                  
 4.2.11  預(yù)處理中間代碼 262                  
 4.2.12  后處理目標(biāo)代碼 265                  
 4.2.13  機(jī)器代碼生成 267                  
 4.3  匯編程序. 連接程序和裝入程序 268                  
 4.3.1  匯編程序設(shè)計(jì)問題 270                  
 4.3.2  連接程序設(shè)計(jì)問題 272                  
 4.4  小結(jié) 273                  
 第5章  存儲(chǔ)管理 283                  
 5.1  顯式回收的數(shù)據(jù)空間分配 284                  
 5.1.1  基本存儲(chǔ)空間分配 285                  
 5.1.2  鏈表 288                  
 5.1.3  可擴(kuò)展數(shù)組 290                  
 5.2  隱式回收的數(shù)據(jù)空間分配 291                  
 5.2.1  基本垃圾收集算法 291                  
 5.2.2  背景預(yù)備 292                  
 5.2.3  引用計(jì)數(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  識(shí)別 315                  
 6.1.2  類型檢查 321                  
 6.1.3  小結(jié) 328                  
 6.2  源語(yǔ)言數(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  對(duì)象類型 337                  
 6.2.10  接口類型 344                  
 6.3  例程及其活動(dòng) 345                  
 6.3.1  活動(dòng)記錄 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  控制流語(yǔ)句的代碼生成 359                  
 6.4.1  局部控制流 359                  
 6.4.2  例程調(diào)用 366                  
 6.4.3  運(yùn)行時(shí)錯(cuò)誤處理 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簡(jiǎn)介 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  惰性計(jì)算 392                  
 7.2  編譯函數(shù)式語(yǔ)言 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  高級(jí)圖處理 421                  
 7.8.1  可變長(zhǎng)度結(jié)點(diǎn) 421                  
 7.8.2  指針標(biāo)記 421                  
 7.8.3  聚集結(jié)點(diǎn)分配 421                  
 7.8.4  向量應(yīng)用結(jié)點(diǎn) 422                  
 7.9  小結(jié) 422                  
 第8章  邏輯式程序 427                  
 8.1  邏輯式程序設(shè)計(jì)模型 428                  
 8.1.1  構(gòu)建模塊 428                  
 8.1.2  推理機(jī)制 430                  
 8.2  解釋的通用實(shí)現(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  合一的實(shí)現(xiàn) 437                  
 8.3.3  兩個(gè)自由變量的合一 440                  
 8.3.4  小結(jié) 441                  
 8.4  編譯的通用實(shí)現(xiàn)模型 441                  
 8.4.1  列表程序 442                  
 8.4.2  編譯子句的搜索和合一 444                  
 8.4.3  WAM中的優(yōu)化子句選擇 448                  
 8.4.4  應(yīng)用“cut”機(jī)制 450                  
 8.4.5  謂詞assert和retract的實(shí)現(xiàn) 452                  
 8.5  合一的編譯代碼 455                  
 8.5.1  WAM中的合一指令 456                  
 8.5.2  通過手工局部計(jì)算得到合一指令 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è)計(jì)模型 474                  
 9.1.1  共享變量和管程 474                  
 9.1.2  消息傳遞模型 476                  
 9.1.3  面向?qū)ο笳Z(yǔ)言 477                  
 9.1.4  Linda元組空間 477                  
 9.1.5  數(shù)據(jù)并行語(yǔ)言 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(yǔ)言 485                  
 9.5.1  對(duì)象定位 485                  
 9.5.2  對(duì)象遷移 486                  
 9.5.3  對(duì)象復(fù)制 487                  
 9.6  元組空間 488                  
 9.6.1  避免關(guān)聯(lián)尋址的開銷 488                  
 9.6.2  元組空間的分布實(shí)現(xiàn) 490                  
 9.7  自動(dòng)并行 492                  
 9.7.1  自動(dòng)地使用并行性 492                  
 9.7.2  數(shù)據(jù)依賴 494                  
 9.7.3  循環(huán)轉(zhuǎn)換 495                  
 9.7.4  分布式存儲(chǔ)器的自動(dòng)并行 496                  
 9.8  小結(jié) 498                  
 附錄A  一個(gè)簡(jiǎn)單的面向?qū)ο缶幾g程序/解釋程序 502                  
 附錄B  練習(xí)答案  509                  
 附錄C  參考文獻(xiàn) 519                  
 附錄D  術(shù)語(yǔ)表 527