目 录
第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.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
token28
抽象语法树和节点29
3.2 解析器生成器30
什么是解析器生成器30
解析器生成器的种类30
解析器生成器的选择31
3.3 JavaCC 的概要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.1 JavaCC 的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.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 系列CPU220
32 位CPU220
指令集221
IA-32 的变迁222
IA-32 的64 位扩展——AMD64222
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 汇编的对象与DSL282
表示汇编的类282
表示汇编对象283
15.3 cbc 的x86 汇编DSL285
利用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 ld371
链接器处理的文件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.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
地址无关的可执行文件：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
评价“自制编译器”