編譯器構(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　語(yǔ)法和語(yǔ)義　6
1.4.1　靜態(tài)語(yǔ)義　7
1.4.2　運(yùn)行時(shí)語(yǔ)義　7
1.5　編譯器的組織　9
1.5.1　詞法分析器　10
1.5.2　語(yǔ)法分析器　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ì)語(yǔ)言和編譯器設(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è)簡(jiǎn)單的編譯器　18
2.1　ac語(yǔ)言的一個(gè)非形式化定義　18
2.2　ac的形式化定義　19
2.2.1　語(yǔ)法規(guī)范　19
2.2.2　單詞規(guī)范　20
2.3　一個(gè)簡(jiǎn)單編譯器的各階段　21
2.4　詞法分析　22
2.5　語(yǔ)法分析　23
2.5.1　預(yù)測(cè)語(yǔ)法分析例程　24
2.5.2　實(shí)現(xiàn)產(chǎn)生式　25
2.6　抽象語(yǔ)法樹　25
2.7　語(yǔ)義分析　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章　文法和語(yǔ)法分析　64
4.1　上下文無(wú)關(guān)文法　64
4.1.1　最左推導(dǎo)　66
4.1.2　最右推導(dǎo)　66
4.1.3　語(yǔ)法分析樹　66
4.1.4　其他類型的文法　67
4.2　CFG的性質(zhì)　68
4.2.1　歸約文法　68
4.2.2　二義性　68
4.2.3　錯(cuò)誤的語(yǔ)言定義　69
4.3　轉(zhuǎn)換擴(kuò)展文法　69
4.4　語(yǔ)法分析器和識(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章　自頂向下語(yǔ)法分析　82
5.1　概述　82
5.2　LL(k)文法　83
5.3　遞歸下降LL(1)語(yǔ)法分析器　85
5.4　表驅(qū)動(dòng)LL(1)語(yǔ)法分析器　86
5.5　獲得LL(1)文法　88
5.5.1　公共前綴　88
5.5.2　左遞歸　89
5.6　一個(gè)非LL(1)語(yǔ)言　90
5.7　LL(1)分析器的性質(zhì)　92
5.8　分析表的表示　92
5.8.1　緊湊存儲(chǔ)　93
5.8.2　壓縮　94
5.9　語(yǔ)法錯(cuò)誤恢復(fù)和修復(fù)　96
5.9.1　錯(cuò)誤恢復(fù)　96
5.9.2　錯(cuò)誤修復(fù)　96
5.9.3　LL(1)分析器中的錯(cuò)誤檢測(cè)　97
5.9.4　LL(1)分析器中的錯(cuò)誤恢復(fù)　97
習(xí)題　98
第6章　自底向上語(yǔ)法分析　102
6.1　概述　102
6.2　移進(jìn)–歸約語(yǔ)法分析器　103
6.2.1　LR語(yǔ)法分析器和最右推導(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章　語(yǔ)法制導(dǎo)翻譯　135
7.1　概述　135
7.1.1　語(yǔ)義動(dòng)作和語(yǔ)義值　135
7.1.2　綜合屬性和繼承屬性　136
7.2　自底向上語(yǔ)法制導(dǎo)翻譯　137
7.2.1　示例　137
7.2.2　 產(chǎn)生式克隆　139
7.2.3　強(qiáng)制執(zhí)行語(yǔ)義動(dòng)作　140
7.2.4　激進(jìn)的文法重構(gòu)　141
7.3　自頂向下語(yǔ)法制導(dǎo)翻譯　142
7.4　抽象語(yǔ)法樹　143
7.4.1　具體語(yǔ)法樹與抽象語(yǔ)法樹　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　訪問(wèn)者模式　153
7.7.3　反射訪問(wèn)者模式　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)語(yǔ)言和作用域　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　使用抽象語(yǔ)法樹進(jìn)行類型
檢查　173
8.6　變量和類型聲明　174
8.6.1　簡(jiǎn)單變量聲明　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　類型檢查簡(jiǎn)介　188
8.8.1　簡(jiǎn)單標(biāo)識(shí)符和字面量　190
8.8.2　賦值語(yǔ)句　190
8.8.3　檢查表達(dá)式　191
8.8.4　檢查復(fù)雜名字　191
8.9　總結(jié)　194
習(xí)題　195
第9章　語(yǔ)義分析　198
9.1　控制結(jié)構(gòu)的語(yǔ)義分析　198
9.1.1　可達(dá)性和終止分析　199
9.1.2　if語(yǔ)句　200
9.1.3　while、do和repeat循環(huán)
語(yǔ)句　203
9.1.4　for循環(huán)語(yǔ)句　204
9.1.5　break、continue、return和
goto語(yǔ)句　205
9.1.6　switch和case語(yǔ)句　210
9.1.7　異常處理　214
9.2　方法調(diào)用的語(yǔ)義分析　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　簡(jiǎn)介和設(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　代碼生成訪問(wèn)者　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)中的字段訪問(wèn)　260
12.2.2　運(yùn)行時(shí)訪問(wèn)幀　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é)碼翻譯過(guò)程的示例　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　過(guò)程間寄存器分配　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　直接過(guò)程調(diào)用圖　325
14.2.4　深度優(yōu)先生成樹　326
14.2.5　支配關(guān)系　329
14.2.6　簡(jiǎn)單的支配關(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