自制编译器

贯穿编译、汇编、链接、加载的全过程！
比“龙书”更具实践性！

1.实战
通过实际动手制作一个精简版C语言编译器，让读者深入了解C语言程序编译、运行背后的细节。
2.全面
不仅限于编译器，对以编译器为中心的编程语言的运行环境，即编译器、汇编器、链接器、硬件以及运行时环境等，均有所涉及。
3.杰出
日本知名技术书作家青木峰郎耗时3年精心打造，通过具体的例子讲解概念，通俗易懂，更适合入门。

本书将带领读者从头开始制作一门语言的编译器。笔者特意为本书设计了C?语言，C?可以说是C语言的子集，实现了包括指针运算等在内的C语言的主要部分。本书所实现的编译器就是C?语言的编译器， 是实实在在的编译器，而非有诸多限制的玩具。另外，除编译器之外，本书对以编译器为中心的编程语言的运行环境，即编译器、汇编器、链接器、硬件、运行时环境等都有所提及，介绍了程序运行的所有环节。

青木峰郎（作者）
程序员，著有《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?和cbc13
2．1C?语言的概要14
C?的Hello，World！14
C?中删减的功能14
import关键字15
导入文件的规范16
2．2C?编译器cbc的构成17
cbc的代码树17
cbc的包18
compiler包中的类群18
main函数的实现19
commandMain函数的实现19
Java5泛型20
build函数的实现20
Java5的foreach语句21
compile函数的实现21
第1部分代码分析
第3章
语法分析的概要24
3．1语法分析的方法25
代码分析中的问题点25
代码分析的一般规律25
词法分析、语法分析、语义分析25
扫描器的动作26
单词的种类和语义值27
token28
抽象语法树和节点29
3．2解析器生成器30
什么是解析器生成器30
解析器生成器的种类30
解析器生成器的选择31
3．3JavaCC的概要33
什么是JavaCC33
语法描述文件33
语法描述文件的例子34
运行JavaCC35
启动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．1JavaCC的action93
本章的目的93
简单的action93
执行action的时间点93
返回语义值的action95
获取终端符号的语义值95
Token类的属性96
获取非终端符号的语义值98
语法树的结构99
选择和action99
重复和action100
本节总结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
外部符号的import128
总结129
8．4cbc 的解析器的启动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．1cbc的中间代码179
组成中间代码的类180
中间代码节点类的属性181
中间代码的运算符和类型182
各类中间代码183
中间代码的意义184
11．2IRGenerator类的概要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．2x86系列CPU的历史220
x86系列CPU220
32位CPU220
指令集221
IA-32的变迁222
IA-32的64位扩展——AMD64222
12．3IA-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．2GNU汇编器的语法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．2Linux/x86下的函数调用269
到函数调用完成为止269
到函数开始执行为止270
到返回原处理流程为止271
到清理操作完成为止271
函数调用总结272
14．3Linux/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．2x86汇编的对象与DSL282
表示汇编的类282
表示汇编对象283
15．3cbc的x86汇编DSL285
利用DSL生成汇编对象285
表示寄存器286
表示立即数和内存引用287
表示指令287
表示汇编伪操作、标签和注释288
15．4CodeGenerator类的概要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．6alloca函数的实现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．3cbc中的优化339
cbc中的优化原则339
cbc中实现的优化339
cbc中优化的实现339
17．4更深层的优化341
基于模式匹配选择指令341
分配寄存器342
控制流分析342
大规模的数据流分析和SSA形式342
总结343
第4部分链接和加载
第18章
生成目标文件346
18．1ELF文件的结构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和GNUld371
链接器处理的文件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．so396
系统内核传递的信息397
AUX矢量397
读入共享库398
符号消解和重定位399
运行初始化代码400
执行主程序401
执行终止处理402
ld．so解析的环境变量402
20．3动态加载404
所谓动态加载404
Linux下的动态加载404
动态加载的架构405
20．4GNU 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
地址无关的可执行文件：PIE416
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