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。分层之后每种语言只需要写一个前端把源码统一翻译成一种中间表示每种平台只需要写一个后端把中间表示翻译成自己的机器指令。工作量降到 NM。这个思路在工业界的价值极大。你家公司如果同时要支持三种前端语言、两种后端芯片分层和不分层的工作量差了三倍。而且中间表示这一层做得越规范跨语言复用和跨平台移植的成本就越低。不过这里有个新手常见的误解以为中间表示只有一种标准形态。实际上不同编译器选择的中间表示差别很大有的是三地址码有的是带基本块和控制流图的 SSA 形式有的干脆直接用树。它们之间也不是谁替代谁的关系很多编译器会同时维护好几层中间表示逐层降低抽象程度。你在学习时先掌握三地址码这种最朴素的形态就够了它的结构足够简单能让你把注意力放在如何表达计算和控制流这件事上而不是被各种表示形式绕晕。1.3 编译器和解释器的界线其实很模糊新手很容易把编译器和解释器当成两个对立的东西。教科书上的定义是编译器把源程序整体翻译成目标程序解释器逐条读入源程序并直接执行。这个定义没错但它把现实简化得过于干净了。我举个最直观的例子。很多语言的执行引擎是先编译成一种中间字节码再由虚拟机解释执行。这算编译器还是解释器两样都算。字节码的生成过程就是正经的编译只不过目标不是硬件指令而是虚拟机指令虚拟机的执行过程就是正经的解释。再往上一层如果虚拟机在运行时发现某段代码反复执行就把它即时编译成本地机器指令那这就是JIT 编译编译和解释在同一套系统里循环发生。理解这一点对学习的好处是你不必纠结我写的是编译器还是解释器因为从零写一个编译器最好的入门形式恰恰是写一个解释器。你先把 AST 直接解释执行跑通了整条链路再去考虑把它降级成中间代码、再生成目标代码。这种先跑通、再优化的路径比一上来就死磕寄存器分配要现实得多也更容易获得正反馈。我在带新人的时候第一周的目标永远是能跑出一个结果而不是能跑出一个高性能的结果。2. 词法分析把字符流切成有意义的词词法分析是整个编译器里最简单的一环也是最容易让人轻视的一环。说它简单是因为它的理论模型很成熟正则表达式、有限自动机这些东西几十年没变过说它容易被轻视是因为很多人觉得切词有什么难的按空格和符号劈开不就完了。真动手写就发现if (a1) x1;这一行里必须是一个记号而不是两个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 fToken({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:i2] 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_termparse_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。括号节点也会被删掉——因为括号的作用在树的形状上已经体现了(12)*3和12*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 完全问题所以现实中的解法全是近似的启发式算法。最常用的启发式叫简化-溢出先把度数小于 KK 是可用寄存器数的节点一个个从图里删掉删的过程中压栈删不动了就挑一个度数最大或者代价最低的节点标记为溢出强制删掉它、继续简化最后把栈里的节点逐个弹出来染色。被标记溢出的变量读写时绕着内存走性能会掉但至少程序是对的。这里有个实践中的小经验优先溢出循环里的变量代价最高。同样是一次溢出发生在循环体内会被执行成千上万次发生在循环外可能只执行一次。所以启发式算法里通常会给节点加权重权重正比于它所在的循环嵌套深度。这个调整对最终性能的影响很大值得在实现时专门处理。如果你的目标不是真实硬件而是一个虚拟机的字节码那么寄存器分配这一步可以跳过——虚拟机的寄存器是无限的你可以直接用内存地址。这也是为什么入门阶段我推荐先做字节码后端把寄存器分配留到第二阶段。5.3 指令选择本质上是模式匹配指令选择要解决的问题是给定一棵或者一串中间表示怎么映射到目标机器的指令集上。比如a a 1有的机器有专门的自增指令一步搞定有的机器没有得用加载、加法、存回三条。通用的做法是树模式匹配把中间表示当成一棵树把目标机器的每条指令也描述成一棵小树或者一条模式然后想办法用这些小树覆盖整棵大树。覆盖的方式不唯一不同的覆盖组合对应不同的代价所以还要算代价选最优。这就是所谓的动态规划树覆盖。如果想快速入门可以先用最简单的贪心策略从上往下扫遇到能匹配的模式就生成对应的指令。效果会比最优差一些但跑通整个链路足够了。等你有余力了再去补上代价模型和 DP。这一层还有一个常被忽略的活儿指令调度。生成的指令顺序会直接影响流水线的执行效率有些指令之间需要等好几个周期插几条无关指令进去就能填满空档。不过这个已经属于性能调优范畴了新手阶段完全可以不碰。6. 从零写一个四则运算编译器一条能真正走完的路理论讲了这么长不动手全是空的。我给的路线是先写一个完整的解释器再把它改造成编译器。这样你能在最短时间内看到一个能跑的结果后续所有改造都是在这个能跑的基础上做增量。6.1 目标砍到最小第一个版本的规格我建议定成这样支持整数类型一个类型就够支持 - * /和括号优先级正确支持变量声明和赋值支持print输出表达式支持if和while这两个控制流出错时有行号能指出大概位置就这些。不要加字符串、不要加函数、不要加数组、不要加浮点。我见过太多人在第一阶段就把规格定得跟一门真语言一样结果写到一半发现符号表要重写前功尽弃。规格越小跑通越快正反馈越强。6.2 分阶段验收清单把整个工程切成五段每段有明确的验收标准跑通了才进下一段阶段交付物验收标准常见卡点一词法分析器输入a 1 2;能打出 6 个带位置的记号双字符运算符被切开、行号错位二语法分析器能打出1 2 * 3的 AST且乘法在树的深层左递归导致栈溢出、优先级写反三解释器print 1 2 * 3;输出 7递归求值时运算顺序错、除零崩掉四控制流while循环能正确终止if分支走对循环条件求值位置错、跳转标签重复五中间代码 后端同一段源码走中间代码路径输出一致临时变量编号冲突、基本块划分错这个表格的价值在于每一步都能独立验证。你在第二阶段发现 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 去读。这种顺藤摸瓜的读法效率比从入口函数一路走读要高得多。最后一个我自己吃过亏的地方别在第一个编译器上追求完美。我在写第一个自研编译器时花了两周纠结错误处理的消息格式又花了一周优化符号表的数据结构结果核心流程一直没跑通整个项目烂尾了。后来重写的时候我给自己定了死规矩任何非核心功能一律先用最笨的办法实现跑通再说。报错信息就一行字符串符号表就用字典优化一个都不做。那次三周就跑通了完整链路后面所有改进都是在这个能跑的东西上做的增量。先有再优这个顺序在编译器这个领域尤其重要因为它的链路太长了任何一环卡住你都看不到最终结果。