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