简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考编译原理课程的读者用于检验词法分析、语法分析、语义分析与代码生成等核心章节的掌握程度。试卷内容覆盖正规表达式与最简DFA构造、逆波兰表示与三元式序列、文法二义性证明与语言描述、First集与Follow集计算、LL(1)文法判定及预测分析表构造以及if-then-else语句的四元式翻译等典型题型知识点分布完整适合作为期末复习、自测与课堂练习的参考材料。目前已有391人学习下载读者可借助这份试卷梳理编译原理各阶段的解题思路对照题目查漏补缺熟悉常见考点的出题形式与答题规范为课程考试与后续深入学习打下基础。1. 编译原理期末复盘从正规式到四元式的完整知识地图编译原理这门课很多人复习到一半会发现一个尴尬的事实词法分析、语法分析、语义分析、中间代码生成这几块单看每一块都能说出点东西但合上书就串不起来。这份试卷库把考点压在了五类题型上——正规表达式与最简DFA、逆波兰表示与四元式、文法二义性证明、LL(1)文法与预测分析表、控制语句的四元式翻译。梳理下来会发现它其实是一条完整的流水线先用正规式描述词法再用文法描述语法接着用First/Follow集和预测分析表做自顶向下分析最后把语句翻译成四元式。适合正在系统复习编译原理、想拿一张能直接对着查漏补缺的地图的人。下面按这条流水线逐块拆。2. 词法分析双件套正规表达式构造与最简DFA的复习重点词法分析是整条流水线的入口试卷第一题30分全压在这里说明它是性价比最高的复习模块。这一块的核心链路是自然语言描述 → 正规表达式 → NFA → DFA → 最简DFA。很多人卡在第一步不是不会画自动机而是读不懂题目里那句中文到底在说什么。2.1 从自然语言到正规表达式两个典型题型的拆解试卷给了两个小题分别代表两种出题思路。第一小题字母表 {0,1} 上不以 0 开头但以 11 结尾的所有字符串。拆解思路是分段拼接——开头部分、中间部分、结尾部分。不以0开头意味着首字符必须是1以11结尾意味着最后两位固定是11中间可以是任意01串。所以正规式写成1(0|1)*11这里有个容易翻车的地方如果中间部分写成(0|1)*那字符串111会被匹配吗会——首字符1中间空串结尾11合起来就是111正确。但字符串11呢首字符1中间空串结尾11需要三个1所以11不匹配这也符合“以11结尾且不以0开头”的定义吗11确实不以0开头且以11结尾应该被包含。问题出在首字符1和结尾11共用了同一个1。修正方式是让中间部分允许为空但首字符和结尾不重叠1(0|1)*11 | 11或者更简洁地写成1(0|1)*11并单独处理长度为2的情况。梳理下来会发现这类题最容易漏的就是“最短字符串”的边界情况。第二小题包含01子串的所有字符串。这个相对直接用(0|1)*01(0|1)*就能覆盖。但要注意“包含”意味着01可以在任意位置前后都可以有任意字符。2.2 NFA到DFA再到最简DFA子集构造法与化简的实操要点拿到正规式之后构造等价DFA的标准路径是正规式 → NFAThompson构造法→ DFA子集构造法→ 最简DFAHopcroft或填表化简法。子集构造法的关键是维护一个状态集合的集合每个DFA状态对应NFA状态的一个子集。实际操作中最容易出错的是ε闭包的计算——每次求move(S, a)之后必须再对结果求一次ε闭包。漏掉这一步DFA就会少状态。最简DFA的化简用填表法比较稳先画一个下三角表标记所有“一个终态一个非终态”的状态对为可区分然后迭代如果两个状态在某个输入下转移到已标记可区分的状态对则它们也可区分最后剩下的不可区分状态对就可以合并。注意最简DFA的“最简”是指状态数最少不是指边最少。合并状态时终态只能和终态合并非终态只能和非终态合并。这一块的复习建议是拿三道题手算一遍每道题都从正规式写到最简DFA中间不要跳步。跳步的人考场上会在ε闭包那里卡住。3. 语法分析核心战场二义性证明、First/Follow集与LL(1)预测分析表语法分析是编译原理试卷里分值最重、也最容易拉开差距的部分。这份试卷里二义性证明占20分LL(1)相关占25分加起来45分几乎半壁江山。这两块的知识点其实是连着的二义性说明文法不能用自顶向下或自底向上的确定性方法分析而LL(1)文法则是一种保证无二义、可确定性自顶向下分析的文法类型。3.1 文法二义性证明找两棵不同的语法树试卷给的文法G开始符号N是这样的N → SE | E S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9证明二义性的标准做法是找到一个句子它能对应两棵不同的语法分析树或两个不同的最左推导。对于这个文法关键观察是N可以推导出SE或E而S又可以推导出SD或D。这意味着一个数字串可能通过不同的路径生成。比如句子10既可以走 N→E→10也可以走 N→SE→DE→10S→D→1E→0。两条路径对应两棵不同的树二义性得证。第二问“此文法所描述的语言是什么”需要从文法规则反推。E生成偶数0,2,4,6,8,10D生成单个数字0-9S生成一个或多个数字的序列因为S→SD|D递归地在右边追加数字N生成SE或E。合起来看这个文法描述的是所有非空数字串但有一个限制最后一个数字必须是偶数。因为N→SE中E是偶数结尾N→E也是偶数结尾。所以语言是所有以偶数结尾的非空数字串。注意证明二义性时一定要写出两个完整的推导过程或画出两棵树不能只说“显然有两条路径”。阅卷时只看具体推导。3.2 First集与Follow集计算规则和三个高频错误试卷第四题给的文法G是E → TE E → E | ε T → FT T → T | ε F → PF F → *F | ε P → (E) | ^ | a | b计算First集和Follow集是LL(1)分析的基础。First集的计算规则是对于产生式A→αFirst(A)包含First(α)如果α能推导出ε则ε也加入First(A)。Follow集的计算规则是对于产生式A→αBβFollow(B)包含First(β)-{ε}如果β能推导出ε则Follow(B)包含Follow(A)。这个文法的First集和Follow集整理如下非终结符First集Follow集E{(, ^, a, b}{), #}E{, ε}{), #}T{(, ^, a, b}{, ), #}T{(, ^, a, b, ε}{, ), #}F{(, ^, a, b}{, ), #}F{*, ε}{, ), #}P{(, ^, a, b}{*, , ), #}三个高频错误第一忘记把ε加入First集尤其是E、T、F这些含ε产生式的非终结符第二Follow集计算时忘记处理β能推导ε的情况导致Follow没有传递第三开始符号的Follow集忘记加#。3.3 LL(1)文法判定与预测分析表构造证明文法是LL(1)的条件是对于每个非终结符A的任意两个不同产生式A→α和A→β满足First(α) ∩ First(β) ∅如果β能推导ε则First(α) ∩ Follow(A) ∅。对于这个文法检查E的两个产生式E→E的First是{}E→ε的First是{ε}而Follow(E){), #}{} ∩ {), #} ∅满足。T的两个产生式T→T和T→εFirst(T){(, ^, a, b}First(ε){ε}Follow(T){, ), #}{(, ^, a, b} ∩ {, ), #} ∅满足。F同理。所以文法是LL(1)的。预测分析表的构造行是非终结符列是终结符和#。对于每个产生式A→α对每个a∈First(α)在M[A, a]填入A→α如果ε∈First(α)则对每个b∈Follow(A)在M[A, b]填入A→α。构造出来的表里E行在(、^、a、b列都填E→TEE行在列填E→E在)和#列填E→εT行在(、^、a、b列填T→FTT行在(、^、a、b列填T→T在、)、#列填T→εF行在(、^、a、b列填F→PFF行在列填F→F在、)、#列填F→εP行在(列填P→(E)在^列填P→^在a列填P→a在b列填P→b。注意预测分析表里每个单元格最多只能有一个产生式如果有多个说明文法不是LL(1)的。检查时重点看含ε产生式的非终结符它们的Follow集和别的产生式的First集有没有交集。4. 中间代码生成逆波兰表示与四元式序列的翻译套路中间代码生成是编译原理里最“工程化”的一块试卷里占了25分逆波兰四元式10分控制语句四元式15分。这块的复习方法和前面不同——前面靠理解这块靠熟练。因为翻译规则是固定的练多了就是肌肉记忆。4.1 逆波兰表示运算符优先级与栈的配合试卷要求写出AB*(C-D)E/(C-D)的逆波兰表示。逆波兰表示就是后缀表达式转换规则是遇到操作数直接输出遇到运算符则与栈顶运算符比较优先级如果栈顶优先级不低于当前运算符就弹出栈顶输出直到栈顶优先级低于当前运算符或栈为空然后当前运算符入栈。对于这个表达式逐步转换的结果是A B C D - * E C D - / 验证方式是用栈求值从左到右扫描遇到操作数入栈遇到运算符弹出两个操作数计算后入栈。最终栈里只剩一个值说明表达式合法。这里最容易错的地方是括号的处理。左括号直接入栈右括号则弹出栈顶直到遇到左括号左括号弹出但不输出。很多人会把左括号也输出到后缀表达式里这是错的。4.2 四元式序列从表达式到控制流的翻译四元式的一般形式是(op, arg1, arg2, result)。对于表达式AB*(C-D)E/(C-D)四元式序列如下(, C, D, T1) // T1 C - D 实际是减法这里应为(-, C, D, T1) (*, B, T1, T2) // T2 B * T1 (, A, T2, T3) // T3 A T2 (-, C, D, T4) // T4 C - D (/, E, T4, T5) // T5 E / T4 (, T3, T5, T6) // T6 T3 T5注意第一个四元式应该是减法(-, C, D, T1)上面写是笔误。四元式的关键是临时变量的分配和运算顺序——先算括号里的再算乘除最后算加减。对于控制语句if x0 y0 then z:xy else begin x:x2; y:y3 end四元式翻译需要用到标号和跳转(, x, 0, T1) // T1 x 0 (, y, 0, T2) // T2 y 0 (and, T1, T2, T3) // T3 T1 and T2 (j, T3, 0, 5) // 如果T3为假跳转到第5条 (, x, y, T4) // T4 x y (:, T4, _, z) // z T4 (j, _, _, 9) // 无条件跳转到第9条 (, x, 2, T5) // T5 x 2 (:, T5, _, x) // x T5 (, y, 3, T6) // T6 y 3 (:, T6, _, y) // y T6这里的关键是回填技术——在生成跳转指令时目标标号可能还不知道需要留空后续回填。考试时如果不需要回填直接写标号即可。注意四元式的标号从1开始还是从100开始不同教材不一样。试卷里没有明确要求按自己习惯来但同一题内要统一。5. 易错点集中排查这五处最容易丢分复习到后期知识点都过了一遍但考场上丢分往往不是因为不会而是因为踩了固定的坑。梳理下来这份试卷涉及的内容里有五个地方最容易翻车。易漏点一正规式构造时忽略最短字符串。为什么漏因为习惯性地写1(0|1)*11觉得已经覆盖了所有情况但忘了11这种首尾重叠的短串。怎么补写完正规式后手动枚举长度最短的几个字符串逐个验证是否被覆盖。易漏点二子集构造法忘记ε闭包。为什么漏因为move操作很直观而ε闭包容易被当成“已经处理过了”。怎么补每次求完move(S, a)之后强制自己再写一步ε-closure(move(S, a))养成条件反射。易漏点三Follow集计算时忘记传递。为什么漏因为Follow的规则比First多一层——当β能推导ε时Follow(A)要全部加入Follow(B)。很多人只处理了First(β)的情况。怎么补对每个产生式先判断β是否含ε含的话单独处理传递。易漏点四预测分析表多个产生式冲突时不会判断。为什么漏因为LL(1)的判定条件背了但没真正用过。怎么补构造完表后逐行检查每个非终结符的每个终结符列如果有两个产生式回去看First集和Follow集是否真的相交。易漏点五四元式翻译时跳转标号写错。为什么漏因为控制流的跳转目标需要数行号数着数着就乱了。怎么补先给每条四元式编号再写跳转跳转指令的目标写编号而不是“下一行”。写完后再从头核对一遍。6. 考前查漏补缺一份可执行的复习清单最后一章落到具体怎么查漏补缺。编译原理这门课光看不动手考场上一定卡壳。下面这份清单是按题型组织的每一条都对应一个可执行的动作不是泛泛的“复习XX”。题型自查动作合格标准正规式与DFA拿3道题从正规式手写到最简DFA不跳步ε闭包每步都写逆波兰表示拿5个含括号的表达式手写后缀式括号处理正确栈操作不跳二义性证明找2个文法各找2个二义句子能画出两棵不同的树First/Follow集拿3个含ε产生式的文法手算全对尤其是Follow传递LL(1)判定与预测表拿2个文法判定并构造表表中无冲突单元格四元式翻译拿3个if-then-else语句手写四元式跳转标号正确回填逻辑清晰具体执行时建议按“先手算再对答案”的顺序。手算的时候不要翻书算完再对照教材或笔记检查。错的地方用红笔标出来第二天再算一遍同样的题。如果第二遍还错说明不是粗心是知识点没吃透回去看对应的章节。还有一个技巧把最容易混的几个概念做成一张对比卡。比如NFA和DFA的区别、First集和Follow集的区别、逆波兰和四元式的区别。考前最后一天只看这张卡不翻书。提示如果时间只够复习一块优先复习LL(1)相关。因为First/Follow集、预测分析表、LL(1)判定这三块是连着的复习一块等于复习三块性价比最高。从那以后我每次复习编译原理都强制自己先手写一遍完整流程——从正规式到DFA从文法到预测表从表达式到四元式——不跳任何一步。跳步的人考场上会在最基础的地方翻车而编译原理的分数恰恰就藏在这些基础步骤里。希望帮到你。本文还有配套的精品资源点击获取