Compilation Principle

自动关联目录:Compilation Principle

编译原理回答的是一个很具体的工程问题:如何把人写的字符流,机械地、可验证地、可优化地翻译成机器能执行的指令流。

它不是"背文法"的学科。真正有价值的部分是三件事:

  1. 如何用有限状态机把无结构的字符切成有结构的单词(词法)
  2. 如何用下推自动机判定一串单词是否符合某种嵌套结构,并还原出树(语法)
  3. 如何在树上挂动作,把结构一步步降级成线性指令,同时搬走冗余(语义 + 中间代码 + 优化)

理解这三点之后,正则引擎、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——从头写一个真的能跑的编译器