自制编译器pdf

贯穿编译、汇编、链接、加载的全过程！

比“龙书”更具实践性！

1.实战

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

2.全面

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

3.杰出

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

自制编译器 内容简介

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

自制编译器 目录

第1章 开始制作编译器

1.1 本书的概要

本书的主题

本书制作的编译器

编译示例

可执行文件

编译

程序运行环境

1.2 编译过程

编译的4个阶段

语法分析

语义分析

生成中间代码

代码生成

优化

总结

1.3 使用Cb编译器进行编译

Cb编译器的必要环境

安装Cb编译器

Cb的Hello， World！

第2章 cb和cbc

2.1 Cb语言的概要

Cb的Hello，World！

Cb中删减的功能

import关键字

导入文件的规范

2.2 Cb编译器cbc的构成

cbc的代码树

cbc的包

compiler包中的类群

main函数的实现

commandMain函数的实现

Java5泛型

build函数的实现

Java 5的foreach语句

compile函数的实现

第1部分 代码分析

第3章 语法分析的概要

3.1 语法分析的方法

代码分析中的问题点

代码分析的一般规律

词法分析、语法分析、语义分析

扫描器的动作

单词的种类和语义值

token

抽象语法树和节点

3.2 解析器生成器

什么是解析器生成器

解析器生成器的种类

解析器生成器的选择

3.3 JavaCC的概要

什么是JavaCC

语法描述文件

语法描述文件的例子

运行JavaCC

启动JavaCC所生成的解析器

中文的处理

第4章 词法分析

4.1 基于JavaCC的扫描器的描述

本章的目的

JavaCC的正则表达式

固定字符串

连接

字符组

排除型字符组

重复1次或多次

重复0次或多次

重复n次到m次

正好重复n次

可以省略

选择

4.2 扫描没有结构的单词

TOKEN命令

扫描标识符和保留字

选择匹配规则

扫描数值

4.3 扫描不生成token的单词

SKIP命令和SPECIAL_OKEN命令

跳过空白符

跳过行注释

4.4 扫描具有结构的单词

最长匹配原则和它的问题

基于状态迁移的扫描

MORE命令

跳过块注释

扫描字符串字面量

扫描字符字面量

第5章 基于JavaCC的解析器的描述

5.1 基于EBNF语法的描述

本章的目的

基于JavaCC的语法描述

终端符和非终端符

JavaCC的EBNF表示法

连接

重复0次或多次

重复1次或多次

选择

可以省略

5.2 语法的二义性和token的超前扫描

语法的二义性

JavaCC的局限性

提取左侧共通部分

token的超前扫描

可以省略的规则和冲突

重复和冲突

更灵活的超前扫描

超前扫描的相关注意事项

第6章 语法分析

6.1 定义的分析

表示程序整体的符号

语法的单位

import声明的语法

各类定义的语法

变量定义的语法

函数定义的语法

结构体定义和联合体定义的语法

结构体成员和联合体成员的语法

typedef语句的语法

类型的语法

C语言和Cb在变量定义上的区别

基本类型的语法

6.2 语句的分析

语句的语法

if语句的语法

省略if语句和大括号

while语句的语法

for语句的语法

各类跳转语句的语法

6.3 表达式的分析

表达式的整体结构

expr的规则

条件表达式

二元运算符

6.4 项的分析

项的规则

前置运算符的规则

后置运算符的规则

字面量的规则

第2部分 抽象语法树和中间代码

第7章 JavaCC的action和抽象语法树

7.1 JavaCC的action

本章的目的

简单的action

执行action的时间点

返回语义值的action

获取终端符号的语义值

Token类的属性

获取非终端符号的语义值

语法树的结构

选择和action

重复和action

本节总结

7.2 抽象语法树和节点

Node类群

Node类的定义

抽象语法树的表示

基于节点表示表达式的例子

第8章 抽象语法树的生成

8.1 表达式的抽象语法树

字面量的抽象语法树

类型的表示

为什么需要TypeRef类

一元运算的抽象语法树

