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  = t2

IR 的作用:

  • 解耦前后端: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词法单元,带类别和属性值
LexemeToken 在源码里的原始字符串
Grammar产生式集合,定义语言结构
AST抽象语法树,去掉了无语义的语法细节
IR中间表示,前后端的接口
SSA静态单赋值,IR 的一种形式,每个变量只赋值一次
CFG控制流图(也可指上下文无关文法,看语境)
Basic Block顺序执行、只有一个入口一个出口的代码段
Pass对 IR 的一次完整扫描变换
Spill寄存器不够,把值临时放到内存
Front/Back End与目标机无关 / 相关的两半