企业官网建设流程全解析

1. 编译器到底替谁在干活：一行代码到机器指令之间发生了什么

编译原理这门课，我见过太多人在第二周就掉队了。掉队的原因通常不是它有多难，而是一上来就被塞了一堆状态机、推导式、集合的闭包运算，脑子里建立起"这是一门数学课"的印象，然后就本能的抵触。可实际上，编译器要解决的问题朴素得近乎体力活：把人能看懂的文字，翻译成机器能执行的指令。它本质上是个翻译官，而且是个要求极为苛刻的翻译官——不能译错一个字，还得翻译得足够快。

我一般建议新手先把"编译器"这个词拆开看。词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成，这六个环节构成了传统编译器的骨架。你写下的x = a + b * 2;，在这六个环节里会依次变成一长串记号、一棵树、一张带类型的表格、一串三地址形式的三元式、一版被打过补丁的三元式，最后变成几条寄存器搬移和加法乘法指令。整个过程没有任何玄学，每一步都有明确的输入和输出，每一步都可以单独拿出来调试。

搞清楚这条链路的意义在于：你以后遇到的绝大多数"程序行为诡异"的问题，都能定位到这条链路的某一段。代码报错说"第 12 行第 5 列缺少分号"，那是词法或语法阶段的问题；报错说"不能把字符串赋给整型变量"，那是语义阶段的问题；程序跑起来结果莫名其妙地不对，但语法检查全过，那可能就是优化阶段动了不该动的东西。知道每一段管什么，你就知道该往哪儿看。

1.1 用a = b + 1把六个阶段走一遍

我拿一个最小例子把这条链路走完，这样后面每一章你都能对上号。假设源码是这么一行：

a = b + 1;

第一站，词法分析。输入是一串字符，输出是一串"记号"（token）。切出来的结果是：标识符a、等号=、标识符b、加号+、整数字面量1、分号;。注意每个记号除了类型，通常还带两个信息：它在原文里的值和它的位置。位置信息看着不起眼，但它是后面所有错误提示能精确到"第几行第几列"的唯一来源。这一步干的是"切词"，它不知道a和b是不是变量，也不知道这行语句合不合法，它只负责切得对。

第二站，语法分析。输入是记号序列，输出是一棵语法树或者抽象语法树（AST）。语法分析器会检查标识符 = 标识符 + 整数字面量 ;这个序列是否符合"赋值语句"的文法规则。如果符合，它就构造出一个树形结构，根节点是赋值，左子节点是变量a，右子节点是一个加法表达式，加法表达式下面挂b和1。到这里，程序的结构关系被显式地表达出来了——+是作用在b和1上的，而不是作用在a和b上的，这种"谁跟谁结合"的信息，词法阶段是完全看不出来的。

第三站，语义分析。这一站开始"懂人事"了。它会去查符号表：a和b这两个名字声明过吗？它们的类型是什么？整数字面量+一个整型变量，类型对不对？如果a是字符串类型，这里就会报类型不匹配。同时，它还要判断这个赋值是不是"可达的"、有没有被重复声明之类的问题。很多新手误以为编译器只有在语法错误时才拦人，实际上语义阶段的拦截量更大，只是报错信息看起来更像是"业务逻辑"层面的。

第四站，中间代码生成。到了这里，树被"拍扁"成了一条条简单的、类似汇编但和具体硬件无关的指令：

t1 = b + 1 a = t1

这就是三地址码的典型样子，每条指令最多涉及一个运算和三个地址。为什么要拍扁？因为树形结构对后续的优化和生成不友好。树是嵌套的，你很难对着树做"把这个加法移到循环外面去"这种操作；而一条条线性的指令，天然适合做数据流分析。

第五站，优化。假设b在上下文里是个已知的常量，比如前面有b = 3;，那么常量传播会把t1 = b + 1变成t1 = 4，常量折叠再把它直接算成4。如果后面t1没人用，死代码消除会把它删掉。优化这一步最考验功力，也最容易写出 bug——优化必须保证程序的可观察行为不发生改变，稍微动错一处就是"程序能跑但结果不对"这种最难查的问题。

第六站，目标代码生成。最后把中间代码映射成具体平台上的指令，分配寄存器、选择寻址方式、安排指令顺序。这一步一旦涉及"分配寄存器"这个子问题，难度就上来了，后面第 5 章会专门讲。

把这六步串起来看，你会发现编译器并没有任何"智能"，它是极其死板的分阶段流水线。每一站的输出就是下一站的输入，边界清晰到你可以用文件把中间结果存下来逐步排查。这也是我在调试自研编译器时最常用的招——把每个阶段的产物打出来，看是哪一站开始偏的。

1.2 前端、中端、后端为什么这么切

