自制编译器 PDF 高质量版

编辑推荐

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

1.实战    通过实际动手制作一个精简版C语言编译器，让读者深入了解C语言程序编译、运行背后的细节。

2.全面    不仅限于编译器，对以编译器为中心的编程语言的运行环境，即编译器、汇编器、链接器、硬件以及运行时环境等，均有所涉及。

3.杰出    日本知名技术书作家青木峰郎耗时3年精心打造，通过具体的例子讲解概念，通俗易懂，更适合入门。

内容简介

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

目录

• 第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
• 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.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 和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.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