二元运算的抽象语法树

条件表达式的抽象语法树

赋值表达式的抽象语法树

8.2 语句的抽象语法树

if语句的抽象语法树

while语句的抽象语法树

程序块的抽象语法树

8.3 声明的抽象语法树

变量声明列表的抽象语法树

函数定义的抽象语法树

表示声明列表的抽象语法树

表示程序整体的抽象语法树

外部符号的import

总结

8.4 cbc的解析器的启动

Parser对象的生成

文件的解析

解析器的启动

第9章 语义分析（1）引用的消解

9.1 语义分析的概要

本章目的

抽象语法树的遍历

不使用Visitor模式的抽象语法树的处理

基于Visitor模式的抽象语法树的处理

Vistor模式的一般化

cbc中Visitor模式的实现

语义分析相关的cbc的类

9.2 变量引用的消解

问题概要

实现的概要

Scope树的结构

LocaIResolver类的属性

LocaIResolver类的启动

变量定义的添加

函数定义的处理

pushScope方法

currentScope方法

popScope方法

添加临时作用域

建立VariableNode和变量定义的关联

从作用域树取得变量定义

9.3 类型名称的消解

问题概要

实现的概要

孙peResolver类的属性

TypeResolver类的启动

类型的声明

类型和抽象语法树的遍历

变量定义的类型消解

函数定义的类型消解

第10章 语义分析（2）静态类型检查

10.1 类型定义的检查

问题概要

实现的概要

检测有向图中的闭环的算法

结构体、联合体的循环定义检查

10.2 表达式的有效性检查

问题概要

实现的概要

DereferenceChecker类的启动

SemanticError异常的捕获

非指针类型取值操作的检查

获取非左值表达式地址的检查

隐式的指针生成

10.3 静态类型检查

问题概要

实现的概要

Cb中操作数的类型

隐式类型转换

TyperChecker类的启动

二元运算符的类型检查

隐式类型转换的实现

第11章 中间代码的转换

11.1 cbc的中间代码

组成中间代码的类

中间代码节点类的属性

中间代码的运算符和类型

各类中间代码

中间代码的意义

11.2 IRGenerator类的概要

抽象语法树的遍历和返回值

IRGenerator类的启动

函数本体的转换

作为语句的表达式的判别

11.3 流程控制语句的转换

if语句的转换（1）概要

if语句的转换（2）没有else部分的情况

if语句的转换（3）存在else部分的情况

while语句的转换

break语句的转换（1）问题的定义

break语句的转换（2）实现的方针

break语句的转换（3）实现

11.4 没有副作用的表达式的转换

UnaryOpNode对象的转换

BinaryOpNode对象的转换

指针加减运算的转换

11.5 左值的转换

左边和右边

左值和右值

cbc中左值的表现

结构体成员的偏移

成员引用（expr.memb）的转换

左值转换的例外：数组和函数

成员引用的表达式（ptr-＞memb）的转换

11.6 存在副作用的表达式的转换

表达式的副作用

有副作用的表达式的转换方针

简单赋值表达式的转换（1）语句

临时变量的引入

简单赋值表达式的转换（2）表达式

后置自增的转换

第3部分 汇编代码

第12章 x86架构的概要

12.1 计算机的系统结构

CPU和存储器

寄存器

地址

物理地址和虚拟地址

各类设备

缓存

12.2 x86系列CPU的历史

x86系列CPU

32位CPU

指令集

IA-32的变迁

IA-32的64位扩展——AMD64

12.3 IA-32的概要

IA-32的寄存器

通用寄存器

机器栈

机器栈的操作

机器栈的用途

栈帧

指令指针

标志寄存器

12.4 数据的表现形式和格式

无符号整数的表现形式

有符号整数的表现形式

负整数的表现形式和二进制补码

字节序

对齐

结构体的表现形式

第13章 x86汇编器编程

13.1 基于GNU汇编器的编程

GNU汇编器

汇编语言的Hello，World！

基于GNU汇编器的汇编代码

13.2 GNU汇编器的语法

