目　錄
第1章　開始製作編譯器　　1
1.1　本書的概要　　2
本書的主題　　2
本書製作的編譯器　　 2
編譯示例　　2
可執行文件　　3
編譯　　4
程序運行環境　　6
1.2　編譯過程　　8
編譯的4 個階段　　8
語法分析　　8
語義分析　　9
生成中間代碼　　9
代碼生成　　10
優化　　10
總結　　10
1.3　使用CЬ編譯器進行編譯　　11
CЬ編譯器的必要環境　　11
安裝CЬ編譯器　　11
CЬ的Hello, World!　　12
第2章　CЬ和cbc　　13
2.1　CЬ語言的概要　　14
CЬ的Hello, World ！　　14
CЬ中刪減的功能　　 14
import 關鍵字　　15
導入文件的規範　　16
2.2　CЬ編譯器cbc 的構成　　17
cbc 的代碼樹　　17
cbc 的包　　18
compiler 包中的類群　　18
main 函數的實現　　 19
commandMain 函數的實現　　19
Java5 泛型　　20
build 函數的實現　　 20
Java 5 的foreach 語句　　21
compile 函數的實現　　21
第1部分　代碼分析
第3章　語法分析的概要　　24
3.1　語法分析的方法　　25
代碼分析中的問題點　　25
代碼分析的一般規律　　25
詞法分析、語法分析、語義分析　　25
掃描器的動作　　26
單詞的種類和語義值　　27
token　　28
抽象語法樹和節點　　29
3.2　解析器生成器　　30
什麼是解析器生成器　　30
解析器生成器的種類　　30
解析器生成器的選擇　　31
3.3　JavaCC 的概要　　33
什麼是JavaCC　　33
語法描述文件　　33
語法描述文件的例子　　34
運行JavaCC　　35
啓動JavaCC 所生成的解析器　　36
中文的處理　　37
第4章　詞法分析　　39
4.1　基於JavaCC 的掃描器的描述　　40
本章的目的　　40
JavaCC 的正則錶達式　　40
固定字符串　　41
連接　　41
字符組　　41
排除型字符組　　41
重復1 次或多次　　42
重復0 次或多次　　42
重復n 次到m 次　　 42
正好重復n 次　　43
可以省略　　43
選擇　　43
4.2　掃描沒有結構的單詞　　44
TOKEN 命令　　44
掃描標識符和保留字　　44
選擇匹配規則　　45
掃描數值　　46
4.3　掃描不生成token 的單詞　　48
SKIP 命令和SPECIAL_TOKEN 命令　　48
跳過空白符　　48
跳過行注釋　　49
4.4 掃描具有結構的單詞　　50
最長匹配原則和它的問題　　50
基於狀態遷移的掃描　　50
MORE 命令　　51
跳過塊注釋　　52
掃描字符串字麵量　　53
掃描字符字麵量　　53
第5章　基於JavaCC 的解析器的描述　　55
5.1　基於EBNF 語法的描述　　56
本章的目的　　56
基於JavaCC 的語法描述　　56
終端符和非終端符　　57
JavaCC 的EBNF 錶示法　　58
連接　　58
重復0 次或多次　　59
重復1 次或多次　　59
選擇　　60
可以省略　　60
5.2　語法的二義性和token 的超前掃描　　61
語法的二義性　　61
JavaCC 的局限性　　62
提取左側共通部分　　63
token 的超前掃描　　63
可以省略的規則和衝突　　64
重復和衝突　　65
更靈活的超前掃描　　66
超前掃描的相關注意事項　　66
第6章　語法分析　　68
6.1　定義的分析　　69
錶示程序整體的符號　　69
語法的單位　　69
import 聲明的語法　　70
各類定義的語法　　71
變量定義的語法　　72
函數定義的語法　　73
結構體定義和聯閤體定義的語法　　74
結構體成員和聯閤體成員的語法　　75
typedef 語句的語法　　76
類型的語法　　76
C 語言和CЬ在變量定義上的區彆　　77
基本類型的語法　　77
6.2　語句的分析　　79
語句的語法　　79
if 語句的語法　　80
省略if 語句和大括號　　80
while 語句的語法　　81
for 語句的語法　　81
各類跳轉語句的語法　　82
6.3　錶達式的分析　　83
錶達式的整體結構　　83
expr 的規則　　83
條件錶達式　　84
二元運算符　　85
6.4　項的分析　　88
項的規則　　88
前置運算符的規則　　88
後置運算符的規則　　89
字麵量的規則　　89
第2部分　抽象語法樹和中間代碼
第7章　JavaCC 的action 和抽象語法樹　　92
7.1　JavaCC 的action　　93
本章的目的　　93
簡單的action　　93
執行action 的時間點　　93
返迴語義值的action　　95
獲取終端符號的語義值　　95
Token 類的屬性　　96
獲取非終端符號的語義值　　98
語法樹的結構　　99
選擇和action　　99
重復和action　　100
本節總結　　102
7.2　抽象語法樹和節點　　103
Node 類群　　103
Node 類的定義　　105
抽象語法樹的錶示　　105
基於節點錶示錶達式的例子　　107
第8章　抽象語法樹的生成　　110
8.1　錶達式的抽象語法樹　　111
字麵量的抽象語法樹　　111
類型的錶示　　112
為什麼需要TypeRef 類　　113
一元運算的抽象語法樹　　114
二元運算的抽象語法樹　　116
條件錶達式的抽象語法樹　　117
賦值錶達式的抽象語法樹　　118
8.2　語句的抽象語法樹　　121
if 語句的抽象語法樹　　121
while 語句的抽象語法樹　　122
程序塊的抽象語法樹　　123
8.3　聲明的抽象語法樹　　125
變量聲明列錶的抽象語法樹　　125
函數定義的抽象語法樹　　126
錶示聲明列錶的抽象語法樹　　127
錶示程序整體的抽象語法樹　　128
外部符號的import　　128
總結　　129
8.4　cbc 的解析器的啓動　　132
Parser 對象的生成　　132
文件的解析　　133
解析器的啓動　　134
第9章　語義分析（1）引用的消解　　135
9.1　語義分析的概要　　136
本章目的　　136
抽象語法樹的遍曆　　137
不使用Visitor 模式的抽象語法樹的處理　　137
基於Visitor 模式的抽象語法樹的處理　　138
Vistor 模式的一般化　　140
cbc 中Visitor 模式的實現　　141
語義分析相關的cbc 的類　　142
9.2　變量引用的消解　　144
問題概要　　144
實現的概要　　144
Scope 樹的結構　　145
LocalResolver 類的屬性　　146
LocalResolver 類的啓動　　146
變量定義的添加　　147
函數定義的處理　　148
pushScope 方法　　149
currentScope 方法　　149
popScope 方法　　150
添加臨時作用域　　150
建立VariableNode 和變量定義的關聯　　151
從作用域樹取得變量定義　　151
9.3　類型名稱的消解　　153
問題概要　　153
實現的概要　　153
TypeResolver 類的屬性　　153
TypeResolver 類的啓動　　154
類型的聲明　　154
類型和抽象語法樹的遍曆　　155
變量定義的類型消解　　156
函數定義的類型消解　　157
第10章　語義分析（2）靜態類型檢查　　159
10.1　類型定義的檢查　　160
問題概要　　160
實現的概要　　161
檢測有嚮圖中的閉環的算法　　162
結構體、聯閤體的循環定義檢查　　163
10.2　錶達式的有效性檢查　　165
問題概要　　165
實現的概要　　165
DereferenceChecker 類的啓動　　166
SemanticError 異常的捕獲　　167
非指針類型取值操作的檢查　　167
獲取非左值錶達式地址的檢查　　168
隱式的指針生成　　169
10.3　靜態類型檢查　　170
問題概要　　170
實現的概要　　170
CЬ中操作數的類型　　171
隱式類型轉換　　172
TyperChecker 類的啓動　　173
二元運算符的類型檢查　　174
隱式類型轉換的實現　　175
第11章　中間代碼的轉換　　178
11.1　cbc 的中間代碼　　179
組成中間代碼的類　　180
中間代碼節點類的屬性　　181
中間代碼的運算符和類型　　182
各類中間代碼　　183
中間代碼的意義　　184
11.2　IRGenerator 類的概要　　185
抽象語法樹的遍曆和返迴值　　185
IRGenerator 類的啓動　　185
函數本體的轉換　　186
作為語句的錶達式的判彆　　187
11.3　流程控製語句的轉換　　189
if 語句的轉換（1）概要　　189
if 語句的轉換（2）沒有else 部分的情況　　190
if 語句的轉換（3）存在else 部分的情況　　191
while 語句的轉換　　191
break 語句的轉換（1）問題的定義　　192
break 語句的轉換（2）實現的方針　　193
break 語句的轉換（3）實現　　194
11.4　沒有副作用的錶達式的轉換　　196
UnaryOpNode 對象的轉換　　196
BinaryOpNode 對象的轉換　　197
指針加減運算的轉換　　198
11.5　左值的轉換　　200
左邊和右邊　　200
左值和右值　　200
cbc 中左值的錶現　　201
結構體成員的偏移　　202
成員引用（expr.memb）的轉換　　203
左值轉換的例外：數組和函數　　204
成員引用的錶達式（ptr->memb）的轉換　　205
11.6　存在副作用的錶達式的轉換　　206
錶達式的副作用　　206
有副作用的錶達式的轉換方針　　206
簡單賦值錶達式的轉換（1）語句　　207
臨時變量的引入　　208
簡單賦值錶達式的轉換（2）錶達式　　209
後置自增的轉換　　210
第3部分　匯編代碼
第12章　x86 架構的概要　　214
12.1　計算機的係統結構　　215
CPU 和存儲器　　215
寄存器　　215
地址　　216
物理地址和虛擬地址　　216
各類設備　　217
緩存　　218
12.2　x86 係列CPU 的曆史　　220
x86 係列CPU　　220
32 位CPU　　220
指令集　　221
IA-32 的變遷　　222
IA-32 的64 位擴展——AMD64　　222
12.3　IA-32 的概要　　224
IA-32 的寄存器　　224
通用寄存器　　225
機器棧　　226
機器棧的操作　　227
機器棧的用途　　227
棧幀　　228
指令指針　　229
標誌寄存器　　229
12.4　數據的錶現形式和格式　　231
無符號整數的錶現形式　　231
有符號整數的錶現形式　　231
負整數的錶現形式和二進製補碼　　232
字節序　　233
對齊　　233
結構體的錶現形式　　234
第13章　x86 匯編器編程　　236
13.1　基於GNU 匯編器的編程　　237
GNU 匯編器　　237
匯編語言的Hello, World!　　237
基於GNU 匯編器的匯編代碼　　238
13.2　GNU 匯編器的語法　　240
匯編版的Hello, World!　　240
指令　　241
匯編僞操作　　241
標簽　　241
注釋　　242
助記符後綴　　242
各種各樣的操作數　　243
間接內存引用　　244
x86 指令集的概要　　245
13.3　傳輸指令　　246
mov 指令　　246
push 指令和pop 指令　　247
lea 指令　　248
movsx 指令和movzx 指令　　249
符號擴展和零擴展　　250
13.4　算術運算指令　　251
add 指令　　251
進位標誌　　252
sub 指令　　252
imul 指令　　252
idiv 指令和div 指令　　253
inc 指令　　254
dec 指令　　255
neg 指令　　255
13.5　位運算指令　　256
and 指令　　256
or 指令　　257
xor 指令　　257
not 指令　　257
sal 指令　　258
sar 指令　　258
shr 指令　　259
13.6　流程的控製　　260
jmp 指令　　260
條件跳轉指令（jz、jnz、je、jne、……）　　261
cmp 指令　　262
test 指令　　263
標誌位獲取指令（SETcc）　　263
call 指令　　264
ret 指令　　265
第14章　函數和變量　　266
14.1　程序調用約定　　267
什麼是程序調用約定　　267
Linux/x86 下的程序調用約定　　267
14.2　Linux/x86 下的函數調用　　269
到函數調用完成為止　　269
到函數開始執行為止　　270
到返迴原處理流程為止　　271
到清理操作完成為止　　271
函數調用總結　　272
14.3　Linux/x86 下函數調用的細節　　274
寄存器的保存和復原　　274
caller-save 寄存器和callee-save 寄存器　　274
caller-save 寄存器和callee-save 寄存器的靈活應用　　275
大數值和浮點數的返迴方法　　276
其他平颱的程序調用約定　　277
第15章　編譯錶達式和語句　　278
15.1　確認編譯結果　　279
利用cbc 進行確認的方法　　279
利用gcc 進行確認的方法　　280
15.2　x86 匯編的對象與DSL　　282
錶示匯編的類　　282
錶示匯編對象　　283
15.3　cbc 的x86 匯編DSL　　285
利用DSL 生成匯編對象　　285
錶示寄存器　　286
錶示立即數和內存引用　　287
錶示指令　　287
錶示匯編僞操作、標簽和注釋　　288
15.4　CodeGenerator 類的概要　　290
CodeGenerator 類的字段　　290
CodeGenerator 類的處理概述　　290
實現compileStmts 方法　　291
cbc 的編譯策略　　 292
15.5　編譯單純的錶達式　　294
編譯Int 節點　　294
編譯Str 節點　　294
編譯Uni 節點(1) 按位取反　　295
編譯Uni 節點(2) 邏輯非　　297
15.6　編譯二元運算　　298
編譯Bin 節點　　298
實現compileBinaryOp 方法　　299
實現除法和餘數　　300
實現比較運算　　300
15.7　引用變量和賦值　　301
編譯Var 節點　　301
編譯Addr 節點　　302
編譯Mem 節點　　 303
編譯Assign 節點　　303
15.8　編譯jump 語句　　305
編譯LabelStmt 節點　　305
編譯Jump 節點　　305
編譯CJump 節點　　305
編譯Call 節點　　306
編譯Return 節點　　307
第16章　分配棧幀　　308
16.1　操作棧　　309
cbc 中的棧幀　　309
棧指針操作原則　　310
函數體編譯順序　　310
16.2　參數和局部變量的內存分配　　312
本節概述　　312
參數的內存分配　　312
局部變量的內存分配：原則　　313
局部變量的內存分配　　314
處理作用域內的局部變量　　315
對齊的計算　　316
子作用域變量的內存分配　　316
16.3　利用虛擬棧分配臨時變量　　318
虛擬棧的作用　　318
虛擬棧的接口　　319
虛擬棧的結構　　319
virtualPush 方法的實現　　320
VirtualStack#extend 方法的實現　　320
VirtualStack#top 方法的實現　　321
virtualPop 方法的實現　　321
VirtualStack#rewind 方法的實現　　321
虛擬棧的運作　　322
16.4　調整棧訪問的偏移量　　323
本節概要　　323
StackFrameInfo 類　　323
計算正在使用的callee-save 寄存器　　324
計算臨時變量區域的大小　　325
調整局部變量的偏移量　　325
調整臨時變量的偏移量　　326
16.5　生成函數序言和尾聲　　327
本節概要　　327
生成函數序言　　327
生成函數尾聲　　328
16.6　alloca 函數的實現　　330
什麼是alloca 函數　　330
實現原則　　330
alloca 函數的影響　　331
alloca 函數的實現　　331
第17章　優化的方法 333
17.1　什麼是優化　　334
各種各樣的優化　　334
優化的案例　　334
常量摺疊　　334
代數簡化　　335
降低運算強度　　335
削除共同子錶達式　　335
消除無效語句　　336
函數內聯　　336
17.2　優化的分類　　337
基於方法的優化分類　　337
基於作用範圍的優化分類　　337
基於作用階段的優化分類　　338
17.3　cbc 中的優化　　339
cbc 中的優化原則　　339
cbc 中實現的優化　　339
cbc 中優化的實現　　339
17.4　更深層的優化　　341
基於模式匹配選擇指令　　341
分配寄存器　　342
控製流分析　　342
大規模的數據流分析和SSA 形式　　342
總結　　343
第4部分　鏈接和加載
第18章　生成目標文件 346
18.1　ELF 文件的結構　　347
ELF 的目的　　347
ELF 的節和段　　348
目標文件的主要ELF 節　　348
使用readelf 命令輸齣節頭　　349
使用readelf 命令輸齣程序頭　　350
使用readelf 命令輸齣符號錶　　351
readelf 命令的選項　　351
什麼是DWARF 格式　　352
18.2　全局變量及其在ELF 文件中的錶示　　354
分配給任意ELF 節　　354
分配給通用ELF 節　　354
分配.bss 節　　355
通用符號　　355
記錄全局變量對應的符號　　357
記錄符號的附加信息　　357
記錄通用符號的附加信息　　358
總結　　358
18.3　編譯全局變量　　360
generate 方法的實現　　360
generateAssemblyCode 方法的實現　　360
編譯全局變量　　361
編譯立即數　　362
編譯通用符號　　363
編譯字符串字麵量　　364
生成函數頭　　365
計算函數的代碼大小　　366
總結　　366
18.4　生成目標文件　　367
as 命令調用的概要　　367
引用GNUAssembler 類　　367
調用as 命令　　367
第19章　鏈接和庫　　369
19.1　鏈接的概要　　370
鏈接的執行示例　　370
gcc 和GNU ld　　371
鏈接器處理的文件　　372
常用庫　　374
鏈接器的輸入和輸齣　　374
19.2　什麼是鏈接　　375
鏈接時進行的處理　　375
閤並節　　375
重定位　　376
符號消解　　377
19.3　動態鏈接和靜態鏈接　　379
兩種鏈接方法　　379
動態鏈接的優點　　379
動態鏈接的缺點　　380
動態鏈接示例　　380
靜態鏈接示例　　381
庫的檢索規則　　381
19.4　生成庫　　383
生成靜態庫　　383
Linux 中共享庫的管理　　383
生成共享庫　　384
鏈接生成的共享庫　　385
第20章　加載程序　　387
20.1 加載ELF 段　　388
利用mmap 係統調用進行文件映射　　388
進程的內存鏡像　　389
內存空間的屬性　　390
ELF 段對應的內存空間　　390
和ELF 文件不對應的內存空間　　392
ELF 文件加載的實現　　393
20.2　動態鏈接過程　　395
動態鏈接加載器　　395
程序從啓動到終止的過程　　395
啓動ld.so　　396
係統內核傳遞的信息　　397
AUX 矢量　　397
讀入共享庫　　398
符號消解和重定位　　399
運行初始化代碼　　400
執行主程序　　401
執行終止處理　　402
ld.so 解析的環境變量　　402
20.3　動態加載　　404
所謂動態加載　　404
Linux 下的動態加載　　404
動態加載的架構　　405
20.4　GNU ld 的鏈接　　406
用於cbc 的ld 選項的結構　　406
C 運行時　　407
生成可執行文件　　408
生成共享庫　　408
第21章　生成地址無關代碼　　410
21.1　地址無關代碼　　411
什麼是地址無關代碼　　411
全局偏移錶（GOT）　　412
獲取GOT 地址　　412
使用GOT 地址訪問全局變量　　413
訪問使用GOT 地址的文件內部的全局變量　　414
過程鏈接錶（PLT）　　414
調用PLT 入口　　416
地址無關的可執行文件：PIE　　416
21.2　全局變量引用的實現　　418
獲取GOT 地址　　418
PICThunk 函數的實現　　418
刪除重復函數並設置不可見屬性　　419
加載GOT 地址　　420
locateSymbols 函數的實現　　421
全局變量的引用　　421
訪問全局變量：地址無關代碼的情況下　　 422
函數的符號　　423
字符串常量的引用　　424
21.3　鏈接器調用的實現　　425
生成可執行文件　　425
generateSharedLibrary 方法　　426
21.4　從程序解析到執行　　428
build 和加載的過程　　428
詞法分析　　429
語法分析　　429
生成中間代碼　　430
生成代碼　　431
匯編　　432
生成共享庫　　432
生成可執行文件　　433
加載　　433
第22章　擴展閱讀　　434
22.1 參考書推薦　　435
編譯器相關　　435
語法分析相關　　435
匯編語言相關　　436
22.2 鏈接、加載相關　　437
22.3 各種編程語言的功能　　438
異常封裝相關的圖書　　438
垃圾迴收　　438
垃圾迴收相關的圖書　　439
麵嚮對象編程語言的實現　　439
函數式語言　　440
附　　錄　　441
A.1 參考文獻　　442
A.2 在綫資料　　444
A.3 源代碼　　445
· · · · · · (收起)