第一次翻开Engineering a Compiler的概述章节我脑子里一直有个画面写了几百行代码按一下编译程序就跑起来了。中间到底发生了什么很多人会随口说一句“编译器把代码翻译成了机器码”。可这个“翻译”远没有听起来那么轻松——高级语言和机器码之间隔着的不只是词汇转换而是好几个性质完全不同的处理阶段每个阶段都在回答一个不同的问题。这篇笔记是我读“编译概述”部分的一份整理主要想聊聊几条主线编译器整体流水线、前后端为什么切分、中间表示为什么重要、后端要面对的三座山以及优化器的真实作用。适合还没系统读过编译原理、又不想一开始就被形式语言理论劝退的人参考。写编译器的人常说一句话所谓编译器就是“一种把一种语言翻译成另一种语言的程序”。但这句话的误导性在于它让人以为翻译过程是局部的、逐行替换的。实际上从源代码到目标代码的转化是一次典型的“语义鸿沟跨越”。在概述章节里作者反复强调的就是这件事不要试图一步跨过鸿沟要把跨越拆成一条流水线。1. 编译器不是“翻译官”而是一条多层流水线1.1 输入与输出之间的“语义鸿沟”有多大高级语言描述的是人的意图声明一个变量、调用一个函数、表达一个条件分支。目标机器码描述的是机器的动作把某个寄存器里的值移到另一个寄存器、把一个立即数加载到内存地址、根据标志位跳转到某条指令。看起来都是“让计算机做事”但两者之间没有一一对应的关系。举例来说源代码里写a b c * d这是一段非常自然的表达式。可机器码里没有“表达式”这个东西只有被拆碎的一条条指令。更关键的是编译器还需要知道a、b、c、d这些名字分别占用多少内存、存放在哪里、作用域从哪一行开始到哪一行结束。这种从“名字”到“地址”的映射高级语言里通常看不见机器码里又没有名字。两者之间的差异就是概述里反复说的“语义鸿沟”。面对这样的鸿沟不可能靠一个超大函数直接完成转换。书里给出的思路是把编译器看成一条流水线每个阶段只解决一个层面的问题先检查单词拼写再分析句子结构接着判断语句有没有意义然后把有意义的程序转成一个中间表示最后再针对具体机器做翻译和优化。每一级都只需要理解上一级的输出不需要关心整个程序的全部复杂性。1.2 分析阶段与合成阶段整条流水线的主干很多编译教材喜欢把编译器分成“分析”和“合成”两大部分这本也不例外。分析部分负责“理解源代码”输入是字符流输出是某种结构化表示比如语法树合成部分负责“根据理解写出目标代码”输入是中间表示输出是汇编或机器码。分析和合成之间通常还会插入一个“中间表示”它是前后端之间的接口。我整理了一张最典型的流水线表前端和后端的每一段职责一眼就能看清阶段主要输入主要输出核心追问词法分析字符流Token流哪些字符组成一个合法单词语法分析Token流抽象语法树这些词的组合是否构成合法结构语义分析抽象语法树带标注的树/符号表结构正确是否有意义中间代码生成带标注的树中间表示如何用更接近机器的指令描述它机器无关优化中间表示等价的中间表示能不能少算一点、早算一点代码生成中间表示目标指令序列每条操作应映射到哪条指令机器相关优化目标指令序列优化后的指令序列寄存器怎么分、顺序怎么排这张表我建议读者先记在心里因为后面所有章节都是在往这些格子里填细节。概述的价值就在这里在你还没接触那些复杂的算法之前先把地图画出来知道自己在哪要去哪。每个阶段在书里被称为一个“pass”。Pass这个词直译是“一遍”意思是编译器会一遍一遍地读取程序表示每次做一点加工。多pass看起来浪费因为要反复遍历中间结果但它的好处非常明显逻辑清晰、可复用、可测试。比如同一个前端可以接不同的后端同一个后端可以接不同语言的前端。如果某个pass只需做局部修改其他pass完全不用动。1.3 编译器还负责编排整条工具链很多人初学时会漏掉一件事简化到极致的“编译”命令背后其实不只是编译器在干活。源代码从文本变成可执行程序通常还要经过预处理、汇编、链接这几个环节。编译器更像是整条工具链的调度者它负责任务划分、加载配置、调用外部工具、处理中间文件。在概述部分作者把这些外围工作交代得很清楚。预处理负责处理宏展开、文件包含这类“文本层面”的事情汇编负责把汇编语言转成目标文件链接负责把多个目标文件和运行库拼在一起解决符号引用和地址重定位。很多人对“编译”的理解止步于“编译器”实际上可执行文件的生成依赖多个程序的协作。读到这里我最大的感受是编译器的边界不是天然的而是设计出来的。编译器不是非得包含哪些固定模块它是一组可以按需组合的pass集合。理解了这一点后面读各种优化pass时就不会困惑为什么一种编译器可以做某种转换另一种编译器却选择不做。2. 前端与后端的切分中间表示才是承重墙2.1 没有中间表示复杂度会失控概述部分有一张图让我印象很深语言侧有一堆特性机器侧有一堆差异如果每个语言和每个机器之间都建立直连通道那么实现个数会变成语言数乘以机器数。这个数量一旦多起来维护成本就不是线性增长而是爆炸式增长。中间表示就是打断这种“两两直连”的枢纽。前端只负责把源代码变成中间表示后端只负责把中间表示变成机器码。这样一来新增一种语言只需多写一个前端新增一种机器只需多写一个后端整体复杂度从“乘法”变成“加法”。用工程上的话讲中间表示是一个“契约”。前端承诺只要我输出的中间表示满足约定后端就一定能把它翻译成目标代码。后端承诺只要输入的中间表示符合约定我就能高效产生代码。这种契约让前后端可以独立开发、独立测试。这大概是编译器工程里最重要的模块化思想。2.2 常见IR形态树、线性指令、SSA各有用处中间表示不是只有一种概述会介绍好几种形态。它们没有绝对的好坏只有是否适合当前处理阶段。最直观的两种是抽象语法树AST和三地址码稍微进阶一点的是SSA。我整理了一张对照表方便理解IR形态形态特征典型用途直观感受AST树形结构前端分析和语义检查保留了源码结构适合做高层层面的检查三地址码线性指令序列中端到后端的过渡每条指令最多一次运算贴近机器DAG有向无环图公共子表达式合并可以把重复计算合并成一个节点SSA三地址码变体优化器内部表示每个变量只赋值一次依赖关系清晰AST是最接近源代码的表示它把表达式、语句、声明组织成一棵树。语法分析做完之后AST非常“贴人”适合做类型检查、作用域分析、错误提示。但AST离机器太远里面充满了嵌套表达式不方便直接映射成指令。三地址码则把嵌套表达式拆散成一条条简单指令。比如a b c * d会被拆成t1 c * d和a b t1两条指令。每条指令最多只做一个运算非常接近真实机器的能力。这样做的好处是后面做寄存器分配、指令选择时每条IR都有明确的“操作”和“操作数”编译器不需要再解析一整棵表达式树。SSA是很多人读编译教材时的第一道坎。它的核心特点是每个变量只赋值一次后面的赋值会引入一个新版本例如x1 ...、x2 x1 1。为什么这样设计因为它让“某个位置的值到底从哪来”变得极其显式。优化器在分析数据依赖时不需要在代码里来回搜索看着变量版本号就能知道值的来源。2.3 IR不是一种走到黑还要做提升和降低真正工程中的编译器通常会使用多个层次的IR而不是全程只用一个。源语言侧会用高层IR保留数组、结构体、函数调用等信息越接近后端IR就会越“低层”越来越显式地表达寄存器、内存、控制流跳转。把IR从高往低转的过程叫“降低”。降低会让表示更加贴近机器但也意味着丢失一部分语言语义。比如一个函数调用在高层次IR里可能就是一条call指令到了低层次IR可能就要展开成参数传递、保存寄存器、生成调用指令、恢复寄存器等一系列操作。我自己的经验是很多前端开发者读到这里会有点不习惯为什么不能直接把AST翻译成汇编原因在于AST里嵌套结构太多、语言特征太多直接翻译会让“指令选择”和“优化”都变得非常吃力。只有经过降低和转换所有的程序都呈现为一种统一、规整的结构时优化器才好在上面做分析。所以中间表示不只是“前后端之间的一个夹层”它实际上是编译器架构中最承重的那堵墙。理解了IR就理解了为什么编译器可以有那么多独立的pass也就能理解为什么现代编译器能通过“共享中间表示”同时支持大量语言和大量目标平台。3. 词法、语法、语义三个关卡各自在审什么3.1 词法分析先判断“单词拼写”编译器读入的原始输入是字符流也就是一个很长的字符串。词法分析要做的事就是把这个字符串切成一个有意义的单词序列语言学里叫“词素”编译器里叫“Token”。Token一般会把类型也标注出来这是一个标识符、一个数字字面量、一个运算符、还是一个左括号。拿a b c * d来说词法分析输出的Token可能是这样的标识符a、赋值运算符、标识符b、加法运算符、标识符c、乘法运算符、标识符d。这一步只看词本身完全不管a和b是什么类型也不管和*谁优先。词法分析通常用正则表达式来描述合法Token再用有限自动机来高效识别。有限自动机的直觉是一张带状态的跳转表读一个字符判断当前状态如果走到接受状态就说明识别出了一个Token。它很像一个超高速的“拼写检查器”只判断“这个单词拼得对不对”。为什么要单独拆分一个词法阶段因为正则语言的处理可以高度自动化且非常快。如果不用Token流直接让语法分析去处理字符语法分析会变得极其笨重。拆出来之后错误定位也更友好——词法错误可以直接告诉程序员“第几行第几列出现了一个无法识别的字符”而不是模模糊糊地说某段语法有问题。3.2 语法分析再判断“句子结构”有了Token流之后语法分析要判断这些Token的组合是否符合语言的结构规则。这个规则是用上下文无关文法描述的常见的形式包括递归下降、移进-归约等算法。语法分析的输出是一棵抽象语法树树里的嵌套结构直接反映了表达式的优先级和结合性。一个经典例子是a b * c。如果语法分析直接按从左到右的顺序处理会错误地算出(a b) * c。语言的文法会规定乘法的优先级高于加法所以最终生成的语法树应该把b * c先作为一棵子树再接在加法下面。括号也可以改变结构语法树里(a b) * c就是另一棵完全不同的树。这一层主要抓的是“句子通不通”是不是少了右括号是不是有个操作符后面没跟操作数是不是if语句后面没跟条件。语法错误可以在运行任何语义判断之前就被发现。我自己读这里时觉得语法分析的困难在于文法设计既不能太宽导致接受不合法的句子也不能太窄导致合法程序被拒绝。很多人在学习时会纠结于递归下降和移进-归约算法其实概述阶段不需要进入细节。需要建立的概念是语法分析是在Token流之上构建一棵有结构的树这棵树把“线性输入”变成了“分级嵌套”这正是后续语义分析和代码生成需要的形态。3.3 语义分析判断“这句话有没有意义”程序语法正确不代表它有意义。x y 1在语法上完全合法但如果x或y从未声明过那么程序就是错误的。语义分析负责捕捉这些“结构正确但含义可疑”的问题。语义分析的核心工作至少包括三块符号表管理、作用域解析、类型检查。符号表记录每个标识符的类型、声明位置、作用域等信息作用域解析负责回答“这里的名字x到底指向哪个声明”类型检查负责验证操作数的类型是否符合运算符的要求。用一个例子说明int x; x x 1词法、语法、语义都通过因为x已声明且是整数整数加整数赋给整数没问题。但如果写成int x; x x str语法树依然能生成语义分析却会指出类型不匹配。类型错误是语义层最常见的错误之一。语义分析通常直接在AST或带标注的树上进行。它能回答程序里各个名字的含义比如“这里的变量a是外层函数的那个a还是内层代码块新声明的那个a”。这部分工作也为后面中间代码生成打基础因为生成代码需要知道每个变量占用多少空间、是什么类型、从哪加载。3.4 三个层次分开的根本原因把复杂度切碎为什么编译器不能一次性生成目标代码而要分三关来审一个重要原因是错误诊断的质量。词法错误说“非法字符”语法错误说“缺右括号”语义错误说“类型不匹配”。每一层只需要在一类约束上做检查因此错误定位又快又准。另一个原因是复用性。同一个语法分析器可以服务于多种语义规则同一个语义分析器也可以接不同的代码生成后端。如果所有检查全部混在一起任何一个小需求的改动都可能引发连锁调整。我自己在写小型编译Demo时体会最深的是把三个阶段分开之后调试的思维负担大大降低。词法阶段错了就盯着Token流看语法阶段错了就盯着语法树看语义阶段错了就看符号表和类型标注。你不会在成千上万行字符里漫无目的地寻找错误。4. 指令选择、寄存器分配与指令调度后端的三座山4.1 指令选择IR中的“一句话”该翻译成哪条机器指令进入后端编译器面对的问题从“理解程序”变成了“让程序跑得更快更稳”。中间表示里的一个“加法操作”可能对应目标机器的很多种实现方式可以是两个寄存器相加可以是一个寄存器加一个立即数也可以是在一次内存访问里完成偏移量计算。指令选择要做的就是为每段IR找到代价最小的一种映射。问题在于机器指令集往往存在大量语义重叠的操作方式。这时不能只看“能否实现”还要看“哪种实现更合理”。有些复杂指令看起来很高级但执行周期更长有些简单指令组合起来反而更快。指令选择本质上是一个模式匹配加代价计算的问题在概述章节里用“树覆盖”这个概念来描述。一个很实际的理解方式是后端不是“一句IR对应一句汇编”的查表器。它更像一个施工队看到一张图纸必须决定是用预制件拼装还是现场浇铸。不同决策会影响建筑速度也就是程序的运行性能。4.2 寄存器分配所有人都想住单间但房间有限目标机器上的物理寄存器通常只有十几个到几十个而中间表示里的“临时变量”数量可能成百上千。如何把这些临时变量映射到物理寄存器就是寄存器分配问题。概述里介绍了一个非常经典的处理框架把变量当作图里的节点如果两个变量在某个时刻同时存活也就是都还可能被后续代码使用就在它们之间连一条边。目标变成“用有限数量的颜色寄存器去给这个图染色并保证相邻节点不能用同一种颜色”。这就是“图着色寄存器分配”的直觉。当颜色不够时一些变量必须被“溢出”到内存。这意味着需要额外的加载和保存指令程序性能会受到影响。寄存器分配的难点因此不是一个纯粹的图论问题而是在“能用多少个寄存器”和“多产生多少存取指令”之间找平衡。我读到这里才真正意识到普通程序员写汇编时可以针对手头代码“见招拆招”但编译器必须在整段程序的全局范围做决定。它看不到运行时的数据只能通过活跃性分析来判断哪些值必须保留。这个决策的质量直接影响最终程序的运行速度。4.3 指令调度排列顺序不是小事现代CPU并不是严格按程序顺序一条一条执行的。它有流水线、乱序执行、多发射机制。指令序列的顺序会影响CPU能否有效并行、是否会因为等待前一条指令结果而停顿。指令调度的目标是调整指令顺序在不改变程序语义的前提下把相互独立的指令放到一起让CPU的执行单元尽量忙碌。这和“手工优化”很像比如某个寄存器要等上一次运算完成才能用中间可以穿插几条无关的指令把等待时间隐藏起来。需要注意的是调度高度依赖于具体机器的微架构。不同CPU的流水线深度、乱序窗口大小、访存延迟都不一样。这就是为什么“机器相关优化”只能交给后端前端和通用IR阶段很难承担这个工作。读到这一节我理解了为什么编译器领域常说后端不是把IR机械翻译成汇编而是一台充满权衡的资源调度系统。4.4 后端为什么是编译器里真正难啃的部分前端的成功标准相对清晰能正确理解语言、能给出好错误信息。后端的成功标准则非常模糊既要正确还要快、要省、要稳。指令选择、寄存器分配、指令调度三者互相影响改任何一个都会牵扯另外两个。许多初学编译的人会低估后端觉得“反正就是查表翻译”。实际上现代编译器里后端往往是最庞大、最复杂、最依赖工程经验的部分。概述不会教你怎么实现一套工业级的后端但会反复告诉你后端的问题最终都是“在有限资源下做最优化决策”的问题。读到这里我对“编译器是理论学科还是工程学科”有了新的理解前端背后有成熟的形式语言理论后端则需要大量试验、测量、启发式策略。理解这个区别对于你决定往哪个方向深入学习很有帮助。5. 优化器到底在优化什么不变式、数据流与代价模型5.1 优化的前提是“语义等价”优化器听上去很高大上但它有一个铁律在程序可观察行为不变的前提下减少程序运行所需的某种资源。可观察行为包括程序的输出、对外部状态的修改、以及程序的终止与否。一个优化如果让程序输出发生变化那就不是优化而是bug。这意味着优化器不是想怎么改就怎么改。它的每一个变换都必须有“正确性论证”。比如常量传播如果分析得出某个变量在某个位置总是固定值就可以用这个值替代变量读取这种替换是安全的因为它不影响任何可观察结果。一个常见误区是觉得优化器做的变换越多越好。实际上静态编译器看不到程序的真实输入只能做保守分析。很多判断“不知道有没有影响”的情况下正确的做法是什么都不做。优化器最怕的不是没优化到位而是错误地优化导致程序行为改变。5.2 基于数据流分析做全局判断绝大多数经典优化都以数据流分析为基础。所谓数据流分析是在程序的中间表示上计算一些事实比如“这个变量的值可能来自哪里”“这个变量在某个点之后还会不会用到”。举两个最直观的例子。第一个是常量传播假设有一段代码是k 42; z k 1数据流分析发现k在这两行之间没有被修改过那么完全可以把z k 1换成z 43。第二个是死代码删除如果一个赋值语句的结果在后续代码里永远不会被读取而且这个赋值本身没有副作用那么这条语句就可以被删掉。这两类优化都需要准确知道“值的流向”也就是一群定义-使用关系。数据流分析听起来抽象其实很像“程序内部的信息八卦”某个变量定义后一路传给了哪些使用点中途是否有别的赋值阻碍了传递。概述阶段不需要实现这些算法但明白它们的输入输出对理解优化器大有帮助。5.3 从局部到全局再到循环和跨函数优化器通常分层次做变换。局部优化针对一个基本块也就是没有分支的直线代码全局优化针对整个函数范围的控制流图更高层面的优化还会专门盯着循环做因为程序的大部分运行时间都集中在循环里。常见的优化手段包括常数折叠、代数化简、公共子表达式消除、循环不变量外提、循环展开、函数内联等。每个优化都有自己的适用场景和代价模型。循环不变量外提指的是如果某个计算在循环体内每次迭代结果都一样就把它挪到循环外面只算一次。这看起来很明显但编译器必须证明它“每次都一样”还要确认这个改动不会改变循环里的其他行为。函数内联则是用空间换时间把函数体复制到调用点去掉了调用开销但可能导致代码膨胀。优化器通常需要预设阈值决定多大函数值得内联。读到这里你会发现优化器本质上是一个“带预算的决策者”。它永远在问这个变换值不值得做做了会不会在另一个维度上变差5.4 优化不是免费的午餐收益要付成本很多教程把优化说得像“白捡性能”实际工程里优化是有代价的。代价之一是编译时间优化越多编译越慢大型项目里这个差距非常明显。代价之二是代码体积一些优化会增加指令数量比如循环展开会让可执行文件变大。代价之三是调试体验优化后的代码位置和源代码位置很难一一对应调试时变量可能被优化没、行号可能错位。这就是为什么实际项目里Debug版本通常会关闭大部分优化Release版本才开激进优化。优化器还面临一个很现实的问题它必须在“静态可知信息”里做决定。编译器没有运行时profile数据只能靠分析和启发式。有些优化在某类程序上收益明显在另一类程序上反而有害。工业级编译器通常会提供不同优化级别让用户根据场景取舍。这也是我读完概述后对“优化”二字祛魅的过程优化不是魔法而是一场有成本的工程权衡。6. 读完概述后我刷新掉的几个认知6.1 “编译器”这个词比我想象的宽泛得多以前说到编译器我只会想到“把高级语言变成机器码”。读完概述才发现编译器是一整套“把一种结构化文本变成另一种结构化表示”的方法论。正则表达式、有限自动机、语法分析器、符号表、类型检查这些技术在IDE补全、代码跳转、静态检查、配置解析、模板引擎、网络协议分析里到处都在用。甚至我平时写工具时用到的很多“解析库”本质上都是编译器前端的思想。理解了AST和Token流之后再看到某个复杂的配置校验逻辑我会本能地把它拆成“先词法再语法再语义”三个层次。这套思维方式的复用价值其实不亚于编译器本身。6.2 编译器和解释器的边界是模糊的很多初学者会问“编译器和解释器到底有什么区别”。概述读完之后我心里有了一个更准确的答案它们不是两种绝对对立的技术路线而是“翻译时机”和“执行方式”的连续光谱。最传统的编译器把程序一次性翻译成机器码然后交给硬件直接执行。解释器则一边读源程序一边执行似乎不需要单独的翻译阶段。但现代运行时里很多解释器会把热点代码在运行时编译成机器码再执行这种“即时编译”本质上也是一种编译器。反过来很多编译流程里也有类似解释器的东西比如在普通代码生成之前用解释方式直接运行IR来做常量折叠。所以再纠结“这个是编译器还是解释器”意义不大。更有用的思考方式是问“这个程序经历了哪些表示转换”和“每种表示转换的目标是什么”。这是概述给我的一个很重要的方法论。6.3 给后来读者的几条读书建议如果你正准备精读这本编译教材或者只是想把编译基础补起来我有几条实际建议。第一先把第一章的流水线图画明白别急着啃正则表达式和文法推导。搞清楚每个pass的输入输出整个知识框架就立住了。第二尽量动手写一个小的前端Demo哪怕只支持最简单的表达式也会让你对“Token流”“语法树”“符号表”的理解完全不同。第三遇到复杂算法时不要直接背步骤先问三个问题这个问题要解决什么冲突资源限制是什么最朴素的暴力解法是什么。带着这三个问题去读会顺利很多。我自己读这个概述部分的最深体会是编译器不是把“复杂度”消灭而是把“复杂度”拆碎再用清晰的结构去驾驭它。每读一章都像在原先模糊的机器上安了一块新的透镜。如果你也打算精读这本书我建议别急着翻后面的章节先把概述里的流水线用自己的话重新画一遍标清楚每个阶段的输入、输出、错误类型和主要约束。画完之后再往下走你会发现后面那些看上去繁复的算法都有了一个明确的位置可以安放。