跳到主要内容

引论

编译原理引论​

编译器(Compiler)本质上是一个"翻译程序":它读入一段用源语言(比如 C、Java)写成的程序,输出一段用目标语言(通常是机器码或字节码)表达的、语义等价的程序。在这个翻译过程中,编译器还要顺带发现源程序里的错误,并给出足够清晰的诊断信息。

通俗理解:编译器就像一个专业的同声传译。你说中文(源语言),他说英文(目标语言),要求是意思一模一样。他不仅要翻译得对,还要在你语法出错时提醒你:"第 3 句里的主语没了。"

编译器 vs 解释器​

翻译源程序的方式并不只有编译一种,另一条路是解释器(Interpreter):它不生成目标代码,而是直接在虚拟机或运行时里"边读边执行"源程序或其中间表示。

  • 编译器(AOT,Ahead-of-Time):一次翻译,多次执行。启动快,运行时开销小,典型代表是 C/C++、Rust。
  • 解释器:不预先翻译,运行时逐条解释。启动灵活、便于交互,但执行慢,典型代表是早期的 Python、Shell、JS 引擎的解释模式。
  • 混合方案:现代运行时几乎都走这条路。JVM 先把 Java 源码编译成字节码(AOT 部分),运行时再由 JIT(Just-in-Time)把热点字节码即时编译为机器码;V8、CPython、PyPy 都是类似思路。JIT 相当于"边解释边发现热点,把热点段临时上升成机器码",兼顾了启动速度和峰值性能。

也就是说,"编译器"和"解释器"并不是非此即彼,它们只是同一件事——把源语言变成目标机器能理解的形式——在什么时候翻译上做了不同的权衡。

编译器的结构​

一个典型的编译器可以分成两大部分:前端(分析) 负责理解源程序,后端(综合) 负责生成目标代码。中间用一种与源语言、目标机都尽量解耦的**中间表示(IR)**做桥梁。

分析阶段一般包含三步:

  1. 词法分析(Lexical Analysis):把字符流切成一个个有意义的"词"(Token),比如 if、x、==、10。此时空格、注释被丢弃。
  2. 语法分析(Syntax Analysis / Parsing):按语法规则把 Token 序列组织成语法树(AST),表达"这是一个赋值语句"、"这是一个函数调用"。
  3. 语义分析(Semantic Analysis):在 AST 上做类型检查、作用域检查、隐式类型转换插入等,确保程序不仅"读得通",还"说得通"。

综合阶段则接着做:

  1. 中间代码生成:把 AST 或注释过的 AST 翻译成一种规整的 IR(如三地址码、SSA、LLVM IR)。
  2. 代码优化:基于 IR 做常量折叠、公共子表达式消除、循环不变量外提、内联等优化,既有机器无关的部分,也有面向目标机的部分。
  3. 目标代码生成:把 IR 翻译成汇编或机器码,涉及指令选择、寄存器分配、指令调度。

贯穿始终的还有两件事:符号表管理(跟踪每个标识符的类型、作用域、存储位置)和错误处理(在任何阶段发现问题都要能定位并报告,理想情况下还能"恢复"以继续检查后面的错误)。

源程序 → [词法] → Token 流 → [语法] → AST → [语义] → 注释 AST
↓
[中间代码生成] → IR → [优化] → 优化后的 IR → [目标代码生成] → 汇编 / 机器码
↑
符号表 & 错误处理贯穿全过程

编译器与其他工具​

一个源程序从纯文本变成可运行的二进制,编译器只是其中一环。围绕它还有一整套工具:

  • 预处理器(Preprocessor):处理宏展开、#include、条件编译等,输出"完整"的源代码交给编译器。C/C++ 里最典型。
  • 汇编器(Assembler):把汇编代码翻译成可重定位的目标文件(.o)。
  • 链接器(Linker):把多个目标文件以及库中的符号解析并拼接起来,生成可执行文件,解决"这个函数在哪个文件"的问题。
  • 装载器 / 加载器(Loader):在程序运行时把可执行文件加载到内存,做地址重定位、动态库解析。

这些工具加上编译器共同构成了"程序处理系统"。理解它们的分工,能让你在遇到"undefined reference"、"symbol not found"、"segmentation fault at load time" 这类报错时,一眼看出问题出在哪一层。

编译器技术的应用​

编译原理的价值远不止"造一门新语言"。它是一整套关于"程序 → 程序"变换的方法论,几乎所有涉及"分析代码、变换代码"的工具背后,都能看到它的影子:

  • 新型体系结构:GPU、TPU、NPU、各种 DSA(Domain-Specific Accelerator)都需要专属后端。CUDA、TVM、MLIR、Triton 等生态本质上都是编译器技术在异构硬件上的延展。
  • 程序翻译(Source-to-Source):Babel 把新版 JS 转成兼容旧浏览器的 JS,TypeScript 编译成 JS,都是典型的源到源翻译。
  • 软件生产率工具:静态分析(Clang-Tidy、ESLint、SonarQube)、IDE 补全与跳转、自动重构、代码格式化,全部依赖词法/语法/语义层面的分析能力。
  • 安全与验证:污点分析、符号执行、形式化验证也大量借用编译器的中间表示和数据流分析。

可以说,只要你还在写程序,编译原理就不会离你太远。

一个简单例子​

下面用一段极简的代码看看前端到底做了什么:

position = initial + rate * 60;

词法分析会把它切成一串 Token:

id(position)  =  id(initial)  +  id(rate)  *  num(60)  ;

语法分析会把 Token 流组织成一棵 AST:

     assign
/ \
id +
(position) / \
id *
(initial) / \
id num
(rate) (60)

语义分析会在树上加类型信息。如果 position、initial、rate 是 float,而 60 是 int,编译器会自动在 60 上插入一个"int 转 float"的节点,让类型对齐;同时通过符号表确认这三个变量都已经声明过、类型是否匹配。

到这一步,源程序才算被"读懂"了。接下来后端会把这棵注释过的 AST 变成 IR,再一步步压成机器指令。整个编译过程,就是从"人能看懂的字符串"到"CPU 能执行的电信号"之间的层层降级——后面几章我们会顺着这条流水线,一个阶段一个阶段拆开来讲。