教材里常把编译器分成前端、中端、后端三段：前端负责"看懂源码"，包括词法、语法、语义和中间代码生成；中端负责"优化中间代码"；后端负责"映射到目标机器"。这个划分不是因为好看，而是为了算一笔很实在的账。

假设有 N 种源语言、M 种目标平台。如果不分层，每种语言对每种平台都要写一个完整编译器，工作量是 N×M。分层之后，每种语言只需要写一个前端，把源码统一翻译成一种中间表示；每种平台只需要写一个后端，把中间表示翻译成自己的机器指令。工作量降到 N+M。

这个思路在工业界的价值极大。你家公司如果同时要支持三种前端语言、两种后端芯片，分层和不分层的工作量差了三倍。而且中间表示这一层做得越规范，跨语言复用和跨平台移植的成本就越低。

不过这里有个新手常见的误解：以为中间表示只有一种标准形态。实际上不同编译器选择的中间表示差别很大，有的是三地址码，有的是带基本块和控制流图的 SSA 形式，有的干脆直接用树。它们之间也不是谁替代谁的关系，很多编译器会同时维护好几层中间表示，逐层降低抽象程度。你在学习时先掌握"三地址码"这种最朴素的形态就够了，它的结构足够简单，能让你把注意力放在"如何表达计算和控制流"这件事上，而不是被各种表示形式绕晕。

1.3 编译器和解释器的界线其实很模糊

新手很容易把编译器和解释器当成两个对立的东西。教科书上的定义是：编译器把源程序整体翻译成目标程序，解释器逐条读入源程序并直接执行。这个定义没错，但它把现实简化得过于干净了。

我举个最直观的例子。很多语言的执行引擎是先编译成一种中间字节码，再由虚拟机解释执行。这算编译器还是解释器？两样都算。字节码的生成过程就是正经的编译，只不过目标不是硬件指令而是虚拟机指令；虚拟机的执行过程就是正经的解释。再往上一层，如果虚拟机在运行时发现某段代码反复执行，就把它即时编译成本地机器指令，那这就是JIT 编译，编译和解释在同一套系统里循环发生。

理解这一点对学习的好处是：你不必纠结"我写的是编译器还是解释器"，因为从零写一个编译器最好的入门形式，恰恰是写一个"解释器"。你先把 AST 直接解释执行，跑通了整条链路，再去考虑把它降级成中间代码、再生成目标代码。这种"先跑通、再优化"的路径，比一上来就死磕寄存器分配要现实得多，也更容易获得正反馈。我在带新人的时候，第一周的目标永远是"能跑出一个结果"，而不是"能跑出一个高性能的结果"。

2. 词法分析：把字符流切成有意义的"词"

词法分析是整个编译器里最简单的一环，也是最容易让人轻视的一环。说它简单，是因为它的理论模型很成熟，正则表达式、有限自动机这些东西几十年没变过；说它容易被轻视，是因为很多人觉得"切词有什么难的，按空格和符号劈开不就完了"。真动手写就发现，if (a>=1) x=1;这一行里，>=必须是一个记号而不是两个，x和=之间没有空格也得切开，if和iff要区分开，字符串字面量里的空格不能切。这些细节全是坑。

2.1 为什么不拿正则表达式一把梭

有人会问：既然词法规则都能用正则表达，那我写一堆正则去匹配不就完了，为什么要专门搞个词法分析器？

第一个原因很硬：正则表达式的表达力不够。正则语言表达不了嵌套结构。你不会在词法阶段遇到嵌套吗？会的，如果你要把注释或者字符串里的转义序列处理干净，你会发现正则写起来极其别扭。更关键的是，编程语言的括号匹配、嵌套语句这些结构，本质上是上下文无关的，正则根本管不了。这就是为什么词法分析和语法分析必须分成两阶段——不是工程上的偷懒，是理论上的必然。

第二个原因是性能。词法分析要遍历源码的每一个字符，这是编译过程中最热的路径之一。用现成的正则引擎去做，每次匹配都要回溯、都要建状态，开销很大。而手写或者自动生成的状态机，每个字符只需要一次状态转移，是严格的线性时间。第三方正则库再快，也很难比一个为特定文法定制的状态机快。

第三个原因，也是最容易被忽视的：错误定位。词法分析器需要知道每个记号从哪一行哪一列开始、到哪结束。用正则匹配，你拿到的只是一个子串和它的偏移，还得反算行列号。手写状态机则可以在每个字符步进时顺手维护行号和列号，出错时直接报"第 3 行第 8 列附近出现了非法字符"。这个体验差别，在你调试自己的编译器时会体现得非常明显。

2.2 有限状态机是怎么从正则"长"出来的

我讲一个具体规则，把"正则到状态机"这个过程走一遍。假设标识符的规则是：首字符必须是字母或下划线，后续字符可以是字母、数字或下划线。对应的正则写法是[A-Za-z_][A-Za-z0-9_]*。

