编译原理核心：从词法分析到目标代码的完整流水线

1. 源程序到机器码编译器内部是怎么样的流水线我第一次接触编译原理第一章时心态和大多数人一样不就是把代码翻译成机器能懂的指令吗有什么好学的。直到我真正在终端里执行一条编译命令看着屏幕上唰唰刷过一长串警告和报错才开始意识到这段从.c或.java到可执行文件的路程远没有想象中那么简单。编译器的本质确实是一个翻译器。但它不是那种拿着字典逐词翻译的翻译器而是一条分工明确、层层递进的流水线。大多数经典教材在第一章就会把这条流水线完整铺开通常包含六个阶段词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。你可能有疑惑为什么不能一次性把源文件处理成机器码非要拆成这么多步骤答案其实和我们写大型项目时要拆模块是一个道理。一次完成所有事情听起来高效实际上会让每一步的逻辑纠缠在一起一个字符的偏差都可能让错误来源完全不可追踪。分阶段之后每个环节只关心一件事词法分析只管把字符变成词语法分析只管把词拼成结构正确的句子语义分析只管检查这些句子是否说得通各司其职任何一步出错都能快速定位。1.1 六个阶段不是六个工具而是一个流程你可以把编译过程想象成工厂里加工一个金属零件。源程序是原材料先被切割成合适大小的毛坯词法分析再被锻造成接近成品的形状语法分析然后由质检员检验内部结构是否合格语义分析接着转成一种便于运输和再加工的中间形态中间代码经过精加工打磨代码优化最后成型为适配特定机床的成品零件目标代码生成。词法分析读入的是字符序列比如你写了一个int age 25;它会把这一串字符拆成int、age、、25、;这样的记号也就是 token。这些记号就像自然语言里的单词。语法分析接着处理这些单词判断它们组织在一起是否符合语言规定的句子结构。语义分析再进一步确认这些结构是否有意义比如age到底有没有被声明、给它赋一个字符串是否合理。中间代码生成是为后面两步做准备的。它把一个源程序转换成一种和具体机器无关的表示常见的是三地址码。这样一来代码优化可以在不同平台上复用同一套逻辑而不必针对每一种芯片重新写一套。优化做完之后最后一步目标代码生成才会针对具体的处理器架构把中间代码转成汇编或机器指令。1.2 编译与解释的边界其实很模糊第一章里几乎必提编译和解释的区别。教科书上的经典说法是编译器一次性把源代码翻译成目标程序然后独立运行解释器则是一行一行读入、执行不产生独立的可执行文件。这个说法没错但它容易给人造成一种错觉——编译和解释是非此即彼的两条路。实际工程里这条边界已经越来越模糊。很多主流开源运行时采用的是混合策略。比如某些语言先把源代码编译成字节码这种中间表示再在运行时解释执行再进一步热点代码还会在运行过程中被动态编译成机器码。你很难说它到底是编译器还是解释器因为它们已经变成了一个流程里的不同环节。第一章的定位是全景导览它不需要你把六个阶段全部吃透但要让你建立一张完整的地图知道编译器在整个软件工具链里占据什么位置知道一个程序从文本到可执行文件要经过哪些关卡。这张地图一旦建立后面每一章再深入细节时你就不会迷路。这是第一章最重要的意义也是很多初学者最容易忽略的价值。2. 词法分析正则表达式是如何变成能扫描代码的程序如果说编译流水线的第一步是词法分析那这一步要解决的问题其实非常朴实如何从一长串字符里又快又准地把单词切出来。大家平时写代码时都很自然的空格、换行、括号分隔在编译器看来都只是一个普通的字符没有任何先天意义必须靠规则来识别。我第一次手写词法分析器时以为这不过是个字符匹配的活儿真正动手才发现里面全是细节。比如你怎么区分关键字int和变量名integer怎么判断123abc是合法的还是非法的更麻烦的是像这种两个字符的操作符扫描器扫到时是直接把它当作一个记号结束还是应该再往后看一眼确认它是不是的一部分2.1 记号、模式与词素三个容易混淆的名词讨论词法分析绕不开三个词token记号、pattern模式、lexeme词素。三者的区别是第一章里必考的概念也确实是初学者的重灾区。词素是源程序中实际出现的字符序列比如你写了个变量名yourScore那yourScore这个字符串就是一个词素。模式是描述一类词素规则的描述比如“以字母开头、后跟字母或数字的字符串”。记号则是给这一类词素贴上的分类标签可以理解为“标识符”“关键字”“整数常量”这样的类型名称。用自然语言类比的话词素是具体说出的某个词模式是这个词在词典里的词性规则记号就是这个词的词性本身比如“名词”或“动词”。词法分析器的任务就是读入一个个字符把它们组装成词素再根据规则把它归入某个记号类型。大多数教科书写“词法分析器返回记号”但严格来说它返回的不只是一个类型。现实中返回的通常是一个包含了类型和属性值的结构类似(ID, yourScore)其中属性值保留了这个词素本身的信息供后续的语法分析和语义分析使用。2.2 从正则表达式到有限自动机的直觉理解词法规则用什么来描述第一章会告诉你答案是正则表达式。因为大部分词法结构比如标识符、数字、字符串字面量都属于正则文法能够描述的范畴不需要更强的表达能力。但正则表达式只是一个描述规则计算机没法直接拿正则表达式去扫描字符。真正执行扫描任务的是有限自动机。你可以把它想象成一台只有几个状态的小机器每次读一个字符根据当前状态和输入字符决定跳到哪个下一个状态。如果最终停在接受状态说明输入字符序列符合规则。从正则表达式到有限自动机的转换教材里会花不少篇幅讲算法细节但第一章通常只要求你建立直觉。简单来说正则表达式里的a|b在自动机里对应一个分叉a*对应一个可循环回跳的圈ab对应依次转移的两条边。读到这里你也应该能感受到词法分析器不是靠一个巨大的 if-else 去逐字符硬比而是有了一套相对优雅的数学模型。实际实现时很多教学项目为了简单会直接用正则库或者手写分支逻辑但工业级编译器里的词法分析器几乎都是基于确定的有限自动机自动生成的这也是第一章反复强调这部分内容的原因。2.3 词法错误为什么一般捡软的捏词法分析阶段能检测的错误非常有限。它看到一段字符不符合任何词法模式时通常只会报一个“非法字符”之类的错误。它不会知道这个错误是程序员手抖打错了一个字符还是拼写了一个不在语言里的新关键字。工业编译器对词法错误的处理策略普遍是“尽量恢复继续向后”。最常见的做法是报告出错位置和异常字符然后跳过这个字符继续扫描。这样做的原因是词法层面的错误通常不影响后续大范围代码的解析犯不着因为一个字符就让整个编译过程终止。等你学到后面的语法分析就会发现那个阶段的错误恢复策略要复杂得多。我写第一个词法分析器时犯过一个很经典的错误遇到了无法识别的字符后直接终止了整个编译流程。结果一个输入文件里只要有一个中文标点混进了英文代码后面所有代码都不会继续编译报错信息也只有一句排查起来极其痛苦。后来我重新读第一章关于错误恢复的描述才意识到一个健壮的分析器应该像扫雷一样碰到一颗雷记下位置然后继续把整片区域扫完把所有雷的位置都标记出来而不是第一颗雷就收工。3. 语法分析上下文无关文法决定了一门语言的骨架过了词法分析这一关编译器手里有了一份记号流但它还只是一个个孤立的单词。接下来要做的事情是把这些单词组织成符合语法规则的句子。这就是语法分析在编译流程中它承担的是建立结构骨架的任务。你可以把语法分析器想象成一个严格的语文老师它不关心这个词是什么意思只关心你说的话是不是符合语法规范。主谓宾顺序对不对从句是不是正确嵌套括号是不是一一配对。如果这些基本结构都乱了它就直接给你判不合格。而判断的标准不是一份几千页的规则手册而是一套叫上下文无关文法的数学体系。3.1 产生式与推导树语法分析器在猜什么上下文无关文法的核心是产生式形如表达式 → 表达式 项 | 项。读作“一个表达式可以是两个表达式的加法也可以只是一个项”。箭头左边的是非终结符它像一个抽象的概念类别右边的可以继续展开成其他非终结符也可以展开成词法阶段已经识别出的终结符也就是实际的单词或符号。语法分析的过程本质上就是根据这些产生式规则从起始符号开始不断展开尝试匹配输入的记号流。每一次成功匹配都会生成一棵语法树也叫推导树。树的根节点是起始符号叶子节点是那些终结符内部节点则是非终结符。我当初理解推导树时脑子里用的是做菜谱类比。非终结符就是“一道菜”产生式就是“这道菜由哪些材料配比而成”。比如“鱼香肉丝 → 肉丝 木耳 调料”然后“肉丝 → 猪肉 刀工处理”。一棵语法树就是一张完整的菜谱分解图从成品一路拆到具体食材和操作步骤。为什么要搞这么复杂的一棵树因为后续的语义分析、代码生成都需要知道“这个加法表达式在这个 if 语句的什么位置”“这个函数调用的实参列表对应哪几个语法成分”。有了树形结构一切位置关系都可以通过父子节点、兄弟节点的关系来描述编译器就不再面对扁平的一串记号而是有了空间层次感。3.2 自顶向下与自底向上两种策略的取舍语法分析器的构建策略大的方向上分成两类自顶向下和自底向上。第一章通常只是抛出一个概览但理解它们的差异能帮你在后面学 LL 和 LR 分析时少走很多弯路。自顶向下分析是从文法的起始符号出发不断做产生式的展开去匹配输入的记号流。它的思路是“我猜测当前最左边的非终结符应该展开成哪个右侧式然后验证猜得对不对”。实现起来相对直观也容易手工编写但面对某些文法会产生回溯甚至死循环。自底向上分析走的是另一条路。它从输入记号流出发不断把已扫描到的记号序列归约成等价的非终结符逐步收缩到文法的起始符号。这个过程听起来像在做逆向操作但它的功率更强能够分析更大的文法族。大多数工业级的语法分析器比如那些面向真实编程语言的解析器生成器采用的都是这类方法。两种策略选择的关键在于权衡自顶向下简单、错误定位容易但限制多自底向上能力强、适用面广但实现复杂度高。学习阶段我建议两个都动手试一遍不用做到精通只要亲手写过一次递归下降分析器和一次简单的 LR 分析表构建很多概念自然就通了。3.3 语法错误的恢复技巧与真实编译器里的处理语法错误是程序员最常遇到的编译错误类型。你可能已经发现现代编译器的报错信息越来越人性化了它会告诉你出错的行列位置有时还会附带一句“你是不是漏了一个分号”。这些体验背后是语法错误恢复机制在发挥作用。第一章会介绍几种基本策略。最简单的是恐慌模式语法分析器一旦发现某个语法成分无法匹配就跳过输入记号流中大量的标记直到找到一个它能够恢复同步的记号比如分号或右括号然后接着往下分析。这样做效率高实现简单缺点是可能会跳过多余代码。还有一种方式是错误产生式也就是在文法里主动加入一些能匹配常见错误的产生式。比如语法规则里额外允许if (表达式 语句这种缺右括号的形式等分析到之后在语义层面报错。这样的好处是报错更精准程序员能直接看到“这里缺右括号”而不是看到一堆莫名其妙的“无法解析”。很多初学者会好奇既然现代 IDE 这么聪明能在你打字的同时就划红线标错误为什么编译器还要费这么大劲做错误恢复原因在于 IDE 的智能提示用的是一个增量式的解析器它分析的是频繁变动的文本而传统编译器面对的是整个文件的一次性编译两者对错误处理的要求和使用场景完全不同。4. 语义分析到代码生成编译器靠什么读懂而不是认出代码语法分析通过之后编译器已经知道代码的结构了比如它知道x y 1是一个赋值语句也知道这个赋值语句里右侧是一个加法表达式。但结构正确只是第一步编译器还必须知道这个赋值操作有没有意义。比如x是一个整数而y是一个字符串把字符串和整数相加就没有意义这种问题语法分析器是管不了的。语义分析阶段要干的事情正是审查程序在语义上是否合法。它需要维持一张符号表记录程序里出现的每一个名称、它们的类型、作用域、声明位置等信息。类型检查是语义分析里最常见的工作比如检查操作数类型是否匹配、函数调用参数个数和类型是否符合声明、变量使用前是否已经被声明等。4.1 语义分析管的那些看得懂但说不通的问题语法分析能看出int a hello;在结构上是一个声明语句但它看不出把一个字符串字面量赋给整型变量有什么不对。语义分析这时候就会站出来说类型不匹配。除了类型检查语义分析还要处理作用域相关的问题。比如你在内层作用域重新声明了一个变量和外层作用域的变量重名语义分析要能判断后续代码里用到这个名称时引用的是哪一个声明。这不是一个简单的问题因为同名变量的遮蔽关系在编译期间必须完全确定语义分析阶段就要把每个标识符引用关联到正确的声明上。初学者容易忽略的一点是语义分析并不是把代码“读懂”了——它不需要理解程序要计算什么业务逻辑。它只是根据语言规范检查程序的“语义合法性”。再打个比方语法分析检查的是句子合不合语法语义分析检查的是句子的搭配合不合逻辑但它不关心这句话表达的内容是否有道理。4.2 中间代码为什么是编译器里的通用语语义分析验证通过之后编译器会把程序转换成中间代码。这里说的中间代码不是某种真实的机器语言而是介于源语言和目标机器语言之间的一种表示形式三地址码是其中最经典的一种。所谓三地址码是指每条指令的形式大致像一个a b c这样的表达式其中最多有三个操作数的地址因此得名。为什么非要多出一层中间表示一个很直接的理由是复用。如果某个语言需要支持几十种不同的目标平台而每种平台都有自己独特的指令集和寄存器结构那编译器能不能只写一份前端的翻译逻辑再针对每种平台各写一份从中间代码到机器码的后端逻辑答案就在这一层设计里。在这个架构下前端只需要负责把源语言翻译成统一的中间代码后端只需要负责把中间代码翻译成具体目标平台的目标代码。某个新语言想让多个平台支持只要复用这套后端框架某个新架构要让多种语言支持只要复用这套前端框架。这也是很多编译器框架能支持多种语言和多种后端的原因所在。4.3 优化只是让程序更快吗代码优化阶段很容易被误解为单纯追求执行速度的阶段。实际上优化包括多个维度。有的优化是为了减少执行时间比如把循环里不变的常量计算提到循环外有的优化是为了减小代码体积比如合并功能相同的分支还有的优化是为了降低能耗这在移动端和嵌入式领域越来越重要。第一章不会深入各优化算法但会让你记住一个核心思想优化必须在保持程序语义不变的前提下进行。这意味着优化器不能随便“自作聪明”地改动代码逻辑任何优化后的代码都必须和优化前的代码产生相同的结果。为了做到这一点优化器需要做非常深入的数据流分析搞清楚哪些变量在哪条路径上是活跃的、哪些赋值其实是死代码可以被安全删除。我自己做优化时有一次试图把一段看起来重复的表达式提取出来手动改完测试发现结果全对开心得不行后来才发现测试用例恰好没有覆盖某个边界情况。这件事给我留下的经验是编译器优化器能自动完成的变换都要建立在严格的分析证明之上任何“看着像等价”的手工优化都可能埋雷。目标代码生成是流水线的最后一站。它负责把优化后的中间代码映射到目标机器的指令集上。这个步骤涉及两个核心问题指令选择也就是为每条中间代码挑选合适的机器指令寄存器分配也就是决定程序使用的虚拟变量分别放在哪些物理寄存器里。寄存器分配在工程上非常关键因为寄存器的数量有限分配得好不好直接影响生成代码的执行效率。5. 第一章之后这份全局地图该怎么继续用很多初学者学习编译原理时第一遍会直接卡在第一章后面那些语法制导翻译的定义上回头再看第一章会觉得很无聊觉得全是概念。我的体会是第一章的正确打开方式不是背诵六个阶段的定义而是把它当作一个“认知脚手架”。后续章节会逐一把第一张地图上的每个阶段放大。比如第二章大概率重点讲词法分析第三章深入语法分析第四、第五章聊中间代码生成等。每学一个章节你都应该回看自己实现了什么、和编译器流水线的大图有什么关系。如果一个阶段学完了却说不清它接的上一个阶段和下一个阶段分别是什么那大概率是学脱节了。5.1 编译器不是一门课是一条工程流水线如果你不是在参加理论考试而是想真正掌握编译技术我强烈建议不要只停留在概念层面。找一个简单的教学语言自己动手写一个能编译表达式的小型编译器目标不需要多大能处理加减乘除、变量声明和函数调用就足够了。写的过程中你会发现很多章节里根本不会写到的细节。比如词法分析时如何管理输入缓冲区分行扫描、错误信息如何携带行列号、符号表如何处理嵌套作用域、中间代码如何记录调试信息。这些细节本质上都是工程问题但它们恰恰也是新手最容易崩溃的地方。我至今记得自己第一次跑通一个完整流水线时的感觉输入的是一段文本输出的是一个能执行计算的程序。那一刻我才把第一章讲的那张大图从纸面上搬到了自己手里。学编译原理的经验往往不是听会的是做会的。5.2 给新手的学习路径建议如果你现在刚翻开编译原理的第一章我的建议是第一遍读的时候不用死记每一种分析算法的细节先把整体流程的输入输出搞清楚。每读完一个阶段的描述合上书自己用大白话向别人解释一遍这个阶段在干什么输入是什么输出是什么。第二遍再回来的时候配合动手实践。挑一个你熟悉的语言试着写一个最小的词法分析器只要能识别标识符、数字和基本操作符就很有收获了。之后再逐步扩展到语法分析先处理简单的算术表达式再处理 if 语句。循序渐进的过程里你会自然理解为什么正则表达式适合描述词法结构但不适合描述嵌套的语法结构、为什么语义分析需要符号表这些概念。不要觉得编译器只能由少数人写。实际上现在有大量开源工具能帮你在几天之内搭出一个完整的小型编译器骨架编译原理的知识体系也早就不只服务于编译器本身。文本解析、模板引擎、静态代码分析、数据库 SQL 解析器这些领域都在大量应用同样的技术。学好第一章相当于拿到了一把能打开很多工具引擎的钥匙。5.3 章节小结看懂第一章就能看懂的隐藏信号第一章看起来只是罗列了一些基础概念但它其实在向你传递几个贯穿全书的关键信号。第一个信号是任何复杂的系统都可以通过分层来降低复杂度编译器的六个阶段就是这种思想的最好示范。第二个信号是描述一个结构化的文本需要一套严谨的形式化体系正则表达式、上下文无关文法、属性文法一个个递进地提供了表达能力各异的框架。第三个信号是错误处理和恢复不是边角料它在真实编译器里占据的价值远超它在教科书里所占的篇幅。从个人学习的角度说我见过不少同学在第一章就纠结于每个名词的精确定义导致进度非常缓慢。我现在觉得第一遍学习时更需要抓住的是各阶段之间的衔接关系。这就像看地图先看清主干道路的走向再去研究每条街道的细节才不会迷失。如果你刚开始学编译原理又恰好对整条流水线感到一头雾水我的建议是把“字符流先变记号流记号流再变语法树语法树再变中间表示中间表示最终变目标代码”这条主线刻在脑子里。之后无论学到多复杂的算法都回头用这条主线校准一下自己的位置。学完这一章再回看那些报错信息你会比从前更清楚地知道它们究竟来自流水线的哪一环。