編譯器工程

第1章　編譯總覽        1
1.1  概述        1
1.2  為什么研究編譯器構造法        2
1.3  編譯的基本原則        2
1.4  編譯器的結構        3
1.5  翻譯綜述        5
1.5.1  理解輸入        5
1.5.2  創(chuàng)建和維護運行時環(huán)境        7
1.5.3  改進代碼        8
1.5.4  生成輸出程序        9
1.6  編譯器應有的性質        13
1.7  概括和展望        14
本章注釋        15
第2章　掃描        16
2.1  概述        16
2.2  識別字        17
2.2.1  識別器的形式        18
2.2.2  識別更復雜的字        19
2.2.3  掃描器的自動構建        20
2.3  正則表達式        21
2.3.1  正則表達式的定義        22
2.3.2  例子        23
2.3.3  RE的性質        25
2.4  從正則表達式到掃描器以及從掃描器到正則表達式        26
2.4.1  非確定性有窮自動機         26
2.4.2  正則表達式到NFA：Thompson構造法        28
2.4.3  NFA到DFA：子集構造法        29
2.4.4  DFA到最小DFA：Hopcroft算法        32
2.4.5  DFA到正則表達式        34
2.4.6  將DFA作為識別器        35
2.5  實現(xiàn)掃描器        35
2.5.1  表驅動掃描器        35
2.5.2  直接編碼掃描器        37
2.5.3  處理關鍵字        37
2.5.4  描述動作        38
2.6  高級話題        38
2.7  概括和展望        41
本章注釋        41
第3章  語法分析        42
3.1  概述        42
3.2  表示語法        42
3.2.1  上下文無關文法        43
3.2.2  構造句子        45
3.2.3  使用結構描述優(yōu)先權        48
3.2.4  發(fā)現(xiàn)特定派生        49
3.2.5  上下文無關文法與正則表達式的對比        50
3.3  自頂向下分析        51
3.3.1  例子        52
3.3.2  自頂向下分析的復雜因素        54
3.3.3  消除左遞歸        54
3.3.4  消除回溯        55
3.3.5  自頂向下遞歸下降分析器        59
3.4  自底向上分析        62
3.4.1  移入歸約分析        63
3.4.2  發(fā)現(xiàn)句柄        65
3.4.3  LR(1)分析器        67
3.5  構建LR(1)表格        70
3.5.1  LR(1)項目        71
3.5.2  構造規(guī)范集合        72
3.5.3  填充表格        74
3.5.4  表構造法的出錯        76
3.6  實踐中的問題        78
3.6.1  錯誤恢復        79
3.6.2  一元操作符        79
3.6.3  處理上下文相關歧義性        80
3.6.4  左遞歸與右遞歸        81
3.7  高級話題        82
3.7.1  優(yōu)化文法        83
3.7.2  減小LR(1)表格的大小        84
3.8  概括和展望        86
本章注釋        87
第4章  上下文相關分析        88
4.1  概述        88
4.2  類型系統(tǒng)概述        89
4.2.1  類型系統(tǒng)的目的        89
4.2.2  類型系統(tǒng)的組成部分        93
4.3  屬性文法框架        99
4.3.1  評估方法        101
4.3.2  循環(huán)性        102
4.3.3  擴展例子        102
4.3.4  屬性文法方法的問題        107
4.4  特定語法制導翻譯        109
4.4.1  實現(xiàn)特定語法制導翻譯        110
4.4.2  例子        111
4.5  高級話題        117
4.5.1  類型推斷中的較難問題        117
4.5.2  更改結合性        118
4.6  概括和展望        119
本章注釋        120
第5章  中間表示        121
5.1  概述        121
5.2  分類法        121
5.3  圖示IR        123
5.3.1  與語法相關的樹        123
5.3.2  圖        126
5.4  線性IR        128
5.4.1  棧機器代碼        129
5.4.2  三地址代碼        129
5.4.3  表示線性代碼        130
5.5  靜態(tài)單賦值形式        131
5.6  把值映射到名字        133
5.6.1  命名臨時值        134
5.6.2  內存模型        135
5.7  符號表        137
5.7.1  散列表        138
5.7.2  構建符號表        139
5.7.3  處理嵌套作用域        139
5.7.4  符號表的多種運用        142
5.8  概括和展望        143
本章注釋        143
第6章  過程抽象        144
6.1  概述        144
6.2  控制抽象        145
6.3  名字空間        147
6.3.1  類Algol語言的名字空間        147
6.3.2  活動記錄        150
6.3.3  面向對象語言的名字空間        153
6.4  過程間的值傳遞        158
6.4.1  參數(shù)傳遞        158
6.4.2  返回值        160
6.5  建立可尋址性        161
6.5.1  平凡基地址        161
6.5.2  其他過程的局部變量        162
6.6  標準鏈接        164
6.7  管理內存        167
6.7.1  內存布局        167
6.7.2  堆管理算法        170
6.7.3  隱式釋放        172
6.8  概括和展望        175
本章注釋        176
第7章  代碼形態(tài)        177
7.1  概述        177
7.2  指定存儲位置        178
7.2.1  布局數(shù)據(jù)區(qū)         178
7.2.2  把值保存在寄存器中        179
7.2.3  機器特性        180
7.3  算術操作符        180
7.3.1  降低對寄存器的要求        181
7.3.2  存取參數(shù)值        183
7.3.3  表達式中的函數(shù)調用        184
7.3.4  其他算術操作符        184
7.3.5  混合型表達式        184
7.3.6  作為操作符的賦值        184
7.3.7  交換性、結合性以及數(shù)系        185
7.4  布爾操作符和關系操作符        185
7.4.1  表示        186
7.4.2  關系操作的硬件支持        189
7.4.3  選擇表示        191
7.5  存儲和存取數(shù)組        191
7.5.1  引用向量元素        191
7.5.2  數(shù)組存儲布局        193
7.5.3  引用數(shù)組元素        194
7.5.4  范圍檢測        197
7.6  字符串        197
7.6.1  串的表示        198
7.6.2  串賦值        198
7.6.3  串連接        200
7.6.4  串長        201
7.7  結構引用        201
7.7.1  裝入和存儲匿名值        201
7.7.2  理解結構布局        202
7.7.3  結構數(shù)組        203
7.7.4  聯(lián)合和運行時標簽        204
7.8  控制流結構        204
7.8.1  條件執(zhí)行        205
7.8.2  循環(huán)和迭代        207
7.8.3  選擇語句        210
7.8.4  中斷語句        211
7.9  過程調用        212
7.9.1  評估實參        212
7.9.2  過程值參數(shù)        213
7.9.3  保存和恢復寄存器        213
7.9.4  葉過程的優(yōu)化        214
7.10  實現(xiàn)面向對象語言        214
7.10.1  單一類，無繼承        214
7.10.2  單一繼承        216
7.11  概括和展望        219
本章注釋        219
第8章  代碼優(yōu)化概述        221
8.1  概述        221
8.2  背景知識        222
8.2.1  LINPACK的一個例子        223
8.2.2  優(yōu)化的各種考慮        224
8.2.3  優(yōu)化的機會        226
8.3  冗余表達式        226
8.3.1  構建有向無環(huán)圖        227
8.3.2  值編號        229
8.3.3  冗余消除的經(jīng)驗        232
8.4  優(yōu)化作用域        233
8.4.1  局部方法        233
8.4.2  超局部方法        233
8.4.3  區(qū)域方法        234
8.4.4  全局方法        235
8.4.5  完整程序方法        235
8.5  比基本塊大的區(qū)域上的值編號        235
8.5.1  超局部值編號        235
8.5.2  基于支配者的值編號        238
8.6  全局冗余消除        241
8.6.1  計算可用表達式        242
8.6.2  取代冗余計算        243
8.6.3  結合上述兩個階段        244
8.7  高級話題        245
8.7.1  通過復制增加上下文        246
8.7.2  內聯(lián)替換        247
8.8  概括和展望        248
本章注釋        249
第9章  數(shù)據(jù)流分析        250
9.1  概述        250
9.2  迭代數(shù)據(jù)流分析        251
9.2.1  活變量        251
9.2.2  迭代LIVEOUT解算器的性質        256
9.2.3  數(shù)據(jù)流分析的局限性        258
9.2.4  數(shù)據(jù)流分析的其他問題        260
9.3  靜態(tài)單一賦值形式        262
9.3.1  構建SSA形式的簡單方法        263
9.3.2  支配        263
9.3.3  放置f函數(shù)        267
9.3.4  重命名        269
9.3.5  從SSA形式重新構造可執(zhí)行代碼        273
9.4  高級話題        277
9.4.1  結構數(shù)據(jù)流算法和可約性        277
9.4.2  過程間分析        279
9.5  概括和展望        281
本章注釋        282
第10章  標量優(yōu)化        283
10.1  概述        283
10.2  轉換分類        284
10.2.1  機器無關轉換        284
10.2.2  機器相關轉換        286
10.3  優(yōu)化示例        286
10.3.1  消除無用和不可達代碼        286
10.3.2  代碼移動        291
10.3.3  特化        297
10.3.4  激活其他轉換        299
10.3.5  冗余消除        301
10.4  高級話題        302
10.4.1  優(yōu)化組合        302
10.4.2  強度減弱        304
10.4.3  優(yōu)化的其他目標        311
10.4.4  優(yōu)化序列的選擇        312
10.5  概括和展望        312
本章注釋        313
第11章  指令篩選        315
11.1  概述        315
11.2  簡單的樹遍歷方案         318
11.3  通過樹模式匹配實現(xiàn)指令篩選        322
11.3.1  重寫規(guī)則        323
11.3.2  尋找鋪蓋        326
11.3.3  工具        328
11.4  指令篩選與窺孔優(yōu)化        329
11.4.1  窺孔優(yōu)化        329
11.4.2  窺孔轉換器        333
11.5  高級話題        334
11.5.1  學習窺孔模式        334
11.5.2  生成指令序列        335
11.6  概括和展望        336
本章注釋        336
第12章  指令調度        338
12.1  概述        338
12.2  指令調度問題        339
12.2.1  調度質量的其他度量        342
12.2.2  使調度困難的因素        342
12.3  列表調度        343
12.3.1  效率        345
12.3.2  其他的優(yōu)先度方案        346
12.3.3  前向與向后列表調度        346
12.3.4  使用列表調度的原因        348
12.4  高級話題        349
12.4.1  區(qū)域調度        349
12.4.2  上下文的復制        354
12.5  概括和展望        356
本章注釋        356
第13章  寄存器分配        357
13.1  概述        357
13.2  背景問題        357
13.2.1  內存與寄存器        358
13.2.2  分配與賦值        358
13.2.3  寄存器分類        359
13.3  局部寄存器分配和賦值        359
13.3.1  自頂向下的局部寄存器分配        360
13.3.2  自底向上的局部寄存器分配        360
13.4  移到超出單一塊的范圍        363
13.4.1  活性和存活范圍        363
13.4.2  塊邊界處的復雜性        364
13.5  全局寄存器分配和賦值        365
13.5.1  發(fā)現(xiàn)全局存活范圍        366
13.5.2  評估全局溢出代價        367
13.5.3  沖突和沖突圖        368
13.5.4  自頂向下著色        370
13.5.5  自底向上著色        371
13.5.6  接合存活范圍以降低度        372
13.5.7  回顧與比較        373
13.5.8  在沖突圖中編碼機器限制        374
13.6  高級話題        375
13.6.1  圖著色分配的若干變形        375
13.6.2  寄存器分配中較困難的問題        377
13.7  概括和展望        379
本章注釋        379
附錄A  ILOC        380
A.1  概述        380
A.2  命名約定        381
A.3  各種操作        382
A.3.1  算術        382
A.3.2  移位        382
A.3.3  內存操作        383
A.3.4  寄存器到寄存器的拷貝操作        383
A.4  例子        384
A.5  控制流操作        384
A.5.1  其他比較和分支語法        385
A.5.2  跳轉        386
A.6  SSA形式的表示        386
附錄B  數(shù)據(jù)結構        389
B.1  概述        389
B.2  表示集合        389
B.2.1  把集合表示成有序表        390
B.2.2  把集合表示成位向量        391
B.2.3  表示稀疏集合        391
B.3  實現(xiàn)中間表示        392
B.3.1  圖式中間表示        392
B.3.2  線性中間形式        395
B.4  實現(xiàn)散列表        396
B.4.1  選擇散列函數(shù)        397
B.4.2  開放散列        398
B.4.3  開放尋址        399
B.4.4  存儲符號記錄        400
B.4.5  增加嵌套詞法作用域        401
B.5  一個靈活的符號表設計        403
附錄注釋        404
參考文獻        405
練習        424
索引        452