这个正则转成状态机，只需要两个状态：

• 状态 0（起始态）：读到字母或下划线，进入状态 1；读到别的字符，报错或者交给别的规则处理。
• 状态 1（接受态）：读到字母、数字或下划线，继续留在状态 1；读到其他字符，说明标识符结束，回退一个字符，产出一个标识符记号。

就这么点东西。数字字面量的规则稍微麻烦一点，要考虑整数、小数、科学计数法，但方法完全一样：把每一种合法前缀对应成一个状态，读到不合法字符就停。

自动生成词法分析器的工具，干的事情就是帮你把这个转换做完：你写正则，它构造出非确定有限自动机（NFA），再用子集构造法转成确定有限自动机（DFA），最后生成一张状态转移表和一坨查表代码。听起来很高级，但你去翻它生成的代码，核心就是一个while循环加一张二维数组。

注意：学习阶段我不建议一上手就用生成器。你手写过一遍，才知道那张转移表是怎么来的，出问题时才知道该改正则还是改状态。等你写过两三个手写词法器之后，再用生成器提效，才是合理的顺序。

2.3 手写词法分析器必须处理的几个工程细节

理论讲完了，讲点真正会卡住人的东西。

最长匹配原则。遇到>=的时候，你不能读到>就急着产出一个大于号，必须先看下一个字符是不是=。遇到1..5这种写法，你要判断是1.加.5还是1加..加5。通用做法是：每读一个字符就尝试往前走一步，直到下一个字符无法让状态机继续转移，再回退一步。这个"能走多远走多远，走不动了退一步"的策略，就叫最长匹配。实现上通常需要一个前瞻字符（peek），也就是能偷看下一个字符但不消耗它。

关键字和标识符的分离。if符合标识符的正则，iff也符合。所以词法分析器一般走两步：先按标识符规则切出一个完整的词，然后拿这个词去一张关键字哈希表里查一遍。查到就返回关键字记号，查不到就返回标识符记号。这个设计的好处是关键字表可以随时增删，不需要改状态机。要注意的是，关键字必须先于标识符判断，否则if会永远被当成变量名。

位置信息的维护。每个记号至少要记下起始行号、起始列号，报错时才能定位。遇到换行符时要重置列号并递增行号，遇到制表符要决定算几列（通常按一个字符算，简单省事）。这里最坑的是多行注释和字符串字面量里的换行——你得保证行号在那里也是对的，否则后面所有报错的行号全错位。

错误恢复。真实的源码里一定有非法字符。一个好用的词法分析器不应该遇到第一个非法字符就整个崩掉，而是跳过这个字符、记录一条错误、继续往下扫。这样用户一次编译就能看到所有词法错误，而不是改一个报一个。这个细节不做，你自己调试时会痛苦不堪。

下面这段是最小可用版本，去掉了一切花哨，你可以直接跑：

KEYWORDS = {"if", "else", "while", "int", "print"} class Token: def __init__(self, kind, value, line, col): self.kind, self.value = kind, value self.line, self.col = line, col def __repr__(self): return f"Token({self.kind}, {self.value!r}, {self.line}:{self.col})" def tokenize(src): tokens, i, line, col = [], 0, 1, 1 n = len(src) while i < n: ch = src[i] if ch in " \t\r": i += 1; col += 1 continue if ch == "\n": i += 1; line += 1; col = 1 continue if ch.isalpha() or ch == "_": start_col, start = col, i while i < n and (src[i].isalnum() or src[i] == "_"): i += 1; col += 1 word = src[start:i] kind = "KW" if word in KEYWORDS else "IDENT" tokens.append(Token(kind, word, line, start_col)) continue if ch.isdigit(): start_col, start = col, i while i < n and src[i].isdigit(): i += 1; col += 1 tokens.append(Token("INT", int(src[start:i]), line, start_col)) continue # 双字符运算符优先，保证最长匹配 two = src[i:i+2] if two in (">=", "<=", "==", "!=", "&&", "||"): tokens.append(Token("OP", two, line, col)) i += 2; col += 2 continue if ch in "+-*/=<>(){},;!": tokens.append(Token("OP", ch, line, col)) i += 1; col += 1 continue raise SyntaxError(f"非法字符 {ch!r} 于 {line}:{col}") tokens.append(Token("EOF", None, line, col)) return tokens

这段代码里有几处是刻意这么写的：双字符运算符的判断放在单字符之前，就是为了最长匹配；遇到非法字符直接抛错而不静默跳过，是因为初学阶段我更希望它"响亮地失败"；行号和列号的维护穿插在每个分支里，看着啰嗦，但省掉了后期反算位置的麻烦。等你跑通之后，可以试着把错误处理改成"记录错误并继续"，感受一下两种策略的差别。

3. 语法分析：从"词"到"树"的那一跳

