1 Overview
编译器在做什么
编译器的输入是字符序列,输出是指令序列。它做的全部事情可以概括为一句话:
逐步把"无结构的文本"转换成"有结构的中间表示",每转换一次就丢弃一点源语言的表层信息、补充一点机器需要的信息,直到足够生成指令。
这个过程天然分层,因为每一层能判定的事情是不同的:
| 层次 | 能判定 | 判不了 |
|---|---|---|
| 词法 | 这是标识符还是关键字 | 括号配不配 |
| 语法 | 括号配不配、结构对不对 | 变量有没有声明 |
| 语义 | 类型对不对、变量声明了吗 | 这段循环能不能优化 |
| IR/优化 | 数据依赖、控制流 | 寄存器够不够 |
"括号配不配"词法判不了,是因为计数需要无限状态的记忆(多少个 ( 就要多少个 )),有限状态机做不到。a + b 里的 + 是二元还是一元,语法判不了,得靠类型信息——这就是语义层的活。
各阶段详解
词法分析(Lexical Analysis / Scanning)
输入字符流,输出 Token 流。
i = a + b * 2;
│
▼
[ID:i] [ASSIGN:=] [ID:a] [PLUS:+] [ID:b] [STAR:*] [NUM:2] [SEMI:;]要做的事:
- 切分:按最长匹配原则把字符切成单词
- 归类:给每个单词打上类别标签(标识符 / 关键字 / 常量 / 运算符 / 界符)
- 丢弃:空白、换行、注释在这里就被扔掉了,后面的阶段看不到它们
关键字的处理有两种做法:
- 保留字表:先当标识符扫出来,再查表判断是不是关键字(简单,C 的做法)
- 直接写进词法规则:关键字作为独立的正则(干净,但会让自动机变大)
语法分析(Syntax Analysis / Parsing)
输入 Token 流,输出语法树。
=
/ \
i +
/ \
a *
/ \
b 2语法分析器依据**文法(Grammar)**工作。文法是一组产生式,描述"什么样的 Token 序列是合法的"。
关键点:语法分析不只判对错,还要产出结构。判对错是副产品,产出树才是目的——后续所有阶段都在这棵树上操作。
具体语法树(CST / Parse Tree) 忠实反映文法,包含 ( )、分号等所有细节。抽象语法树(AST) 只保留有语义的节点。实际编译器都是直接从 parser 构造 AST。
语义分析(Semantic Analysis)
在 AST 上做的、文法表达不了的检查:
- 符号表(Symbol Table):把标识符映射到它的声明(类型、作用域、存储类别)
- 类型检查:
int + string是否合法,函数调用实参形参是否匹配 - 作用域解析:
x指的是哪个x - 唯一性检查:重复定义、未声明使用
这一步的输出常被称为 装饰过的 AST(Decorated AST)——树上每个节点都挂上了类型等属性。
为什么这些不能放进文法?因为要用文法表达"变量必须先声明后使用",需要把上下文无关文法升级成上下文有关文法,那会让语法分析变得不可判定或指数级复杂。把能推迟的检查尽量推迟到语义层,是编译器的基本设计取舍。
中间代码生成
把树形结构线性化成 IR。典型形式是三地址码(Three-Address Code, TAC):
t1 = b * 2
t2 = a + t1
i = t2IR 的作用:
- 解耦前后端:M 种语言 × N 种目标机,有 IR 只需 M+N 个模块,没有 IR 需要 M×N 个
- 便于优化:线性/图状结构比树更适合做数据流分析
- 便于复用:一套优化 Pass 服务所有语言
优化
在 IR 上做语义保持变换(semantics-preserving transformation)——程序的可观测行为不变,但更快/更小。
常见机器无关优化:
- 常量传播 / 常量折叠
- 公共子表达式消除(CSE)
- 死代码消除(DCE)
- 函数内联
- 循环不变量外提、循环展开
- 强度削弱(
x*2→x<<1)
目标代码生成
- 指令选择:IR 的一个操作对应目标机哪条/哪几条指令
- 寄存器分配:无限多的虚拟寄存器 → 有限的物理寄存器,放不下的**溢出(spill)**到内存。经典算法是图着色(Chaitin/Briggs)
- 指令调度:重排指令填满流水线、避开冒险
一遍(Pass)与多遍
- 单遍编译器:读一遍源码直接产出目标码。省内存、快,但能做的优化极少,且要求"使用前必须先声明"(因为没机会回头看)。早期 Pascal、C 的一些实现如此。
- 多遍编译器:每个阶段独立扫一遍。现代编译器全是多遍,因为优化需要在 IR 上反复迭代。
编译 vs 解释:一张对照表
| 维度 | 编译 | 解释 |
|---|---|---|
| 翻译时机 | 执行前一次性 | 执行时逐条 |
| 启动速度 | 慢(要先编译) | 快 |
| 运行速度 | 快 | 慢 |
| 错误发现 | 编译期 | 运行到才暴露 |
| 平台依赖 | 产出依赖目标机 | 依赖解释器 |
| 动态特性 | 难支持 | 天然支持 |
现实里两者几乎总是混合的:Java/C#/Lua/Python 都是"编译到字节码 + 虚拟机执行",再加 JIT(即时编译) 把热点字节码在运行期编译成机器码。JIT 的杀手锏是能用运行期才有的信息做优化——比如观测到某个分支 99% 走同一侧,就按这个假设生成代码并加一个去优化(deoptimization)的逃生舱。
错误处理的四个层次
| 层次 | 典型错误 | 常见恢复策略 |
|---|---|---|
| 词法 | 非法字符、字符串没闭合 | 跳过该字符,继续切分 |
| 语法 | 缺分号、括号不匹配 | 恐慌模式、短语层恢复、错误产生式 |
| 语义 | 类型不匹配、未声明 | 报错并继续(尽量多报) |
| 逻辑 | 死循环、数组越界 | 编译器管不了 |
恐慌模式(Panic Mode)恢复是最常用的策略:发现错误后,丢弃 Token 直到遇到某个"同步 Token"(如 ;、}、语句开头的关键字),然后从那里继续。目标是一次编译报多个错,而不是报一个就停——这直接影响开发体验。
一个最小可运行的例子
把 1 + 2 * 3 从头走到尾:
1. 字符流: '1' ' ' '+' ' ' '2' ' ' '*' ' ' '3'
2. 词法: [NUM:1] [PLUS] [NUM:2] [STAR] [NUM:3]
3. 语法(按 E→E+T | T, T→T*F | F, F→num):
E
|
+
/ \
[1] *
/ \
[2] [3]
4. 语义: int + int → int,类型 OK;常量表达式,可折叠
5. IR: t1 = 2 * 3
t2 = 1 + t1
6. 优化: 常量折叠 → t2 = 7
7. 目标码: mov eax, 7注意第 6 步:整个表达式在编译期就变成了一个常量。这不是什么特殊优化,而是常量传播 + 常量折叠这两个最基础的 Pass 迭代到不动点的自然结果。
术语速查
| 术语 | 含义 |
|---|---|
| Token | 词法单元,带类别和属性值 |
| Lexeme | Token 在源码里的原始字符串 |
| Grammar | 产生式集合,定义语言结构 |
| AST | 抽象语法树,去掉了无语义的语法细节 |
| IR | 中间表示,前后端的接口 |
| SSA | 静态单赋值,IR 的一种形式,每个变量只赋值一次 |
| CFG | 控制流图(也可指上下文无关文法,看语境) |
| Basic Block | 顺序执行、只有一个入口一个出口的代码段 |
| Pass | 对 IR 的一次完整扫描变换 |
| Spill | 寄存器不够,把值临时放到内存 |
| Front/Back End | 与目标机无关 / 相关的两半 |