从零开始编写 C 编译器 Chapter 1.0 | Introduction
Note: 所有代码、定义、术语命名都参考 Nora Sandler 的书籍 Write a C Compiler
老生常谈，CPU 只能识别 ISA 规定的机器码，不能识别高级语言。所以有了编译器：将高级语言翻译为机器码(特定的二进制序列)。然而，这套工作是通过一系列编译套件(或语言工具链, Language Toolchins)来实现的。
一般来说，将高级语言翻译为机器码需要经过这几个步骤： 1.
预处理(Preprocess): 将源代码中以 # 开头的指令展开，例如
#include、#define
等语句。一般预处理只是简单的字符串替换。 2. 编译(Compile):
将预处理过的源代码转换为汇编语言(汇编是一系列对机器码的助记符)。 3.
汇编(Assemble): 将汇编语言转换为可重定位的目标文件。 4. 链接(Linker):
将一系列目标文件按照特定的规则装载为一个目标文件，并规定加载到内存的位置。
本系列文章都将聚焦 编译(Compiler) 这个过程。
Hello Assembly
考虑一个最简单的 \(C\) 程序, 命名为
return_2.c ：
1 | |
该程序近包含一个函数，一条语句。可以通过 gcc
命令生成汇编: 1
gcc -S -O -fno-asynchronous-unwind-tables -fcf-protection=none return_2.c
选项 -S
指明只需要进行到编译阶段，需要后续的汇编及链接。选项 -O
表明启用编译器优化。选项 -fno-asynchronous-unwind-tables
表明禁用调试所需要的 unwind
表，这能大大化简我们生成的汇编文件。选项
-fcf-protection=none 表明禁用控制流保护，减少无关指令。
在 return_2.s 中可以大致看到如下几条语句：
1
2
3
4 .globl main
main:
movl $2, %eax
ret
.globl main: 汇编器指令(assembler directive), 表明main为全局符号，所有一同编译的.s文件都应识别到main的符号，供后续连接器使用。main:: 标签(label), 定义main:之后第一条语句所存储的地址(即movl指令的地址)。movl $2, %eax: 将立即数 \(2\) 移入 \(32\) 位寄存器%eax。l后缀表明操作数类型为long word，即 \(32\) 位类型。根据 x86_64 调用规定，函数返回值通过%eax或%rax寄存器传递。ret: 返回到执行main之前的指令。由于main为 C 程序的入口，实际返回到 C 运行时库(用于初始化或结束一个 C 进程)。
通过下列指令链接并运行： 1
2
3
4gcc return_2.s -o return_2
./return_2
echo $?
2
在 shell 中, $? 用于获取上一进程的退出状态码。可以看到
shell 中应该输出了一个 \(2\)。通过上述的汇编我们可以知道，程序只是简单的把
\(2\) 放到了 %eax
寄存器中，为什么能得到退出码呢？
在高级语言的概念中，main
是程序执行的第一条语句，但是在操作系统和编译器的视角里，第一条指令是
C运行时环境 (C Runtime 0, aka cr0) 中的启动部分。
通过 objdump -d return_2
查看机器码，可以看到类似如下的输出: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
260000000000001000 <_init>:
1000: f3 0f 1e fa endbr64
1004: 48 83 ec 08 sub $0x8,%rsp
1008: 48 8b 05 c1 2f 00 00 mov 0x2fc1(%rip),%rax # 3fd0 <__gmon_start__@Base>
100f: 48 85 c0 test %rax,%rax
1012: 74 02 je 1016 <_init+0x16>
1014: ff d0 call *%rax
1016: 48 83 c4 08 add $0x8,%rsp
101a: c3 ret
Disassembly of section .text:
0000000000001020 <_start>:
# ... 省略一点东西
0000000000001119 <main>:
1119: b8 02 00 00 00 mov $0x2,%eax
111e: c3 ret
Disassembly of section .fini:
0000000000001120 <_fini>:
1120: f3 0f 1e fa endbr64
1124: 48 83 ec 08 sub $0x8,%rsp
1128: 48 83 c4 08 add $0x8,%rsp
112c: c3 ret
可以看到，虽然 C 程序只定义了 main,
但是还有很多其他的部分被集成在了 return_2
中。cr0 在 C
程序启动前初始化最基础的运行环境，初始化堆栈、调用 main
程序，并在程序运行结束后 调用 exit 将程序结束状态(即
main 函数的返回值)传递给操作系统。由于 cr0
是其他的汇编文件，因此 main 必须是全局符号，否则
cr0 无法正确调用。
为了能存储所有文件中的符号，还需要维护一张 符号表,
用于指明符号名、是否全局、所在段、偏移量等。在 Linux 系统上可以通过
readelf -a return_2 查看可执行文件的符号表。
1 | |
同时可以注意到，程序还将数据分成了不同的段进行维护:
.text: 存放用户编写的机器指令(main 位于此段，且偏移量为 \(0\))。.data: 存放已初始化的全局变量.bss: 存放未初始化的全局变量。上述两个段通常也被叫作 堆区。.rodata: 存放只读数据，const修饰的变量，字面量等都存放在这个区域。.stack: 存放局部变量和临时变量，同时用于存储函数调用时需要的函数栈帧。也被叫作 栈区。
在不同的目标文件中(例如 return_2.o 和标准库
glibc.so)，各自符号的地址都是从 \(0\)
开始，链接器需要将它们的相对地址替换为合适的绝对地址，并把符号表合并为一张总表，这个过程称为
重定位。
Compiler Driver
正如前面所说，将源代码转换为机器码包括 \(4\) 个阶段。其中的编译阶段还包括几个过程：
- Lex: 词法分析器(Lexer)将源文件中的空格、制表符等无关东西删除，并将源文件中的词元(Token，由于这东西实在无法在中文中找到意思相近的词，后面都将使用单词 token)分类为关键字、常量、标识符等，最终生成一个 tokens 列表。
- Parse: 解析器(Parser)将得到的 tokens list 转换为一棵 抽象语法树(Abstract Syntax Tree, AST)，该树以一种易于遍历和分析的形式表示源程序。上述两过程一般称为 编译器的前端。
- Code generate: 通过分析 AST ，生成对应的汇编代码。在某些复杂的语言中，还会有一个阶段生成中间表示(Inner Represent)代码，是一种脱离于 ISA 结构的类汇编代码。在 IR 的基础上进行代码优化、安全分析等过程，最后再根据 IR 生成对应目标平台的汇编代码。 这一过程也称为 编译器的后端。
真正的编译器应该自动完成上述的几个阶段,
而不需用户手动调用一个又一个的工具。执行这个功能的组建就是 Compiler
Driver。Compiler Driver
是负责协调和调用编译工具链中各个组件的程序。它本身不执行实际的编译工作（如词法分析、语法分析、代码生成等），而是作为一个“调度器”或“胶水层”，按正确顺序调用预处理器、编译器、汇编器和链接器，并自动将常用的编译选项传递给各工具。上述调用的
gcc 或 clang 实际都是 Compiler
Driver，实际的编译器、汇编器、连接器分别叫作
cc、as、ld。
编写编译器的第一步，是编写 Compiler
Driver。为了方便后续的单元测试和调试，我们的 Compiler Driver
需要满足这几个功能: 1. 调用
gcc -E -P INPUT_FILE -o PREPROCESSED_FILE 生成预处理文件。
2. 对于自己实现的编译器，需要支持
--lex、--parse、--codegen这3个参数，使得能在这几个阶段停下，而不进行后续的操作。
3. 调用 gcc ASSEMBLY_FILE -o OUTPUT_FILE
生成最终可执行文件。 4. 可选但推荐: 支持 --debug
选项，保留生成的预处理文件、汇编文件。
最终的 Driver 应该这样工作： 1
2
3
4
5
6
7
8# 用户输入
./main.exe hello.c
# 驱动内部执行
1. gcc -E -P hello.c -o hello.i
2. ./compiler hello.i -o hello.s # 可选 --lex --parse --codegen
3. gcc hello.s -o hello
4. rm hello.i hello.s
首先定义 setting 模块维护 目标平台 和
编译选项。 1
2
3
4type stage = Lex | Parse | Codegen | Assembly | Executable
type target = OS_X | Linux
let platform = ref Linux (* default to Linux *)
对于编译 --lex 等参数的实现，可以采用十分不优雅的
if 塔来实现: 1
2
3
4
5
6
7
8
9
10
11
12
13
14let compile stage src_file =
let source = In_channel.with_open_text src_file In_channel.input_all in
(* Lex it *)
let tokens = Lexer.lexer source in
if stage = Settings.Lex then ()
else
let ast = Parser.parser tokens in
if stage = Settings.Parse then ()
else
let asm_ast = Codegen.codegen ast in
if stage = Settings.Codegen then ()
else
let asm_filename = Filename.chop_extension src_file ^ ".s" in
Emit.emit asm_filename asm_ast
对于调用 gcc 生成执行文件，通过 Sys 包或者用
python、bash 等脚本语言简单写一个就行:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21let run_command cmd args =
if Sys.command (Filename.quote_command cmd args) <> 0 then
failwith ("Command failed: " ^ cmd)
let preprocess src =
let _ = validate_extension src in
let output = replace_extension src ".i" in
let _ = run_command "gcc" ["-E"; "-P"; src; "-o"; output ] in
output
let compile stage preprocess_src =
let _ = Compile.compile stage preprocess_src in
run_command "rm" [ preprocess_src ];
replace_extension preprocess_src ".s"
let assemble_and_link ?(cleanup = true) src =
let assembly_file = replace_extension src ".s" in
let output_file = Filename.chop_extension src in
let _ = run_command "gcc" [ assembly_file; "-o"; output_file ] in
(* cleanup .s files *)
if cleanup then run_command "rm" [ assembly_file ]
对于 解析命令行参数 可以通过 Cmdliner
包来读入用户数据。最后我们只需要一个 driver
函数作为入口即可：
1 | |