自製編譯器 自制编译器

青木峰郎（作者）
程序員，著有《Ruby程序設計268技（第2版）》《Ruby源代碼完全解說》《Linux程序設計》等多部編程相關著作，並積極參與標準庫維護、文檔維護等各種各樣的活動。

嚴聖逸（譯者）
畢業於上海交通大學。8年軟件開發經驗，期間赴日本工作。現就職於想能信息科技（上海）有限公司，從事基於雲平台的客戶關系管理及各類營銷自動化系統的開發工作。譯有《高效團隊開發：工具與方法》。

絕雲（譯者）
畢業於清華大學軟件學院。曾在日本創意公司KAYAC從事即時通信軟件及社交遊戲的開發工作，現任螞蟻金服前端架構專家。譯有《寫給大家看的算法書》等圖書，曾參與《像外行一樣思考，像專家一樣實踐（修訂版）》的審校。

第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