简介吉林大学《编译原理》期末试题解答是一份面向该校历年期末考试的真题汇编适合正在学习编译原理、准备期末或考研复习的本科生使用尤其适合需要熟悉吉大命题风格的同学。压缩包内为1个PDF文件约4.56MB目录清晰、按年份编排收录2003级至2017级及唐敖庆班的多套试题并穿插知识点总结与试题样例部分年度附有完整或部分解答。内容围绕词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与运行时系统等核心主题展开语法分析中的LL(1)、LR(1)等典型方法也常在历年试题中出现结合不同年份的考题设计能够帮助读者把抽象编译流程转化为具体答题思路。目前已有2739人学习下载适合用于系统梳理知识框架、考前限时训练以及对照解答查漏补缺既可作为期末冲刺材料也可用于日常巩固对编译器构造的整体理解。1. 吉林大学编译原理期末试题解答这份真题合集到底能帮你什么期末考试周拿到这份吉林大学编译原理期末试题解答最直接的感受就是终于有人把课本上分散的构造算法按真题的考法串成了一条线。编译原理这门课难就难在它不考记忆考的是手算能力——给定一个文法你能否在规定时间内把 FIRST/FOLLOW 集合算对、把 LR 项目集规范族推完、把四元式写对。这份题解覆盖了词法分析、语法分析、语法制导翻译和中间代码生成等核心考点适合两类人一类是吉大本校学生考前用它对照讲义查漏补缺另一类是使用同类教材清华大学出版社第三版是主流的考生用它来练手算节奏和踩坑意识。它不是标准答案的堆砌而是解题路径的复盘。2. 真题覆盖范围从词法到代码生成的考点地图2.1 题解里的模块划分与分值权重我拿到这份 PDF 后先做了一件事把里面的题目按编译原理的经典知识模块拆开对照吉大课程讲义的章节顺序标出每个模块的优先级。编译原理的期末卷面结构这些年变化不大题型一般固定为选择题或判断题考概念大题考手算流程。其中真正决定分数差距的是语法分析相关的两到三道大题。考核模块常见题型题解覆盖的解题步骤学习优先级词法分析正则式转 NFA/DFA、最小化 DFA子集构造法、Hopcroft 最小化高语法分析LL(1) 分析表、递归下降子程序FIRST/FOLLOW 计算、预测分析表构建极高LR 分析项目集规范族、SLR/LR(1) 分析表闭包与转移函数、冲突消解极高语法制导翻译属性文法、中间代码生成语义规则、四元式序列高运行时环境符号表组织、存储分配作用域与活动记录中代码优化基本块划分、DAG 构造局部优化、循环优化中这个模块优先级不是拍脑袋定的。吉大期末试卷里LL(1) 和 LR 分析的大题通常占 30 到 40 分词法分析占 15 到 20 分语法制导翻译约 10 到 15 分其余知识点分散在选择题和简答题里。所以复习顺序应该是先保证语法分析两道大题能完整推完再去抠词法和翻译的细节。2.2 拿到题解先做什么照考点矩阵核对讲义常见做法是拿到题解就从头到尾抄一遍这其实效率很低。我一般会先做一次“考点矩阵核对”把讲义目录的每一节标题列出来再翻题解找出对应题目标出“已覆盖”和“未出现”。这一步能让你快速发现两个问题一是讲义里有些章节老师上课没讲但考题出现了二是题解里反复出现的题型你在讲义上根本没做标记。以语法分析为例吉大讲义中关于自顶向下分析的章节必考的知识点是“消除左递归 提取左因子 FIRST/FOLLOW 集合计算 预测分析表构造”。题解里如果这四个子考点都有对应题目那你的复习重点就很明确把这几道题按考试标准重新手算三遍而不是去纠结递归下降子程序中每个函数的 C 语言实现细节。对照的时候建议在题解上用铅笔做标注每道题旁边写清楚它对应讲义第几页、考核的是哪个算法、你第一遍做的时候卡在哪一步。这份题解就从一个“答案文件”变成了“复习地图”。整个过程花不了半小时但后面的复习效率会高很多。3. 词法与自顶向下正则式转 NFA 和 FIRST/FOLLOW 的手算流程3.1 正则式转 NFA用 Thompson 构造法拿满步骤分词法分析的大题通常是给一个正则表达式要求画出 NFA再通过子集构造法转成 DFA最后做最小化。这份题解里这类题目的答案写得比较完整但如果你只是看答案很难发现自己到底在哪一步丢分。以经典真题a(b|a)*b为例标准做法是先用 Thompson 构造法搭出 NFA 骨架步骤 1拆解正则式结构 a(b|a)*b ——连接运算拆成三个部分a、(b|a)*、b 步骤 2为 a 构造基础 NFA 状态 0 --a-- 状态 1 步骤 3为 (b|a)* 构造 NFA先构造 b|a 的并再加星号 b|a 的并结构从新起点分别用 b 和 a 指向两个分支终点 星号结构在并结构外围增加 ε 回边和跳过边 步骤 4为末尾的 b 构造 NFA 状态 --b-- 终态 步骤 5依次连接三段得到完整 NFA这里最容易被扣分的不是画图而是 ε 转移边。很多人在构造(b|a)*的星号结构时只画了回边忘了画“直接跳过整个子结构”的那条 ε 边。少了这条边NFA 就少了“匹配零次”的路径后续子集构造出来的 DFA 也会少一个状态后面的最小化步骤就全乱了。从 NFA 转 DFA 时子集构造法的核心是逐层计算 ε-闭包。常见做法是先把 NFA 的起始状态的 ε-闭包算出来作为 DFA 的初态然后对每个输入符号计算转移后的新状态集。题解里这一步通常直接给结果表我建议你自己在草稿纸上重新推一遍每一行都标注“该状态集合包含 NFA 的哪些状态”这样一旦结果对不上能快速定位是闭包算错还是转移表抄错。3.2 FIRST 与 FOLLOW左递归消解之后的集合计算语法分析部分的第一道大题通常是给一个含左递归的文法要求先消除左递归再计算 FIRST 和 FOLLOW 集合最后构造 LL(1) 分析表。以课本高频文法为例原文法 E - E T | T T - T * F | F F - (E) | i 消除左递归后 E - T E E - T E | ε T - F T T - * F T | ε F - (E) | i消除左递归这一步本身不难但有个细节值得强调只有直接左递归需要这种改写间接左递归要先代入再处理。吉大期末题里如果出现间接左递归通常会和“提左因子”结合考你要先判断文法中是否存在A - B...且B - A...这种两条以上产生式构成的环路。题解里如果某道题直接给出了消除后的文法建议你反推一步验证是否是“先判断、后代入、再改写”的顺序。FIRST 集合的计算规则可以提炼成一句口诀产生式右部第一个符号是终结符就直接加入是非终结符就递归查它的 FIRST能推出 ε 就继续看下一个符号。手算时建议用迭代法而不是递归法因为迭代法更容易看出集合是否还在增长初始化所有 FIRST 集合为空 第一轮扫描 E - T EFIRST(E) 加入 FIRST(T) E - T EFIRST(E) 加入 {} E - εFIRST(E) 加入 {ε} T - F TFIRST(T) 加入 FIRST(F) T - * F TFIRST(T) 加入 {*} T - εFIRST(T) 加入 {ε} F - (E)FIRST(F) 加入 {(} F - iFIRST(F) 加入 {i} 第二轮扫描直到所有集合不再变化这里的关键点是因为E的 FIRST 会通过E - T E继承T的 FIRST而T又会继承F的 FIRST所以你必须一轮一轮地传播。手算时经常有人只扫一遍就停导致FIRST(E)里漏掉(和i。判卷时这种错误一眼就能看出来因为后面的 LL(1) 分析表对应位置会空掉。FOLLOW 集合的计算规则比 FIRST 更容易出错。核心是三条规则开始符号的 FOLLOW 加入#产生式右部某个非终结符后面跟着另一个符号就把后者的 FIRST去掉 ε加入前者的 FOLLOW产生式右部某个非终结符后面没有符号或者后面跟着的符号能推出 ε就把产生式左部的 FOLLOW 加入这个非终结符的 FOLLOW。注意第三条规则中的“能推出 ε”判断需要你先把所有能推出 ε 的非终结符列出来这个准备工作很多人会忘。3.3 LL(1) 分析表构造与冲突检查算完 FIRST 和 FOLLOW 之后构造 LL(1) 分析表就是一个填表动作对每个产生式用它的 FIRST 集合中的每个终结符作为触发条件填入对应格子如果 FIRST 里有 ε则对该产生式左部的 FOLLOW 集合中的每个终结符也填入这个产生式。填完之后必须做一次冲突检查同一个格子如果出现了两个不同的产生式说明文法不是 LL(1) 的。题解里如果某道题的分析表出现了冲突通常答案会注明“该文法不是 LL(1) 文法”。这时候你要能说出冲突的根源是什么是左因子未提取干净还是 FIRST/FOLLOW 集合本身有交集。我见过不少同学把这种冲突当作计算错误然后反复重算浪费大量时间还产生了自我怀疑。遇到冲突题正确姿势是回到文法层面分析先用“提取左因子”消除公共前缀再看提取后是否还存在冲突如果还存在就说明这个文法不适合用 LL(1) 分析需要改用 LR 方法。顺带说一句清华大学出版社第三版第二章的课后习题里就有不少 FIRST/FOLLOW 的练习和吉大期末题的手算要求几乎一致。如果你觉得题解中的题目量不够练手拿那本教材的第二章习题当补充题库是性价比最高的选择——考纲重合度在九成以上。4. LR 分析项目集规范族、SLR 分析表与冲突处理4.1 构造项目集规范族闭包操作最容易翻车LR 分析的大题通常是整张卷子里最耗时的也是最能拉开差距的。它的标准流程是写出增广文法加一条S - S构造 LR(0) 项目集规范族再根据项目集画出 SLR(1) 分析表。题解里这一步通常只给最终的项目集列表中间的闭包计算过程被省略了但这恰恰是多数人丢分的地方。以课本经典文法为例增广文法 0. S - S 1. S - L R 2. S - R 3. L - * R 4. L - i 5. R - L构造初始项目集 I0 时首先要放S - .S然后对这个项目做闭包点号后面是S所以要加入所有左部为S的产生式项目即S - .L R和S - .R。这时候点号后面的L和R又都是非终结符所以继续加入L - .* R、L - .i、R - .L。注意R - .L的点号后面是L而L的产生式已经在集合里了所以闭包到此结束。I0 { S - .S, S - .L R, S - .R, L - .* R, L - .i, R - .L }这个闭包过程里最常见的错误是漏掉R - .L这一条。因为R的出现是由S - .R引入的而R - .L中又再次出现了L形成一个闭包链。漏掉一环后续的整个项目集规范族都会错位分析表自然也对不上。我在帮人核对时发现凡是答案和标准结果差一个状态的八成都是闭包这一步少补了一条产生式。4.2 SLR(1) 冲突消解FOLLOW 集的不一定够用构造完项目集规范族之后下一步是画 SLR(1) 分析表。这张表的行是状态编号列是终结符和非终结符动作分为移进、归约、接受和转移。构建规则可以概括为三句话项目A - α.aβ中.a且a是终结符则在状态 i 与输入 a 对应的格子填s jj 是转移后的状态项目A - α.是归约项目则在状态 i 对应FOLLOW(A)中每个终结符的格子填r kk 是产生式编号项目S - S.则在状态 i 对应#的格子填acc。这个规则的实现难点不在记忆而在判断当归约项目和移进项目同时出现在一个状态里时需要检查它们的动作集合是否有交集。经典例子是上面那个文法项目集 I2 里既有S - L.R点号后面是终结符要移进又有R - L.归约项目。如果用 FOLLOW(R) 来决定归约动作而 FOLLOW(R) 恰好包含因为S - L R中 R 后面没有符号会把FOLLOW(S)里的#传给FOLLOW(R)但是否在 FOLLOW(R) 里要看R出现在L R的哪个位置——R 在产生式末尾所以 FOLLOW(R) 包含 FOLLOW(S) 即#而在L后面出现在S - L R的中间它不属于 FOLLOW(R)此时冲突能否被解决取决于 FOLLOW(R) 是否包含。判断方法很简单把 FOLLOW(R) 集合展开看它和移进符号是否相交。如果不相交SLR(1) 可以处理这个冲突如果相交说明 SLR(1) 分析表会出现冲突格子这道题就需要升级到 LR(1) 或 LALR 分析。期末卷面上如果出现这种设计通常是为了考你“能判断出该文法不是 SLR(1)”这个结论而不是真的让你构造完整的 LR(1) 自动机——LR(1) 的项目集会膨胀到几十个手算不现实。4.3 LR 分析的备考优先级先保证 SLR再谈 LR(1)结合这份题解覆盖的内容我给的复习优先级是先确保 LR(0) 项目集规范族能完整推完中间不能断再练 SLR(1) 分析表的构建和冲突判断最后才是 LR(1) 的构造思路。因为期末大题的细节通常是“构造 SLR 分析表并说明冲突”LR(1) 只要理解“通过向前看符号来细分状态”这个核心思想就能应付简答题。如果你在推项目集时发现状态数量和答案不一致不要急着往下画。先检查两个最容易出错的位置一是闭包过程中新增的非终结符产生式是否补全二是从当前状态读入某个符号后转移到的下一个状态是否包含了所有“点号在该符号后”的项目。前者是闭包遗漏后者是转移遗漏这两种错误在卷面上体现出来的问题完全不同——闭包遗漏会导致整个状态家族少一支转移遗漏则只影响一个状态的内容。5. 避坑与排查判卷视角下最容易丢分的五类错误5.1 高频踩坑记录第一类FOLLOW 集合里混入终结符。现象计算FOLLOW(F)时把产生式F - (E)中E后面的内容直接加进去得到错误集合。原因没有区分“产生式右部中该非终结符后面的符号”和“该非终结符所在产生式左部的 FOLLOW”。解决每次只盯着“某个非终结符在右部出现的位置”看它后面紧跟的是什么如果一个非终结符在多个产生式的右部出现要为每个位置分别计算再取并集。第二类项目集闭包漏补产生式。现象状态列表少一个状态或某状态项目数明显偏少。原因闭包操作只做了一轮没有意识到新加入的非终结符项目会再次引入新的非终结符。解决每次向闭包中增加新项目后扫描这个新项目点号后的非终结符检查其产生式是否已在集合中循环直到不再有新项目加入。第三类四元式临时变量编号混乱。现象中间代码生成时同一个临时变量被复用了两次或者赋值语句的运算顺序错位。原因没有按“每产生一个新值就申请一个新临时变量”的原则编号。解决写四元式时强制按t1、t2、t3...顺序递增编号每个运算结果的临时变量不能复用遇到嵌套表达式时先算内层再算外层输出顺序和运算顺序保持一致。第四类预测分析表行列写反。现象考点对、算法对但表格里移进/归约动作填错了格子。原因把 FIRST 触发的“填入产生式”错写成按列查找或按行查找时把非终结符行和终结符列搞混。解决填表前先画一个坐标标注行头是非终结符列头是终结符和#每填一个格子前先确认“当前状态 当前输入”的组合。第五类DFA 最小化时把终态和非终态混在一起。现象最小化后的状态数比标准答案多或少。原因第一次划分时没有把终态集合和非终态集合严格分开。解决第一步永远是“终态一组、非终态一组”的初始划分后续每轮划分只针对每一组内部进行组与组之间不做合并。5.2 交卷前的自查清单做完一道手算大题后用这套清单检查一遍FIRST 集合扫描了几轮是否每轮都有新增内容FOLLOW 集合是否对每个非终结符都考虑了“作为开始符号”和“出现在产生式右部”两类情况LL(1) 分析表是否有冲突格子冲突时是否明确写了“非 LL(1)”项目集的闭包过程是否循环到没有新项目加入为止四元式里每个临时变量是否只赋值一次最后检查所有表格里终结符是否加了下划线标识#是否单独占一列。这套检查流程走下来能挽回的分数通常在 10 分以上。其中第五类错误最隐蔽因为它不会让后续步骤崩盘但你最终的结果就是和标准答案不一致。解决办法是养成一个习惯做完最小化后用一个短的输入串走一遍新旧两个 DFA看接受状态的行为是否一致。如果一致说明最小化正确不一致说明划分有误。6. 把真题答案变成自己的复习脚本三轮复盘与逆推考点6.1 三轮复盘法从抄答案到限时盲做题解最大的价值不是“看不懂时查一下”而是“做完后对一下”。我的习惯是把每道大题做三轮第一轮对照题解边看边在草稿纸上复现每一步目标是理解答案为什么要这么走第二轮合上题解按考试标准在 20 分钟内独立完成过程中不许翻任何资料第三轮再次合上题解但故意把题目条件改一两个数字比如把正则式里的*改成把文法中的某个终结符换掉检验自己是不是真的掌握了算法而不是背住了答案。第三轮是最有效的。因为编译原理的题目只要换了条件整个计算流程就要重新走一遍如果你只会背某道题的固定过程遇到变体就会暴露。改条件时优先改那些“不影响算法流程但影响结果”的部分比如换终结符、加一个产生式、把左递归改成间接左递归这些都是吉大出题人的常见改法。6.2 逆推考点给每道题贴上“解法触发器”在看题解时我会额外做一件事在每道题的答案末尾写一行“解法触发器”——用一句话概括“看到什么条件就用什么方法”。比如看到“文法含左递归”触发“先消除左递归再算 FIRST”看到“状态里同时有移进和归约”触发“检查 FOLLOW 是否相交判断 SLR 可行性”看到“属性文法求值”触发“先标继承属性和综合属性再画依赖图”。这行字写多了之后翻题解就不再是找答案而是复习方法论。我把每道题的触发器整理成一个简单表格贴在教材扉页上词法分析对应的触发器是“正则式优先拆连接和闭包再处理并”LL(1) 对应“算集合要迭代到不动点查冲突要回文法”LR 对应“闭包循环补产生式冲突看 FOLLOW 交集”。考试的时候看到题目第一步不是动手算而是先回忆这道题对应的触发器这样能避免“一看题目很熟一算就漏步骤”的情况。从那以后我每次帮人看编译原理的卷子都强制先问一句“你自己手推过几遍”如果答案是“只看过答案”我就会让他先把答案合上重算一遍再来找我讨论。这个过程很枯燥但确实是把这份试题解答从“参考资料”变成“肌肉记忆”的唯一路径。希望这份题解和你自己的三轮复盘能帮你把编译原理这道坎平稳迈过去。本文还有配套的精品资源点击获取
编译原理期末试题解答：从FIRST/FOLLOW到LR分析
简介吉林大学《编译原理》期末试题解答是一份面向该校历年期末考试的真题汇编适合正在学习编译原理、准备期末或考研复习的本科生使用尤其适合需要熟悉吉大命题风格的同学。压缩包内为1个PDF文件约4.56MB目录清晰、按年份编排收录2003级至2017级及唐敖庆班的多套试题并穿插知识点总结与试题样例部分年度附有完整或部分解答。内容围绕词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与运行时系统等核心主题展开语法分析中的LL(1)、LR(1)等典型方法也常在历年试题中出现结合不同年份的考题设计能够帮助读者把抽象编译流程转化为具体答题思路。目前已有2739人学习下载适合用于系统梳理知识框架、考前限时训练以及对照解答查漏补缺既可作为期末冲刺材料也可用于日常巩固对编译器构造的整体理解。1. 吉林大学编译原理期末试题解答这份真题合集到底能帮你什么期末考试周拿到这份吉林大学编译原理期末试题解答最直接的感受就是终于有人把课本上分散的构造算法按真题的考法串成了一条线。编译原理这门课难就难在它不考记忆考的是手算能力——给定一个文法你能否在规定时间内把 FIRST/FOLLOW 集合算对、把 LR 项目集规范族推完、把四元式写对。这份题解覆盖了词法分析、语法分析、语法制导翻译和中间代码生成等核心考点适合两类人一类是吉大本校学生考前用它对照讲义查漏补缺另一类是使用同类教材清华大学出版社第三版是主流的考生用它来练手算节奏和踩坑意识。它不是标准答案的堆砌而是解题路径的复盘。2. 真题覆盖范围从词法到代码生成的考点地图2.1 题解里的模块划分与分值权重我拿到这份 PDF 后先做了一件事把里面的题目按编译原理的经典知识模块拆开对照吉大课程讲义的章节顺序标出每个模块的优先级。编译原理的期末卷面结构这些年变化不大题型一般固定为选择题或判断题考概念大题考手算流程。其中真正决定分数差距的是语法分析相关的两到三道大题。考核模块常见题型题解覆盖的解题步骤学习优先级词法分析正则式转 NFA/DFA、最小化 DFA子集构造法、Hopcroft 最小化高语法分析LL(1) 分析表、递归下降子程序FIRST/FOLLOW 计算、预测分析表构建极高LR 分析项目集规范族、SLR/LR(1) 分析表闭包与转移函数、冲突消解极高语法制导翻译属性文法、中间代码生成语义规则、四元式序列高运行时环境符号表组织、存储分配作用域与活动记录中代码优化基本块划分、DAG 构造局部优化、循环优化中这个模块优先级不是拍脑袋定的。吉大期末试卷里LL(1) 和 LR 分析的大题通常占 30 到 40 分词法分析占 15 到 20 分语法制导翻译约 10 到 15 分其余知识点分散在选择题和简答题里。所以复习顺序应该是先保证语法分析两道大题能完整推完再去抠词法和翻译的细节。2.2 拿到题解先做什么照考点矩阵核对讲义常见做法是拿到题解就从头到尾抄一遍这其实效率很低。我一般会先做一次“考点矩阵核对”把讲义目录的每一节标题列出来再翻题解找出对应题目标出“已覆盖”和“未出现”。这一步能让你快速发现两个问题一是讲义里有些章节老师上课没讲但考题出现了二是题解里反复出现的题型你在讲义上根本没做标记。以语法分析为例吉大讲义中关于自顶向下分析的章节必考的知识点是“消除左递归 提取左因子 FIRST/FOLLOW 集合计算 预测分析表构造”。题解里如果这四个子考点都有对应题目那你的复习重点就很明确把这几道题按考试标准重新手算三遍而不是去纠结递归下降子程序中每个函数的 C 语言实现细节。对照的时候建议在题解上用铅笔做标注每道题旁边写清楚它对应讲义第几页、考核的是哪个算法、你第一遍做的时候卡在哪一步。这份题解就从一个“答案文件”变成了“复习地图”。整个过程花不了半小时但后面的复习效率会高很多。3. 词法与自顶向下正则式转 NFA 和 FIRST/FOLLOW 的手算流程3.1 正则式转 NFA用 Thompson 构造法拿满步骤分词法分析的大题通常是给一个正则表达式要求画出 NFA再通过子集构造法转成 DFA最后做最小化。这份题解里这类题目的答案写得比较完整但如果你只是看答案很难发现自己到底在哪一步丢分。以经典真题a(b|a)*b为例标准做法是先用 Thompson 构造法搭出 NFA 骨架步骤 1拆解正则式结构 a(b|a)*b ——连接运算拆成三个部分a、(b|a)*、b 步骤 2为 a 构造基础 NFA 状态 0 --a-- 状态 1 步骤 3为 (b|a)* 构造 NFA先构造 b|a 的并再加星号 b|a 的并结构从新起点分别用 b 和 a 指向两个分支终点 星号结构在并结构外围增加 ε 回边和跳过边 步骤 4为末尾的 b 构造 NFA 状态 --b-- 终态 步骤 5依次连接三段得到完整 NFA这里最容易被扣分的不是画图而是 ε 转移边。很多人在构造(b|a)*的星号结构时只画了回边忘了画“直接跳过整个子结构”的那条 ε 边。少了这条边NFA 就少了“匹配零次”的路径后续子集构造出来的 DFA 也会少一个状态后面的最小化步骤就全乱了。从 NFA 转 DFA 时子集构造法的核心是逐层计算 ε-闭包。常见做法是先把 NFA 的起始状态的 ε-闭包算出来作为 DFA 的初态然后对每个输入符号计算转移后的新状态集。题解里这一步通常直接给结果表我建议你自己在草稿纸上重新推一遍每一行都标注“该状态集合包含 NFA 的哪些状态”这样一旦结果对不上能快速定位是闭包算错还是转移表抄错。3.2 FIRST 与 FOLLOW左递归消解之后的集合计算语法分析部分的第一道大题通常是给一个含左递归的文法要求先消除左递归再计算 FIRST 和 FOLLOW 集合最后构造 LL(1) 分析表。以课本高频文法为例原文法 E - E T | T T - T * F | F F - (E) | i 消除左递归后 E - T E E - T E | ε T - F T T - * F T | ε F - (E) | i消除左递归这一步本身不难但有个细节值得强调只有直接左递归需要这种改写间接左递归要先代入再处理。吉大期末题里如果出现间接左递归通常会和“提左因子”结合考你要先判断文法中是否存在A - B...且B - A...这种两条以上产生式构成的环路。题解里如果某道题直接给出了消除后的文法建议你反推一步验证是否是“先判断、后代入、再改写”的顺序。FIRST 集合的计算规则可以提炼成一句口诀产生式右部第一个符号是终结符就直接加入是非终结符就递归查它的 FIRST能推出 ε 就继续看下一个符号。手算时建议用迭代法而不是递归法因为迭代法更容易看出集合是否还在增长初始化所有 FIRST 集合为空 第一轮扫描 E - T EFIRST(E) 加入 FIRST(T) E - T EFIRST(E) 加入 {} E - εFIRST(E) 加入 {ε} T - F TFIRST(T) 加入 FIRST(F) T - * F TFIRST(T) 加入 {*} T - εFIRST(T) 加入 {ε} F - (E)FIRST(F) 加入 {(} F - iFIRST(F) 加入 {i} 第二轮扫描直到所有集合不再变化这里的关键点是因为E的 FIRST 会通过E - T E继承T的 FIRST而T又会继承F的 FIRST所以你必须一轮一轮地传播。手算时经常有人只扫一遍就停导致FIRST(E)里漏掉(和i。判卷时这种错误一眼就能看出来因为后面的 LL(1) 分析表对应位置会空掉。FOLLOW 集合的计算规则比 FIRST 更容易出错。核心是三条规则开始符号的 FOLLOW 加入#产生式右部某个非终结符后面跟着另一个符号就把后者的 FIRST去掉 ε加入前者的 FOLLOW产生式右部某个非终结符后面没有符号或者后面跟着的符号能推出 ε就把产生式左部的 FOLLOW 加入这个非终结符的 FOLLOW。注意第三条规则中的“能推出 ε”判断需要你先把所有能推出 ε 的非终结符列出来这个准备工作很多人会忘。3.3 LL(1) 分析表构造与冲突检查算完 FIRST 和 FOLLOW 之后构造 LL(1) 分析表就是一个填表动作对每个产生式用它的 FIRST 集合中的每个终结符作为触发条件填入对应格子如果 FIRST 里有 ε则对该产生式左部的 FOLLOW 集合中的每个终结符也填入这个产生式。填完之后必须做一次冲突检查同一个格子如果出现了两个不同的产生式说明文法不是 LL(1) 的。题解里如果某道题的分析表出现了冲突通常答案会注明“该文法不是 LL(1) 文法”。这时候你要能说出冲突的根源是什么是左因子未提取干净还是 FIRST/FOLLOW 集合本身有交集。我见过不少同学把这种冲突当作计算错误然后反复重算浪费大量时间还产生了自我怀疑。遇到冲突题正确姿势是回到文法层面分析先用“提取左因子”消除公共前缀再看提取后是否还存在冲突如果还存在就说明这个文法不适合用 LL(1) 分析需要改用 LR 方法。顺带说一句清华大学出版社第三版第二章的课后习题里就有不少 FIRST/FOLLOW 的练习和吉大期末题的手算要求几乎一致。如果你觉得题解中的题目量不够练手拿那本教材的第二章习题当补充题库是性价比最高的选择——考纲重合度在九成以上。4. LR 分析项目集规范族、SLR 分析表与冲突处理4.1 构造项目集规范族闭包操作最容易翻车LR 分析的大题通常是整张卷子里最耗时的也是最能拉开差距的。它的标准流程是写出增广文法加一条S - S构造 LR(0) 项目集规范族再根据项目集画出 SLR(1) 分析表。题解里这一步通常只给最终的项目集列表中间的闭包计算过程被省略了但这恰恰是多数人丢分的地方。以课本经典文法为例增广文法 0. S - S 1. S - L R 2. S - R 3. L - * R 4. L - i 5. R - L构造初始项目集 I0 时首先要放S - .S然后对这个项目做闭包点号后面是S所以要加入所有左部为S的产生式项目即S - .L R和S - .R。这时候点号后面的L和R又都是非终结符所以继续加入L - .* R、L - .i、R - .L。注意R - .L的点号后面是L而L的产生式已经在集合里了所以闭包到此结束。I0 { S - .S, S - .L R, S - .R, L - .* R, L - .i, R - .L }这个闭包过程里最常见的错误是漏掉R - .L这一条。因为R的出现是由S - .R引入的而R - .L中又再次出现了L形成一个闭包链。漏掉一环后续的整个项目集规范族都会错位分析表自然也对不上。我在帮人核对时发现凡是答案和标准结果差一个状态的八成都是闭包这一步少补了一条产生式。4.2 SLR(1) 冲突消解FOLLOW 集的不一定够用构造完项目集规范族之后下一步是画 SLR(1) 分析表。这张表的行是状态编号列是终结符和非终结符动作分为移进、归约、接受和转移。构建规则可以概括为三句话项目A - α.aβ中.a且a是终结符则在状态 i 与输入 a 对应的格子填s jj 是转移后的状态项目A - α.是归约项目则在状态 i 对应FOLLOW(A)中每个终结符的格子填r kk 是产生式编号项目S - S.则在状态 i 对应#的格子填acc。这个规则的实现难点不在记忆而在判断当归约项目和移进项目同时出现在一个状态里时需要检查它们的动作集合是否有交集。经典例子是上面那个文法项目集 I2 里既有S - L.R点号后面是终结符要移进又有R - L.归约项目。如果用 FOLLOW(R) 来决定归约动作而 FOLLOW(R) 恰好包含因为S - L R中 R 后面没有符号会把FOLLOW(S)里的#传给FOLLOW(R)但是否在 FOLLOW(R) 里要看R出现在L R的哪个位置——R 在产生式末尾所以 FOLLOW(R) 包含 FOLLOW(S) 即#而在L后面出现在S - L R的中间它不属于 FOLLOW(R)此时冲突能否被解决取决于 FOLLOW(R) 是否包含。判断方法很简单把 FOLLOW(R) 集合展开看它和移进符号是否相交。如果不相交SLR(1) 可以处理这个冲突如果相交说明 SLR(1) 分析表会出现冲突格子这道题就需要升级到 LR(1) 或 LALR 分析。期末卷面上如果出现这种设计通常是为了考你“能判断出该文法不是 SLR(1)”这个结论而不是真的让你构造完整的 LR(1) 自动机——LR(1) 的项目集会膨胀到几十个手算不现实。4.3 LR 分析的备考优先级先保证 SLR再谈 LR(1)结合这份题解覆盖的内容我给的复习优先级是先确保 LR(0) 项目集规范族能完整推完中间不能断再练 SLR(1) 分析表的构建和冲突判断最后才是 LR(1) 的构造思路。因为期末大题的细节通常是“构造 SLR 分析表并说明冲突”LR(1) 只要理解“通过向前看符号来细分状态”这个核心思想就能应付简答题。如果你在推项目集时发现状态数量和答案不一致不要急着往下画。先检查两个最容易出错的位置一是闭包过程中新增的非终结符产生式是否补全二是从当前状态读入某个符号后转移到的下一个状态是否包含了所有“点号在该符号后”的项目。前者是闭包遗漏后者是转移遗漏这两种错误在卷面上体现出来的问题完全不同——闭包遗漏会导致整个状态家族少一支转移遗漏则只影响一个状态的内容。5. 避坑与排查判卷视角下最容易丢分的五类错误5.1 高频踩坑记录第一类FOLLOW 集合里混入终结符。现象计算FOLLOW(F)时把产生式F - (E)中E后面的内容直接加进去得到错误集合。原因没有区分“产生式右部中该非终结符后面的符号”和“该非终结符所在产生式左部的 FOLLOW”。解决每次只盯着“某个非终结符在右部出现的位置”看它后面紧跟的是什么如果一个非终结符在多个产生式的右部出现要为每个位置分别计算再取并集。第二类项目集闭包漏补产生式。现象状态列表少一个状态或某状态项目数明显偏少。原因闭包操作只做了一轮没有意识到新加入的非终结符项目会再次引入新的非终结符。解决每次向闭包中增加新项目后扫描这个新项目点号后的非终结符检查其产生式是否已在集合中循环直到不再有新项目加入。第三类四元式临时变量编号混乱。现象中间代码生成时同一个临时变量被复用了两次或者赋值语句的运算顺序错位。原因没有按“每产生一个新值就申请一个新临时变量”的原则编号。解决写四元式时强制按t1、t2、t3...顺序递增编号每个运算结果的临时变量不能复用遇到嵌套表达式时先算内层再算外层输出顺序和运算顺序保持一致。第四类预测分析表行列写反。现象考点对、算法对但表格里移进/归约动作填错了格子。原因把 FIRST 触发的“填入产生式”错写成按列查找或按行查找时把非终结符行和终结符列搞混。解决填表前先画一个坐标标注行头是非终结符列头是终结符和#每填一个格子前先确认“当前状态 当前输入”的组合。第五类DFA 最小化时把终态和非终态混在一起。现象最小化后的状态数比标准答案多或少。原因第一次划分时没有把终态集合和非终态集合严格分开。解决第一步永远是“终态一组、非终态一组”的初始划分后续每轮划分只针对每一组内部进行组与组之间不做合并。5.2 交卷前的自查清单做完一道手算大题后用这套清单检查一遍FIRST 集合扫描了几轮是否每轮都有新增内容FOLLOW 集合是否对每个非终结符都考虑了“作为开始符号”和“出现在产生式右部”两类情况LL(1) 分析表是否有冲突格子冲突时是否明确写了“非 LL(1)”项目集的闭包过程是否循环到没有新项目加入为止四元式里每个临时变量是否只赋值一次最后检查所有表格里终结符是否加了下划线标识#是否单独占一列。这套检查流程走下来能挽回的分数通常在 10 分以上。其中第五类错误最隐蔽因为它不会让后续步骤崩盘但你最终的结果就是和标准答案不一致。解决办法是养成一个习惯做完最小化后用一个短的输入串走一遍新旧两个 DFA看接受状态的行为是否一致。如果一致说明最小化正确不一致说明划分有误。6. 把真题答案变成自己的复习脚本三轮复盘与逆推考点6.1 三轮复盘法从抄答案到限时盲做题解最大的价值不是“看不懂时查一下”而是“做完后对一下”。我的习惯是把每道大题做三轮第一轮对照题解边看边在草稿纸上复现每一步目标是理解答案为什么要这么走第二轮合上题解按考试标准在 20 分钟内独立完成过程中不许翻任何资料第三轮再次合上题解但故意把题目条件改一两个数字比如把正则式里的*改成把文法中的某个终结符换掉检验自己是不是真的掌握了算法而不是背住了答案。第三轮是最有效的。因为编译原理的题目只要换了条件整个计算流程就要重新走一遍如果你只会背某道题的固定过程遇到变体就会暴露。改条件时优先改那些“不影响算法流程但影响结果”的部分比如换终结符、加一个产生式、把左递归改成间接左递归这些都是吉大出题人的常见改法。6.2 逆推考点给每道题贴上“解法触发器”在看题解时我会额外做一件事在每道题的答案末尾写一行“解法触发器”——用一句话概括“看到什么条件就用什么方法”。比如看到“文法含左递归”触发“先消除左递归再算 FIRST”看到“状态里同时有移进和归约”触发“检查 FOLLOW 是否相交判断 SLR 可行性”看到“属性文法求值”触发“先标继承属性和综合属性再画依赖图”。这行字写多了之后翻题解就不再是找答案而是复习方法论。我把每道题的触发器整理成一个简单表格贴在教材扉页上词法分析对应的触发器是“正则式优先拆连接和闭包再处理并”LL(1) 对应“算集合要迭代到不动点查冲突要回文法”LR 对应“闭包循环补产生式冲突看 FOLLOW 交集”。考试的时候看到题目第一步不是动手算而是先回忆这道题对应的触发器这样能避免“一看题目很熟一算就漏步骤”的情况。从那以后我每次帮人看编译原理的卷子都强制先问一句“你自己手推过几遍”如果答案是“只看过答案”我就会让他先把答案合上重算一遍再来找我讨论。这个过程很枯燥但确实是把这份试题解答从“参考资料”变成“肌肉记忆”的唯一路径。希望这份题解和你自己的三轮复盘能帮你把编译原理这道坎平稳迈过去。本文还有配套的精品资源点击获取
