編譯器工程

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