词法分析给出来的是一个扁平的记号序列，a、=、b、+、1、;。这个序列里没有任何结构信息。a = b + 1和a = b、+1在序列层面长得几乎一样，只有语法分析才能告诉你，"加法是右结合到b和1上的"。这一跳是从"线性"到"层次"的跨越，也是整个入门阶段最需要动手的一步。

3.1 上下文无关文法为什么刚好够用

先说结论：编程语言绝大多数语法结构，用上下文无关文法（CFG）就能描述，而且刚好够用。这里的"刚好"值得琢磨。

正则文法不够用，前面已经说过了——它处理不了嵌套。你不能用正则去匹配"任意深度的括号配对"，因为正则没有栈。而编程语言里到处都是嵌套：f(g(h(x)))、if里套while、表达式里套括号。没有栈就没有嵌套，所以词法分析那一层的能力上限就在这儿。

上下文相关文法又太强。它可以描述"变量必须先声明后使用"这类规则，但这类规则用文法去表达，会导致文法变得极其臃肿，而且解析效率会崩掉。更重要的是，这类规则在工程上更适合放到语义分析阶段用符号表来做——用文法去管"声明顺序"，等于用大炮打蚊子。

所以工业界的普遍做法是：用 CFG 描述结构，用符号表和类型系统描述约束。前者管"长什么样"，后者管"合不合理"。这条分工线一旦想明白，你就知道为什么编译原理要分成语法和语义两章了。

用扩展巴科斯范式（EBNF）写一个四则运算表达式加赋值语句的文法，大概是这样：

program -> stmt* stmt -> IDENT "=" expr ";" | "print" expr ";" expr -> term (("+" | "-") term)* term -> factor (("*" | "/") factor)* factor -> INT | IDENT | "(" expr ")" | "-" factor

这份文法里有个很关键的设计：用分层的非终结符来表达优先级。expr管加减，term管乘除，factor管括号和原子。因为expr的规则里调用term，而term的规则里又调用factor，所以乘除天然比加减"更深一层"，解析出来的树也就自然体现出乘除先算。这个技巧比在解析器里写一堆优先级判断要干净得多，我强烈建议新手用这种方式，别急着上优先级爬升算法。

3.2 递归下降和自底向上，新手先啃哪个

语法分析有两大流派：自顶向下的递归下降，和自底向上的LR 类分析。

递归下降的写法极其直观：文法的每个非终结符，对应一个函数。parse_expr里面调用parse_term，parse_term里面调用parse_factor。函数返回的是这个语法结构对应的树节点。你写完这份代码，几乎可以逐行对照文法去读，改起来也方便。

LR 类分析则是另一套思路：用一个栈，根据当前状态和前瞻记号查表决定"移进"还是"归约"。它的理论优美，能处理的文法范围比递归下降大，而且分析过程是严格线性的。但它的分析表要靠工具生成，手写基本不现实，出错时的调试体验也相当糟糕。

我的建议很明确：新手先写递归下降。理由有三条。第一，递归下降的代码结构和人的思维一致，你能把注意力放在"文法怎么写"上，而不是"分析表怎么算"上。第二，递归下降的错误处理和恢复非常灵活，你可以在任何位置插入自定义的报错逻辑，这在写真实语言时价值巨大。第三，递归下降是最容易调试的——出问题时你可以直接单步跟踪，看到底是哪个函数返回了不该返回的东西。

LR 那一套不是不学，而是放到后面。等你能熟练写出递归下降解析器、理解了"移进归约"在干什么之后，再去看 LR 分析表的构造，会顺畅得多。反过来先学 LR，很容易陷在"为什么这个状态要归约到那个状态"里出不来。

3.3 左递归与结合性的处理细节

写递归下降时第一个会撞上的墙，是直接左递归。假设你把加法写成：

expr -> expr "+" term | term

翻译成代码就是parse_expr里先调用parse_expr，这会立刻无限递归，栈溢出。解决办法是机械地把左递归改写成循环：

expr -> term ("+" term)*

代码里就变成了"先解析一个 term，然后 while 循环看下一个记号是不是加号，是的话吃掉它、再解析一个 term、把两边拼成一个加法节点"。这个改写模式几乎适用于所有二元运算符，记住它就行。

第二个坑是结合性。a - b - c到底应该是(a - b) - c还是a - (b - c)？数学上减法左结合，所以是前者。用 while 循环的写法天然产生左结合：每次循环都把"已有结果"和"新解析的部分"拼成一个新节点，新节点在左边。如果你需要右结合（比如赋值运算符、幂运算），就得改成递归写法：

assign -> IDENT "=" assign | expr

