第3章编译原理

课程目录第3章编译原理

编译原理：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成

说实话，很多C语言开发者写了好几年代码，对编译器的认识还停留在「点一下按钮，出来个exe」的阶段。我以前带团队的时候，有个同事调试一个诡异的段错误，折腾了两天，最后发现是变量声明写在了可执行语句后面——C89标准不允许这么干，但编译器只给了个警告，没报错。他当时就懵了：「编译器不是应该帮我检查所有错误吗？」

嗯，这就是我们今天要聊的话题。编译器不是神仙，它只是按部就班地执行一套流程。这套流程，说白了就是六个阶段：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成。每个阶段都有自己的职责，也有自己的脾气。

1. 词法分析：把字符流变成Token流

这是编译器的第一步。你写的源代码，在编译器眼里就是一串字符。词法分析器（也叫扫描器）的任务，就是把这些字符组合成有意义的单词——我们叫它Token。

举个例子，你写了这么一行：

int a = 42 + b * 3;

词法分析器会把它拆成：

Token类型	词素
关键字	int
标识符	a
运算符	=
整型字面量	42
运算符	+
标识符	b
运算符	*
整型字面量	3
分隔符	;

每个Token都带着类型信息和位置信息。位置信息很重要——编译器报错时告诉你「第10行第5列有错误」，就是词法分析阶段记录下来的。

个人经验：我曾经手写过一个小型脚本语言的词法分析器，用的是手工状态机。当时踩过一个坑：C语言里「++」是两个加号，但如果你词法分析器写得不够严谨，可能会把「+ +」（中间有空格）也当成自增运算符。实际上，词法分析器遵循「最长匹配」原则——能匹配多长就匹配多长。

2. 语法分析：检查句子结构对不对

词法分析完了，我们有了Token流。但Token流本身没有结构——就像你有一堆单词，但不知道它们组成的是不是一句通顺的话。语法分析器就是干这个的。

它根据语言的文法规则（比如C语言的BNF范式），构建一棵抽象语法树（AST）。这棵树反映了程序的结构层次。

还是刚才的例子：

int a = 42 + b * 3;

语法分析器会生成类似这样的AST结构：

Declaration
├── Type: int
├── Identifier: a
└── Assignment
    └── BinaryOp: +
        ├── Literal: 42
        └── BinaryOp: *
            ├── Identifier: b
            └── Literal: 3

注意这里有个细节：b * 3被优先组合在一起，因为乘法的优先级高于加法。这就是语法分析器要处理的事情——它必须理解运算符优先级和结合性。

避坑指南：我曾经见过一个项目，团队自己写了个DSL的解析器，语法分析用的是递归下降法。结果有个嵌套很深的表达式，直接导致栈溢出。递归下降法虽然直观，但要注意递归深度。工业级编译器通常会用LALR(1)或GLR等更健壮的解析算法。

3. 语义分析：检查这句话有没有意义

语法正确不代表语义正确。你想想看，下面这段代码语法上完全没问题：

int a = "hello";

但语义上，你不能把一个字符串赋值给整型变量（除非有隐式转换，但C语言里字符串到整型没有隐式转换）。语义分析器就是做这些检查的。

语义分析阶段主要做三件事：

类型检查：操作数的类型是否匹配？函数调用时参数类型对不对？
作用域解析：变量在使用之前有没有声明？有没有重复定义？
控制流检查：break语句是否在循环或switch内部？return语句是否在函数内？

语义分析器会在AST上遍历，同时维护一个符号表。符号表记录了每个标识符的类型、作用域、存储类别等信息。

  核心要点：语义分析阶段会生成带类型标注的AST，也叫「带注释的语法树」。这棵树比原始的AST多了类型信息，为后续的中间代码生成做准备。

4. 中间代码生成：从抽象到具体的第一步

有了带类型信息的AST，接下来要把它转换成一种更接近机器、但又独立于具体机器的表示形式——中间代码。

常见的中间代码形式有三地址码（Three-Address Code）、静态单赋值形式（SSA）等。以三地址码为例，每条指令最多有三个操作数：