汇编版的Hello，World！

指令

汇编伪操作

标签

注释

助记符后缀

各种各样的操作数

间接内存引用

x86指令集的概要

13.3 传输指令

mov指令

push指令和POP指令

lea指令

movsx指令和movzx指令

符号扩展和零扩展

13.4 算术运算指令

add指令

进位标志

sub指令

imul指令

idiv指令和div指令

inc指令

dec指令

neg指令

13.5 位运算指令

and指令

or指令

xor指令

not指令

sal指令

sar指令

shr指令

13.6 流程的控制

jmp指令

条件跳转指令（jz、jnz、je、jne、⋯⋯）

cmp指令

test指令

标志位获取指令（SETcc）

call指令

ret指令

第14章 函数和变量

14.1 程序调用约定

什么是程序调用约定

Linux/x86下的程序调用约定

14.2 Linux/x86下的函数调用

到函数调用完成为止

到函数开始执行为止

到返回原处理流程为止

到清理操作完成为止

函数调用总结

14.3 Linux/x86下函数调用的细节

寄存器的保存和复原

caller-save寄存器和callee-save寄存器

caller-save寄存器和callee-save寄存器的灵活应用

大数值和浮点数的返回方法

其他平台的程序调用约定

第15章 编译表达式和语句

15.1 确认编译结果

利用cbc进行确认的方法

利用gcc进行确认的方法

15.2 x86汇编的对象与DSL

表示汇编的类

表示汇编对象

15.3 cbc的x86汇编DSL

利用DSL生成汇编对象

表示寄存器

表示立即数和内存引用

表示指令

表示汇编伪操作、标签和注释

15.4 CodeGenerator类的概要

CodeGenerator类的字段

CodeGenerator类的处理概述

实现compileStmts方法

cbc的编译策略

15.5 编译单纯的表达式

编译Int节点

编译Str节点

编译Uni节点（1）按位取反

编译Uni节点（2）逻辑非

15.6 编译二元运算

编译Bin节点

实现compileBinaryOp方法

实现除法和余数

实现比较运算

15.7 引用变量和赋值

编译Var节点

编译Addr节点

编译Mem节点

编译Assign节点

15.8 编译jump语句

编译LabelStmt节点

编译Jump节点

编译CJump节点

编译Call节点

编译Return节点

第16章 分配栈帧

16.1 操作栈

cbc中的栈帧

栈指针操作原则

函数体编译顺序

16.2 参数和局部变量的内存分配

本节概述

参数的内存分配

局部变量的内存分配：原则

局部变量的内存分配

处理作用域内的局部变量

对齐的计算

子作用域变量的内存分配

16.3 利用虚拟栈分配临时变量

虚拟栈的作用

虚拟栈的接口

虚拟栈的结构

virtualPush方法的实现

VirtualStack#extend方法的实现

VirtualStack#top方法的实现

virtualPop方法的实现

VirtualStack#rewind方法的实现

虚拟栈的运作

16.4 调整栈访问的偏移量

本节概要

StackFramelnfo类

计算正在使用的callee-save寄存器

计算临时变量区域的大小

调整局部变量的偏移量

调整临时变量的偏移量

16.5 生成函数序言和尾声

本节概要

生成函数序言

生成函数尾声

16.6 alloca函数的实现

什么是alloca函数

实现原则

alloca函数的影响

alloca函数的实现

第17章 优化的方法

17.1 什么是优化

各种各样的优化

优化的案例

常量折叠

代数简化

降低运算强度

削除共同子表达式

消除无效语句

函数内联

17.2 优化的分类

基于方法的优化分类

基于作用范围的优化分类

基于作用阶段的优化分类

17.3 cbc中的优化

cbc中的优化原则

cbc中实现的优化

cbc中优化的实现

17.4 更深层的优化

基于模式匹配选择指令

分配寄存器

控制流分析

大规模的数据流分析和SSA形式

总结

第4部分 链接和加载

第18章 生成目标文件

18.1 ELF文件的结构

ELF的目的

