現(xiàn)代編譯原理（C語(yǔ)言描述）

第一部分　編譯基本原理
第1章　緒論　1
1.1　模塊與接口　1
1.2　工具和軟件　3
1.3　樹(shù)語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)　3
程序設(shè)計(jì)：直線式程序解釋器　7
推薦閱讀　9
習(xí)題　9
第2章　詞法分析　10
2.1　詞法單詞　10
2.2　正則表達(dá)式　11
2.3　有限自動(dòng)機(jī)　13
2.4　非確定有限自動(dòng)機(jī)　15
2.4.1　將正則表達(dá)式轉(zhuǎn)換為NFA　16
2.4.2　將NFA轉(zhuǎn)換為DFA　18
2.5　Lex：詞法分析器的生成器　20
程序設(shè)計(jì)：詞法分析　22
推薦閱讀　23
習(xí)題　23
第3章　語(yǔ)法分析　27
3.1　上下文無(wú)關(guān)文法　28
3.1.1　推導(dǎo)　29
3.1.2　語(yǔ)法分析樹(shù)　29
3.1.3　二義性文法　30
3.1.4　文件結(jié)束符　31
3.2　預(yù)測(cè)分析　32
3.2.1　FIRST集合和FOLLOW集合　33
3.2.2　構(gòu)造一個(gè)預(yù)測(cè)分析器　35
3.2.3　消除左遞歸　36
3.2.4　提取左因子　37
3.2.5　錯(cuò)誤恢復(fù)　37
3.3　LR分析　39
3.3.1　LR分析引擎　40
3.3.2　LR(0)分析器生成器　41
3.3.3　SLR分析器的生成　44
3.3.4　LR(1)項(xiàng)和LR(1)分析表　45
3.3.5　LALR(1)分析表　46
3.3.6　各類(lèi)文法的層次　47
3.3.7　二義性文法的LR分析　47
3.4　使用分析器的生成器　48
3.4.1　沖突　49
3.4.2　優(yōu)先級(jí)指導(dǎo)　50
3.4.3　語(yǔ)法和語(yǔ)義　53
3.5　錯(cuò)誤恢復(fù)　54
3.5.1　用error符號(hào)恢復(fù)　54
3.5.2　全局錯(cuò)誤修復(fù)　55
程序設(shè)計(jì)：語(yǔ)法分析　57
推薦閱讀　58
習(xí)題　58
第4章　抽象語(yǔ)法　62
4.1　語(yǔ)義動(dòng)作　62
4.1.1　遞歸下降　62
4.1.2　Yacc生成的分析器　62
4.1.3　語(yǔ)義動(dòng)作的解釋器　64
4.2　抽象語(yǔ)法分析樹(shù)　65
4.2.1　位置　67
4.2.2　Tiger的抽象語(yǔ)法　68
程序設(shè)計(jì)：抽象語(yǔ)法　71
推薦閱讀　71
習(xí)題　72
第5章　語(yǔ)義分析　73
5.1　符號(hào)表　73
5.1.1　多個(gè)符號(hào)表　74
5.1.2　高效的命令式風(fēng)格符號(hào)表　75
5.1.3　高效的函數(shù)式符號(hào)表　76
5.1.4　Tiger編譯器的符號(hào)　77
5.1.5　函數(shù)式風(fēng)格的符號(hào)表　79
5.2　Tiger編譯器的綁定　79
5.3　表達(dá)式的類(lèi)型檢查　82
5.4　聲明的類(lèi)型檢查　84
5.4.1　變量聲明　84
5.4.2　類(lèi)型聲明　85
5.4.3　函數(shù)聲明　85
5.4.4　遞歸聲明　86
程序設(shè)計(jì)：類(lèi)型檢查　87
習(xí)題　87
第6章　活動(dòng)記錄　89
6.1　棧幀　90
6.1.1　幀指針　91
6.1.2　寄存器　92
6.1.3　參數(shù)傳遞　92
6.1.4　返回地址　94
6.1.5　棧幀內(nèi)的變量　94
6.1.6　靜態(tài)鏈　95
6.2　Tiger編譯器的棧幀　96
6.2.1　棧幀描述的表示　98
6.2.2　局部變量　98
6.2.3　計(jì)算逃逸變量　99
6.2.4　臨時(shí)變量和標(biāo)號(hào)　100
6.2.5　兩層抽象　100
6.2.6　管理靜態(tài)鏈　102
6.2.7　追蹤層次信息　102
程序設(shè)計(jì)：棧幀　103
推薦閱讀　103
習(xí)題　103
第7章　翻譯成中間代碼　106
7.1　中間表示樹(shù)　106
7.2　翻譯為樹(shù)中間語(yǔ)言　108
7.2.1　表達(dá)式的種類(lèi)　108
7.2.2　簡(jiǎn)單變量　111
7.2.3　追隨靜態(tài)鏈　112
7.2.4　數(shù)組變量　113
7.2.5　結(jié)構(gòu)化的左值　114
7.2.6　下標(biāo)和域選擇　114
7.2.7　關(guān)于安全性的勸告　115
7.2.8　算術(shù)操作　116
7.2.9　條件表達(dá)式　116
7.2.10　字符串　117
7.2.11　記錄和數(shù)組的創(chuàng)建　118
7.2.12　while循環(huán)　119
7.2.13　for循環(huán)　119
7.2.14　函數(shù)調(diào)用　120
7.3　聲明　120
7.3.1　變量定義　120
7.3.2　函數(shù)定義　120
7.3.3　片段　121
程序設(shè)計(jì)：翻譯成樹(shù)　122
習(xí)題　123
第8章　基本塊和軌跡　125
8.1　規(guī)范樹(shù)　126
8.1.1　ESEQ的轉(zhuǎn)換　126
8.1.2　一般重寫(xiě)規(guī)則　126
8.1.3　將CALL移到頂層　130
8.1.4　線性語(yǔ)句表　131
8.2　處理?xiàng)l件分支　131
8.2.1　基本塊　131
8.2.2　軌跡　132
8.2.3　完善　133
8.2.4　最優(yōu)軌跡　133
推薦閱讀　134
習(xí)題　134
第9章　指令選擇　136
9.1　指令選擇算法　138
9.1.1　Maximal Munch算法　138
9.1.2　動(dòng)態(tài)規(guī)劃　140
9.1.3　樹(shù)文法　141
9.1.4　快速匹配　143
9.1.5　覆蓋算法的效率　143
9.2　CISC機(jī)器　144
9.3　Tiger編譯器的指令選擇　146
9.3.1　抽象的匯編語(yǔ)言指令　146
9.3.2　生成匯編指令　148
9.3.3　過(guò)程調(diào)用　151
9.3.4　無(wú)幀指針的情形　151
程序設(shè)計(jì)：指令選擇　152
推薦閱讀　153
習(xí)題　154
第10章　活躍分析　155
10.1　數(shù)據(jù)流方程的解　156
10.1.1　活躍性計(jì)算　156
10.1.2　集合的表示　158
10.1.3　時(shí)間復(fù)雜度　158
10.1.4　最小不動(dòng)點(diǎn)　159
10.1.5　靜態(tài)活躍性與動(dòng)態(tài)活躍性　160
10.1.6　沖突圖　161
10.2　Tiger編譯器的活躍分析　162
10.2.1　圖　162
10.2.2　控制流圖　163
10.2.3　活躍分析　164
程序設(shè)計(jì)：構(gòu)造流圖　164
程序設(shè)計(jì)：活躍分析模塊　165
習(xí)題　165
第11章　寄存器分配　166
11.1　通過(guò)簡(jiǎn)化進(jìn)行著色　166
11.2　合并　168
11.3　預(yù)著色的結(jié)點(diǎn)　171
11.3.1　機(jī)器寄存器的臨時(shí)副本　171
11.3.2　調(diào)用者保護(hù)的寄存器和被調(diào)用者保護(hù)的寄存器　172
11.3.3　含預(yù)著色結(jié)點(diǎn)的例子　172
11.4　圖著色的實(shí)現(xiàn)　175
11.4.1　傳送指令工作表的管理　176
11.4.2　數(shù)據(jù)結(jié)構(gòu)　176
11.4.3　程序代碼　177
11.5　針對(duì)樹(shù)的寄存器分配　181
程序設(shè)計(jì)：圖著色　184
推薦閱讀　185
習(xí)題　185
第12章　整合為一體　188
程序設(shè)計(jì)：過(guò)程入口/出口　189
程序設(shè)計(jì)：創(chuàng)建一個(gè)可運(yùn)行的編譯器　191
第二部分高級(jí)主題
第13章　垃圾收集　193
13.1　標(biāo)記-清掃式收集　194
13.2　引用計(jì)數(shù)　197
13.3　復(fù)制式收集　198
13.4　分代收集　201
13.5　增量式收集　203
13.6　Baker算法　205
13.7　編譯器接口　205
13.7.1　快速分配　205
13.7.2　數(shù)據(jù)布局的描述　206
13.7.3　導(dǎo)出指針　207
程序設(shè)計(jì)：描述字　208
程序設(shè)計(jì)：垃圾收集　208
推薦閱讀　208
習(xí)題　210
第14章　面向?qū)ο蟮恼Z(yǔ)言　211
14.1　類(lèi)　211
14.2　數(shù)據(jù)域的單繼承性　213
14.3　多繼承　214
14.4　測(cè)試類(lèi)成員關(guān)系　216
14.5　私有域和私有方法　218
14.6　無(wú)類(lèi)語(yǔ)言　219
14.7　面向?qū)ο蟪绦虻膬?yōu)化　219
程序設(shè)計(jì)：OBJECT-Tiger　220
推薦閱讀　220
習(xí)題　221
第15章　函數(shù)式程序設(shè)計(jì)語(yǔ)言　222
15.1　一個(gè)簡(jiǎn)單的函數(shù)式語(yǔ)言　222
15.2　閉包　224
15.3　不變的變量　225
15.3.1　基于延續(xù)的I/O　226
15.3.2　語(yǔ)言上的變化　227
15.3.3　純函數(shù)式語(yǔ)言的優(yōu)化　228
15.4　內(nèi)聯(lián)擴(kuò)展　229
15.5　閉包變換　233
15.6　高效的尾遞歸　235
15.7　懶惰計(jì)算　236
15.7.1　傳名調(diào)用計(jì)算　237
15.7.2　按需調(diào)用　238
15.7.3　懶惰程序的計(jì)算　239
15.7.4　懶惰函數(shù)式程序的優(yōu)化　239
15.7.5　嚴(yán)格性分析　241
推薦閱讀　243
程序設(shè)計(jì)：編譯函數(shù)式語(yǔ)言　244
習(xí)題　244
第16章　多態(tài)類(lèi)型　246
16.1　參數(shù)多態(tài)性　246
16.1.1　顯式帶類(lèi)型的多態(tài)語(yǔ)言　247
16.1.2　多態(tài)類(lèi)型的檢查　248
16.2　類(lèi)型推論　253
16.2.1　一個(gè)隱式類(lèi)型的多態(tài)語(yǔ)言　254
16.2.2　類(lèi)型推論算法　255
16.2.3　遞歸的數(shù)據(jù)類(lèi)型　257
16.2.4　Hindley-Milner類(lèi)型的能力　259
16.3　多態(tài)變量的表示　259
16.3.1　多態(tài)函數(shù)的擴(kuò)展　260
16.3.2　完全的裝箱轉(zhuǎn)換　261
16.3.3　基于強(qiáng)制的表示分析　262
16.3.4　將類(lèi)型作為運(yùn)行時(shí)參數(shù)傳遞　264
16.4　靜態(tài)重載的解決方法　265
推薦閱讀　266
習(xí)題　266
第17章　數(shù)據(jù)流分析　269
17.1　流分析使用的中間表示　270
17.2　各種數(shù)據(jù)流分析　271
17.2.1　到達(dá)定值　271
17.2.2　可用表達(dá)式　273
17.2.3　到達(dá)表達(dá)式　274
17.2.4　活躍分析　274
17.3　使用數(shù)據(jù)流分析結(jié)果的幾種轉(zhuǎn)換　274
17.3.1　公共子表達(dá)式刪除　274
17.3.2　常數(shù)傳播　275
17.3.3　復(fù)寫(xiě)傳播　275
17.3.4　死代碼刪除　275
17.4　加快數(shù)據(jù)流分析　276
17.4.1　位向量　276
17.4.2　基本塊　276
17.4.3　結(jié)點(diǎn)排序　277
17.4.4　使用-定值鏈和定值-使用鏈　277
17.4.5　工作表算法　278
17.4.6　增量式數(shù)據(jù)流分析　278
17.5　別名分析　281
17.5.1　基于類(lèi)型的別名分析　282
17.5.2　基于流的別名分析　283
17.5.3　使用可能別名信息　284
17.5.4　嚴(yán)格的純函數(shù)式語(yǔ)言中的別名分析　285
推薦閱讀　285
習(xí)題　285
第18章　循環(huán)優(yōu)化　287
18.1　必經(jīng)結(jié)點(diǎn)　289
18.1.1　尋找必經(jīng)結(jié)點(diǎn)的算法　289
18.1.2　直接必經(jīng)結(jié)點(diǎn)　289
18.1.3　循環(huán)　290
18.1.4　循環(huán)前置結(jié)點(diǎn)　291
18.2　循環(huán)不變量計(jì)算　292
18.3　歸納變量　293
18.3.1　發(fā)現(xiàn)歸納變量　294
18.3.2　強(qiáng)度削弱　295
18.3.3　刪除　296
18.3.4　重寫(xiě)比較　296
18.4　數(shù)組邊界檢查　297
18.5　循環(huán)展開(kāi)　300
推薦閱讀　301
習(xí)題　301
第19章　靜態(tài)單賦值形式　303
19.1　轉(zhuǎn)化為SSA形式　305
19.1.1　插入φ函數(shù)的標(biāo)準(zhǔn)　306
19.1.2　必經(jīng)結(jié)點(diǎn)邊界　306
19.1.3　插入φ函數(shù)　308
19.1.4　變量重命名　309
19.1.5　邊分割　310
19.2　必經(jīng)結(jié)點(diǎn)樹(shù)的高效計(jì)算　310
19.2.1　深度優(yōu)先生成樹(shù)　310
19.2.2　半必經(jīng)結(jié)點(diǎn)　311
19.2.3　Lengauer-Tarjan算法　312
19.3　使用SSA的優(yōu)化算法　315
19.3.1　死代碼刪除　315
19.3.2　簡(jiǎn)單的常數(shù)傳播　316
19.3.3　條件常數(shù)傳播　317
19.3.4　保持必經(jīng)結(jié)點(diǎn)性質(zhì)　319
19.4　數(shù)組、指針和存儲(chǔ)器　320
19.5　控制依賴圖　321
19.6　從SSA形式轉(zhuǎn)變回來(lái)　323
19.7　函數(shù)式中間形式　324
推薦閱讀　327
習(xí)題　328
第20章　流水和調(diào)度　331
20.1　沒(méi)有資源約束時(shí)的循環(huán)調(diào)度　332
20.2　有資源約束的循環(huán)流水　336
20.2.1　模調(diào)度　337
20.2.2　尋找最小的啟動(dòng)間距　338
20.2.3　其他控制流　340
20.2.4　編譯器應(yīng)該調(diào)度指令嗎　340
20.3　分支預(yù)測(cè)　341
20.3.1　靜態(tài)分支預(yù)測(cè)　342
20.3.2　編譯器應(yīng)該預(yù)測(cè)分支嗎　342
推薦閱讀　343
習(xí)題　343
第21章　存儲(chǔ)層次　346
21.1　cache的組織結(jié)構(gòu)　346
21.2　cache塊對(duì)齊　349
21.3　預(yù)取　350
21.4　循環(huán)交換　354
21.5　分塊　355
21.6　垃圾收集和存儲(chǔ)層次　357
推薦閱讀　358
習(xí)題　358
附錄　Tiger語(yǔ)言參考手冊(cè)　360
參考文獻(xiàn)　368
索引　376