简介东南大学编译原理期末试卷PDF面向高校计算机专业学生、考研备考者及自学者用于巩固编译原理核心知识。资源共1个PDF文件压缩包仅46KB内含7道英文原题覆盖上下文无关文法构造a/b/c出现偶数次、b开头等约束、最小状态DFA设计、左递归消除与LL(1)分析表构建、算符优先文法判定、LR(1)分析表构造、注释分析树绘制及C程序运行时存储组织与活动记录等核心考点。通过本试卷可系统检验对词法、语法和语义分析的理解熟悉东大出题风格和英文命题形式题目从基础文法设计到栈帧布局梯度合理适合期末冲刺、考研专业课自测或教师命题参考。已有214人学习下载资源轻量且具较高参考价值。1. 一份东南大学编译原理试卷为什么值得当“复习主线”来用期末考试前两周我把手头能找到的几份编译原理真题卷按考点拆了一遍发现一个反直觉的事实真正卡住我的不是那些偏题怪题而是几个基础概念的“组合考法”。比如文法消左递归和 FIRST 集计算放在同一道题里单看课本都能懂合在一起就不知道先写哪个、写到哪一步算完。一份东南大学编译原理试卷价值恰好在这里——它用一道大题把三四个基础点串起来逼你用“做题”而不是“看书”的方式确认自己到底会不会。考研备考、期末冲刺、甚至工作中想回头补编译原理基础的人都能拿它当复习主线先裸做、再对点补、最后提速。这份资源不是用来“背题”的是用来给知识漏洞做定位的。2. 试卷背后的考点地图从词法分析到代码生成的六个知识块拿到一份真题第一件事不是动笔做而是先看它考了什么。把三到五年内的试卷放在一起横向扫一遍你会发现编译原理的考点高度稳定变来变去就是六个知识块。了解这张地图你才能决定哪块花大力气、哪块混个眼熟。2.1 词法与语法分析占分最稳的“送分区域”词法分析在试卷里出现的形式几乎只有三种写正则表达式、根据正则构造 DFA、用子集法把 NFA 转 DFA。语法分析则是写文法、消除左递归、提左公因子、计算 FIRST 与 FOLLOW 集、构造 LL(1) 或 LR 分析表。这块内容在试卷里通常占三十分上下是所有大题里最接近“背模板”的——它的解题步骤固定只要你按顺序写就算最后结果错了步骤分也能拿回大半。我在复习时把词法分析当作热身题每天早上先做一道 DFA 构造题找手感。语法分析则当成主菜因为它的变形最多有的年份考 LL(1)有的年份考 SLR(1)还有的把两种放一起让你对比。一个值得注意的边界是东南大学这类课程试卷不会考太偏的形式化定义它更倾向“给一个文法让你构造分析表并说明冲突”也就是说动手构造的过程本身就占了七成分数。2.2 文法制导翻译与中间代码命题最偏重的部分这一块是很多人的分水岭。试卷里它通常以“给一段程序或一个文法写出带属性的翻译方案然后生成三地址代码”的形式出现。考的内容包括属性文法的定义、综合属性与继承属性的区别、后缀翻译方案、布尔表达式短路计算、回填技术。它难不是因为概念抽象而是因为步骤长一步错步步错。我见过不少同学的复习误区是花大量时间背属性文法的定义结果到了考场上发现考的是“给一个声明语句写出其翻译并生成中间代码”——你背的概念根本用不上。正确的备考姿势应该是对着真题里的中间代码大题把“声明语句翻译”“赋值语句翻译”“布尔表达式翻译”三个模板练熟。每一道题都要从文法规则一路写到三地址码中间不能跳步。2.3 运行时环境与代码优化容易被忽略的二十到三十分运行时环境在这类试卷里经常以简答题出现比如问“静态作用域与动态作用域的区别”“活动记录里保存哪些内容”。代码优化则考察基本块划分、DAG 图构造、循环优化。这部分之所以容易被忽略是因为它不像语法分析那样有强模板感但它胜在概念清晰属于“背了就能拿分”的题。我在第一遍做真题时直接跳过了运行时环境的简答题后来复盘才发现这份试卷里简答题分值不小而且答案几乎就是教材目录的原话。复习这块的正确策略是先扫一遍试卷里所有简答题统计它们在六个知识块里的分布再决定背什么。对大多数学校来说词法和语法分析占大头中间代码次之运行时环境和优化各占一成左右。有了这个比例你就能算出自己该在每块上投多少时间。3. 真题的三遍刷法怎么用一份试卷把知识漏洞挖干净很多同学刷题的模式是“做一遍→对答案→看懂了→下一份”这是效率最低的用法。因为看懂的题不等于你会做更不等于你考试的时候能在限定时间内做完。我一般把一份试卷拆成三遍来用每一遍目的不同。3.1 第一遍裸做把“不会”标记成待修知识点第一遍不查书、不查笔记、不限时把整份试卷从头做到尾不会的题在题号旁边写“不会”并标注卡在哪一步。比如写 LL(1) 分析表时发现冲突不会检查就在旁边写“冲突检查不会”写中间代码时发现不知道怎么处理数组下标就写“数组元素地址计算不熟”。这一步的价值在于它把模糊的“我感觉没复习好”变成了一列具体的“我不会什么”。一份试卷做下来你手里就有一张知识漏洞清单。具体做法是准备一个专门的笔记本左侧抄题号、右侧写卡点描述。卡点描述要去指向教材章节比如“FIRST 集计算中 ε 的处理”比“语法分析不熟”有用得多。裸做时不要一卡住就看答案至少给自己十五分钟试错实在做不下去才标记跳过。这个试错过程本身就是记忆的一部分直接看答案会损失掉这个关键刺激。3.2 第二遍对点补按错题倒查课本与笔记第二遍在第一遍完成后的第二天开始。这一遍你不是从头做卷子而是拿着第一遍记下的“漏洞清单”回翻教材、课堂笔记把对应知识点看懂然后只看错题大声讲一遍自己的解题思路。从“看懂答案”到“能讲清楚”中间隔着一个巨大的能力鸿沟。能讲清楚的标准是你合上书拿着空白纸从头到尾复现一遍该题的完整推导过程每一步都知道自己在做什么、为什么这么做。还有一个小技巧把卡点在课本目录上做标记。当你累积做了三四份试卷后翻目录你会发现某些章节被标了四五次这些章节才是真正的薄弱环节。一份试卷只考一个点说明不了什么反复出现的卡点才值得花整块时间彻底解决。第二遍刷完后你的目标是把漏洞清单上的每一行划掉。3.3 第三遍提速用限时训练校准答题节奏第三遍放在考前三天限时做整卷。按这份试卷常见的题型结构和分值分布设定时间预算语法分析大题分配三十分钟中间代码大题二十五分钟简答题十五分钟其余时间给词法分析和综合题。限时训练的核心指标不是分数而是你在哪类题上超时。如果你发现每次都在 FIRST 与 FOLLOW 集计算上多耗五分钟说明你对 ε 传播规则还不够机械需要针对性地刷十道同类小题。这一步我建议连续做两到三份整卷让身体适应考试的节奏感。不必每一份都对答案重点是记录“每一类题实际用了多少分钟”和“有没有在某一步卡死”。真实考场上的后悔药只有一种在平时限时训练里已经遇到过类似的卡点并给自己定过应急预案——比如“FIRST 集算到一半算不下去时先跳去做简答题回头再来”。4. 五大高频题型的分步拆解从写文法到回填地址刷过几份试卷后你会清楚看到绝大部分题目逃不出五个题型套路。把每个套路的固定解题步骤练成条件反射比做十套新题更有用。下面是我按这五类题拆出来的分步清单每一步都是踩过坑换来的。4.1 写文法与消除左递归先写步骤再写结果题目常给一段语言描述比如“所有以 a 开头、以 b 结尾的字符串中间可以有任意个 c”要求写文法并消除左递归。我的固定步骤是先写最直觉的文法再检查有没有左递归或二义性最后改写。E → E T | T T → T * F | F F → ( E ) | id消除左递归的通用改写是把A → Aα | β改成A → βA和A → αA | ε。注意改写后要再验证一遍新文法接受的语言集合和原来一致不要改着改着把语言变窄了。最容易丢分的是遗漏 ε 产生式的处理比如A → ε这一步很多人会忘写而它在后续构造预测分析表时直接决定 FOLLOW 集的计算。参数说明改写时先把左递归的产生式按“直接左递归”和“间接左递归”分类间接左递归要先做代入展开再消除顺序不能反。试卷里通常只考直接左递归但你要有这个分类意识遇到间接情况不至于懵。4.2 计算 FIRST 与 FOLLOW 集合注意那个 εFIRST 与 FOLLOW 集的计算是语法分析题的“体力活”但它有几个固定丢分点。FIRST 集计算要点是从左往右扫描产生式右部遇到终结符就停遇到非终结符则把它的 FIRST 集加入若这个非终结符可推导出 ε则继续往后扫描。FOLLOW 集计算更难因为要同时扫描所有产生式的右部找每个非终结符后面跟了什么。文法 E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id这个经典文法的 FIRST 集很好算FOLLOW 集的难点在于 E 和 T ——它们本身可以推导出 ε所以在计算 FOLLOW(E) 时要处理F → ( E )中 E 后面的右括号还要处理E → ε对 FOLLOW(E) 的影响。一个通用检查法则是如果某个非终结符能推导出 ε它的 FIRST 集必然包含 ε且这个事实会传导到 FOLLOW 集的计算中。做题时每算完一个集合就检查一次是否漏掉了 ε 的传导链能避免八成以上失误。4.3 构造 LL(1) 预测分析表冲突检查是得分关键LL(1) 分析表构造本质上是把 FIRST 和 FOLLOW 集的计算结果填入表格。每一个产生式A → α对 α 的 FIRST 集中每个终结符 a在表项 M[A, a] 填入该产生式如果 α 能推导出 ε则对 FOLLOW(A) 中每个终结符 b在 M[A, b] 也填入该产生式。表格填完后必须做冲突检查任何一个表项如果出现两个以上产生式说明文法不是 LL(1)。考卷上常问“该文法是否是 LL(1) 文法”答案就在冲突检查这一步里。做这步时建议画一张大一点的表格行是非终结符列是所有终结符加$。填完后再花两分钟逐格检查一遍宁可慢一点也别急着交卷因为冲突检查本身就是考点。如果发现冲突还要能说明冲突是由哪个终结符引起的并指出能否通过提取左公因子消除。4.4 SLR(1) 分析表与活前缀识别规约与移进的冲突SLR(1) 是自底向上分析的经典考点构造步骤比 LL(1) 长一倍先写增广文法再构造 LR(0) 项目集族然后根据项目集计算 ACTION 和 GOTO 表。最容易出错的是识别“移进-规约冲突”和“规约-规约冲突”判断标准是同一个项目集里看是否存在[A → α·aβ]和[B → γ·]同时出现再检查 FOLLOW 集是否与 a 有交集。这里有个血泪经验做 SLR(1) 表之前先检查文法是否含有二义性。如果一个文法有二义性SLR 分析表必然有冲突你会发现项目集分明按照教科书的步骤构造却怎么也对不上标准答案根源往往在文法本身。遇到这种情况立刻回查文法不要硬磕分析表。4.5 回填技术与优化代码生成题的常见给分点中间代码生成题最常见的考法是布尔表达式翻译。比如a b or c d这样的表达式要求写出带回填的三地址代码。固定套路是为每个布尔子表达式生成临时变量和跳转语句待条件确定后再回填跳转目标。1: if a b goto L1 2: goto L2 3: L1: if c d goto L_true 4: L2: ...回填技术的关键在于维护一个跳转指令列表记录了哪些指令的目标地址尚未确定。调试技巧是写完三地址码后从头模拟一遍输入的不同取值组合看看控制流是否走到了正确的标签。代码优化题则可以从基本块划分开始——先找入口语句再确定基本块边界然后构造 DAG 做局部公共子表达式删除。这类题目的给分点通常集中在“找基本块”和“画 DAG”两步后者画错了就全盘皆输所以要格外仔细地按操作数顺序建节点。5. 刷试卷的避坑指南五个真实踩坑记录刷题过程中有几个坑几乎每次都会有人踩进去。这些坑不解决做再多卷子也是原地踏步。5.1 只看答案不写推导看懂和会做是两回事现象对答案时觉得每题都“看懂了”合上书自己一写就卡壳。原因看答案只激活了识别记忆没激活生成记忆。考试要求的是从零生成推导过程两种能力完全不同。解决给自己定一条铁律——任何一道错题必须合上答案后完整复写一遍推导并且要能口头解释每一步的动机。这个“合书复写”的步骤能把“好像会了”变成“真会了”。5.2 硬背 FIRST/FOLLOW 规则不理解就会在 ε 上翻车现象背熟了定义一遇到含 ε 产生式的文法就出错FIRST 集漏掉 ε 的传播FOLLOW 集少加某个符号。原因没有真正理解“ε 是一个符号出现在 FIRST 集里意味着该非终结符可以匹配空串”只是机械地套用规则。解决遇到 ε 时停顿一下问自己三个问题——这个非终结符能推导出空串吗如果能它的 FIRST 集必须包含 ε这个事实会影响哪些产生式的 FIRST 集又会影响哪些 FOLLOW 集把这三个问题回答一遍再动笔基本不会再漏。5.3 跳过验证步骤分析表冲突查不出来等于白做现象LL(1) 分析表构造完了自我感觉良好对答案才发现表项里漏填了产生式或填了冲突项。原因构造时没有逐格检查也没有意识到“冲突检查”本身就是考试要求的步骤。解决表格填完后强制自己再走一遍验证流程——逐行逐列核对 FIRST/FOLLOW 集的填入是否完整再看每个表项是否只有一个产生式。这个过程耗时不超过三分钟却是整道大题最容易拿分又最常被忽略的部分。5.4 用新教材的符号约定对照旧考题约定不一致导致误判现象自己按手头教材的符号定义做题对答案时发现和参考答案不一致误以为自己做错了。原因编译原理教材在 DFA 的起始状态标注、ACTION 表的空白格含义、以及 ε 是否显式写出等细节上存在符号差异。解决做题前先花五分钟总结这份试卷参考答案的符号约定比如状态是否用圆圈、死状态是否显式画出、ACTION 表里错误项是留空还是标 e。考试时最好沿用教材的约定阅卷标准通常以教材为准。5.5 刷题只刷客观题编译原理的证明与简答才是拉分项现象大量刷语法分析的选择题、判断题遇到“证明某文法是 LL(1) 的”或“说明某翻译方案的正确性”这类题就跳过。原因这类题不能快速获得正误反馈复习体验不够“爽”。但试卷里这类题目的区分度恰恰最高会的人用三五行论证拿满分不会的人只能空着。解决每份试卷的简答与证明题单独建立一个文档先用自己的话写答案再对照参考答案补充术语精确度。平时觉得麻烦考场上才不慌。6. 把真题价值榨干做一张自己的考点收敛表最后分享一个测量复习效果的办法。找一张 A4 纸竖着画三行分别是“知识块”“第一轮失分点”“第二轮失分点”。把六个知识块填进去前两轮做试卷时每错一题就在对应行加一条短记录。复习收尾时看这张表如果第三轮刷试卷时某知识块的失分点连续两次没有新增就说明这块已经沉淀住了。知识块第一轮失分点第二轮失分点词法分析DFA 最小化漏了合并步骤无语法分析FOLLOW 集漏 ε 传导FIRST 集在嵌套非终结符上算慢中间代码回填目标地址写混无运行时环境活动记录内容记不全活动记录内容记不全代码优化基本块划分边界判断错误无这张表的另一个用途是考前两小时快速过一遍比翻整本笔记高效得多。我自己考编译原理之前用这个办法把三轮失分点压缩成了一页纸进考场前只看它心里有底不慌神。复习到后期会发现那些反复出现在失分点里的题目才是你真正需要内化的东西。希望这三遍刷法、五类拆解和这张收敛表能帮到你让你手里的每一份试卷都物尽其用。本文还有配套的精品资源点击获取
编译原理真题三遍刷法：从词法分析到中间代码的考点突破
简介东南大学编译原理期末试卷PDF面向高校计算机专业学生、考研备考者及自学者用于巩固编译原理核心知识。资源共1个PDF文件压缩包仅46KB内含7道英文原题覆盖上下文无关文法构造a/b/c出现偶数次、b开头等约束、最小状态DFA设计、左递归消除与LL(1)分析表构建、算符优先文法判定、LR(1)分析表构造、注释分析树绘制及C程序运行时存储组织与活动记录等核心考点。通过本试卷可系统检验对词法、语法和语义分析的理解熟悉东大出题风格和英文命题形式题目从基础文法设计到栈帧布局梯度合理适合期末冲刺、考研专业课自测或教师命题参考。已有214人学习下载资源轻量且具较高参考价值。1. 一份东南大学编译原理试卷为什么值得当“复习主线”来用期末考试前两周我把手头能找到的几份编译原理真题卷按考点拆了一遍发现一个反直觉的事实真正卡住我的不是那些偏题怪题而是几个基础概念的“组合考法”。比如文法消左递归和 FIRST 集计算放在同一道题里单看课本都能懂合在一起就不知道先写哪个、写到哪一步算完。一份东南大学编译原理试卷价值恰好在这里——它用一道大题把三四个基础点串起来逼你用“做题”而不是“看书”的方式确认自己到底会不会。考研备考、期末冲刺、甚至工作中想回头补编译原理基础的人都能拿它当复习主线先裸做、再对点补、最后提速。这份资源不是用来“背题”的是用来给知识漏洞做定位的。2. 试卷背后的考点地图从词法分析到代码生成的六个知识块拿到一份真题第一件事不是动笔做而是先看它考了什么。把三到五年内的试卷放在一起横向扫一遍你会发现编译原理的考点高度稳定变来变去就是六个知识块。了解这张地图你才能决定哪块花大力气、哪块混个眼熟。2.1 词法与语法分析占分最稳的“送分区域”词法分析在试卷里出现的形式几乎只有三种写正则表达式、根据正则构造 DFA、用子集法把 NFA 转 DFA。语法分析则是写文法、消除左递归、提左公因子、计算 FIRST 与 FOLLOW 集、构造 LL(1) 或 LR 分析表。这块内容在试卷里通常占三十分上下是所有大题里最接近“背模板”的——它的解题步骤固定只要你按顺序写就算最后结果错了步骤分也能拿回大半。我在复习时把词法分析当作热身题每天早上先做一道 DFA 构造题找手感。语法分析则当成主菜因为它的变形最多有的年份考 LL(1)有的年份考 SLR(1)还有的把两种放一起让你对比。一个值得注意的边界是东南大学这类课程试卷不会考太偏的形式化定义它更倾向“给一个文法让你构造分析表并说明冲突”也就是说动手构造的过程本身就占了七成分数。2.2 文法制导翻译与中间代码命题最偏重的部分这一块是很多人的分水岭。试卷里它通常以“给一段程序或一个文法写出带属性的翻译方案然后生成三地址代码”的形式出现。考的内容包括属性文法的定义、综合属性与继承属性的区别、后缀翻译方案、布尔表达式短路计算、回填技术。它难不是因为概念抽象而是因为步骤长一步错步步错。我见过不少同学的复习误区是花大量时间背属性文法的定义结果到了考场上发现考的是“给一个声明语句写出其翻译并生成中间代码”——你背的概念根本用不上。正确的备考姿势应该是对着真题里的中间代码大题把“声明语句翻译”“赋值语句翻译”“布尔表达式翻译”三个模板练熟。每一道题都要从文法规则一路写到三地址码中间不能跳步。2.3 运行时环境与代码优化容易被忽略的二十到三十分运行时环境在这类试卷里经常以简答题出现比如问“静态作用域与动态作用域的区别”“活动记录里保存哪些内容”。代码优化则考察基本块划分、DAG 图构造、循环优化。这部分之所以容易被忽略是因为它不像语法分析那样有强模板感但它胜在概念清晰属于“背了就能拿分”的题。我在第一遍做真题时直接跳过了运行时环境的简答题后来复盘才发现这份试卷里简答题分值不小而且答案几乎就是教材目录的原话。复习这块的正确策略是先扫一遍试卷里所有简答题统计它们在六个知识块里的分布再决定背什么。对大多数学校来说词法和语法分析占大头中间代码次之运行时环境和优化各占一成左右。有了这个比例你就能算出自己该在每块上投多少时间。3. 真题的三遍刷法怎么用一份试卷把知识漏洞挖干净很多同学刷题的模式是“做一遍→对答案→看懂了→下一份”这是效率最低的用法。因为看懂的题不等于你会做更不等于你考试的时候能在限定时间内做完。我一般把一份试卷拆成三遍来用每一遍目的不同。3.1 第一遍裸做把“不会”标记成待修知识点第一遍不查书、不查笔记、不限时把整份试卷从头做到尾不会的题在题号旁边写“不会”并标注卡在哪一步。比如写 LL(1) 分析表时发现冲突不会检查就在旁边写“冲突检查不会”写中间代码时发现不知道怎么处理数组下标就写“数组元素地址计算不熟”。这一步的价值在于它把模糊的“我感觉没复习好”变成了一列具体的“我不会什么”。一份试卷做下来你手里就有一张知识漏洞清单。具体做法是准备一个专门的笔记本左侧抄题号、右侧写卡点描述。卡点描述要去指向教材章节比如“FIRST 集计算中 ε 的处理”比“语法分析不熟”有用得多。裸做时不要一卡住就看答案至少给自己十五分钟试错实在做不下去才标记跳过。这个试错过程本身就是记忆的一部分直接看答案会损失掉这个关键刺激。3.2 第二遍对点补按错题倒查课本与笔记第二遍在第一遍完成后的第二天开始。这一遍你不是从头做卷子而是拿着第一遍记下的“漏洞清单”回翻教材、课堂笔记把对应知识点看懂然后只看错题大声讲一遍自己的解题思路。从“看懂答案”到“能讲清楚”中间隔着一个巨大的能力鸿沟。能讲清楚的标准是你合上书拿着空白纸从头到尾复现一遍该题的完整推导过程每一步都知道自己在做什么、为什么这么做。还有一个小技巧把卡点在课本目录上做标记。当你累积做了三四份试卷后翻目录你会发现某些章节被标了四五次这些章节才是真正的薄弱环节。一份试卷只考一个点说明不了什么反复出现的卡点才值得花整块时间彻底解决。第二遍刷完后你的目标是把漏洞清单上的每一行划掉。3.3 第三遍提速用限时训练校准答题节奏第三遍放在考前三天限时做整卷。按这份试卷常见的题型结构和分值分布设定时间预算语法分析大题分配三十分钟中间代码大题二十五分钟简答题十五分钟其余时间给词法分析和综合题。限时训练的核心指标不是分数而是你在哪类题上超时。如果你发现每次都在 FIRST 与 FOLLOW 集计算上多耗五分钟说明你对 ε 传播规则还不够机械需要针对性地刷十道同类小题。这一步我建议连续做两到三份整卷让身体适应考试的节奏感。不必每一份都对答案重点是记录“每一类题实际用了多少分钟”和“有没有在某一步卡死”。真实考场上的后悔药只有一种在平时限时训练里已经遇到过类似的卡点并给自己定过应急预案——比如“FIRST 集算到一半算不下去时先跳去做简答题回头再来”。4. 五大高频题型的分步拆解从写文法到回填地址刷过几份试卷后你会清楚看到绝大部分题目逃不出五个题型套路。把每个套路的固定解题步骤练成条件反射比做十套新题更有用。下面是我按这五类题拆出来的分步清单每一步都是踩过坑换来的。4.1 写文法与消除左递归先写步骤再写结果题目常给一段语言描述比如“所有以 a 开头、以 b 结尾的字符串中间可以有任意个 c”要求写文法并消除左递归。我的固定步骤是先写最直觉的文法再检查有没有左递归或二义性最后改写。E → E T | T T → T * F | F F → ( E ) | id消除左递归的通用改写是把A → Aα | β改成A → βA和A → αA | ε。注意改写后要再验证一遍新文法接受的语言集合和原来一致不要改着改着把语言变窄了。最容易丢分的是遗漏 ε 产生式的处理比如A → ε这一步很多人会忘写而它在后续构造预测分析表时直接决定 FOLLOW 集的计算。参数说明改写时先把左递归的产生式按“直接左递归”和“间接左递归”分类间接左递归要先做代入展开再消除顺序不能反。试卷里通常只考直接左递归但你要有这个分类意识遇到间接情况不至于懵。4.2 计算 FIRST 与 FOLLOW 集合注意那个 εFIRST 与 FOLLOW 集的计算是语法分析题的“体力活”但它有几个固定丢分点。FIRST 集计算要点是从左往右扫描产生式右部遇到终结符就停遇到非终结符则把它的 FIRST 集加入若这个非终结符可推导出 ε则继续往后扫描。FOLLOW 集计算更难因为要同时扫描所有产生式的右部找每个非终结符后面跟了什么。文法 E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id这个经典文法的 FIRST 集很好算FOLLOW 集的难点在于 E 和 T ——它们本身可以推导出 ε所以在计算 FOLLOW(E) 时要处理F → ( E )中 E 后面的右括号还要处理E → ε对 FOLLOW(E) 的影响。一个通用检查法则是如果某个非终结符能推导出 ε它的 FIRST 集必然包含 ε且这个事实会传导到 FOLLOW 集的计算中。做题时每算完一个集合就检查一次是否漏掉了 ε 的传导链能避免八成以上失误。4.3 构造 LL(1) 预测分析表冲突检查是得分关键LL(1) 分析表构造本质上是把 FIRST 和 FOLLOW 集的计算结果填入表格。每一个产生式A → α对 α 的 FIRST 集中每个终结符 a在表项 M[A, a] 填入该产生式如果 α 能推导出 ε则对 FOLLOW(A) 中每个终结符 b在 M[A, b] 也填入该产生式。表格填完后必须做冲突检查任何一个表项如果出现两个以上产生式说明文法不是 LL(1)。考卷上常问“该文法是否是 LL(1) 文法”答案就在冲突检查这一步里。做这步时建议画一张大一点的表格行是非终结符列是所有终结符加$。填完后再花两分钟逐格检查一遍宁可慢一点也别急着交卷因为冲突检查本身就是考点。如果发现冲突还要能说明冲突是由哪个终结符引起的并指出能否通过提取左公因子消除。4.4 SLR(1) 分析表与活前缀识别规约与移进的冲突SLR(1) 是自底向上分析的经典考点构造步骤比 LL(1) 长一倍先写增广文法再构造 LR(0) 项目集族然后根据项目集计算 ACTION 和 GOTO 表。最容易出错的是识别“移进-规约冲突”和“规约-规约冲突”判断标准是同一个项目集里看是否存在[A → α·aβ]和[B → γ·]同时出现再检查 FOLLOW 集是否与 a 有交集。这里有个血泪经验做 SLR(1) 表之前先检查文法是否含有二义性。如果一个文法有二义性SLR 分析表必然有冲突你会发现项目集分明按照教科书的步骤构造却怎么也对不上标准答案根源往往在文法本身。遇到这种情况立刻回查文法不要硬磕分析表。4.5 回填技术与优化代码生成题的常见给分点中间代码生成题最常见的考法是布尔表达式翻译。比如a b or c d这样的表达式要求写出带回填的三地址代码。固定套路是为每个布尔子表达式生成临时变量和跳转语句待条件确定后再回填跳转目标。1: if a b goto L1 2: goto L2 3: L1: if c d goto L_true 4: L2: ...回填技术的关键在于维护一个跳转指令列表记录了哪些指令的目标地址尚未确定。调试技巧是写完三地址码后从头模拟一遍输入的不同取值组合看看控制流是否走到了正确的标签。代码优化题则可以从基本块划分开始——先找入口语句再确定基本块边界然后构造 DAG 做局部公共子表达式删除。这类题目的给分点通常集中在“找基本块”和“画 DAG”两步后者画错了就全盘皆输所以要格外仔细地按操作数顺序建节点。5. 刷试卷的避坑指南五个真实踩坑记录刷题过程中有几个坑几乎每次都会有人踩进去。这些坑不解决做再多卷子也是原地踏步。5.1 只看答案不写推导看懂和会做是两回事现象对答案时觉得每题都“看懂了”合上书自己一写就卡壳。原因看答案只激活了识别记忆没激活生成记忆。考试要求的是从零生成推导过程两种能力完全不同。解决给自己定一条铁律——任何一道错题必须合上答案后完整复写一遍推导并且要能口头解释每一步的动机。这个“合书复写”的步骤能把“好像会了”变成“真会了”。5.2 硬背 FIRST/FOLLOW 规则不理解就会在 ε 上翻车现象背熟了定义一遇到含 ε 产生式的文法就出错FIRST 集漏掉 ε 的传播FOLLOW 集少加某个符号。原因没有真正理解“ε 是一个符号出现在 FIRST 集里意味着该非终结符可以匹配空串”只是机械地套用规则。解决遇到 ε 时停顿一下问自己三个问题——这个非终结符能推导出空串吗如果能它的 FIRST 集必须包含 ε这个事实会影响哪些产生式的 FIRST 集又会影响哪些 FOLLOW 集把这三个问题回答一遍再动笔基本不会再漏。5.3 跳过验证步骤分析表冲突查不出来等于白做现象LL(1) 分析表构造完了自我感觉良好对答案才发现表项里漏填了产生式或填了冲突项。原因构造时没有逐格检查也没有意识到“冲突检查”本身就是考试要求的步骤。解决表格填完后强制自己再走一遍验证流程——逐行逐列核对 FIRST/FOLLOW 集的填入是否完整再看每个表项是否只有一个产生式。这个过程耗时不超过三分钟却是整道大题最容易拿分又最常被忽略的部分。5.4 用新教材的符号约定对照旧考题约定不一致导致误判现象自己按手头教材的符号定义做题对答案时发现和参考答案不一致误以为自己做错了。原因编译原理教材在 DFA 的起始状态标注、ACTION 表的空白格含义、以及 ε 是否显式写出等细节上存在符号差异。解决做题前先花五分钟总结这份试卷参考答案的符号约定比如状态是否用圆圈、死状态是否显式画出、ACTION 表里错误项是留空还是标 e。考试时最好沿用教材的约定阅卷标准通常以教材为准。5.5 刷题只刷客观题编译原理的证明与简答才是拉分项现象大量刷语法分析的选择题、判断题遇到“证明某文法是 LL(1) 的”或“说明某翻译方案的正确性”这类题就跳过。原因这类题不能快速获得正误反馈复习体验不够“爽”。但试卷里这类题目的区分度恰恰最高会的人用三五行论证拿满分不会的人只能空着。解决每份试卷的简答与证明题单独建立一个文档先用自己的话写答案再对照参考答案补充术语精确度。平时觉得麻烦考场上才不慌。6. 把真题价值榨干做一张自己的考点收敛表最后分享一个测量复习效果的办法。找一张 A4 纸竖着画三行分别是“知识块”“第一轮失分点”“第二轮失分点”。把六个知识块填进去前两轮做试卷时每错一题就在对应行加一条短记录。复习收尾时看这张表如果第三轮刷试卷时某知识块的失分点连续两次没有新增就说明这块已经沉淀住了。知识块第一轮失分点第二轮失分点词法分析DFA 最小化漏了合并步骤无语法分析FOLLOW 集漏 ε 传导FIRST 集在嵌套非终结符上算慢中间代码回填目标地址写混无运行时环境活动记录内容记不全活动记录内容记不全代码优化基本块划分边界判断错误无这张表的另一个用途是考前两小时快速过一遍比翻整本笔记高效得多。我自己考编译原理之前用这个办法把三轮失分点压缩成了一页纸进考场前只看它心里有底不慌神。复习到后期会发现那些反复出现在失分点里的题目才是你真正需要内化的东西。希望这三遍刷法、五类拆解和这张收敛表能帮到你让你手里的每一份试卷都物尽其用。本文还有配套的精品资源点击获取