第三个坑是一元负号。-x和a - b里的减号长得一样，但前者是一元运算，后者是二元。处理方式是在factor层面单独判一个负号：如果当前记号是-，就吃掉它并递归调用parse_factor，构造一个取负节点。注意一定要放在factor层而不是expr层，否则-2 * 3会被解析成-(2 * 3)而非(-2) * 3，虽然数值上一样，但一旦涉及优先级更复杂的情况就会出错。

3.4 AST 和语法树不是一回事

很多人把"语法树"和"抽象语法树"混着说，这俩其实有区别。

**语法树（parse tree）**忠实反映推导过程，文法里的每个非终结符都会在树上有一个节点。上面那个四则运算文法解析1 + 2，语法树会是这样一条链：program → stmt → expr → expr + term → term + term → factor + term → INT + term → ...。光是"1 加 2"这一件小事，树上就有七八个节点，其中大部分节点只是在体现文法结构，对后续的语义分析毫无信息量。

**抽象语法树（AST）**则把所有这些"只是为了推导"的中间节点全部删掉，只保留有语义的节点：一个加法节点，左子节点是整数 1，右子节点是整数 2。括号节点也会被删掉——因为括号的作用在树的形状上已经体现了，(1+2)*3和1+2*3的 AST 结构天然不同，不需要一个额外的括号节点去标记。

为什么要在乎这个区别？因为后面的所有阶段都是对着 AST 工作的。语义分析遍历它、中间代码生成遍历它、报错的时候用它定位。AST 越干净，后面的代码越好写。如果你把语法树的冗余节点全留着，那你在做类型检查时就得写一堆"跳过这个节点、跳过那个节点"的判断，代码会迅速腐烂。

设计 AST 节点时有个经验：每个节点类型对应一种"有意义的操作"。二元运算、一元运算、整数常量、字符串常量、变量引用、赋值、函数调用、if、while、return、代码块。这些节点够用了。别一上来就设计出三四十种节点类型，等你真正需要时再加。我在第一个自研编译器里设计了太多节点，结果大部分从头到尾没被用过，纯粹增加了维护负担。

4. 语义分析：给每个名字上户口

AST 建出来之后，编译器手里有了一个结构清晰的树，但它对树上的内容还是一无所知。x = y + 1这棵树长得完全合法，可y到底存不存在？它是整数还是浮点数？如果是不存在的名字，这行代码就是个定时炸弹。语义分析的任务就是把这些信息补齐，让编译器对程序有真正的"理解"。

4.1 符号表和作用域链

符号表是语义分析的核心数据结构，说白了就是一张记录"名字 → 属性"的映射表。属性包括类型、种类（变量、函数、类型别名）、作用域层级、内存布局信息等等。

听起来简单，但真正的复杂度在作用域上。同一个名字x可以在全局是一个整数，在某个函数里是浮点数，在更内层的代码块里又是别的类型。要正确处理这种嵌套，符号表通常实现成一串哈希表，每进入一个作用域就压入一张新表，离开就弹出。查找时从最内层往外层逐张表查，找到第一个就停。

这个结构带来的一个经典细节叫变量遮蔽（shadowing）：内层的x会遮住外层的x，但外层那个x并没有消失，只是暂时查不到。所以你在弹出作用域时，必须确保外层那个定义还在。如果用一张扁平的表去存，遮蔽的名字会把外层覆盖掉，退出作用域后就没法恢复了。我在早期实现里就踩过这个坑，症状是"函数里的局部变量和全局变量同名时，函数结束后全局变量消失了"——非常诡异，查了好久才发现是符号表结构选错了。

还有一个容易忽略的点：先声明后使用还是可以先使用后声明？大多数静态语言要求先声明。但函数之间可以互相调用，这就产生了循环依赖。常见的处理方式是"两遍扫描"：第一遍只收集所有的顶层声明，把名字和签名登记进符号表；第二遍再检查函数体。这样函数 A 调用函数 B、B 又调用 A 就不会报"未定义"。这个技巧几乎所有的真实编译器都会用，值得记住。

4.2 类型检查的范围比你想的大也比你想的小

类型检查是语义分析里最有存在感的部分，但它做的事情比很多人想的要窄。

它检查的是：运算符两边的类型是否兼容（整数不能加字符串）、函数调用的实参类型和形参是否匹配、返回值的类型是否和声明一致、数组下标是不是整数、条件表达式是不是布尔类型。这些都是局部规则，每条规则只看一个节点和它的直接子节点。

它不检查的是：数组访问是否越界、除零、空指针、资源泄漏、并发竞态。这些需要运行时的信息，静态分析最多做保守的近似推断。这就是为什么类型正确的程序依然会崩——类型系统保证的是"不会出现某类错误"，而不是"不会出现任何错误"。

想清楚这个边界，你对类型系统的期待就会变得合理。静态类型不是什么都能拦，它的价值在于把一大批低级错误挡在运行之前，同时给优化器提供可靠的信息（知道x一定是整数，就可以放心地把x * 2优化成x << 1）。动态类型语言把检查推迟到运行时，换来的是灵活性和更少的样板代码，代价是错误暴露得晚、优化空间小。这是取舍，没有绝对的对错。

