编译原理简介

概述

编译器将高级语言源代码翻译为目标机器码，是连接程序员与硬件的关键桥梁。理解编译原理有助于写出更高效的代码，并为理解语言设计、程序优化和工具链（如 LLVM）奠定基础。

相关内容：形式语言与自动机

---

1. 编译器的整体结构

graph LR
    A[源代码] --> B[词法分析]
    B --> C[语法分析]
    C --> D[语义分析]
    D --> E[中间代码生成]
    E --> F[优化]
    F --> G[目标代码生成]
    G --> H[目标代码]

    subgraph 前端 Frontend
        B
        C
        D
    end

    subgraph 中端 Middle-end
        E
        F
    end

    subgraph 后端 Backend
        G
    end

编译过程通常分为前端（与源语言相关）和后端（与目标平台相关），中间通过中间表示（IR） 解耦。

---

2. 词法分析（Lexical Analysis）

词法分析器（Lexer/Scanner）将源代码字符流转换为词法单元（Token） 流。

2.1 示例

源代码: if (x >= 42) { y = x + 1; }

Token 流:
  IF  LPAREN  ID("x")  GE  NUM(42)  RPAREN
  LBRACE  ID("y")  ASSIGN  ID("x")  PLUS  NUM(1)  SEMICOLON  RBRACE

2.2 正则表达式 → DFA

词法规则用正则表达式描述，执行时转换为确定性有限自动机（DFA）：

\[ \text{正则表达式} \xrightarrow{\text{Thompson}} \text{NFA} \xrightarrow{\text{子集构造}} \text{DFA} \xrightarrow{\text{最小化}} \text{最小 DFA} \]

示例：标识符的正则表达式 [a-zA-Z_][a-zA-Z0-9_]*

         letter/underscore    letter/digit/underscore
  ──→ (q0) ──────────────→ ((q1)) ◄─────────────────┐
                              │                       │
                              └───────────────────────┘

2.3 词法分析工具

• Lex/Flex：经典的词法分析器生成器
• 正则表达式引擎：现代语言内置

---

3. 语法分析（Parsing）

语法分析器（Parser）根据上下文无关文法（CFG） 将 Token 流组织成语法树。

3.1 上下文无关文法

// 简单算术表达式文法
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | num | id

3.2 自顶向下分析：LL 分析

LL(k) ：从左到右扫描（L），最左推导（L），向前看 k 个 Token。

递归下降解析是最直观的 LL 解析方式：

def parse_expr():
    """E → T (('+' | '-') T)*"""
    left = parse_term()
    while current_token in ('+', '-'):
        op = current_token
        advance()
        right = parse_term()
        left = BinOp(op, left, right)
    return left

def parse_term():
    """T → F (('*' | '/') F)*"""
    left = parse_factor()
    while current_token in ('*', '/'):
        op = current_token
        advance()
        right = parse_factor()
        left = BinOp(op, left, right)
    return left

def parse_factor():
    """F → '(' E ')' | num | id"""
    if current_token == '(':
        advance()
        node = parse_expr()
        expect(')')
        return node
    elif current_token.isdigit():
        node = Num(int(current_token))
        advance()
        return node

LL 分析要求文法无左递归，需要消除：

