Compilation Principle
自动关联目录:Compilation Principle
编译原理回答的是一个很具体的工程问题:如何把人写的字符流,机械地、可验证地、可优化地翻译成机器能执行的指令流。
它不是"背文法"的学科。真正有价值的部分是三件事:
- 如何用有限状态机把无结构的字符切成有结构的单词(词法)
- 如何用下推自动机判定一串单词是否符合某种嵌套结构,并还原出树(语法)
- 如何在树上挂动作,把结构一步步降级成线性指令,同时搬走冗余(语义 + 中间代码 + 优化)
理解这三点之后,正则引擎、JSON/YAML 解析器、SQL 执行计划、模板引擎、着色器交叉编译(HLSL→GLSL/Metal)、乃至 UE 蓝图的编译,本质上都是同一套东西换了个皮。
编译器全景
源代码(字符流)
│
├─ 词法分析 Lexical Analysis ──► Token 流
│
├─ 语法分析 Syntax Analysis ───► 语法树(CST → AST)
│
├─ 语义分析 Semantic Analysis ─► 带类型的 AST + 符号表
│ (类型检查、作用域解析、重载决议)
│
├─ 中间代码生成 ───────────────► IR(三地址码 / SSA / 字节码)
│
├─ 机器无关优化 ───────────────► 优化后的 IR
│ (常量传播、死代码消除、内联、循环优化)
│
├─ 目标代码生成 ───────────────► 汇编 / 机器码
│ (指令选择、寄存器分配、指令调度)
│
└─ 机器相关优化 ───────────────► 最终目标文件前端(Front End)负责前三步,与机器无关;后端(Back End)负责后三步,与目标机强相关。中间用 IR(Intermediate Representation) 解耦——这就是 LLVM 能"一种前端 + N 种后端"的根本原因:前端只管产出 LLVM IR,后端只管消费 LLVM IR,两边互不关心。
前端 vs 后端 vs 遍(Pass)
| 概念 | 职责 | 典型产物 |
|---|---|---|
| 前端 | 词法、语法、语义 | AST + 符号表 |
| 中端 | 机器无关优化 | 优化后 IR |
| 后端 | 指令选择、寄存器分配、调度 | 目标机器码 |
遍(Pass) 是对 IR 的一次完整扫描与变换。现代编译器(LLVM、GCC)是把几十个 Pass 串成流水线,每个 Pass 只做一件事,靠"反复跑到不动点"来累积优化效果。
while (changed) {
changed = ConstantPropagation();
changed |= DeadCodeElimination();
changed |= SimplifyCFG();
}这种"小变换 × 多轮迭代"的结构,比写一个大而全的优化器好维护得多——每个 Pass 可以单独测试、单独关掉、单独排错。
解释器、编译器、转译器
三者的界限在产品里经常是模糊的,但概念上要分清:
- 编译器(Compiler):先把整个程序翻译成目标语言,再执行目标语言。C/C++、Rust 属于此类。
- 解释器(Interpreter):直接读源程序的结构并求值,不产出独立的目标程序。早期 BASIC、shell 属于此类。
- 转译器(Transpiler):源和目标都是高级语言。TypeScript→JavaScript、HLSL→GLSL、Babel 属于此类。
- 混合式:先编译成字节码,再由虚拟机解释/即时编译执行。Java(bytecode + JVM)、C#(IL + CLR)、Lua(bytecode + LuaVM)、Python(.pyc + CPython VM)都是这一类。
Lua 是理解这一套的好样本:它先编译成字节码(指令集非常小,5.x 只有几十条),再由寄存器式虚拟机执行。所以"Lua 是解释型语言"这句话只对了一半——它有完整的编译前端。
自举与交叉编译
自举(Bootstrapping):用语言 A 写一个能编译语言 A 的编译器。做法是先用 B 写 A 的最小编译器,再用 A 写完整的 A 编译器并用前者编译。Go 1.5、Rust 都走过这条路。
交叉编译:编译器运行的平台 ≠ 产出代码运行的平台。手游/主机/UE 打包天天在做这件事(Windows 上编 Android/iOS/Switch)。交叉编译之所以可行,正是因为前端与目标机解耦,只要换后端即可。
阅读顺序
本目录按编译流水线的顺序组织,建议顺着读:
| 章节 | 主题 | 核心问题 |
|---|---|---|
| 1 Overview | 总览 | 编译器的整体结构与术语 |
| 2 Lexical Analysis | 词法分析 | 字符流 → Token 流 |
| 3 Syntax Analysis | 语法分析 | Token 流 → 语法树 |
| 4 Syntax-Directed Translation | 语法制导翻译 | 在语法树上挂语义动作 |
| 5 Intermediate Code Generation | 中间代码生成 | 树 → 线性 IR,进入优化领域 |
参考
- 《编译原理》(龙书,Compilers: Principles, Techniques and Tools)
- 《编译器设计》(Engineering a Compiler,Cooper & Torczon)——工程视角更强
- CS143: Compilation(Stanford)
- LLVM 官方教程 Kaleidoscope——从头写一个真的能跑的编译器