ELF的节和段

目标文件的主要ELF节

使用readelf命令输出节头

使用readelf命令输出程序头

使用readelf命令输出符号表

readelf命令的选项

什么是DWARF格式

18.2 全局变量及其在ELF文件中的表示

分配给任意ELF节

分配给通用ELF节

分配.bss节

通用符号

记录全局变量对应的符号

记录符号的附加信息

记录通用符号的附加信息

总结

18.3 编译全局变量

generate方法的实现

generateAssemblyCode方法的实现

编译全局变量

编译立即数

编译通用符号

编译字符串字面量

生成函数头

计算函数的代码大小

总结

18.4 生成目标文件

as命令调用的概要

引用GNUAssembler类

调用as命令

第19章 链接和库

19.1 链接的概要

链接的执行示例

gcc和GNU Id

链接器处理的文件

常用库

链接器的输入和输出

19.2 什么是链接

链接时进行的处理

合并节

重定位

符号消解

19.3 动态链接和静态链接

两种链接方法

动态链接的优点

动态链接的缺点

动态链接示例

静态链接示例

库的检索规则

19.4 生成库

生成静态库

Linux中共享库的管理

生成共享库

链接生成的共享库

第20章 加载程序

20.1 加载ELF段

利用mmap系统调用进行文件映射

进程的内存镜像

内存空间的属性

ELF段对应的内存空间

和ELF文件不对应的内存空间

ELF文件加载的实现

20.2 动态链接过程

动态链接加载器

程序从启动到终止的过程

启动Id.so

系统内核传递的信息

AUX矢量

读入共享库

符号消解和重定位

运行初始化代码

执行主程序

执行终止处理

Id.so解析的环境变量

20.3 动态加载

所谓动态加载

Linux下的动态加载

动态加载的架构

20.4 GNU Id的链接

用于cbc的Id选项的结构

C运行时

生成可执行文件

生成共享库

第21章 生成地址无关代码

21.1 地址无关代码

什么是地址无关代码

全局偏移表（GOT）

获取GOT地址

使用GOT地址访问全局变量

访问使用GOT地址的文件内部的全局变量

过程链接表（PLT）

调用PLT入口

地址无关的可执行文件：PIE

21.2 全局变量引用的实现

获取GOT地址

PICThunk函数的实现

删除重复函数并设置不可见属性

加载GOT地址

IocateSymbols函数的实现

全局变量的引用

访问全局变量：地址无关代码的情况下

函数的符号

字符串常量的引用

21.3 链接器调用的实现

生成可执行文件

generateShared Library方法

21.4 从程序解析到执行

build和加载的过程

词法分析

语法分析

生成中间代码

生成代码

汇编

生成共享库

生成可执行文件

加载

第22章 扩展阅读

22.1 参考书推荐

编译器相关

语法分析相关

汇编语言相关

22.2 链接、加载相关

22.3 各种编程语言的功能

异常封装相关的图书

垃圾回收

垃圾回收相关的图书

面向对象编程语言的实现

函数式语言

附录

A.1 参考文献

A.2 在线资料

A.3 源代码

自制编译器 精彩文摘

预处理

C 语言的代码首先由预处理器（preprocessor）对 #include 和 #define 进行处理。具体来说，读入头文件，将所有的宏展开，这就是预处理（preprocess）。预处理的英文是 preprocess，就是前处理的意思。这里的“前”是在什么之前呢？当然是编译之前了。

预处理的内容近似于 sed 命令和 awk 命令这样的纯文本操作，不考虑 C 语言语法的含义。

狭义的编译

接着，编译器对预处理器的输出进行编译，生成汇编语言（assemble language）的代码。一般来说，汇编语言的代码的文件扩展名是“.s”。

汇编语言是由机器语言转换过来的人类较易阅读的文本形式的语言。机器语言是以 CPU 的执行效率为第一要素设计的，用二进制代码表示，每一个 bit 都有自己的含义，人类很难理解。因此，一般要使用与机器语言直接对应的汇编语言，以方便人们理解。