\[ A \to A\alpha \mid \beta \quad \Rightarrow \quad A \to \beta A', \quad A' \to \alpha A' \mid \epsilon \]

3.3 自底向上分析：LR 分析

LR(k)：从左到右扫描（L），最右推导的逆（R），向前看 k 个 Token。

LR 分析比 LL 更强大，能处理更多文法。

分析方法	能力	复杂度	工具
LL(1)	较弱	简单	ANTLR, 递归下降
SLR(1)	中等	中等	Yacc 变体
LALR(1)	较强	中等	Yacc/Bison
LR(1)	最强	较高	较少使用

LR 分析核心操作：

• 移进（Shift）：读入一个 Token 压栈
• 规约（Reduce）：栈顶匹配文法规则右部，替换为左部

---

4. 抽象语法树（AST）

AST 是源代码的树形结构表示，去除了语法噪声（如括号、分号）。

源代码: x = 2 * (y + 3)

AST:
        Assign
       /      \
    Var(x)    Mul
             /    \
          Num(2)  Add
                 /    \
             Var(y)  Num(3)

AST 是后续分析和代码生成的基础数据结构。

---

5. 语义分析（Semantic Analysis）

语义分析检查 AST 的语义正确性，主要任务：

5.1 类型检查

int x = "hello";   // 类型错误：不能将 string 赋给 int
float y = 3 + 2.5; // OK：int 隐式提升为 float

类型检查规则：

\[ \frac{\Gamma \vdash e_1 : \text{int} \quad \Gamma \vdash e_2 : \text{int}}{\Gamma \vdash e_1 + e_2 : \text{int}} \quad (\text{T-Add}) \]

5.2 符号表

符号表记录程序中所有标识符的信息：

名称	类型	作用域	地址/偏移
x	int	main	rbp-4
y	float	main	rbp-8
add	int→int→int	global	0x4000a0

5.3 作用域解析

int x = 1;          // 全局 x
void foo() {
    int x = 2;      // 局部 x，遮蔽全局
    {
        int x = 3;  // 更内层，遮蔽外层
    }
}

---

6. 中间表示（IR）

IR 是源语言和目标代码之间的桥梁，便于优化。

6.1 三地址码

源代码: a = b * c + d

三地址码:
  t1 = b * c
  t2 = t1 + d
  a = t2

每条指令最多涉及三个地址（两个操作数 + 一个结果）。

6.2 SSA 形式

静态单赋值（Static Single Assignment）：每个变量只被赋值一次。

// 原始
x = 1
x = x + 1
y = x

// SSA 形式
x1 = 1
x2 = x1 + 1
y1 = x2

SSA 简化了数据流分析和优化。分支汇合处使用 \(\phi\) 函数：

// if (cond) x = 1; else x = 2; y = x;
if cond goto L1 else L2
L1: x1 = 1; goto L3
L2: x2 = 2; goto L3
L3: x3 = φ(x1, x2)
    y1 = x3

---

7. 优化

7.1 常见优化技术

优化	描述	示例
常量折叠	编译期计算常量表达式	3+4 → 7
常量传播	用已知常量替换变量	x=5; y=x+1 → y=6
死代码消除	移除不可达/无用代码	删除未使用的变量
公共子表达式消除	避免重复计算	a*b+a*b → t=a*b; t+t
循环不变量外提	将循环内不变的计算移到循环外	-
循环展开	减少循环开销	展开循环体
内联展开	将函数调用替换为函数体	消除调用开销
尾调用优化	尾递归转循环	避免栈溢出
强度削减	用低开销操作替换高开销操作	x*2 → x<<1

7.2 数据流分析

优化依赖数据流分析，在控制流图（CFG）上传播信息：

• 到达定值分析（Reaching Definitions）：哪些赋值语句的定值可以到达某个程序点
• 活跃变量分析（Live Variables）：某个变量在之后是否还会被使用
• 可用表达式分析（Available Expressions）：某个表达式是否已经被计算且值未改变

---

8. 目标代码生成

8.1 指令选择

将 IR 映射为目标机器指令：

IR: t1 = a + b

x86-64:
  mov eax, [rbp-4]    ; 加载 a
  add eax, [rbp-8]    ; 加上 b
  mov [rbp-12], eax   ; 存储到 t1

8.2 寄存器分配

寄存器数量有限，需要决定哪些变量放在寄存器中：

• 图着色算法：构建冲突图（同时活跃的变量连边），用 \(k\) 种颜色着色（\(k\) = 寄存器数量）
• 着色失败的变量溢出（spill） 到内存

8.3 指令调度

重排指令以利用流水线，减少停顿。

---

9. 解释器、编译器与 JIT

方式	工作方式	优势	劣势
解释器	逐条执行源码/字节码	启动快，易调试	运行慢
AOT 编译器	预先编译为机器码	运行最快	编译慢，平台相关
JIT 编译器	运行时编译热点代码	运行时优化	启动慢，内存占用高

JIT 编译流程：

graph LR
    A[字节码] --> B{是否热点?}
    B -->|否| C[解释执行]
    B -->|是| D[JIT 编译为机器码]
    D --> E[缓存机器码]
    E --> F[直接执行机器码]
    C --> B

---

10. LLVM 架构

LLVM 是现代编译器基础设施，采用模块化设计。

graph TD
    subgraph 前端
        A1[Clang - C/C++]
        A2[Rust 前端]
        A3[Swift 前端]
    end

    subgraph LLVM Core
        B[LLVM IR]
        C[优化 Pass]
    end

    subgraph 后端
        D1[x86-64 CodeGen]
        D2[ARM CodeGen]
        D3[RISC-V CodeGen]
        D4[WASM CodeGen]
    end

    A1 --> B
    A2 --> B
    A3 --> B
    B --> C
    C --> D1
    C --> D2
    C --> D3
    C --> D4

10.1 LLVM IR 示例

define i32 @add(i32 %a, i32 %b) {
entry:
    %result = add i32 %a, %b
    ret i32 %result
}

LLVM IR 特点：

• 类型化：所有值都有类型
• SSA 形式：每个变量只赋值一次
• 三种形式：内存中的数据结构、人类可读的 .ll 文件、紧凑的位码 .bc 文件

10.2 LLVM 的影响

• Clang：C/C++/Objective-C 编译器
• Rust：使用 LLVM 作为后端
• Swift：Apple 的新语言，基于 LLVM
• Julia：科学计算语言，使用 LLVM JIT
• Numba：Python 数值计算 JIT

---

11. 编译器构造工具

工具	用途	代表
词法分析器生成器	正则表达式 → DFA	Lex, Flex, re2c
语法分析器生成器	文法 → 解析器	Yacc, Bison, ANTLR
编译器框架	完整编译器基础设施	LLVM, GCC
解析器组合子	函数式解析	Parsec (Haskell), nom (Rust)

---

参考资料

• "Compilers: Principles, Techniques, and Tools"（龙书）- Aho, Lam, Sethi, Ullman
• "Engineering a Compiler" - Cooper & Torczon
• LLVM 官方文档：https://llvm.org/docs/

---

评论