編譯器構(gòu)造

目　　錄
Crafting a Compiler
前言
致謝
第1章　引言　1
1.1　編譯技術(shù)歷史　1
1.2　編譯器的功能　2
1.2.1　編譯器生成的機(jī)器代碼　3
1.2.2　目標(biāo)代碼格式　4
1.3　解釋器　5
1.4　語法和語義　6
1.4.1　靜態(tài)語義　7
1.4.2　運(yùn)行時(shí)語義　7
1.5　編譯器的組織　9
1.5.1　詞法分析器　10
1.5.2　語法分析器　10
1.5.3　類型檢查器　10
1.5.4　翻譯器　10
1.5.5　符號(hào)表　11
1.5.6　優(yōu)化器　11
1.5.7　代碼生成器　11
1.5.8　編譯器編寫工具　12
1.6　程序設(shè)計(jì)語言和編譯器設(shè)計(jì)　12
1.7　計(jì)算機(jī)體系結(jié)構(gòu)和編譯器設(shè)計(jì)　13
1.8　編譯器設(shè)計(jì)考慮　13
1.8.1　調(diào)試編譯器　14
1.8.2　優(yōu)化編譯器　14
1.8.3　可重定位編譯器　14
1.9　集成開發(fā)環(huán)境　15
習(xí)題　15
第2章　一個(gè)簡單的編譯器　18
2.1　ac語言的一個(gè)非形式化定義　18
2.2　ac的形式化定義　19
2.2.1　語法規(guī)范　19
2.2.2　單詞規(guī)范　20
2.3　一個(gè)簡單編譯器的各階段　21
2.4　詞法分析　22
2.5　語法分析　23
2.5.1　預(yù)測語法分析例程　24
2.5.2　實(shí)現(xiàn)產(chǎn)生式　25
2.6　抽象語法樹　25
2.7　語義分析　27
2.7.1　符號(hào)表　27
2.7.2　類型檢查　27
2.8　代碼生成　29
習(xí)題　31
第3章　詞法分析——理論與實(shí)踐　32
3.1　詞法分析器概述　32
3.2　正則表達(dá)式　34
3.3　示例　35
3.4　有限自動(dòng)機(jī)與詞法分析器　36
3.5　詞法分析器生成器　39
3.5.1　在Lex中定義單詞　40
3.5.2　字符集　40
3.5.3　使用正則表達(dá)式定義單詞　41
3.5.4　使用Lex處理字符　43
3.6　其他詞法分析器生成器　44
3.7　構(gòu)建詞法分析器的實(shí)際考慮　45
3.7.1　處理標(biāo)識(shí)符和字面值　45
3.7.2　使用編譯器指示以及列出
源碼行　48
3.7.3　結(jié)束詞法分析器　49
3.7.4　多超前字符　49
3.7.5　性能考慮　51
3.7.6　詞法錯(cuò)誤恢復(fù)　52
3.8　正則表達(dá)式和有限自動(dòng)機(jī)　53
3.8.1　將正則表達(dá)式轉(zhuǎn)換為NFA　54
3.8.2　創(chuàng)建DFA　54
3.8.3　優(yōu)化有限自動(dòng)機(jī)　56
3.8.4　將有限自動(dòng)機(jī)轉(zhuǎn)換為正則
表達(dá)式　58
3.9　總結(jié)　60
習(xí)題　61
第4章　文法和語法分析　64
4.1　上下文無關(guān)文法　64
4.1.1　最左推導(dǎo)　66
4.1.2　最右推導(dǎo)　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　錯(cuò)誤的語言定義　69
4.3　轉(zhuǎn)換擴(kuò)展文法　69
4.4　語法分析器和識(shí)別器　70
4.5　文法分析算法　72
4.5.1　文法表示　72
4.5.2　推導(dǎo)空字符串　73
4.5.3　First集　74
4.5.4　Follow集　77
習(xí)題　79
第5章　自頂向下語法分析　82
5.1　概述　82
5.2　LL(k)文法　83
5.3　遞歸下降LL(1)語法分析器　85
5.4　表驅(qū)動(dòng)LL(1)語法分析器　86
5.5　獲得LL(1)文法　88
5.5.1　公共前綴　88
5.5.2　左遞歸　89
5.6　一個(gè)非LL(1)語言　90
5.7　LL(1)分析器的性質(zhì)　92
5.8　分析表的表示　92
5.8.1　緊湊存儲(chǔ)　93
5.8.2　壓縮　94
5.9　語法錯(cuò)誤恢復(fù)和修復(fù)　96
5.9.1　錯(cuò)誤恢復(fù)　96
5.9.2　錯(cuò)誤修復(fù)　96
5.9.3　LL(1)分析器中的錯(cuò)誤檢測　97
5.9.4　LL(1)分析器中的錯(cuò)誤恢復(fù)　97
習(xí)題　98
第6章　自底向上語法分析　102
6.1　概述　102
6.2　移進(jìn)–歸約語法分析器　103
6.2.1　LR語法分析器和最右推導(dǎo)　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
習(xí)題　129
第7章　語法制導(dǎo)翻譯　135
7.1　概述　135
7.1.1　語義動(dòng)作和語義值　135
7.1.2　綜合屬性和繼承屬性　136
7.2　自底向上語法制導(dǎo)翻譯　137
7.2.1　示例　137
7.2.2　 產(chǎn)生式克隆　139
7.2.3　強(qiáng)制執(zhí)行語義動(dòng)作　140
7.2.4　激進(jìn)的文法重構(gòu)　141
7.3　自頂向下語法制導(dǎo)翻譯　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è)計(jì)和構(gòu)造　146
7.5.1　設(shè)計(jì)　147
7.5.2　構(gòu)造　148
7.6　左值和右值的AST結(jié)構(gòu)　150
7.7　AST設(shè)計(jì)模式　152
7.7.1　節(jié)點(diǎn)類層次　152
7.7.2　訪問者模式　153
7.7.3　反射訪問者模式　154
習(xí)題　157
第8章　符號(hào)表和聲明處理　160
8.1　構(gòu)造符號(hào)表　160
8.1.1　靜態(tài)作用域　161
8.1.2　符號(hào)表接口　162
8.2　塊結(jié)構(gòu)語言和作用域　163
8.2.1　處理作用域　163
8.2.2　單符號(hào)表還是多符號(hào)表　163
8.3　基本實(shí)現(xiàn)技術(shù)　164
8.3.1　插入和查找名字　164
8.3.2　名字空間　166
8.3.3　一個(gè)高效的符號(hào)表實(shí)現(xiàn)　166
8.4　高級(jí)特性　169
8.4.1　記錄和類型名　169
8.4.2　重載和類型層次　170
8.4.3　隱式聲明　170
8.4.4　導(dǎo)出指示和導(dǎo)入指示　171
8.4.5　改變搜索規(guī)則　171
8.5　聲明處理基礎(chǔ)　172
8.5.1　符號(hào)表中的屬性　172
8.5.2　類型描述符結(jié)構(gòu)　172
8.5.3　使用抽象語法樹進(jìn)行類型
檢查　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　簡單標(biāo)識(shí)符和字面量　190
8.8.2　賦值語句　190
8.8.3　檢查表達(dá)式　191
8.8.4　檢查復(fù)雜名字　191
8.9　總結(jié)　194
習(xí)題　195
第9章　語義分析　198
9.1　控制結(jié)構(gòu)的語義分析　198
9.1.1　可達(dá)性和終止分析　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
習(xí)題　223
第10章　中間表示　227
10.1　概述　227
10.1.1　示例　228
10.1.2　中端　229
10.2　Java虛擬機(jī)　230
10.2.1　簡介和設(shè)計(jì)原則　230
10.2.2　類文件內(nèi)容　231
10.2.3　JVM指令　232
10.3　靜態(tài)單賦值形式　237
習(xí)題　239
第11章　虛擬機(jī)代碼生成　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　局部存儲(chǔ)引用　246
11.3.3　靜態(tài)引用　246
11.3.4　表達(dá)式　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
習(xí)題　256
第12章　運(yùn)行時(shí)支持　258
12.1　靜態(tài)分配　258
12.2　棧分配　259
12.2.1　類和結(jié)構(gòu)中的字段訪問　260
12.2.2　運(yùn)行時(shí)訪問幀　261
12.2.3　處理類和對(duì)象　262
12.2.4　處理多重作用域　263
12.2.5　塊級(jí)分配　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　分配機(jī)制　272
12.4.2　釋放機(jī)制　274
12.4.3　自動(dòng)垃圾收集　274
12.5　基于區(qū)域的內(nèi)存管理　279
習(xí)題　280
第13章　目標(biāo)代碼生成　284
13.1　翻譯字節(jié)碼　285
13.1.1　分配內(nèi)存地址　286
13.1.2　分配數(shù)組和對(duì)象　286
13.1.3　方法調(diào)用　288
13.1.4　字節(jié)碼翻譯過程的示例　290
13.2　翻譯表達(dá)式樹　291
13.3　寄存器分配　294
13.3.1　動(dòng)態(tài)寄存器分配　294
13.3.2　使用圖著色進(jìn)行寄存器
分配　296
13.3.3　基于優(yōu)先級(jí)的寄存器分配　300
13.3.4　過程間寄存器分配　301
13.4　代碼調(diào)度　302
13.4.1　改進(jìn)代碼調(diào)度　305
13.4.2　全局和動(dòng)態(tài)代碼調(diào)度　306
13.5　指令自動(dòng)選擇　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)化級(jí)別　311
13.6.2　自動(dòng)生成窺孔優(yōu)化器　313
習(xí)題　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)系計(jì)算算法　330
14.2.7　快速的支配關(guān)系計(jì)算算法　332
14.2.8　支配前沿　339
14.2.9　區(qū)間　341
14.3　數(shù)據(jù)流分析介紹　349
14.3.1　可用表達(dá)式　349
14.3.2　活躍變量　351
14.4　數(shù)據(jù)流框架　352
14.4.1　數(shù)據(jù)流評(píng)估圖　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
習(xí)題　371
參考文獻(xiàn)　378