t1 = b * 3
t2 = 42 + t1
a = t2

为什么要生成中间代码？直接生成目标代码不行吗？

嗯，这里有两个原因。第一，中间代码是编译器前后端的分界线。前端（词法、语法、语义分析）与具体机器无关，后端（目标代码生成）与具体机器相关。这样，如果你要支持新的CPU架构，只需要重写后端，前端完全不用动。第二，中间代码便于做优化——很多优化算法在中间代码层面更容易实现。

我个人的习惯：在调试编译器时，我经常把中间代码dump出来看。如果中间代码就有问题，那后面的优化和目标代码生成肯定也跑偏。这就像盖房子——地基歪了，上面再怎么装修也没用。

5. 优化：让代码跑得更快、更省

优化是编译器里最复杂、也最有趣的部分。优化的目标是在不改变程序语义的前提下，提高程序的执行效率或减少代码体积。

优化分为很多层次：

局部优化：在基本块内部做优化。比如常量折叠——a = 2 + 3直接变成a = 5。
全局优化：跨基本块的优化。比如循环不变式外提——把循环内不变的表达式移到循环外面。
过程间优化：跨函数的优化。比如内联展开——把短函数的调用直接替换成函数体。

举个例子，常量折叠：

// 优化前
int x = 10;
int y = x * 2 + 5;

// 优化后
int x = 10;
int y = 25;  // 编译器直接算出来了

再比如死代码消除：

// 优化前
int a = 10;
int b = 20;  // b从未被使用
int c = a + 5;

// 优化后
int a = 10;
int c = 15;  // b被删掉了，a+5被折叠了

注意：优化不能改变程序的语义。我记得有一次，一个同事写了个volatile变量，结果编译器优化时把它给优化掉了——因为编译器觉得这个变量从来没被读取过。但实际上，这个变量是被中断服务程序修改的。这就是为什么volatile关键字存在的意义——告诉编译器「别优化我」。

6. 目标代码生成：最终产出

这是编译器的最后一步。把优化后的中间代码转换成目标机器的汇编代码或机器码。

目标代码生成要做的事情包括：

指令选择：把中间代码指令映射到目标机器的具体指令。比如x86架构下，加法可以用ADD指令，也可以用LEA指令（如果只是做地址计算）。
寄存器分配：把虚拟寄存器映射到物理寄存器。寄存器不够用的时候，就要把变量溢出到内存（栈上）。
指令调度：重排指令顺序，充分利用CPU的流水线。比如，把加载指令提前，让数据早点到位。

寄存器分配是个经典难题。我记得以前看LLVM的源码，寄存器分配器用的是图着色算法——把每个虚拟寄存器看作图中的一个节点，如果两个虚拟寄存器在同一个时刻都活跃，它们之间就有一条边。然后给这个图着色，颜色数就是物理寄存器的数量。如果颜色不够，就说明需要溢出。

最终生成的汇编代码大概长这样：

mov eax, [b]
imul eax, 3
add eax, 42
mov [a], eax

当然，现代编译器还会做链接、重定位等后续工作，但那些已经超出了编译原理的范畴，属于链接器的活了。

一张图总结整个流程

下面这张SVG图，把整个编译流程串起来了。我建议你仔细看看，每个阶段之间的箭头代表了数据的流动方向。

从这张图可以看得很清楚：前端（词法、语法、语义分析）负责理解程序，中端（优化）负责改进程序，后端（目标代码生成）负责生成最终的可执行代码。每个阶段都有明确的输入和输出，环环相扣。

好了，这一章的内容就到这里。编译原理的这六个阶段，是理解编译器工作原理的基础。你写C语言的时候，脑子里可以过一遍：我写的这行代码，编译器现在正在哪个阶段处理它？

📚 课程目录

编译原理：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成

1. 词法分析：把字符流变成Token流

2. 语法分析：检查句子结构对不对

3. 语义分析：检查这句话有没有意义

4. 中间代码生成：从抽象到具体的第一步

5. 优化：让代码跑得更快、更省

6. 目标代码生成：最终产出

一张图总结整个流程