实现层面，类型检查通常是一个对 AST 的递归遍历，每个节点返回自己的类型，父节点根据子节点的类型做判断。碰到不匹配就记录错误并返回一个"错误类型"作为占位，避免错误级联——一个错误触发出十个错误提示，是新手编译器最典型的体验灾难。这个"错误类型"的设计技巧很实用，它能让错误传播在某一层停下来。

4.3 中间表示：为什么要"拍扁"

AST 是层次结构，非常适合做语义分析，但到了优化阶段就不太好用了。原因很实在：优化要处理的是"数据怎么流动"和"控制怎么跳转"，这两件事在树上表达得很别扭。

中间表示的做法是把树拍扁成一组线性的、每条只做一件事的指令。最经典的形式是三地址码：

t1 = b * 2 t2 = a + t1 x = t2

每条指令最多一个运算符，结果写到一个临时变量里。这种形式的好处是显而易见的：数据依赖关系变成了显式的"谁用了谁的临时变量"，控制流可以用标签和跳转来表达，任何一条指令都可以被单独看、单独改、单独删。

在拍扁的基础上，还会做一层基本块划分：把连续执行的、中间没有跳转的指令划成一个块。基本块内部是严格顺序的，块与块之间用跳转连接，整体形成控制流图（CFG）。这个结构是做绝大多数优化的基础——常量传播、死代码消除、循环优化，全都是在控制流图上跑的。

再往上一层是SSA 形式（静态单赋值）。它的规则是：每个变量只能被赋值一次。如果源码里一个变量被赋值多次，SSA 会把它拆成x1、x2、x3，然后在控制流汇合的地方插入一个特殊的phi函数来"选择"从哪个分支来的值。SSA 的好处是每个变量的定义点唯一，数据流分析变得极其简单。代价是需要在进入和离开 SSA 时做额外的转换。

新手阶段我建议先只做三地址码，别急着上 SSA。三地址码已经足够让你理解"中间表示是什么"和"为什么需要它"，而 SSA 的构造和销毁是一整套复杂机制，容易让你在还没搞懂优化在干什么的时候就被淹没。等你把常量折叠、死代码消除这些基础优化在三地址码上跑通了，再回头看 SSA，会发现它解决的问题非常清晰。

5. 优化和代码生成：从"能跑"到"跑得快"之间隔着什么

前面的阶段保证程序是对的，从优化开始，编译器才开始追求"好"。这一段的门槛明显更高，也更容易出问题，因为优化的正确性不再是"看起来对"，而是"变换前后程序的可观察行为完全一致"。这个约束比它听起来要严厉得多——你不能改变输出的值，不能改变输出的顺序，不能改变副作用发生的次数或时机。

5.1 常量折叠看着简单，其实处处是坑

常量折叠是最容易理解的优化：编译期能算出来的表达式，就别留到运行时算。x = 2 * 3 + 1直接变成x = 7。实现在三地址码上就是扫一遍，发现某条指令的两个操作数都是常量，就当场算出来，把这条指令替换成一个常量赋值。

同类优化还有常量传播（把已知的常量值替换到使用处）和死代码消除（删掉结果没人用的指令和永远执行不到的分支）。这三个通常配合使用，而且需要反复迭代——常量折叠可能产生新的常量赋值，进而触发更多常量传播，再产生更多折叠机会，直到不动点为止。

坑在哪里？第一个是副作用。x = f() + g()里如果f和g都有副作用，你绝对不能把它们"合并"或者重排。判断一个操作有没有副作用，需要编译器对每个操作都有明确的标记，这个标记漏一个就是 bug。

第二个是浮点数。0.1 + 0.2在编译期算出来和运行期算出来，结果可能不一样，取决于编译器的浮点模型和机器指令。如果你的语言要求严格一致，就不能随便折叠浮点运算，或者必须用和运行时完全相同的计算方式。这个细节很多手写编译器的人根本想不到，直到用户报"优化开着和关着结果不同"才发现。

第三个是溢出。整数溢出的行为在不同语言里定义不同。如果语言规定溢出是未定义行为，那编译器可以放心折叠；如果规定必须回绕，那折叠时就得模拟回绕语义；如果规定要抛异常，那编译期折叠出一个溢出就得在编译期报错。三种语义对应三种实现，写之前先想清楚你的语言要哪一种。

注意：做优化时我强烈建议留一个"关闭所有优化"的开关。一旦出现问题，先关优化看是否复现。这一步能瞬间把问题范围砍掉一半，是我调试编译器时用得最多的一招。

5.2 寄存器分配为什么难

