深入剖析現代編譯器運用的算法和技術。強調代碼優化和代碼生成。體現編譯原理教學的**新理念

●第1章編譯概觀1
1．1簡介1
1．2編譯器結構4
1．3轉換概述7
1．3．1前端8
1．3．2優化器10
1．3．3後端11
1．4小結和展望15
第2章詞法分析器17
2．1簡介17
2．2識別單詞18
2．2．1識別器的形式化20
2．2．2識別更復雜的單詞21
2．3正則表達式24
2．3．1符號表示法的形式化25
2．3．2示例26
2．3．3RE的閉包性質28
2．4從正則表達式到詞法分析器30
2．4．1非確定性有限自動機30
2．4．2從正則表達式到NFA：Thompson構造法33
2．4．3從NFA到DFA：子集構造法34
2．4．4從DFA到**小DFA：Hopcroft算法39
2．4．5將DFA用做識別器42
2．5實現詞法分析器43
2．5．1表驅動詞法分析器44
2．5．2直接編碼的詞法分析器48
2．5．3手工編碼的詞法分析器50
2．5．4處理關鍵字53
2．6高級主題54
2．6．1從DFA到正則表達式54
2．6．2DFA**小化的另一種方法：Brzozowski算法55
2．6．3無閉包的正則表達式56
2．7小結和展望57
第3章語法分析器61
3．1簡介61
3．2語法的表示62
3．2．1為什麼不使用正則表達式62
3．2．2上下文無關語法63
3．2．3更復雜的例子66
3．2．4將語義編碼到結構中69
3．2．5為輸入符號串找到推導71
3．3自頂向下語法分析71
3．3．1為進行自頂向下語法分析而轉換語法73
3．3．2自頂向下的遞歸下降語法分析器81
3．3．3表驅動的LL(1)語法分析器83
3．4自底向上語法分析87
3．4．1LR(1)語法分析算法89
3．4．2構建LR(1)表94
3．4．3表構造過程中的錯誤103
3．5實際問題106
3．5．1出錯恢復106
3．5運算符107
3．5．3處理上下文相關的二義性108
3．5．4左遞歸與右遞歸109
3．6高級主題111
3．6．1優化語法111
3．6．2減小LR(1)表的規模113
3．7小結和展望116
第4章上下文相關分析120
4．1簡介120
4．2類型繫統簡介122
4．2．1類型繫統的目標123
4．2．2類型繫統的組件126
4．3屬性語法框架134
4．3．1求值的方法137
4．3．2環138
4．3．3擴展實例138
4．3．4屬性語法方法的問題143
4．4特設語法制導轉換146
4．4．1特設語法制導轉換的實現147
4．4．2例子148
4．5高級主題155
4．5．1類型推斷中更困難的問題155
4．5．2改變結合性157
4．6小結和展望158
第5章中間表示162
5．1簡介162
5．2圖IR165
5．2．1與語法相關的樹165
5．2．2圖168
5．3線性IR173
5．3．1堆棧機代碼173
5．3．2三地址代碼174
5．3．3線性代碼的表示175
5．3．4根據線性代碼建立控制流圖176
5．4將值映射到名字179
5．4．1臨時值的命名179
5．4．2靜態單賦值形式180
5．4．3內存模型183
5．5符號表186
5．5．1散列表187
5．5．2建立符號表187
5．5．3處理嵌套的作用域188
5．5．4符號表的許多用途191
5．5．5符號表技術的其他用途193
5．6小結和展望193
第6章過程抽像198
6．1簡介198
6．2過程調用200
6．3命名空間203
6．3．1類Algol語言的命名空間203
6．3．2用於支持類Algol語言的運行時結構206
6．3．3面向對像語言的命名空間210
6．3．4支持面向對像語言的運行時結構214
6．4過程之間值的傳遞219
6．4．1傳遞參數219
6．4．2返回值222
6．4．3確定可尋址性223
6．5標準化鏈接227
6．6高級主題231
6．6．1堆的顯式管理231
6．6．2隱式釋放234
6．7小結和展望237
第7章代碼形式245
7．1簡介245
7．2分配存儲位置247
7．2．1設定運行時數據結構的位置248
7．2．2數據區的布局249
7．2．3將值保持在寄存器中252
7．3算術運算符253
7．3．1減少對寄存器的需求254
7．3．2訪問參數值255
7．3．3表達式中的函數調用257
7．3．4其他算術運算符257
7．3．5混合類型表達式258
7．3．6作為運算符的賦值操作258
7．4布爾運算符和關繫運算符259
7．4．1表示260
7．4．2對關繫操作的硬件支持262
7．5數組的存儲和訪問265
7．5．1引素266
7．5．2數組存儲布局267
7．5．3引素268
7．5．4範圍檢查272
7．6字符串273
7．6．1字符串表示273
7．6．2字符串賦值274
7．6．3字符串連接275
7．6．4字符串長度276
7．7結構引用277
7．7．1理解結構布局277
7．7．2結構數組278
7．7．3聯合和運行時標記278
7．7．4指針和匿名值279
7．8控制流結構281
7．8．1條件執行281
7．8．2循環和迭代283
7．8．3case語句286
7．9過程調用289
7．9．1實參求值290
7．9．2保存和恢復寄存器291
7．10小結和展望292
第8章優化簡介298
8．1簡介298
8．2背景299
8．2．1例子300
8．2．2對優化的考慮303
8．2．3優化的時機305
8．3優化的範圍306
8．4局部優化308
8．4．1局部值編號309
8．4．2樹高平衡314
8．5區域優化321
8．5．1超局部值編號321
8．5．2循環展開324
8．6全局優化327
8．6．1利用活動信息查找未初始化變量328
8．6．2全局代碼置放331
8．7過程間優化336
8．7．1內聯替換337
8．7．2過程置放340
8．7．3針對過程間優化的編譯器組織結構344
8．8小結和展望345
第9章數據流分析350
9．1簡介350
9．2迭代數據流分析351
9．2．1支配性352
9．2．2活動變量分析355
9．2．3數據流分析的局限性359
9．2．4其他數據流問題361
9．3靜態單賦值形式365
9．3．1構造靜態單賦值形式的簡單方法366
9．3．2支配邊界366
9．3．3放置函數369
9．3．4重命名372
9．3．5從靜態單賦值形式到其他形式的轉換376
9．3．6使用靜態單賦值形式379
9．4過程間分析383
9．4．1構建調用圖383
9．4．2過程間常量傳播385
9．5高級主題388
9．5．1結構性數據流算法和可歸約性388
9．5．2加速計算支配性的迭代框架算法的執行391
9．6小結和展望393
第10章標量優化398
10．1簡介398
10．2消除無用和不可達代碼401
10．2．1消除無用代碼402
10．2．2消除無用控制流404
10．2．3消除不可達代碼406
10．3代碼移動407
10．3．1緩式代碼移動407
10．3．2代碼提升413
10．4特化414
10．4．1尾調用優化415
10．4．2葉調用優化416
10．4．3參數提升416
10．5冗餘消除417
10．5．1值相同與名字相同417
10．5．2基於支配者的值編號算法418
10．6為其他變換制造時機421
10．6．1超級塊復制421
10．6．2過程復制422
10．6．3循環外提423
10．6．4重命名423
10．7高級主題425
10．7．1合並優化425
10．7．2強度削減429
10．7．3選擇一種優化序列437
10．8小結和展望438
第11章指令選擇441
11．1簡介441
11．2代碼生成443
11．3擴展簡單的樹遍歷方案445
11．4通過樹模式匹配進行指令選擇450
11．4．1重寫規則451
11．4．2找到平鋪方案454
11．4．3工具457
11．5通過窺孔優化進行指令選擇458
11．5．1窺孔優化458
11．5．2窺孔變換程序463
11．6高級主題465
11．6．1學習窺孔模式465
11．6．2生成指令序列466
11．7小結和展望467
第12章指令調度470
12．1簡介470
12．2指令調度問題473
12．2．1度量調度質量的其他方式477
12．2．2是什麼使調度這樣難478
12．3局部表調度478
12．3．1算法478
12．3．2調度具有可變延遲的操作481
12．3．3擴展算法481
12．3．4在表調度算法中打破平局481
12．3．5前向表調度與後向表調度482
12．3．6提高表調度的效率484
12．4區域性調度485
12．4．1調度擴展基本程序塊486
12．4．2跟蹤調度487
12．4．3通過復制構建適當的上下文環境488
12．5高級主題489
12．5．1軟件流水線的策略490
12．5．2用於實現軟件流水線的算法492
12．6小結和展望495
第13章寄存器分配499
13．1簡介499
13．2背景問題500
13．2．1內存與寄存器500
13．2．2分配與指派501
13．2．3寄存器類別502
13．3局部寄存器分配和指派502
13．3．1自頂向下的局部寄存器分配503
13．3．2自底向上的局部寄存器分配504
13．3．3超越單個程序塊506
13．4全局寄存器分配和指派509
13．4．1找到全局活動範圍511
13．4．2估算全局逐出代價512
13．4．3衝突和衝突圖513
13．4．4自頂向下著色515
13．4．5自底向上著色517
13．4．6合並副本以減小度數518
13．4．7比較自頂向下和自底向上全局分配器520
13．4．8將機器的約束條件編碼到衝突圖中521
13．5高級主題523
13．5．1圖著色寄存器分配方法的變體523
13．5．2靜態單賦值形式上的全局寄存器分配525
13．6小結和展望526
附錄AILOC531
附錄B數據結構540
參考文獻559
索引574

本書是編譯器設計領域的經典著作，主要從以下四部分詳解了編譯器的設計過程。第一部分涵蓋編譯器前端設計和建立前端所用工具的設計和構建；第二部分探討從源代碼到編譯器中間形式的映射，考察前端為優化器和後端所生成代碼的種類；第三部分介紹代碼優化，同時包含對分析和轉換的進一步處理；第四部分專門講解編譯器後端使用的算法。本書適合作為高等院校計算機專業本科生和研究生編譯課程的教材和參考書，也可供相關技術人員參考。