編譯器構(gòu)造

目　　錄
Crafting a Compiler
前言
致謝
第1章　引言　1
1.1　編譯技術(shù)歷史　1
1.2　編譯器的功能　2
1.2.1　編譯器生成的機器代碼　3
1.2.2　目標代碼格式　4
1.3　解釋器　5
1.4　語法和語義　6
1.4.1　靜態(tài)語義　7
1.4.2　運行時語義　7
1.5　編譯器的組織　9
1.5.1　詞法分析器　10
1.5.2　語法分析器　10
1.5.3　類型檢查器　10
1.5.4　翻譯器　10
1.5.5　符號表　11
1.5.6　優(yōu)化器　11
1.5.7　代碼生成器　11
1.5.8　編譯器編寫工具　12
1.6　程序設(shè)計語言和編譯器設(shè)計　12
1.7　計算機體系結(jié)構(gòu)和編譯器設(shè)計　13
1.8　編譯器設(shè)計考慮　13
1.8.1　調(diào)試編譯器　14
1.8.2　優(yōu)化編譯器　14
1.8.3　可重定位編譯器　14
1.9　集成開發(fā)環(huán)境　15
習題　15
第2章　一個簡單的編譯器　18
2.1　ac語言的一個非形式化定義　18
2.2　ac的形式化定義　19
2.2.1　語法規(guī)范　19
2.2.2　單詞規(guī)范　20
2.3　一個簡單編譯器的各階段　21
2.4　詞法分析　22
2.5　語法分析　23
2.5.1　預(yù)測語法分析例程　24
2.5.2　實現(xiàn)產(chǎn)生式　25
2.6　抽象語法樹　25
2.7　語義分析　27
2.7.1　符號表　27
2.7.2　類型檢查　27
2.8　代碼生成　29
習題　31
第3章　詞法分析——理論與實踐　32
3.1　詞法分析器概述　32
3.2　正則表達式　34
3.3　示例　35
3.4　有限自動機與詞法分析器　36
3.5　詞法分析器生成器　39
3.5.1　在Lex中定義單詞　40
3.5.2　字符集　40
3.5.3　使用正則表達式定義單詞　41
3.5.4　使用Lex處理字符　43
3.6　其他詞法分析器生成器　44
3.7　構(gòu)建詞法分析器的實際考慮　45
3.7.1　處理標識符和字面值　45
3.7.2　使用編譯器指示以及列出
源碼行　48
3.7.3　結(jié)束詞法分析器　49
3.7.4　多超前字符　49
3.7.5　性能考慮　51
3.7.6　詞法錯誤恢復(fù)　52
3.8　正則表達式和有限自動機　53
3.8.1　將正則表達式轉(zhuǎn)換為NFA　54
3.8.2　創(chuàng)建DFA　54
3.8.3　優(yōu)化有限自動機　56
3.8.4　將有限自動機轉(zhuǎn)換為正則
表達式　58
3.9　總結(jié)　60
習題　61
第4章　文法和語法分析　64
4.1　上下文無關(guān)文法　64
4.1.1　最左推導　66
4.1.2　最右推導　66
4.1.3　語法分析樹　66
4.1.4　其他類型的文法　67
4.2　CFG的性質(zhì)　68
4.2.1　歸約文法　68
4.2.2　二義性　68
4.2.3　錯誤的語言定義　69
4.3　轉(zhuǎn)換擴展文法　69
4.4　語法分析器和識別器　70
4.5　文法分析算法　72
4.5.1　文法表示　72
4.5.2　推導空字符串　73
4.5.3　First集　74
4.5.4　Follow集　77
習題　79
第5章　自頂向下語法分析　82
5.1　概述　82
5.2　LL(k)文法　83
5.3　遞歸下降LL(1)語法分析器　85
5.4　表驅(qū)動LL(1)語法分析器　86
5.5　獲得LL(1)文法　88
5.5.1　公共前綴　88
5.5.2　左遞歸　89
5.6　一個非LL(1)語言　90
5.7　LL(1)分析器的性質(zhì)　92
5.8　分析表的表示　92
5.8.1　緊湊存儲　93
5.8.2　壓縮　94
5.9　語法錯誤恢復(fù)和修復(fù)　96
5.9.1　錯誤恢復(fù)　96
5.9.2　錯誤修復(fù)　96
5.9.3　LL(1)分析器中的錯誤檢測　97
5.9.4　LL(1)分析器中的錯誤恢復(fù)　97
習題　98
第6章　自底向上語法分析　102
6.1　概述　102
6.2　移進–歸約語法分析器　103
6.2.1　LR語法分析器和最右推導　103
6.2.2　LR分析如針織　104
6.2.3　LR分析引擎　105
6.2.4　LR分析表　105
6.2.5　LR(k)分析　107
6.3　構(gòu)造LR(0)分析表　109
6.4　沖突診斷　113
6.4.1　二義性文法　114
6.4.2　非LR(k)文法　116
6.5　沖突消解和表構(gòu)造　117
6.5.1　SLR(k)分析表構(gòu)造　117
6.5.2　LALR(k)分析表構(gòu)造　120
6.5.3　LALR傳播圖　122
6.5.4　LR(k)表構(gòu)造　125
習題　129
第7章　語法制導翻譯　135
7.1　概述　135
7.1.1　語義動作和語義值　135
7.1.2　綜合屬性和繼承屬性　136
7.2　自底向上語法制導翻譯　137
7.2.1　示例　137
7.2.2　 產(chǎn)生式克隆　139
7.2.3　強制執(zhí)行語義動作　140
7.2.4　激進的文法重構(gòu)　141
7.3　自頂向下語法制導翻譯　142
7.4　抽象語法樹　143
7.4.1　具體語法樹與抽象語法樹　144
7.4.2　一種高效的AST數(shù)據(jù)結(jié)構(gòu)　144
7.4.3　創(chuàng)建AST的基礎(chǔ)架構(gòu)　145
7.5　AST設(shè)計和構(gòu)造　146
7.5.1　設(shè)計　147
7.5.2　構(gòu)造　148
7.6　左值和右值的AST結(jié)構(gòu)　150
7.7　AST設(shè)計模式　152
7.7.1　節(jié)點類層次　152
7.7.2　訪問者模式　153
7.7.3　反射訪問者模式　154
習題　157
第8章　符號表和聲明處理　160
8.1　構(gòu)造符號表　160
8.1.1　靜態(tài)作用域　161
8.1.2　符號表接口　162
8.2　塊結(jié)構(gòu)語言和作用域　163
8.2.1　處理作用域　163
8.2.2　單符號表還是多符號表　163
8.3　基本實現(xiàn)技術(shù)　164
8.3.1　插入和查找名字　164
8.3.2　名字空間　166
8.3.3　一個高效的符號表實現(xiàn)　166
8.4　高級特性　169
8.4.1　記錄和類型名　169
8.4.2　重載和類型層次　170
8.4.3　隱式聲明　170
8.4.4　導出指示和導入指示　171
8.4.5　改變搜索規(guī)則　171
8.5　聲明處理基礎(chǔ)　172
8.5.1　符號表中的屬性　172
8.5.2　類型描述符結(jié)構(gòu)　172
8.5.3　使用抽象語法樹進行類型
檢查　173
8.6　變量和類型聲明　174
8.6.1　簡單變量聲明　174
8.6.2　處理類型名　175
8.6.3　類型聲明　176
8.6.4　變量聲明再探　178
8.6.5　靜態(tài)數(shù)組類型　179
8.6.6　結(jié)構(gòu)和記錄類型　180
8.6.7　枚舉類型　181
8.7　類和方法聲明　183
8.7.1　處理類聲明　184
8.7.2　處理方法聲明　186
8.8　類型檢查簡介　188
8.8.1　簡單標識符和字面量　190
8.8.2　賦值語句　190
8.8.3　檢查表達式　191
8.8.4　檢查復(fù)雜名字　191
8.9　總結(jié)　194
習題　195
第9章　語義分析　198
9.1　控制結(jié)構(gòu)的語義分析　198
9.1.1　可達性和終止分析　199
9.1.2　if語句　200
9.1.3　while、do和repeat循環(huán)
語句　203
9.1.4　for循環(huán)語句　204
9.1.5　break、continue、return和
goto語句　205
9.1.6　switch和case語句　210
9.1.7　異常處理　214
9.2　方法調(diào)用的語義分析　218
9.3　總結(jié)　223
習題　223
第10章　中間表示　227
10.1　概述　227
10.1.1　示例　228
10.1.2　中端　229
10.2　Java虛擬機　230
10.2.1　簡介和設(shè)計原則　230
10.2.2　類文件內(nèi)容　231
10.2.3　JVM指令　232
10.3　靜態(tài)單賦值形式　237
習題　239
第11章　虛擬機代碼生成　241
11.1　代碼生成訪問者　241
11.2　類和方法聲明　243
11.2.1　類聲明　243
11.2.2　方法聲明　245
11.3　MethodBodyVisitor　245
11.3.1　常量　245
11.3.2　局部存儲引用　246
11.3.3　靜態(tài)引用　246
11.3.4　表達式　247
11.3.5　賦值　248
11.3.6　方法調(diào)用　249
11.3.7　字段引用　250
11.3.8　數(shù)組引用　251
11.3.9　條件執(zhí)行　252
11.3.10　循環(huán)　252
11.4　LHSVisitor　253
11.4.1　局部引用　254
11.4.2　靜態(tài)引用　254
11.4.3　字段引用　255
11.4.4　數(shù)組引用　255
習題　256
第12章　運行時支持　258
12.1　靜態(tài)分配　258
12.2　棧分配　259
12.2.1　類和結(jié)構(gòu)中的字段訪問　260
12.2.2　運行時訪問幀　261
12.2.3　處理類和對象　262
12.2.4　處理多重作用域　263
12.2.5　塊級分配　264
12.2.6　關(guān)于幀的更多討論　265
12.3　數(shù)組　267
12.3.1　靜態(tài)一維數(shù)組　267
12.3.2　多維數(shù)組　270
12.4　堆管理　272
12.4.1　分配機制　272
12.4.2　釋放機制　274
12.4.3　自動垃圾收集　274
12.5　基于區(qū)域的內(nèi)存管理　279
習題　280
第13章　目標代碼生成　284
13.1　翻譯字節(jié)碼　285
13.1.1　分配內(nèi)存地址　286
13.1.2　分配數(shù)組和對象　286
13.1.3　方法調(diào)用　288
13.1.4　字節(jié)碼翻譯過程的示例　290
13.2　翻譯表達式樹　291
13.3　寄存器分配　294
13.3.1　動態(tài)寄存器分配　294
13.3.2　使用圖著色進行寄存器
分配　296
13.3.3　基于優(yōu)先級的寄存器分配　300
13.3.4　過程間寄存器分配　301
13.4　代碼調(diào)度　302
13.4.1　改進代碼調(diào)度　305
13.4.2　全局和動態(tài)代碼調(diào)度　306
13.5　指令自動選擇　307
13.5.1　使用BURS選擇指令　308
13.5.2　使用Twig選擇指令　310
13.5.3　其他方法　310
13.6　窺孔優(yōu)化　311
13.6.1　窺孔優(yōu)化級別　311
13.6.2　自動生成窺孔優(yōu)化器　313
習題　314
第14章　程序優(yōu)化　318
14.1　概述　318
14.2　控制流分析　323
14.2.1　控制流圖　323
14.2.2　程序和控制流結(jié)構(gòu)　325
14.2.3　直接過程調(diào)用圖　325
14.2.4　深度優(yōu)先生成樹　326
14.2.5　支配關(guān)系　329
14.2.6　簡單的支配關(guān)系計算算法　330
14.2.7　快速的支配關(guān)系計算算法　332
14.2.8　支配前沿　339
14.2.9　區(qū)間　341
14.3　數(shù)據(jù)流分析介紹　349
14.3.1　可用表達式　349
14.3.2　活躍變量　351
14.4　數(shù)據(jù)流框架　352
14.4.1　數(shù)據(jù)流評估圖　353
14.4.2　交格　354
14.4.3　轉(zhuǎn)移函數(shù)　355
14.5　求解　356
14.5.1　迭代　356
14.5.2　初始化　359
14.5.3　終止和快速框架　360
14.5.4　滿足分配律的框架　363
14.6　常量傳播　364
14.7　SSA形式　366
14.7.1　放置函數(shù)　368
14.7.2　重命名　369
習題　371
參考文獻　378