目标代码生成里最硬的骨头是寄存器分配。CPU 的寄存器就那么十几个，而程序里的变量可能有几百个，你必须决定哪些变量在什么时候待在寄存器里，哪些被临时挪到内存（术语叫"溢出"）去。

这件事的难，在于它是NP 完全的。把它建模成图着色问题就很清楚了：每个变量是一个节点，如果两个变量在同一时刻都活着（一个已经定义、还没被最后一次使用），它们就冲突，连一条边。给变量分配寄存器，等价于给这张图着色，颜色数就是可用的寄存器数。图着色是经典的 NP 完全问题，所以现实中的解法全是近似的启发式算法。

最常用的启发式叫简化-溢出：先把度数小于 K（K 是可用寄存器数）的节点一个个从图里删掉，删的过程中压栈；删不动了，就挑一个度数最大（或者代价最低）的节点标记为溢出，强制删掉它、继续简化；最后把栈里的节点逐个弹出来染色。被标记溢出的变量，读写时绕着内存走，性能会掉，但至少程序是对的。

这里有个实践中的小经验：优先溢出循环里的变量，代价最高。同样是一次溢出，发生在循环体内会被执行成千上万次，发生在循环外可能只执行一次。所以启发式算法里通常会给节点加权重，权重正比于它所在的循环嵌套深度。这个调整对最终性能的影响很大，值得在实现时专门处理。

如果你的目标不是真实硬件而是一个虚拟机的字节码，那么寄存器分配这一步可以跳过——虚拟机的"寄存器"是无限的，你可以直接用内存地址。这也是为什么入门阶段我推荐先做字节码后端，把寄存器分配留到第二阶段。

5.3 指令选择本质上是模式匹配

指令选择要解决的问题是：给定一棵（或者一串）中间表示，怎么映射到目标机器的指令集上。比如a = a + 1，有的机器有专门的"自增"指令，一步搞定；有的机器没有，得用加载、加法、存回三条。

通用的做法是树模式匹配：把中间表示当成一棵树，把目标机器的每条指令也描述成一棵小树（或者一条模式），然后想办法用这些小树"覆盖"整棵大树。覆盖的方式不唯一，不同的覆盖组合对应不同的代价，所以还要算代价选最优。这就是所谓的动态规划树覆盖。

如果想快速入门，可以先用最简单的贪心策略：从上往下扫，遇到能匹配的模式就生成对应的指令。效果会比最优差一些，但跑通整个链路足够了。等你有余力了，再去补上代价模型和 DP。

这一层还有一个常被忽略的活儿：指令调度。生成的指令顺序会直接影响流水线的执行效率，有些指令之间需要等好几个周期，插几条无关指令进去就能填满空档。不过这个已经属于性能调优范畴了，新手阶段完全可以不碰。

6. 从零写一个四则运算编译器：一条能真正走完的路

理论讲了这么长，不动手全是空的。我给的路线是先写一个完整的解释器，再把它改造成编译器。这样你能在最短时间内看到一个能跑的结果，后续所有改造都是在这个能跑的基础上做增量。

6.1 目标砍到最小

第一个版本的规格我建议定成这样：

• 支持整数类型，一个类型就够
• 支持+ - * /和括号，优先级正确
• 支持变量声明和赋值
• 支持print输出表达式
• 支持if和while这两个控制流
• 出错时有行号，能指出大概位置

就这些。不要加字符串、不要加函数、不要加数组、不要加浮点。我见过太多人在第一阶段就把规格定得跟一门真语言一样，结果写到一半发现符号表要重写，前功尽弃。规格越小，跑通越快，正反馈越强。

6.2 分阶段验收清单

把整个工程切成五段，每段有明确的验收标准，跑通了才进下一段：

这个表格的价值在于：每一步都能独立验证。你在第二阶段发现 AST 结构不对，不用怀疑解释器的问题，因为解释器还没写。这种"问题被限制在一个阶段内"的调试体验，比一锅端要舒服一个数量级。

6.3 那些一定会撞上的坑

递归下降解析器的空指针问题。parse_expr里的 while 循环结束后，你得保证返回的节点不是空。有时候因为错误恢复的分支没写对，会返回None，然后上一层访问node.left就报错。防御性写法是每个 parse 函数在返回前检查一下。

除零的处理时机。如果你在解释器里直接做 Python 的除法，除零会抛 Python 的异常，堆栈信息全是解释器内部的。你需要在求值的那个节点上包一层判断，抛出你自己的错误、带上行号。这个小细节决定了你的报错信息是"ZeroDivisionError at line 42 in eval_binary"还是"第 42 行：除数不能为零"，体验天差地别。

负数的词法歧义。-5到底是"负号 + 5"还是"负数字面量"？我建议统一处理成"负号 + 5"，也就是让词法分析器只产出-这个记号，由语法分析器在 factor 层构造取负节点。这样a - -5也能正确解析，而把-5硬拆成字面量会让后面的一元运算处理变得很不一致。

