简介东南大学编译原理课程期末考试试卷A卷为全英文闭卷试卷面向计算机科学与技术专业本科生也适合备考研究生入学考试或准备编译原理技术面试的读者。试卷共设多道综合题覆盖上下文无关文法构造、最小状态DFA设计、消除左递归与提取最大公共左因子、算符优先文法分析与解析表构建、LR(1)分析表构造、带注释的语法树以及C语言程序运行时的存储组织与活动记录布局等核心模块既能用于检验基础概念理解也能训练复杂语法分析题目的解题思路。资源包仅含1个PDF文件大小46KB共6页内容紧凑清晰可下载后直接打印练习。针对文法改造、LR分析和存储布局等难点试卷提供了完整的问题场景适合作为考前模拟、知识点查漏补缺或题型参考材料。目前已有214人浏览学习可用于自主评测编译原理核心内容的掌握程度。1. 一份东南大学编译原理试卷 PDF 到底能读出什么别把它当题库刷一个只写着「东南大学编译原理试卷.pdf」的文件躺在下载目录里很多人第一反应是刷完它就稳了。我的看法正好相反——把卷子当题库刷是这门课最常见的低效复习方式。编译原理考的不是「你会不会做这十道题」而是「你能不能从正则表达式一路走到代码生成」。这份 PDF 真正值钱的地方是它能告诉你东南大学在这门课上把分值压在哪、要求你手算到什么程度、哪些地方给了提示哪些地方完全不设防。适合读它的人有三类东南大学在读本科生、考研复试想摸底的人、想拿外校卷子对比出题深度的编译原理学习者。下面按「卷面反推考点 → 手算训练 → 自测闭环 → 避坑排查」的顺序把这份 PDF 读透。2. 从试卷反推考点编译原理常考的六大模块分值到底压在哪拿到一份 PDF 卷子我建议先别做题先做「卷面体检」翻到最后一页统计选择题、填空题、判断题、大题各占多少分再看每道大题考的是哪个模块。这个动作花不了十分钟却能把复习方向校准一大半。2.1 词法分析与有穷自动机为什么 DFA 最小化是必考手算题词法分析这一块几乎每份卷子都会出一个「正则表达式转自动机」的大题。常见考法是给一个正则表达式比如(a|b)*abb要求画出 NFA再用子集构造法转成 DFA最后把 DFA 最小化。这三个步骤环环相扣哪一步手算出错后面全跟着歪。DFA 最小化之所以常考是因为它考察的不只是会不会背划分算法而是能不能用「可区分状态」的思路判断两个状态该不该合并。我见过不少同学把最小化当成「凭肉眼找长得像的状态」结果把不该合并的状态合并了等价正则都写不出来。正确的做法是先删无用状态再按终结符和非终结符分组逐轮划分直到不能再分。2.2 语法分析是重头戏LL(1) 与 LR 系列决定卷面半壁江山语法分析通常是整份卷子分值最高的模块出题形式非常固定给一个上下文无关文法让你算 FIRST 集和 FOLLOW 集判断是不是 LL(1)构造预测分析表或者给一个 LR(0) 项目集规范族判断是 SLR(1) 还是 LR(1)同步列出 ACTION 表和 GOTO 表。东南大学这类理工科强校的卷子往往会把 LL(1) 和 LR(1) 都考到只靠背「什么是自上而下分析」这种概念题是拿不到大题的分的。这一章的复习有个血泪经验跟着教材例题手算一遍比看十遍 PPT 有用。你只需要一道题从文法开始自己推导 FIRST、FOLLOW、分析表再拿一个输入串走一遍分析栈的进出过程全程大概四十分钟做完之后你会发现自己对「预测分析表是怎么被填出来的」有了质的理解。2.3 中间代码与运行时四元式和活动记录是简答题最爱第三大模块是中间代码生成和运行时环境。卷子里通常会出现两种考法一是给一段程序或表达式要求写出三地址码或四元式序列考察数组寻址、布尔表达式的短路翻译、过程调用的参数传递二是简答题问「静态链和动态链的区别」「活动记录里有哪些字段」考察运行时栈的组织方式。很多同学栽在这一章是因为总觉得代码生成是「后面的事」前面的词法和语法分析还没弄明白就没往下看。但期末考试不会因为你没复习到就跳过这一章。我的建议是把三地址码的几种常见形式赋值语句、数组赋值、条件跳转、函数调用单独抄在一张纸上考前反复默写几遍比对着课件空看有效得多。2.4 代码优化与符号表判断、填空里的低垂果实代码优化这一章大题不常见但选择题和填空题一定会占到五分到十分。最常考的概念包括基本块与流图、DAG 优化公共子表达式提取、循环优化、复写传播、常量传播、活跃变量分析。符号表则考作用域、嵌套结构、符号表组织方式。这一部分的复习性价比很高知识点密集但每个都很小适合用零碎时间背。考试前一周我一般把基本块划分、DAG 构造、活跃变量分析三个手算题各做一遍再把概念题过一遍这部分的失分通常能控制到很低的水平。3. 拿真题卷手算训练从文法到分析表的分步拆解这一章是整份 PDF 用法里最重要的一环。别一上来就看答案选一道典型的语法分析大题按下面的步骤自己走一遍。3.1 建文法先消灭二义性再动手试卷里给出的文法不一定都是无二义的。比如经典的表达式文法E → EE | E*E | (E) | id就是二义文法如果直接去构造 LL(1) 分析表你会发现表中大量冲突根本没法往下走。所以手算训练的第一步是把它改写为无二义的形式E → E T | T T → T * F | F F → ( E ) | id这个文法的好处是优先级体现在产生式层级上加号在最外层乘号次之括号最内层结合性则靠左递归表达。改写完之后再算 FIRST 和 FOLLOW才不会出现一堆让人抓狂的冲突项。3.2 算 FIRST 与 FOLLOW最容易算漏的边界条件算 FIRST 集合时最容易犯的错是忽略 ε 的产生式。以刚才的文法为例先找每个非终结符的 FIRSTF以(和id开头因此 FIRST(F) { (, id }没有 ε。T产生式为T → T * F | F右部开头的非终结符是 T 和 F。因为 T 可以推导出 F所以 FIRST(T) FIRST(F) { (, id }。E同理FIRST(E) FIRST(T) { (, id }。FOLLOW 集合的边界条件更容易踩坑。规则只有三条开始符号的 FOLLOW 加入$形如A → α B β的把 FIRST(β) 中除 ε 以外的东西加入 FOLLOW(B)形如A → α B或A → α B β且 β 能推导出 ε 的把 FOLLOW(A) 加入 FOLLOW(B)。很多同学就是在第三条上翻的车——忘了「β 能推出 ε」的前提。用上面的文法手算FOLLOW(E) { $, ) }因为 E 是开始符号且有产生式F → ( E )。FOLLOW(T) FOLLOW(E) ∪ { }因为E → E T里 T 后面没有可推导的串要继承 FOLLOW(E)同时E → E T里 T 后面紧跟的终结符是。FOLLOW(F) FOLLOW(T) ∪ { * }。我一般会建议初学者把这四条规则抄在草稿纸上每填一个符号就圈出是用了哪条规则导致的方便回头检查。如果手边有清华大学出版社第三版的配套教材把第二章课后题里的 FIRST/FOLLOW 小题拿来练手也很合适题目短小适合集中突破边界条件。3.3 构造 LL(1) 分析表冲突就是得分点有了 FIRST 和 FOLLOW预测分析表就是机械劳动了。对每个产生式A → α在表格的 (A, a) 位置填入该产生式其中 a 是 FIRST(α) 中的每个终结符若 α 能推导出 ε则还要在 A 的 FOLLOW 集中每个终结符位置填入该产生式。按这个规则上述文法的部分预测分析表长这样非终结符()*id$EE→TE→TTT→FT→FFF→(E)F→id如果表格中某个格子里出现了两个产生式说明这个文法不是 LL(1) 的。这一步在试卷上往往直接就是得分点判冲突、分析冲突原因、改成等价的无冲突文法。训练时遇到冲突先别急着改文法先确认是不是自己 FOLLOW 集算错了。3.4 用 LR(0) 项目集判断 SLR(1)对照试卷大题的通用流程LR 系列的大题套路更固定写出文法求 LR(0) 项目集规范族再根据 SLR(1) 的规则判断冲突。关键步骤是构造项目集 I0 之后对所有非终结符求闭包然后按每个符号做 GOTO 转移。一个常见的坑是闭包运算里忘了把圆点右边的非终结符产生式待约项目也包含进去导致项目集不全后面 ACTion 表对不上。我练习时会把每个项目集编号写大一点用箭头标出转移关系整个状态图画完再填 ACTION 表和 GOTO 表。状态图画完这张大题基本就拿稳了。熟手可以试着从 I0 一口气推到 I11 不停顿能在二十分钟内画完考试时就从容了。4. 用自测脚本把 PDF 卷变成可复核的练习场真题卷的另一个妙用是当作自测场而不是学习资料。做完题之后怎么确认自己算对了我一般会写一个极小的脚本来核对 FIRST 和 FOLLOW 集合——不是为了作弊而是为了尽早发现自己手算里的系统性错误比如「一遇到 ε 就断链」这类问题。4.1 在本地把 PDF 卷变成可做题版这里先解决一个日常问题PDF 卷子要么是加密的、要么是扫描版直接在屏幕上草稿都没法打。我习惯先把 PDF 用 PDF-XChange Editor 或 Adobe Acrobat 打开另存成可批注的副本再在文件里加一个「做题层」每题旁边插入一个文本框答案写里面批注颜色统一用红色标错。这样一轮做完整个卷面上红色就是你的薄弱点分布图。如果是扫描版字迹太淡看不清时可以用本地 OCR 先过一遍再把文本复制出来核对自己的答案。注意 OCR 对公式识别不一定准不要直接拿识别结果当标准答案。4.2 一个最小 Python 脚本自动算出 FIRST 和 FOLLOW 集合下面这段脚本我每次复习编译原理都会临时敲一遍逻辑简单胜在可以自由改文法来验证手算结果。它用「重复迭代直到集合不再变化」的方式求不动点不依赖额外的库。# 极简 FIRST/FOLLOW 集合计算器适合验证手算结果 from collections import defaultdict # 文法产生式(E, [E, , T]) 表示 E - E T productions [ (E, [E, , T]), (E, [T]), (T, [T, *, F]), (T, [F]), (F, [(, E, )]), (F, [id]), ] terminals {, *, (, ), id, $} nonterminals {E, T, F} eps epsilon start E def compute_first(): first {nt: set() for nt in nonterminals} changed True while changed: changed False for lhs, rhs in productions: i 0 # 针对 A - ε 的情况 if rhs[0] eps: if eps not in first[lhs]: first[lhs].add(eps) changed True continue # 沿产生式右侧逐个符号累计 while i len(rhs): sym rhs[i] before len(first[lhs]) if sym in terminals: first[lhs].add(sym) # 终结符直接加入 else: first[lhs] | {x for x in first[sym] if x ! eps} if len(first[lhs]) ! before: changed True # 如果当前符号不能推出空串就不能继续往后穿越 if sym in terminals or eps not in first[sym]: break i 1 else: # 右侧所有符号都能推出空串把 ε 加入 FIRST if eps not in first[lhs]: first[lhs].add(eps) changed True return first first compute_first() def compute_follow(first): follow {nt: set() for nt in nonterminals} follow[start].add($) changed True while changed: changed False for lhs, rhs in productions: for i, sym in enumerate(rhs): if sym not in nonterminals: continue rest rhs[i1:] if rest: # 规则1后面第一个符号的 FIRST 加入 FOLLOW(B) add_set set() for rs in rest: if rs in terminals: add_set.add(rs) else: add_set | {x for x in first[rs] if x ! eps} before len(follow[sym]) follow[sym] | add_set if len(follow[sym]) ! before: changed True # 若 rs 不能推出空串终止向后扫描 if rs in terminals or eps not in first[rs]: break else: # 规则2β 能推出空FOLLOW(A) 传给 FOLLOW(B) before len(follow[sym]) follow[sym] | follow[lhs] if len(follow[sym]) ! before: changed True else: # 规则2A - α B 的形态 before len(follow[sym]) follow[sym] | follow[lhs] if len(follow[sym]) ! before: changed True return follow follow compute_follow(first) print(FIRST:, {k: sorted(v) for k, v in first.items()}) print(FOLLOW:, {k: sorted(v) for k, v in follow.items()})这段脚本的几个关键参数说明productions是产生式集合右部符号全部用列表展开terminals和nonterminals需要你自己维护脚本不会自动推断空串用字符串epsilon表示。整体逻辑是「不断重算所有 FIRST 和 FOLLOW直到连续两轮结果完全不变」这正是第一节课里讲到的闭包思想。验证方法很简单先手算一遍再把同一个文法输入脚本对比输出。如果脚本结果和你的不一致别急着怀疑脚本——先检查文法的输入格式再回头查自己的 FOLLOW 规则。用 Python 也好、Java 也好语言不重要重要的是你愿意把它写成一段能跑的程序这比背十遍定义都能加深理解。如果你正在做编译原理实验这个脚本还能顺带当词法分析器手算的校验工具。4.3 按卷子的题型做一轮「限时输出」答案要写得出来脚本只是辅助真正的自测必须限制时间。我的做法是把卷子按题型拆成三组词法分析大题一组、语法分析大题一组、中间代码与优化一组每组给自己 40 到 60 分钟开着手机倒计时关掉课件在空白纸上完整写出每一步过程不写「略」。过程比结果重要因为阅卷按步骤给分你的 FIRST 集算错一格可能后面分析表全错但项目集的构造过程仍然能拿一半分。限时输出还有个好处它能逼你把「看懂答案」和「自己写出来」之间的差距提前暴露在考前几天而不是考场上。我见过太多人拿着答案看一遍觉得「哦我会了」关掉答案一写就卡在第一闭包上这就是典型的「眼睛会了手不会」。5. 复习路上的常见翻车点与排查指南这一节写的是我在这门课上见过的、也自己踩过的坑每一条都按「现象 → 原因 → 解决」展开。你在刷 PDF 卷时如果卡住了先来这里对号入座。5.1 翻车点一试卷答案不唯一对答案对到怀疑人生现象同一道文法题你构造的 SLR(1) 分析表和网上的答案不一样你觉得自己没错答案看着也合理于是陷入纠结。原因LR 项目集规范族的编号顺序不唯一只要 GOTO 转移一致、ACTION/GOTO 表内容等价就是正确解法。还有不少教材对产生式编号有不同习惯导致表格展示不同。这不是你算错了而是「同一文法的多种等价表示」。解决对答案时先比对「状态转移关系是否一致」再比对「ACTION 表是否等价」。如果这些都对只是编号不同我一般直接判定自己正确不再跟答案抠字面。5.2 翻车点二FIRST/FOLLOW 计算时 ε 的跨传播漏了现象FOLLOW(E) 里少了一个导致预测分析表和答案对不上。原因计算 FOLLOW 时只用了规则 1忘了规则 2。比如产生式E → E T中T后面的符号是空的必须把 FOLLOW(E) 传播给 FOLLOW(T)。很多人在这一步只盯着「右侧有没有下一个符号」忽略了「下一个符号能否推出空串」。解决在草稿纸上把每条产生式的所有 B 列出来逐个判断「右侧下一个符号能否推导出 ε」。能就往 FOLLOW(B) 里再加 FOLLOW(A)不能就只加 FIRST 集合。练几道题后这个动作会变成肌肉记忆。5.3 翻车点三概念简答题背了但写不到采分点现象名词解释题写了满满一大段得分却很低。比如「什么是活动记录」你写了它的定义但没提静态链、动态链、返回地址、保存寄存器状态这几个关键词。原因概念题踩点给分不是看字数。编译原理里的名词定义往往很长但阅卷时核心关键词就那么四五个。解决复习时把每个概念压成「一句话定义 三个关键词 一个实例」。像活动记录就记「每次函数调用时在栈上分配的一段记录包含返回地址、局部变量、参数、可选的静态链和动态链」实例用一段两层嵌套的函数调用讲清楚。这样考试时写三行就能拿满大部分分。5.4 翻车点四把旧卷子当押题结果题面一变就慌现象刷了三套往年卷考场上发现题目全没见过连题型都有变化心态直接崩。原因旧卷子是「用于训练手算能力」的样本不是「考题池」。编译原理的考点就那么几个但文法可以随便出题目表述可以换花样背题不通用。解决每做完一道旧卷大题在题号旁边标注它考的考点是什么如「正则转 DFA 最小化」「LL(1) 冲突处理」「三地址码生成」做完后统计各考点出现频率再按频率安排后续复习顺序。这样卷子刷完你得到的不是几道题的答案而是一张考点热力图。5.5 翻车点五PDF 打不开、扫描版太糊、文字错乱现象卷子在本地打开要么提示加密要么扫描版字迹拖影OCR 后的文本里→全变成了公式完全没法看。原因扫描版经过多次压缩后画质损失OCR 对公式、下标字符的识别率本来就不高。解决先把文件另存为图片或按页导出再逐页看关键大题。如果只是某个公式看不清用 PDF 阅读器的缩放功能放大该区域再做判断不要依赖 OCR 文本作为唯一的理解来源。这条虽然跟编译原理本身无关但它是你能否把卷子用起来的前提。为了一个损坏的文件卡住复习太不值。6. 把卷子吃透的最后一个技巧做一张「错题归因表」如果你已经把卷子刷完一遍接下来最值得做的事是把错题整理成一张归因表。我的做法是画一个五列的表格连续五轮错题之后你会惊讶地发现错误类型高度集中。题号考点我的答案错在哪错误分类补救动作第三大题FIRST/FOLLOW丢了一个计算失误重算该文法 FOLLOW写清规则序号第七大题SLR(1) 分析表闭包漏了待约项目方法不熟重画项目集到 I8简答二活动记录没写静态链概念不全默写活动记录字段清单错误分类我一般只分五类计算失误、规则遗漏、概念不清、方法不会、题干读错。每一类对应一个特定的补救动作计算失误就重算一遍并放慢速度规则遗漏就把规则抄在卡片上背概念不清就去翻课件里对应小节方法不会就找同类题再做一题题干读错则提醒自己下轮审题时先圈出文法符号再动笔。这张表做完你比多做一套新卷子还值。因为它把你从「盲目刷题」里拉了出来变成「按薄弱点精准补漏」。这是我在编译原理复习上最后用到的一个习惯——先做题再归因最后带着归因表去翻课件。你也不用照搬这张表的格式只要守住「分类 补救」两个核心它就足够好用。希望帮到你。本文还有配套的精品资源点击获取