从词法分析到目标代码生成：编译原理自学路线与公开课推荐

1. 为什么这门公开课值得反复刷在我自己啃编译原理的那段时间最深的感受就是这门课光看书根本学不进去。龙书也好、虎书也罢翻开就是大段的形式化定义、产生式、有限自动机每一页都像天书看十分钟就犯困。直到有人推荐了B站上一套编译原理公开课这才算真正找到入门的抓手。这套课程是由国内某著名军校的计算机学院录制的讲的老师有很深的编译器工程背景不只是照本宣科念教材而是把整个编译器的构建过程当成一个实际工程项目来拆解。课程视频在B站可以免费观看弹幕里常年有一批人在打卡学习学习氛围相当浓烈。我当时跟着这门课从头到尾走了一遍后来又反复回看重点章节前后花了大概三个月的时间从一个只会写业务代码的状态到能独立实现一个可运行的类C语言子集编译器这种成长感在平时工作中真的很难获得。如果你是非科班出身想补体系课、准备应付学校考试或者工作后想深入理解语言运行机制的人这套公开课都算是一个很好的起点。它不像某些培训机构的速成课那样只讲表面概念也不像学术讲座那样曲高和寡而是走了一条理论够用、实践充分、细节扎实的路子恰好弥补了大多数人自学编译原理时“看得懂公式但写不出代码”的尴尬。整门课看下来我最大的收获其实不是背住了几个术语而是理解了编译器并没有想象中那么神奇。它说白了就是一系列的结构化转换把一种语言翻译成另一种语言中间每个阶段都有明确输入输出和对应的数学理论基础。只要你愿意拆开它跟着课程一个模块一个模块地搭起来编译器真的就是从零开始长出来的东西。2. 课程结构拆解七个模块搭建完整编译器认知2.1 从词法分析到目标代码生成的全链路设计这套公开课的精彩之处在于它的课程结构完全是按照一个真实编译器的工作流程来组织的。从最前面的编译器整体结构介绍开始老师就把全貌摆在你眼前词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成还有贯穿始终的符号表管理和错误处理。这七个模块是编译器的标准骨架也是龙书等经典教材的核心组织方式。我特别欣赏的一点是老师在第一章就把“编译器也是一个程序”这件事讲透了。很多人学编译原理最大的心理障碍是觉得编译器是某种高不可攀的系统软件离自己很遥远。但实际上编译器就是一个普通的程序有输入、有处理逻辑、有输出只不过它的输入是源代码字符串输出是另一种语言表示。想通这一点后面的学习心态会完全不同。课程每讲完一个模块都会配一个实际的代码案例而这套代码案例不是零散的而是前一模块的输出恰好是后一模块的输入比如语法分析阶段构建的语法树正好是语义分析阶段要遍历的结构。这种强关联性让学习者始终知道自己在整个流程中的位置不会迷失在细节里。整个课程大概四十多讲每讲五十分钟左右。我第一次刷完用了两周多其间有很多地方需要停下来反复看。如果时间紧张跟着老师课堂上的主线走将课件里的示例代码自己敲一遍也能建立起框架性的认识。但如果真想学到位课后动手做实验是跳不过去的部分。2.2 词法分析与有限自动机的落地理解词法分析是编译器的第一个阶段也是很多人第一次接触形式语言与自动机理论的环节。老师在这个部分没有一上来就丢正则表达式和DFA确定性有限自动机而是先讲了一个朴素的问题读入一段源代码你如何把里面的关键字、标识符、数字、运算符切分成一个个独立的记号从手工逐个字符扫描开始自然引入“最长匹配”的原则然后逐渐优化成用状态转移来识别记号集合的方式。当你在黑板上画出那个状态转移图再把状态图翻译成一张二维表也就是状态转移表DFA这个概念就变得非常直观了。我以前看教材时怎么也弄不明白NFA非确定性有限自动机和DFA到底有什么区别看了课程里用实际字符串匹配过程推演了一遍之后恍然大悟——区别就在于某个状态下输入一个字符后这个状态是确定的还是可能有好几个候选状态。词法分析器的代码实现老师是用C语言手工实现的没有借助lex等自动生成工具。这段代码让我第一次理解了“读字符”“识别单词”“跳过空白”“处理错误字符”这些环节是如何被组织成一个循环的。后来我学其他语言时发现几乎所有手写词法分析器的核心循环都是这个模式不断读入字符驱动有限状态机流转直到某个状态需要产生记号输出时就停止并返回当前积累的单词。2.3 语法分析从自顶向下到自底向上的思维跳跃如果说词法分析是编译原理里最简单的一环语法分析就是第一道真正的门槛。课程在这个模块花费了大量篇幅也确实是整个课程中信息密度最高的一段。语法分析的目标是根据词法分析得到的记号序列按照文法规则构建一棵语法分析树。老师首先介绍了上下文无关文法和BNF表示法这东西说白了就是一种描述语言嵌套结构的规则体系比如表达式可以是一个数字也可是两个表达式相加。这种递归定义的方式和我们在编程中常见的递归函数是同构的。自顶向下分析重点讲了递归下降和LL(1)。递归下降的代码风格非常接近人脑思维方式为每个非终结符写一个函数函数体内按照产生式的右侧逐步“消费”记号流。我第一次写出自己的递归下降解析器时觉得这东西简直太优雅了语法规则几乎就是代码的结构。而LL(1)的FIRST集、FOLLOW集计算则是为了判断一个文法能否用预测分析表来解析。这部分内容理论性比较强但老师用实际文法推导了一遍FIRST集计算过程比看书自己琢磨要好懂很多。自底向上分析重点讲了LR(1)和它的简化版本SLR。这里我第一次接触到了“移进-归约”的概念一边读入记号一边试图反向套用产生式将右侧归约为左侧。每走一步都是一次移进或归约的选择而LR分析表里就是这些选择的决策依据。我学到这里最大的阻碍是那些密密麻麻的分析表后来跟着课程一步步把一张小的SLR分析表构造出来再模拟分析一个句子整个过程走上两三遍才算真正通了。2.4 语义分析与中间代码符号表和类型检查的价值语法分析只解决了“结构是否正确”的问题完全没解决“含义是否正确”的问题。比如一个表达式“int a; a hello”在语法上是合法的但在语义上显然是错的。语义分析模块正是处理这一层问题核心数据就是符号表。老师在这一部分特别强调了符号表设计的重要性。符号表不是一个简单的哈希表而是要支持作用域嵌套的全局变量在函数外可见局部变量只在自己的函数内可见同名变量在不同作用域可以共存这些约束都需要用作用域栈的结构来实现。课程里给出了一个用链表嵌套结构实现符号表的C语言版本虽然代码不长但设计思想非常典型。中间代码这一节引入了三地址码的概念也就是每条指令最多只有一个运算符、三个操作数的表示形式。为什么要引入中间表示因为编译器前端要面对的是源语言的特点而后端要面对的是目标机器的特性中间表示作为两侧的缓冲带让前端和后端可以独立发展。这门课选了类似汇编思想的中间语言——四元式并演示了如何从语法分析树上生成四元式序列。这一步我看第一遍时云里雾里等自己写生成器时才发现其实就是在遍历语法树时对每个节点套用固定的模板难度低于想象。3. 三大编译器构造工具与配套实验3.1 flex与bison的黄金组合课程在讲到自动生成工具时重点演示了flex词法分析器生成器和bison语法分析器生成器。这两个工具是在Unix环境下非常成熟的组合它们接收的描述文件分别是.l和.y后缀前者描述正则表达式到动作的映射后者描述文法产生式到动作的映射。flex和bison的配合思路值得每个学编译的人体会一遍flex负责把输入流切成记号序列bison负责根据记号序列构建语法结构。两者之间的接口就是yylval这个全局变量lexer识别出一个记号后把它的附加值比如标识符名字、数字值写入yylvalparser读记号时就拿到了对应的语义信息。课程配套实验中有一个经典案例用flexbison实现一个简易计算器。整个描述文件篇幅不大但麻雀虽小五脏俱全完整展示了优先级声明、左右结合性、词法动作与语法动作的交互等核心机制。做完这个实验再去看那些大项目的语法源码比如后续我研究某些脚本语言解释器的源码时发现它们内部就是类似的架构只是规模更大、结构更复杂罢了。我用虚拟机的Linux环境跑这些实验时踩过不少坑最典型的一个是flex版本差异导致生成代码编译报错。老教程里用的写法在新版本flex中可能已经不被支持解决方法是安装指定版本的flex和bison或者用课程课件中给出的补丁调整描述文件。这些环境问题看似琐碎其实很能磨性子也是自学路上的必经关卡。3.2 手工递归下降解析器的构建要点除了自动生成工具课程还细致讲解了手写递归下降解析器的关键点。对于一门规模可控的编程语言子集来说手写解析器往往比引入flexbison更直观也更容易掌控错误信息的输出时机。手写递归下降时需要处理的第一个问题是左递归。文法中如果出现产生式形如 E → E T就陷入无限递归因为解析E时调用E自身永远没有终止条件。解决办法是把左递归文法改写为右递归文法然后用循环或尾递归来实现同级运算的迭代表达。在递归下降解析器中处理优先级的最常用手法就是分层设计每一层对应一种优先级比如表达式层、项层、因子层高层函数调用低层函数而低层函数碰到属于高层运算符的记号时则直接返回。这样设计出来的代码结构清晰修改起来也容易。手写解析器的另一个要点是错误恢复。一个健壮的解析器在遇到语法错误时不应该直接崩溃退出而应该能跳过若干记号继续尝试解析后面的内容。课程里介绍了同步记号的方法为每层解析函数定义一个可以中止继续解析的记号集合一旦发现错误就不断读取记号直到遇到同步集合中的记号才恢复解析。我在自己实现时发现同步集合的选取是门艺术选得太多会漏报错误选得太少又会连带报出一堆无关错误。3.3 课内实验项目的完整落地路径课程配套的实验作业是一套经典的分阶段编译器构建项目从最简的词法分析器一直做到能生成目标代码的完整编译器。这套实验的设计非常讲究渐进性第一阶段读入一个简单的源文件并输出所有的记号流第二阶段根据文法建立语法树并用缩进方式打印树结构第三阶段添加符号表和类型检查第四阶段生成中间代码并用简单的解释器执行最后阶段做汇编代码或简单虚拟机代码的生成。我按这个路径走下来实际花费的时间远超预期。每个阶段的代码量其实都不算大几百行C语言就可以覆盖难的是调试。语法分析阶段的问题表现为逻辑复杂度激增一个深层的表达式解析出错trace一下就得迭代很多回合。我把老师课件里给的测试用例全部跑通后又自己写了一批边界测试比如空程序、连续运算符、括号不匹配等大多数Bug都是在这些古怪案例中暴露出来的。这套实验的完成质量直接决定了你对编译原理的理解深度。如果只是看视频不写代码永远停留在“听得懂但做不出”的水准一旦实验跑通了你会忽然发现之前那些抽象的概念都有了具体的形态迪摩根定律、递归下降、分析表驱动这些东西从纸上落到了你的指尖。4. 高效跟课方法给自学者的实战建议4.1 三阶段学习法先跑通、再深挖、后贯通我看这套公开课一共经历了好几轮。第一轮只看不动手主要目标是搞清楚整个编译流程的框架知道每一阶段大概做什么事不要在细节处卡太久遇到讲自动机、FIRST集这类硬核内容时能跟住多少算多少必要时直接往后跳。这个策略让我在极短时间里就对编译器有了全局认识不再害怕那些术语。第二轮就要开始动手了。这时候每看完一个章节就回头把课件里的代码在本地敲一遍、跑一遍、改一改。词法分析那章的代码我敲完之后特意改了识别规则比如增加对十六进制数字的识别以验证自己是不是真懂了状态转移。第三轮属于回头补漏针对当时没搞懂的难点和做实验时发现的薄弱环节精准回看这轮效率最高因为带着明确的问题去看视频注意力完全不会飘。有基础的读者可以压缩节奏但跳步骤是不可取的。我以前见过有人为了赶时间直接从语法分析开始看结果前面记号怎么划分都没弄明白越看越糊涂。词法分析是整个链路的地基这步省略了后面每一步都会受影响。4.2 配套教材的选择与交叉阅读这套课程的主线教材用的是编译原理经典教材也就是大家常说的龙书。龙书写得很全面很多知识点都给了形式化的描述和严谨定义但正因为太全面初次阅读很容易让人退缩。公开课在这时候就起到了导航作用课程讲到哪一章你对应看龙书的那一节这样读书的目的性就强了很多也更容易坚持。除了龙书我还配合看过另一本国外的编译器设计教程它的组织方式更偏工程化里面有很多可运行的示例代码。教材和课程的关系可以是互补的课程给主线龙书给深度工程书给实践。我当时手边还有一本工具书专门讲编译原理习题解析做实验前先把对应的习题刷一两道起到了很好的预热作用。看书和看视频的比例上我的经验是视频约占六成、书约四成。视频动起来了黑板上推导步骤可视化程度高理解起来快但书上的图和定理证明是视频给不了的尤其FIRST/FOLLOW集的算法描述、LR分析表构造的伪代码这些必须回到书本逐行精读才能真正消化。4.3 动手验证的八个自测小任务为了检验自己是否真正掌握了课程的关键知识点我给自己设计了一套自测实验。每个实验规模都很小但覆盖面广做完后对课程的掌握程度就有了比较明确的感觉。一是写一个能识别整数、浮点数、标识符和几个关键字的词法分析器不借助flex全手写状态机实现。二是给定一个小学级别的算术表达式文法手写出它的递归下降解析器并能够正确输出语法树。三是把某段C语言风格代码手动转换为四元式序列与课程中老师演示的答案比照。四是画出给定DFA的状态转移表再用程序模拟运行该自动机识别一串输入。五是阅读一份简单的bison语法文件在纸上推演它如何处理带优先级的中缀表达式。六是手工构造一个简单文法的SLR分析表并模拟分析过程。七是在自己的编译器实现中加入变量声明与作用域检查观察符号表结构的变化。八是把运行时的中间代码改成简单的栈式虚拟机字节码并实现对应的执行器。这八个任务全部做到后编译原理的核心链条基本上就印在脑子里了。5. 常见问题与排查技巧实录5.1 入门阶段的三座大山与翻越方法自学这门公开课时几乎所有人都会在几个地方卡壳。第一个是FIRST集和FOLLOW集的计算。这个知识点抽象程度高光看书上算法很容易绕晕。我的突破办法是把每个非终结符看成一个函数思考它可能以哪些终结符开头把这些可能记录下来就是FIRST集再看它出现在哪些产生式右侧后面可能跟着哪些终结符这些就是FOLLOW集。用这种“思考方式转换法”计算规则就变得自然了。第二个难点是LR分析家族的构造过程尤其是项目集规范族的构建。这一块我一开始怎么也看不出意义所在后来写了个小程序把文法的各个项目集状态自动生成出来对照课程里的手工推导结果才真正理解LR分析表最左端那列状态编号是怎么来的。如果你也卡在这里别硬啃先用工具把结果跑出来再反向对应到算法流程上会顺畅很多。第三个坎是中间代码生成阶段的多遍处理。很多初学的人都知道要生成三地址码但不知道到底怎么组织生成的流程。课程中用了语法制导翻译的思想也就是文法产生式后面附带的语义动作在执行归约时触发。明白“归约时执行动作”这个总纲领之后四元式生成就变成了一组模板化的代码生成逻辑难度瞬间就下来了。5.2 实验环境与调试中的典型翻车现场我在跑课程实验时遇到过几个非常典型的环境问题这里记录一下供后来人参考。第一个是flex生成代码中有一个函数在某些Linux发行版的默认编译器版本下会隐式声明报错。这个问题在课程录制的年代不存在但随着编译器版本更新变成了“时代坑”。解决办法是在flex描述文件头部加上对应的函数声明或者用选项让生成代码兼容旧接口。我就是在这个坑上折腾了小半天才绕出来后来发现课程B站评论区里也有人碰到同样问题已经有人贴出了完整的补丁代码。第二个是bison版本差异导致语法分析文件无法编译。新版bison生成的解析器用了一些新接口而课程配套的代码是面向旧版写的。我最终选择了安装和课程版本一致的bison顺利避开了兼容性问题。如果你不想折腾多个版本也可以把代码接口升级到新版但改动点会比较多。第三个问题不是环境而是思路上的写递归下降解析器时左递归文法的改写总出错。课程在这个地方给过练习但自己实际改写时多了一层运算符优先级处理很容易改出语义偏离的版本。建议用GNU bison的直接左递归写法先对照生成结果再回到手写实现心里就有底了。5.3 针对典型困惑的快速对照针对自学过程中大家问得最多的问题我整理了一个快速对照表希望能在卡住时提供方向困惑点直接原因解决办法词法分析中贪婪匹配导致标识符被截断状态机未设置最长匹配在每次接受状态时暂存位置优先取最长的有效匹配FIRST集计算结果总错未处理空产生式的传递从所有非终结符的空推导集合入手逐轮迭代直到不变式成立递归下降解析器处理负号时和减号冲突文法的语法层次设计不当单独引入一元操作符层优先级高于乘除低于括号LR分析表出现冲突文法存在二义性或SLR能力不足改写文法消除二义性或升级为LR(1)分析表符号表查不到变量作用域没正确出入栈检查每次进入/退出块时符号表指针的压栈和弹栈逻辑四元式跳转地址未回填中间代码生成顺序问题先发临时跳转指令记录地址后用回填技术修正这张表基本上覆盖了每一阶段的常见问题。大部分问题的根源都非常相似要么是数据结构设计不到位要么是对某个定义的理解有偏差。找到根子上的原因再修比盲目改代码有效得多。5.4 学习过程中的心态管理与时间安排最后想聊一点心态问题。编译原理跟普通的应用开发课程很不一样它里面掺杂了相当多的数学元素和抽象逻辑学习曲线比较陡峭。我见过不少人学到语法分析就放弃了因为前面花了很多时间却迟迟看不到“能跑的东西”。如果你也在这种状态中我的建议是刻意降低预期允许自己暂时“不会”。常驻弹幕里那些打卡的人其实也在经历同样的挣扎你不是一个人。时间安排上如果每天能投入两个小时周末再加班半天一个月可以完成第一轮框架学习第二个月边做实验边回看难点第三个月基本上可以完成一个完整的小编译器。这个过程听起来不算短但细算下来比在迷茫中反复横跳高效得多。坚持下来的核心动力是每隔几天都能看到自己的编译器多支持了一种语法、多处理了一种错误那种实实在在的成就反馈其实比任何激励话术都管用。6. 后续延伸从课程走入真实的编译器世界学完这门公开课你掌握的编译器知识完全可以向两个方向延伸。一个方向是学术深挖回到龙书去啃那些被课程跳过的证明细节比如LALR分析表的精化构造、数据流分析的格理论等。另一个方向是工程实践拿已经实现的编译器为基础逐步添加更多语言特性比如数组、结构体、函数调用、指针等最终目标是让它能够编译一种足够复杂的语言子集。我自己的体会是课程结束后真正发生质变的那一步是开始阅读一个开源解释器的源码。带着公开课建立的框架去面对几千行代码你不再是一头雾水而是能迅速定位到哪部分是词法、哪部分是语法、哪部分在维护符号表、哪部分是解释器的求值循环。这种“骨架感”就是课程赋予你的最大财富。要真正吃透一个系统先看骨再看肉才会快。编译原理这门课恰好教你的就是如何看骨架。如果你想更进一步可以试着给现有的语言加一点小特色比如给类C语言增加一个简单的类型推断。这个过程会逼你把词法、语法、语义、中间表示全部重新揉一遍是最完整的复习方式。过程中你会困扰于各种细节但每解决一个问题你对编译器的理解就会更扎实一层。这条路没有终点但每一步都很值得。