错误恢复的位置同步。语法分析出错时，你得知道从哪儿继续。最粗暴的做法是跳到下一个分号。更精细一点的做法是跳过记号直到遇到一组"同步集合"里的记号（比如分号、右花括号）。不做这一步，一个语法错误会引发几十条连锁报错，用户根本没法看。

循环里的作用域。while循环体里声明的变量，每轮循环都应该是一次全新的声明。如果你的符号表没有在每轮循环开始时重置，变量会带着上一轮的值进入下一轮，行为就不对了。这个坑只有在你测"循环体里声明变量"这种边界情况时才会暴露。

7. 新手学编译原理，路上有几个常见的岔路口

最后说点方法论层面的东西。编译原理这门课的知识结构很特殊：理论部分（自动机、文法、数据流分析）非常"数学"，工程部分（写解析器、做优化）又非常"体力活"。两者节奏完全不一样，所以学习路径选错了，很容易出现"书看懂了但一行代码写不出来"或者"代码能跑但不知道为啥对"的情况。

7.1 经典教材为什么容易劝退

那本被反复推荐的经典教材，我承认它是权威，但它不适合作为第一本书。原因不在于它写得不好，而在于它的目标读者是"要设计编译器的人"，而不是"想搞明白编译器怎么回事的人"。它一上来就是形式化的自动机定义、子集构造的完整证明、LR 分析表的构造算法，这些内容你必须知道，但不必第一天就知道。

我的建议是分两条线走。主线跟着一个能出结果的教程走，边看边写，先把手感建立起来。辅线在遇到理论卡点时再去翻经典教材的对应章节，把它当工具书用，而不是从头读到尾。比如你在写词法分析器时搞不懂子集构造，就去翻那一章，看完立刻回来用代码验证。这种"带着问题去查"的方式，吸收率远高于"先啃完理论再动手"。

还有一类资源容易被忽略：看别人的小项目源码。找一个几千行的、完整的玩具编译器，把它从头到尾读一遍。你会发现很多教材里没讲的选择——为什么这里要用哈希表，为什么那个错误要单独处理。这些"工程上的默认做法"才是真正值钱的东西。

7.2 自动机理论要学到什么深度

这是新手最常问的问题之一。我的答案是：够用就行，别陷进去。

你需要掌握的深度是：知道正则表达式、NFA、DFA 三者是等价的，知道子集构造法能把 NFA 转成 DFA，知道 DFA 可以直接查表实现。这三条掌握了，词法分析这一关就过了。

你不需要掌握的深度是：能手工证明正则语言的泵引理、能从零推导 DFA 最小化算法、能背下 LR(1) 项目集的闭包规则。这些东西在理论考试里有用，在实际写编译器的前几年基本用不上。

判断标准很简单：当你发现自己在推导一个状态机，而不是在用它的时候，就该往回撤了。你写词法分析器的目的是切词，不是证明切词的理论可行性。状态图画出来了、代码能跑通了，就往前走，去写语法分析器。理论这块，等你有实际需求（比如要支持某种特别复杂的词法规则）时再回来补。

7.3 什么时候该去读工业级编译器的源码

工业级编译器的源码动辄几十万行，带着复杂的抽象和大量的性能优化，直接进去读的结果通常是"看得懂每个函数在干什么，但完全不明白它们为什么要这样组织"。这个体验非常挫败。

我给的时间点是：当你能独立写完一个完整的、支持控制流和函数的编译器，并且跑通了自己的测试用例之后。这时候你脑子里有了完整的链路图，知道每个阶段该产出什么，再去读工业级实现，才能看出"它为什么这么设计"——为什么它的中间表示要做那么多层，为什么它的错误处理要考虑那么多边界，为什么它的寄存器分配要分好几个 pass。

具体从哪儿切入？从测试用例和文档开始。先找一个能跑通的最小例子，把它的完整编译过程打出来，看到每个阶段的中间产物长什么样。然后顺着一条具体路径往下追，比如"这个常量为什么被折叠掉了"，追到对应的 pass 去读。这种"顺藤摸瓜"的读法，效率比从入口函数一路走读要高得多。

最后一个我自己吃过亏的地方：别在第一个编译器上追求完美。我在写第一个自研编译器时，花了两周纠结错误处理的消息格式，又花了一周优化符号表的数据结构，结果核心流程一直没跑通，整个项目烂尾了。后来重写的时候，我给自己定了死规矩：任何非核心功能一律先用最笨的办法实现，跑通再说。报错信息就一行字符串，符号表就用字典，优化一个都不做。那次三周就跑通了完整链路，后面所有改进都是在这个能跑的东西上做的增量。先有再优，这个顺序在编译器这个领域尤其重要，因为它的链路太长了，任何一环卡住，你都看不到最终结果。