简介《编译原理学习指导》面向计算机专业本科生、考研复习者及自学编译原理的开发者针对课程理论抽象、算法理解困难和教材选择无从下手等问题提供学习路径与参考建议。压缩包内共1个doc文件约34KB篇幅集中便于通读与检索。文档围绕词法分析、语法分析中的LL、递归下降与LR算法、语义分析、运行时环境、中间代码生成及代码优化等核心阶段展开并比较《编译原理》龙书、《现代编译程序设计》和《编译原理及实践》三本经典教材的侧重点帮助读者按理论或实践需求选书。内容还强调理解算法本质重于记忆文字描述适合作为课程同步辅导和考研梳理材料。目前已有153人学习可作为建立编译原理知识框架的入门参考。1. 编译原理的知识地图一条从字符流到指令流的单向流水线编译原理这门课的知识地图最容易被教材目录带偏词法分析、语法分析、语义分析、运行时环境、中间代码、代码生成、代码优化七块一字排开看着像七个互不相干的专题。梳理下来会发现它其实是一条单向流水线——前端把字符流变成抽象语法树中端在树上做类型检查和翻译后端把树降成指令序列。前端的理论密度最高后端的工程细节最碎夹在中间的运行时环境反而最容易被跳过却对日常开发最有用。这张地图适合两类人正在跟课、需要一个把手把零散章节串起来的人以及复习备考、想快速定位自己卡在哪一段的人。先把流水线画出来再往每一段里填算法比从第一页背到最后一页省力得多。2. 前端两关词法分析与语法分析的复习重点前端只做一件事把程序员写的文本变成一棵方便处理的树。两个阶段分工不同词法分析管「一个词长什么样」语法分析管「这些词怎么组合成句」。考试里词法偏计算画自动机、算子集构造语法偏构造推分析表、判冲突类型。很多人复习时把这两块混在一起背结果两头都不牢下面的拆法可以照着对照。2.1 词法分析从正则表达式到自动机的标准路径词法分析要解决的问题很窄把一串字符切成一个个带类别的记号顺手丢掉空白和注释。切的时候有两条固定规则——最长匹配以及规则书写顺序决定优先级。真正让这门课把它抬到理论层面的是背后那条转换链正则表达式先用 Thompson 构造法变成 NFANFA 再用子集构造法变成 DFADFA 最后用划分法最小化。考试里画这三步是常事画错的地方多半集中在 ε-闭包展开和状态集合编号上而不是概念本身。把这条链走通之后词法分析器的实现就变成了「填规则表」。下面是一段词法规则定义结构就是定义段、规则段、用户代码段三部分%{ /* 词法规则识别标识符与整数跳过空白和单行注释 */ %} DIGIT [0-9] LETTER [a-zA-Z_] ID {LETTER}({LETTER}|{DIGIT})* %% [ \t\n] { /* 空白不产生记号 */ } //.* { /* 单行注释整行丢弃 */ } {DIGIT} { return INT; } {ID} { return ID; } %%%%是分段符每条规则由「模式 动作」组成DIGIT、ID这类名字在定义段里先声明规则段直接引用return把记号交给语法分析器。生成工具默认按最长匹配选规则长度相同时排在前面的优先所以关键字的规则通常要写在标识符规则之前否则关键字会被当成普通标识符吞掉。手写词法分析器不是不行但状态一多就会变成一大片 switch改一条规则要动好几处用生成工具规则和动作放在一起维护成本低得多。理论部分的高频考点还有两个一是 NFA 与 DFA 的等价性任何 NFA 都能转成 DFA所以正则语言既能用非确定的方式描述也能用确定的方式执行二是 DFA 最小化后的状态数唯一划分法每一步都在把「行为相同」的状态合并。把这两个结论记住做题时能省掉不少反复验证。2.2 语法分析LL 自顶向下与 LR 自底向上的分野语法分析拿到的输入是记号流输出是语法树。它依赖的形式工具是上下文无关文法四元组、产生式、推导、最左推导与最右推导、句型与句子、二义性。二义性文法不是不能用而是必须额外约定结合性和优先级否则同一串输入能长出两棵不同的树。消除左递归和提取左公因子是自顶向下分析的前置动作前者防止递归下降死循环后者避免回溯。自顶向下的代表是 LL(1)从开始符号出发用预测分析表决定下一步展开哪个产生式。表的构造依赖 FIRST 集和 FOLLOW 集表里每个格子最多一个入口就是 LL(1) 的判定条件。自底向上的代表是 LR从输入串出发不断移进和归约目标是归约到开始符号。LR(0) 项目集规范族由闭包和 GOTO 两项运算生成冲突分移进-归约和归约-归约两类SLR 用 FOLLOW 集缩小归约范围LR(1) 给每个项目带上向前看符号LALR 合并同心项目集来压缩表规模代价是可能引入新的归约-归约冲突。维度LL自顶向下LR自底向上分析方向从开始符号推导出输入串从输入串归约到开始符号核心结构预测分析栈 分析表状态栈 符号栈 分析表主要障碍左递归、公共前缀移进-归约冲突、归约-归约冲突文法能力LL(1) 是 LR(1) 的真子集能处理的文法范围更大手写难度递归下降直观适合手写几乎不手写依赖生成工具典型支撑手写递归下降、部分生成器Yacc/Bison 一类工具这张表最该记住的是第四行LL(1) 文法集合是 LR(1) 的真子集凡是 LL(1) 能处理的文法LR 都能处理反过来不成立。所以「LR 更难」只体现在构造过程上不体现在能力上。自学的人卡在 LR多半不是理解不了移进-归约而是项目集规范族手工推导步骤太多中间错一步后面全错。复习时不要一上来就背表先按「增广文法 → 项目 → 闭包 → GOTO → 规范族 → 分析表」的顺序手推两遍再回头看冲突类型会顺很多。2.3 递归下降唯一要求手写的部分递归下降是 LL(1) 的代码化每个非终结符对应一个函数函数体按产生式右部依次调用其他函数。它不适合复杂文法但胜在直观、好调试写配置格式解析、命令参数解析、小型 DSL 都用得上。写之前必须先消除左递归否则函数会自己调自己直接爆栈。# 递归下降解析加减表达式expr - term ((|-) term)* def parse_expr(tokens): node parse_term(tokens) # 先解析一个 term 作为左操作数 while peek(tokens) in (, -): # 用循环处理左结合避免左递归 op next_token(tokens) # 取出运算符 right parse_term(tokens) # 解析右操作数 node Binary(op, node, right) # 已解析部分整体作为左子树 return nodepeek只看当前记号不消耗next_token消耗并前移循环结构天然对应左结合也顺手绕开了左递归每个函数只对自己那层产生式负责出错时打印当前记号的位置就能定位到出错点。这段代码没有错误恢复真实解析器还要在parse_term里处理括号不匹配、缺少操作数之类的情况。原文强调过一个现实约束换到非 C 平台不一定有 Yacc 类工具可用这时候手写递归下降就是唯一选择。它另一个好处是调试友好加一行日志就能看到解析走到哪个非终结符比对着生成的分析表猜要快得多。3. 语义分析与运行时环境树上的两次加工语法分析产出抽象语法树只说明「结构对了」语义分析负责「意思对了」运行时环境负责「跑起来的时候内存怎么摆」。这两块在教材里常被压缩成一章甚至半章但后者对日常开发的价值可能超过编译原理本身返回值、闭包、内存泄漏这些天天遇到的现象答案都在活动记录和存储分配策略里。3.1 语义分析类型检查、符号表与语法制导翻译语义分析要做的事包括建立符号表、解析名字、类型检查、插入隐式类型转换最后产出带注解的树或中间代码。它依赖的工具是语法制导定义每个产生式配一组属性计算规则。综合属性由子结点算向父结点适合自底向上分析继承属性由父结点或左兄弟算向自己适合自顶向下分析。S 属性定义配 LRL 属性定义配 LL这个搭配关系搞反纸上写得通代码跑不通。# 赋值语句的最小类型检查窄化报错拓宽允许隐式提升 def check_assign(lhs_type, rhs_type): if lhs_type int and rhs_type float: raise TypeError(浮点赋给整型需要显式转换) # 窄化可能丢精度 if lhs_type float and rhs_type int: return float # 拓宽隐式提升 if lhs_type ! rhs_type: raise TypeError(f类型不匹配: {lhs_type} - {rhs_type}) return lhs_type这段只覆盖了标量赋值真实语言的类型系统还要处理数组、结构体、函数签名、多态和重载解析复杂度主要落在类型等价判断上是名字等价还是结构等价子类型能不能当父类型用。符号表一般用哈希表加作用域栈实现进入一个块压栈、退岀弹栈名字解析就是沿栈从顶往下找第一个匹配项。语义分析未必是独立一遍扫描很多实现把它和语法分析交错做边归约边算属性省一次遍历。3.2 运行时环境活动记录、参数传递与动态存储分配运行时环境讲的是程序跑起来之后内存怎么组织。典型分区是代码区、静态数据区、栈区、堆区。每次过程调用压入一个活动记录里面按固定顺序摆放返回值、实参、控制链、访问链、保存的机器状态、局部变量和临时变量。控制链指向调用者访问链指向定义环境静态作用域语言靠访问链找非局部名字嵌套层数越深沿链走的步数越多。参数传递有几种典型方式值传递复制实参引用传递传地址值-结果在入口复制、出口写回。不同方式在「函数内改参数会不会影响调用方」这件事上表现完全不同考试常拿它出对比题。动态存储分配对应 malloc/new 一类操作背后是空闲链表、边界标记、合并相邻空闲块这些机制垃圾回收则是另一条路引用计数、标记-清除、复制、分代各有取舍。维度栈式分配堆式分配生命周期与过程调用绑定随返回释放由程序显式释放或回收器决定分配速度移动栈指针极快查找空闲块较慢碎片问题基本没有外部碎片、内部碎片典型对象局部变量、活动记录动态对象、变长结构错误形态返回局部变量地址悬垂指针、内存泄漏、重复释放这张表能解释不少踩坑现场返回局部数组地址为什么翻车因为活动记录在函数返回时就没了闭包为什么能记住外层变量因为实现上把外层环境搬到了堆上某些语言为什么必须带垃圾回收因为它们大量在堆上创建对象靠程序员手动释放不现实。原文说这部分的意义甚至超过编译原理本身指的就是它把「程序怎么存储、怎么装载、怎么执行」一次性摊开在你面前。4. 后端与工具链中间代码、代码生成、代码优化及配套工具后端把语法树降成指令。教材通常按中间代码、代码生成、代码优化三块讲本科阶段的重点在前两块的理解和手推优化部分知道概念、看懂例子即可。再往前一步是工具链词法和语法这两关完全可以用生成工具顶掉把精力留给真正需要自己写的部分。4.1 中间代码三地址码与堆栈式字节码中间表示的作用是隔离前端和后端前端只面对一种 IR后端只需为一种 IR 写代码生成换语言或换目标机器时不用全部重写。常见形式有抽象语法树、三地址码、控制流图三地址码又分四元式、三元式、间接三元式。堆栈式字节码是另一类指令只操作操作数栈没有寄存器概念生成简单、解释执行简单跨平台也方便。# 后序遍历 AST生成基于操作数栈的指令 def gen(node): if isinstance(node, Num): emit(push, node.value) # 叶子常量压栈 elif isinstance(node, Binary): gen(node.left) # 先算左子树结果留在栈上 gen(node.right) # 再算右子树结果留在栈上 emit({*: mul, : add}[node.op]) # 弹出两个操作数压回结果emit把一条指令追加到输出列表求值顺序是后序和表达式树的递归结构完全一致整个过程不需要寄存器分配所以实现起来很短。代价是指令条数偏多、执行效率不如寄存器机器适合解释器或者作为进一步编译到机器码的中间步骤。原文提到不少解释执行语言的底层字节码就是这种基于栈的指令原因就在这里生成机械、验证容易、移植成本低。4.2 代码生成指令选择与寄存器分配代码生成要把中间代码映射到目标机器指令两件核心工作是指令选择和寄存器分配。指令选择常用树模式匹配把语法树的一小段匹配成一条或几条机器指令同时决定用哪种寻址方式。寄存器分配是真正的难点变量是结点同时存活的两个变量之间连边用 K 种颜色染色颜色不够就把某些变量溢出到栈上。; 三地址码: t1 b * c; t2 a t1 LOAD R1, b ; 把 b 装入寄存器 R1 MUL R1, c ; R1 R1 * c结果即 t1 LOAD R2, a ; 把 a 装入 R2 ADD R2, R1 ; R2 a t1结果即 t2 STORE t2, R2 ; 把结果写回 t2 的内存位置这段假设 a、b、c、t2 都在内存R1、R2 是两个可用寄存器。真实代码生成还要处理寄存器不够时的溢出、常量直接折进寻址方式、以及指令之间的依赖和延迟。原文给的建议很实际如果生成的是堆栈式代码需要考虑的东西不多一旦走到寄存器为基础的代码生成寄存器怎么分配就会变成主要麻烦这也是初学者做完整编译器时最容易卡住的地方。4.3 代码优化本科阶段该停在哪优化分局部和全局。局部优化在基本块内做常量折叠、公共子表达式消除、死代码删除、强度削弱。全局优化要跨基本块依赖数据流分析循环优化收益最大——循环不变代码外提、归纳变量删除、循环展开都属于这一类。# 局部优化常量折叠只处理两个操作数都是常量的二元运算 def fold(node): if isinstance(node, Binary) and isinstance(node.left, Num) and isinstance(node.right, Num): value eval(f{node.left.value}{node.op}{node.right.value}) # 编译期求值 return Num(value) return node这段只对纯算术安全运算符有副作用、可能抛异常、或者涉及浮点精度时编译期求值会改变程序行为。写它是为了看清优化器在树上怎么工作不是让你真去手写一个优化器。本科教学的边界也在这里能说清基本块、控制流图、局部优化和循环优化的思路看得懂例子就够用了。原文的判断很直白——自己做的编译器能正确生成可执行代码已经很不错优化先放一放。4.4 教材分工与 Lex/Yacc 的定位三本常见教材各有分工选错书比不看书更耗时间教材代称定位适合阶段注意点龙书理论全景开篇用一个小例子串起全流程入门到系统复习例子先行部分章节偏理论偏现代工程实践的那本强调实际代码与较新话题想动手写编译器时需要一定编程基础以小型 C 子集编译器贯穿的那本入门细致逐步实现一个教学编译器零基础跟做深度不如前两本但路径完整Lex/Yacc 这类工具的价值在于把规则和动作放在一起改文法比改手写代码便宜得多。原文的建议很直接不建议连词法分析都亲手写语法文件也尽量找现成的改写出一个好文法几乎等于完成编译器的一半。非 Unix 平台上可以装一个类 Unix 兼容环境里面通常带 flex 和 bison用法和 Unix 下一致。实践顺序也有讲究先做解释型语言比直接生成机器代码简单先生成堆栈式代码比一上来就碰寄存器分配简单先用现成语法规约比从零写文法简单。5. 易错点清单五个最容易翻车的地方这一章按「易漏点 → 为什么漏 → 怎么补」组织都是复习和做题时反复出现的坑。每一条都值得在错题本上单独占一行考前翻一遍比重读教材快。5.1 词法分析与语法分析的职责边界易漏点把括号匹配、语句结束判断这类工作塞进词法分析。为什么漏词法分析用正则表达式描述正则没有计数能力天然处理不了任意层嵌套很多人觉得「顺手就做了」结果规则越写越复杂还是覆盖不全。怎么补记住词法只认词形嵌套结构必须留给上下文无关文法。判断标准很简单这条规则需不需要数括号层数、需不需要看上下文需要就放到语法层。词法阶段只做最长匹配和类别标注不承担结构判断。5.2 消除左递归时把语义动作弄丢易漏点做完直接左递归消除后原来产生式里的语义动作没有跟着重排属性算出来是错的。为什么漏教材公式只给文法变换语义动作怎么搬要自己补一搬就容易乱尤其是属性依赖左操作数的时候。怎么补先写带属性的翻译方案再做文法变换变换后逐个检查属性的求值顺序是否仍然成立需要时引入新的综合属性把中间结果带上去。写完用手推一个短串验证别只看文法是否等价。5.3 FIRST/FOLLOW 计算里的空串易漏点产生式右部能推出空串时忘记把 FOLLOW 左部并入 FIRST 右部FOLLOW 传播时漏掉「右部剩余部分可空」的情况。为什么漏空串规则条目多手算时容易只处理以终结符开头的情形ε 那条路径被跳过。怎么补固定顺序先 FIRST 后 FOLLOW每算一个非终结符就标注一次「是否可空」FOLLOW 传播时把「右部剩余部分可空」单独列一行核对。算完拿一个含 ε 的短文法验证能快速暴露遗漏。5.4 LR 项目集闭包与 GOTO 漏项易漏点求闭包时只展开点后面第一个非终结符忘记递归展开新加入的项目GOTO 只对终结符算漏掉非终结符。为什么漏项目集规范族手工推导步骤多中间漏一项后面整张表都错而且错得不明显。怎么补闭包按「点后是非终结符就把它的所有产生式加进来」反复做到不动点GOTO 对每个符号都算一遍终结符和非终结符一视同仁算完用项目数量核对数量对不上就回查闭包。5.5 继承属性与综合属性的求值顺序易漏点在自底向上分析里依赖继承属性或者在自顶向下分析里依赖只能自底向上算的综合属性。为什么漏属性文法的定义和实际遍历顺序脱节纸上推导成立代码跑起来拿不到值。怎么补先确定分析策略再选属性定义形式LL 配 L 属性、LR 配 S 属性确实需要交叉时在语法树上再走一遍独立的语义遍历用显式的多次遍历换顺序自由。这个坑的血泪经验是不要试图在一个遍历里算完所有属性。6. 复习清单按周推进的查漏补缺表复习编译原理最怕两种状态一种是书翻了三遍合上还是画不出那条流水线另一种是每章都懂一到手推分析表就错。下面这张按周推进的表把「看」换成「产出」每一周都有可验收的交付物。周次任务验收标准第 1 周不看书画出七段流水线标出每段输入输出能说清相邻两段之间传的是什么数据第 2 周手推两道正则到最小 DFA 的题写一个四则运算递归下降解析器子集构造不出错解析器能跑通带括号的表达式第 3 周FIRST/FOLLOW 各五题LR(0) 项目集规范族两道能独立构造分析表并指出冲突属于哪一类第 4 周语义分析类型检查一题堆栈式代码生成一题能逐条解释生成指令执行时操作数栈的变化每周结束时做一次三列错题记录知识点、错因、正确步骤。错因那一列不要写「粗心」要写到具体动作比如「闭包展开时漏了第二个非终结符」「FOLLOW 传播时忘了右部剩余可空」。第三列写可复现的步骤下次遇到同类题直接照做。这个方法看起来笨但比反复看书有效因为编译原理的失分本文还有配套的精品资源点击获取
简介《编译原理学习指导》面向计算机专业本科生、考研复习者及自学编译原理的开发者针对课程理论抽象、算法理解困难和教材选择无从下手等问题提供学习路径与参考建议。压缩包内共1个doc文件约34KB篇幅集中便于通读与检索。文档围绕词法分析、语法分析中的LL、递归下降与LR算法、语义分析、运行时环境、中间代码生成及代码优化等核心阶段展开并比较《编译原理》龙书、《现代编译程序设计》和《编译原理及实践》三本经典教材的侧重点帮助读者按理论或实践需求选书。内容还强调理解算法本质重于记忆文字描述适合作为课程同步辅导和考研梳理材料。目前已有153人学习可作为建立编译原理知识框架的入门参考。1. 编译原理的知识地图一条从字符流到指令流的单向流水线编译原理这门课的知识地图最容易被教材目录带偏词法分析、语法分析、语义分析、运行时环境、中间代码、代码生成、代码优化七块一字排开看着像七个互不相干的专题。梳理下来会发现它其实是一条单向流水线——前端把字符流变成抽象语法树中端在树上做类型检查和翻译后端把树降成指令序列。前端的理论密度最高后端的工程细节最碎夹在中间的运行时环境反而最容易被跳过却对日常开发最有用。这张地图适合两类人正在跟课、需要一个把手把零散章节串起来的人以及复习备考、想快速定位自己卡在哪一段的人。先把流水线画出来再往每一段里填算法比从第一页背到最后一页省力得多。2. 前端两关词法分析与语法分析的复习重点前端只做一件事把程序员写的文本变成一棵方便处理的树。两个阶段分工不同词法分析管「一个词长什么样」语法分析管「这些词怎么组合成句」。考试里词法偏计算画自动机、算子集构造语法偏构造推分析表、判冲突类型。很多人复习时把这两块混在一起背结果两头都不牢下面的拆法可以照着对照。2.1 词法分析从正则表达式到自动机的标准路径词法分析要解决的问题很窄把一串字符切成一个个带类别的记号顺手丢掉空白和注释。切的时候有两条固定规则——最长匹配以及规则书写顺序决定优先级。真正让这门课把它抬到理论层面的是背后那条转换链正则表达式先用 Thompson 构造法变成 NFANFA 再用子集构造法变成 DFADFA 最后用划分法最小化。考试里画这三步是常事画错的地方多半集中在 ε-闭包展开和状态集合编号上而不是概念本身。把这条链走通之后词法分析器的实现就变成了「填规则表」。下面是一段词法规则定义结构就是定义段、规则段、用户代码段三部分%{ /* 词法规则识别标识符与整数跳过空白和单行注释 */ %} DIGIT [0-9] LETTER [a-zA-Z_] ID {LETTER}({LETTER}|{DIGIT})* %% [ \t\n] { /* 空白不产生记号 */ } //.* { /* 单行注释整行丢弃 */ } {DIGIT} { return INT; } {ID} { return ID; } %%%%是分段符每条规则由「模式 动作」组成DIGIT、ID这类名字在定义段里先声明规则段直接引用return把记号交给语法分析器。生成工具默认按最长匹配选规则长度相同时排在前面的优先所以关键字的规则通常要写在标识符规则之前否则关键字会被当成普通标识符吞掉。手写词法分析器不是不行但状态一多就会变成一大片 switch改一条规则要动好几处用生成工具规则和动作放在一起维护成本低得多。理论部分的高频考点还有两个一是 NFA 与 DFA 的等价性任何 NFA 都能转成 DFA所以正则语言既能用非确定的方式描述也能用确定的方式执行二是 DFA 最小化后的状态数唯一划分法每一步都在把「行为相同」的状态合并。把这两个结论记住做题时能省掉不少反复验证。2.2 语法分析LL 自顶向下与 LR 自底向上的分野语法分析拿到的输入是记号流输出是语法树。它依赖的形式工具是上下文无关文法四元组、产生式、推导、最左推导与最右推导、句型与句子、二义性。二义性文法不是不能用而是必须额外约定结合性和优先级否则同一串输入能长出两棵不同的树。消除左递归和提取左公因子是自顶向下分析的前置动作前者防止递归下降死循环后者避免回溯。自顶向下的代表是 LL(1)从开始符号出发用预测分析表决定下一步展开哪个产生式。表的构造依赖 FIRST 集和 FOLLOW 集表里每个格子最多一个入口就是 LL(1) 的判定条件。自底向上的代表是 LR从输入串出发不断移进和归约目标是归约到开始符号。LR(0) 项目集规范族由闭包和 GOTO 两项运算生成冲突分移进-归约和归约-归约两类SLR 用 FOLLOW 集缩小归约范围LR(1) 给每个项目带上向前看符号LALR 合并同心项目集来压缩表规模代价是可能引入新的归约-归约冲突。维度LL自顶向下LR自底向上分析方向从开始符号推导出输入串从输入串归约到开始符号核心结构预测分析栈 分析表状态栈 符号栈 分析表主要障碍左递归、公共前缀移进-归约冲突、归约-归约冲突文法能力LL(1) 是 LR(1) 的真子集能处理的文法范围更大手写难度递归下降直观适合手写几乎不手写依赖生成工具典型支撑手写递归下降、部分生成器Yacc/Bison 一类工具这张表最该记住的是第四行LL(1) 文法集合是 LR(1) 的真子集凡是 LL(1) 能处理的文法LR 都能处理反过来不成立。所以「LR 更难」只体现在构造过程上不体现在能力上。自学的人卡在 LR多半不是理解不了移进-归约而是项目集规范族手工推导步骤太多中间错一步后面全错。复习时不要一上来就背表先按「增广文法 → 项目 → 闭包 → GOTO → 规范族 → 分析表」的顺序手推两遍再回头看冲突类型会顺很多。2.3 递归下降唯一要求手写的部分递归下降是 LL(1) 的代码化每个非终结符对应一个函数函数体按产生式右部依次调用其他函数。它不适合复杂文法但胜在直观、好调试写配置格式解析、命令参数解析、小型 DSL 都用得上。写之前必须先消除左递归否则函数会自己调自己直接爆栈。# 递归下降解析加减表达式expr - term ((|-) term)* def parse_expr(tokens): node parse_term(tokens) # 先解析一个 term 作为左操作数 while peek(tokens) in (, -): # 用循环处理左结合避免左递归 op next_token(tokens) # 取出运算符 right parse_term(tokens) # 解析右操作数 node Binary(op, node, right) # 已解析部分整体作为左子树 return nodepeek只看当前记号不消耗next_token消耗并前移循环结构天然对应左结合也顺手绕开了左递归每个函数只对自己那层产生式负责出错时打印当前记号的位置就能定位到出错点。这段代码没有错误恢复真实解析器还要在parse_term里处理括号不匹配、缺少操作数之类的情况。原文强调过一个现实约束换到非 C 平台不一定有 Yacc 类工具可用这时候手写递归下降就是唯一选择。它另一个好处是调试友好加一行日志就能看到解析走到哪个非终结符比对着生成的分析表猜要快得多。3. 语义分析与运行时环境树上的两次加工语法分析产出抽象语法树只说明「结构对了」语义分析负责「意思对了」运行时环境负责「跑起来的时候内存怎么摆」。这两块在教材里常被压缩成一章甚至半章但后者对日常开发的价值可能超过编译原理本身返回值、闭包、内存泄漏这些天天遇到的现象答案都在活动记录和存储分配策略里。3.1 语义分析类型检查、符号表与语法制导翻译语义分析要做的事包括建立符号表、解析名字、类型检查、插入隐式类型转换最后产出带注解的树或中间代码。它依赖的工具是语法制导定义每个产生式配一组属性计算规则。综合属性由子结点算向父结点适合自底向上分析继承属性由父结点或左兄弟算向自己适合自顶向下分析。S 属性定义配 LRL 属性定义配 LL这个搭配关系搞反纸上写得通代码跑不通。# 赋值语句的最小类型检查窄化报错拓宽允许隐式提升 def check_assign(lhs_type, rhs_type): if lhs_type int and rhs_type float: raise TypeError(浮点赋给整型需要显式转换) # 窄化可能丢精度 if lhs_type float and rhs_type int: return float # 拓宽隐式提升 if lhs_type ! rhs_type: raise TypeError(f类型不匹配: {lhs_type} - {rhs_type}) return lhs_type这段只覆盖了标量赋值真实语言的类型系统还要处理数组、结构体、函数签名、多态和重载解析复杂度主要落在类型等价判断上是名字等价还是结构等价子类型能不能当父类型用。符号表一般用哈希表加作用域栈实现进入一个块压栈、退岀弹栈名字解析就是沿栈从顶往下找第一个匹配项。语义分析未必是独立一遍扫描很多实现把它和语法分析交错做边归约边算属性省一次遍历。3.2 运行时环境活动记录、参数传递与动态存储分配运行时环境讲的是程序跑起来之后内存怎么组织。典型分区是代码区、静态数据区、栈区、堆区。每次过程调用压入一个活动记录里面按固定顺序摆放返回值、实参、控制链、访问链、保存的机器状态、局部变量和临时变量。控制链指向调用者访问链指向定义环境静态作用域语言靠访问链找非局部名字嵌套层数越深沿链走的步数越多。参数传递有几种典型方式值传递复制实参引用传递传地址值-结果在入口复制、出口写回。不同方式在「函数内改参数会不会影响调用方」这件事上表现完全不同考试常拿它出对比题。动态存储分配对应 malloc/new 一类操作背后是空闲链表、边界标记、合并相邻空闲块这些机制垃圾回收则是另一条路引用计数、标记-清除、复制、分代各有取舍。维度栈式分配堆式分配生命周期与过程调用绑定随返回释放由程序显式释放或回收器决定分配速度移动栈指针极快查找空闲块较慢碎片问题基本没有外部碎片、内部碎片典型对象局部变量、活动记录动态对象、变长结构错误形态返回局部变量地址悬垂指针、内存泄漏、重复释放这张表能解释不少踩坑现场返回局部数组地址为什么翻车因为活动记录在函数返回时就没了闭包为什么能记住外层变量因为实现上把外层环境搬到了堆上某些语言为什么必须带垃圾回收因为它们大量在堆上创建对象靠程序员手动释放不现实。原文说这部分的意义甚至超过编译原理本身指的就是它把「程序怎么存储、怎么装载、怎么执行」一次性摊开在你面前。4. 后端与工具链中间代码、代码生成、代码优化及配套工具后端把语法树降成指令。教材通常按中间代码、代码生成、代码优化三块讲本科阶段的重点在前两块的理解和手推优化部分知道概念、看懂例子即可。再往前一步是工具链词法和语法这两关完全可以用生成工具顶掉把精力留给真正需要自己写的部分。4.1 中间代码三地址码与堆栈式字节码中间表示的作用是隔离前端和后端前端只面对一种 IR后端只需为一种 IR 写代码生成换语言或换目标机器时不用全部重写。常见形式有抽象语法树、三地址码、控制流图三地址码又分四元式、三元式、间接三元式。堆栈式字节码是另一类指令只操作操作数栈没有寄存器概念生成简单、解释执行简单跨平台也方便。# 后序遍历 AST生成基于操作数栈的指令 def gen(node): if isinstance(node, Num): emit(push, node.value) # 叶子常量压栈 elif isinstance(node, Binary): gen(node.left) # 先算左子树结果留在栈上 gen(node.right) # 再算右子树结果留在栈上 emit({*: mul, : add}[node.op]) # 弹出两个操作数压回结果emit把一条指令追加到输出列表求值顺序是后序和表达式树的递归结构完全一致整个过程不需要寄存器分配所以实现起来很短。代价是指令条数偏多、执行效率不如寄存器机器适合解释器或者作为进一步编译到机器码的中间步骤。原文提到不少解释执行语言的底层字节码就是这种基于栈的指令原因就在这里生成机械、验证容易、移植成本低。4.2 代码生成指令选择与寄存器分配代码生成要把中间代码映射到目标机器指令两件核心工作是指令选择和寄存器分配。指令选择常用树模式匹配把语法树的一小段匹配成一条或几条机器指令同时决定用哪种寻址方式。寄存器分配是真正的难点变量是结点同时存活的两个变量之间连边用 K 种颜色染色颜色不够就把某些变量溢出到栈上。; 三地址码: t1 b * c; t2 a t1 LOAD R1, b ; 把 b 装入寄存器 R1 MUL R1, c ; R1 R1 * c结果即 t1 LOAD R2, a ; 把 a 装入 R2 ADD R2, R1 ; R2 a t1结果即 t2 STORE t2, R2 ; 把结果写回 t2 的内存位置这段假设 a、b、c、t2 都在内存R1、R2 是两个可用寄存器。真实代码生成还要处理寄存器不够时的溢出、常量直接折进寻址方式、以及指令之间的依赖和延迟。原文给的建议很实际如果生成的是堆栈式代码需要考虑的东西不多一旦走到寄存器为基础的代码生成寄存器怎么分配就会变成主要麻烦这也是初学者做完整编译器时最容易卡住的地方。4.3 代码优化本科阶段该停在哪优化分局部和全局。局部优化在基本块内做常量折叠、公共子表达式消除、死代码删除、强度削弱。全局优化要跨基本块依赖数据流分析循环优化收益最大——循环不变代码外提、归纳变量删除、循环展开都属于这一类。# 局部优化常量折叠只处理两个操作数都是常量的二元运算 def fold(node): if isinstance(node, Binary) and isinstance(node.left, Num) and isinstance(node.right, Num): value eval(f{node.left.value}{node.op}{node.right.value}) # 编译期求值 return Num(value) return node这段只对纯算术安全运算符有副作用、可能抛异常、或者涉及浮点精度时编译期求值会改变程序行为。写它是为了看清优化器在树上怎么工作不是让你真去手写一个优化器。本科教学的边界也在这里能说清基本块、控制流图、局部优化和循环优化的思路看得懂例子就够用了。原文的判断很直白——自己做的编译器能正确生成可执行代码已经很不错优化先放一放。4.4 教材分工与 Lex/Yacc 的定位三本常见教材各有分工选错书比不看书更耗时间教材代称定位适合阶段注意点龙书理论全景开篇用一个小例子串起全流程入门到系统复习例子先行部分章节偏理论偏现代工程实践的那本强调实际代码与较新话题想动手写编译器时需要一定编程基础以小型 C 子集编译器贯穿的那本入门细致逐步实现一个教学编译器零基础跟做深度不如前两本但路径完整Lex/Yacc 这类工具的价值在于把规则和动作放在一起改文法比改手写代码便宜得多。原文的建议很直接不建议连词法分析都亲手写语法文件也尽量找现成的改写出一个好文法几乎等于完成编译器的一半。非 Unix 平台上可以装一个类 Unix 兼容环境里面通常带 flex 和 bison用法和 Unix 下一致。实践顺序也有讲究先做解释型语言比直接生成机器代码简单先生成堆栈式代码比一上来就碰寄存器分配简单先用现成语法规约比从零写文法简单。5. 易错点清单五个最容易翻车的地方这一章按「易漏点 → 为什么漏 → 怎么补」组织都是复习和做题时反复出现的坑。每一条都值得在错题本上单独占一行考前翻一遍比重读教材快。5.1 词法分析与语法分析的职责边界易漏点把括号匹配、语句结束判断这类工作塞进词法分析。为什么漏词法分析用正则表达式描述正则没有计数能力天然处理不了任意层嵌套很多人觉得「顺手就做了」结果规则越写越复杂还是覆盖不全。怎么补记住词法只认词形嵌套结构必须留给上下文无关文法。判断标准很简单这条规则需不需要数括号层数、需不需要看上下文需要就放到语法层。词法阶段只做最长匹配和类别标注不承担结构判断。5.2 消除左递归时把语义动作弄丢易漏点做完直接左递归消除后原来产生式里的语义动作没有跟着重排属性算出来是错的。为什么漏教材公式只给文法变换语义动作怎么搬要自己补一搬就容易乱尤其是属性依赖左操作数的时候。怎么补先写带属性的翻译方案再做文法变换变换后逐个检查属性的求值顺序是否仍然成立需要时引入新的综合属性把中间结果带上去。写完用手推一个短串验证别只看文法是否等价。5.3 FIRST/FOLLOW 计算里的空串易漏点产生式右部能推出空串时忘记把 FOLLOW 左部并入 FIRST 右部FOLLOW 传播时漏掉「右部剩余部分可空」的情况。为什么漏空串规则条目多手算时容易只处理以终结符开头的情形ε 那条路径被跳过。怎么补固定顺序先 FIRST 后 FOLLOW每算一个非终结符就标注一次「是否可空」FOLLOW 传播时把「右部剩余部分可空」单独列一行核对。算完拿一个含 ε 的短文法验证能快速暴露遗漏。5.4 LR 项目集闭包与 GOTO 漏项易漏点求闭包时只展开点后面第一个非终结符忘记递归展开新加入的项目GOTO 只对终结符算漏掉非终结符。为什么漏项目集规范族手工推导步骤多中间漏一项后面整张表都错而且错得不明显。怎么补闭包按「点后是非终结符就把它的所有产生式加进来」反复做到不动点GOTO 对每个符号都算一遍终结符和非终结符一视同仁算完用项目数量核对数量对不上就回查闭包。5.5 继承属性与综合属性的求值顺序易漏点在自底向上分析里依赖继承属性或者在自顶向下分析里依赖只能自底向上算的综合属性。为什么漏属性文法的定义和实际遍历顺序脱节纸上推导成立代码跑起来拿不到值。怎么补先确定分析策略再选属性定义形式LL 配 L 属性、LR 配 S 属性确实需要交叉时在语法树上再走一遍独立的语义遍历用显式的多次遍历换顺序自由。这个坑的血泪经验是不要试图在一个遍历里算完所有属性。6. 复习清单按周推进的查漏补缺表复习编译原理最怕两种状态一种是书翻了三遍合上还是画不出那条流水线另一种是每章都懂一到手推分析表就错。下面这张按周推进的表把「看」换成「产出」每一周都有可验收的交付物。周次任务验收标准第 1 周不看书画出七段流水线标出每段输入输出能说清相邻两段之间传的是什么数据第 2 周手推两道正则到最小 DFA 的题写一个四则运算递归下降解析器子集构造不出错解析器能跑通带括号的表达式第 3 周FIRST/FOLLOW 各五题LR(0) 项目集规范族两道能独立构造分析表并指出冲突属于哪一类第 4 周语义分析类型检查一题堆栈式代码生成一题能逐条解释生成指令执行时操作数栈的变化每周结束时做一次三列错题记录知识点、错因、正确步骤。错因那一列不要写「粗心」要写到具体动作比如「闭包展开时漏了第二个非终结符」「FOLLOW 传播时忘了右部剩余可空」。第三列写可复现的步骤下次遇到同类题直接照做。这个方法看起来笨但比反复看书有效因为编译原理的失分本文还有配套的精品资源点击获取
