简介这份常州工学院编译原理试卷资料面向高校计算机专业学生及备考者用于课程复习、考前自测与题型训练。内容围绕编译原理核心考点展开涵盖正规表达式与最简DFA构造、逆波兰表示、文法二义性证明、文法描述语言、First/Follow集计算、LL(1)文法判定与预测分析表构造以及if-then-else语句的四元式翻译等典型题目。资源包共1个doc文件大小约55KB轻量便于下载后直接打印或批注练习。已有392人学习说明其在校内复习与考研基础训练中有一定参考价值。通过完整题目可逐步梳理词法分析、语法分析、语义分析与中间代码生成之间的知识链路适合用来检验复习效果、定位薄弱环节并补充演算过程。1. 30分压在词法上这张《编译原理》试卷的分数分布与拿分逻辑《编译原理》的期末试卷有个反直觉的地方它几乎不考「编译器分哪几个阶段」这种背一遍就能写的题而是把整整 30 分砸在正规表达式和最简 DFA 上。翻一遍常见的编译原理试卷库同源卷子的结构高度一致正规式与 DFA 30 分、逆波兰与三元式 10 分、二义性与语言描述 20 分、First/Follow 与 LL(1) 25 分、四元式 15 分。也就是说过不过线不取决于你读没读过龙书而取决于你能不能在手算状态下把自动机画对、把表填满。这场考试是开卷很多人反而翻车书翻得越勤时间越不够最后 30 分的词法题只写了个正规式就交卷。真正的拿分逻辑是——五类母题各自有一套固定动作动作练熟开卷只是用来确认符号写法。后面按题型拆每道都按卷面真题给答案和思路。2. 词法分析大题正规表达式到最简DFA的两道真题全解这一题 30 分是全卷最值钱也最容易一步错步步错的地方。它的判分点非常死正规式对给一部分DFA 状态转移对给一部分化简到最简再给一部分。三段落一段分数就少一截。2.1 两道真题的正规表达式怎么推卷面第一题长这样为以下字符集编写正规表达式并构造与之等价的最简 DFA字母表 {0,1} 1不以 0 开头但以 11 结尾的所有字符串18 分 2包含 01 子串的所有字符串12 分第 1 小题有三个约束逐个翻译成正规式的「零件」不以 0 开头等价于必须以 1 开头写成1以 11 结尾写成11中间任意长写成(0|1)*。拼起来是1(0|1)*11。但这个式子漏了一种情况——长度只有 2 的串11。1(0|1)*11最少也要 3 个字符。每年都有人在这里丢 3 到 5 分因为11确实满足「以 1 开头、以 11 结尾」。正确写法是取并r1 11 | 1(0|1)*11第 2 小题简单得多只要出现过一次01前后随便什么都可以r2 (0|1)*01(0|1)*推正规式这一步建议养成一个习惯写完立刻枚举长度 0 到 3 的所有串做对拍手算就行。第 1 题枚举 0 到 2 位立刻能发现11漏了第 2 题枚举01、001、010、101四个都过就基本没错。2.2 从 NFA 到最简 DFA子集构造与状态最小化正规式只是「描述」卷面要的是「最简 DFA」中间要走两步先 Thompson 构造得到 NFA再子集构造确定化最后分割法最小化。考场上画 NFA 只要画对 ε 闭包主要时间花在后两步。对r1 11 | 1(0|1)*11直接给出确定化并化简后的结果5 个状态状态含义末尾连续 1 的个数读入 0读入 1q0起始状态qdq2q1末尾连续 1 的个数为 0q1q2q2末尾连续 1 的个数为 1q1q3q3末尾连续 1 的个数 ≥ 2终态q1q3qd死状态读到过前导 0qdqd状态语义这么设计是因为「是否以 11 结尾」只跟末尾连续几个 1 有关跟前面读过什么无关——这正是最小化的依据。最小化的分割过程要写在卷面上它是给分点第一步按终态/非终态分成{q3}和{q0,q1,q2,qd} 第二步考察{q0,q1,q2,qd}读入 1 时 q0→q2、q1→q2、qd→qd 都还在组内q2→q3 跳到了终态组于是 q2 分裂出来 第三步剩下{q0,q1,qd}读入 1 时 q0→q2、q1→q2 同组qd→qd 独在另一组qd 分裂 第四步{q0,q1}读入 0 时 q0→qd、q1→q1分属不同组再分裂。最终 5 个状态各自成组说明 5 个状态已经是最简不能再合并。这段话要一字不落地写因为「证明它最简」本身是题目的一部分。第 2 小题的 DFA 只要 3 个状态状态含义读入 0读入 1p0尚未出现 01且上一个字符不是 0p1p0p1尚未出现 01但上一个字符是 0p1p2p2已经出现过 01终态p2p2注意 p2 是「吸收态」一旦进去就出不来这是「包含子串」类题目的通用形态。识别出这个形态第 2 小题 30 秒就能画完。2.3 用代码对拍确认没多一个状态也没少一条边手画的 DFA 对不对最省时间的验证方式不是再画一遍而是把它翻译成几行代码跟正规式的语义对拍。这段脚本我考试前练手时反复用过import itertools, re def accept(s: str) - bool: 按 2.2 的状态表模拟0起始, 1末尾0个1, 2末尾1个1, 3末尾2个1, 4死状态 state 0 for ch in s: if state 0: state 2 if ch 1 else 4 # 首字符必须是 1否则进死状态 elif state 4: state 4 # 死状态自锁 elif ch 1: state min(state 1, 3) # 连续 1 的个数最多记到 2 else: state 1 # 读到 0连续 1 的计数清零 return state 3 # 只有末尾连续 2 个 1 才接受 pattern re.compile(r^(11|1[01]*11)$) # 正规式直接当参照物 for n in range(0, 10): for bits in itertools.product(01, repeatn): w .join(bits) assert accept(w) bool(pattern.match(w)), w print(all pass)这段代码的判分价值在三处。state 2 if ch 1 else 4对应「不以 0 开头」凡是首位为 0 的串一律进死状态min(state 1, 3)对应「末尾连续 1 的个数封顶为 2」封顶就是状态合并的依据state 3对应唯一的终态。三层语义跟状态表一一对上说明表没写错。range(0, 10)覆盖长度 0 到 9 的全部 1023 个串穷举对拍比人眼扫表可靠得多。参数想改就改两处把range(0, 10)调大能覆盖更长的串把pattern换成第 2 小题的^(0|1)*01(0|1)*$就能顺手验第二张表。提示考场上没法跑代码但这套「状态语义—转移条件—终态判据」的三段式检查法可以直接用眼睛走一遍比重新画图快。3. 表达式翻译逆波兰式、三元式与 if-then-else 的四元式这一块对应卷面的第二题10 分和第五题15 分看起来是两类题本质是同一条流水线把树形的表达式或语句压平成线性的中间代码。压平的手法固定练三道就有肌肉记忆。3.1 逆波兰式与三元式AB*(C-D)E/(C-D) 的完整手算原题写出表达式 AB*(C-D)E/(C-D) 的逆波兰表示及三元式序列。逆波兰式后缀式的判定标准只有一条运算符紧跟在它的两个操作数之后且不再需要括号。手算方法是用一个运算符栈遇到操作数直接输出遇到运算符先弹出栈顶优先级不低于它的运算符遇到右括号弹到左括号为止。按这个规则扫描最终输出A B C D - * E C D - / 拆开看就是两个加数A和B*(C-D)组成A B C D - * 再加E/(C-D)组成E C D - / 。这里容易翻车的是(C-D)出现了两次后半段必须重新生成一遍C D -不能因为前面算过就省掉——后缀式是「表达式」不是「程序」不做公共子表达式消除。三元式把每个运算写成(运算符, 操作数1, 操作数2)操作数如果是中间结果就写它的序号序号三元式说明(1)(-, C, D)算 C-D(2)(*, B, (1))B 乘以 (1) 的结果(3)(, A, (2))A 加上 (2) 的结果(4)(-, C, D)再算一次 C-D(5)(/, E, (4))E 除以 (4) 的结果(6)(, (3), (5))两半相加得到整个表达式的值如果题目允许优化把 (4) 改成直接引用 (1)三元式从 6 条降到 5 条这是三元式最讨巧的地方引用序号就是复用不需要额外的临时变量名。等价的四元式多一列「结果」用 T 开头命名临时变量序号四元式(1)(-, C, D, T1)(2)(*, B, T1, T2)(3)(, A, T2, T3)(4)(/, E, T1, T4)(5)(, T3, T4, T5)四元式的第 4 个分量是「结果存放位置」正因为有这个显式结果公共子表达式 T1 才能被后面直接引用而不用像三元式那样靠序号对齐。这一列是四元式与三元式最本质的差别写在卷面上就是得分点。3.2 if-then-else 的四元式先定跳转目标再填指令原题把语句翻译成四元式序列if x0 y0 then z:xy else begin x:x2; y:y3 end;题面里的x0 y0是x0 ∧ y0的排版脱落按逻辑与处理。这类题的核心不是算术而是控制流的跳转目标必须算准then 分支末尾要有一条无条件的j跳过 else否则程序会把两个分支都执行一遍。先按教科书习惯从 100 开始编号答案如下序号四元式含义100(, x, 0, T1)计算 x0101(jf, T1, -, 107)T1 为假跳到 else 的第一条102(, y, 0, T2)计算 y0103(jf, T2, -, 107)T2 为假同样跳到 else104(, x, y, T3)then 分支xy105(:, T3, -, z)赋给 z106(j, -, -, 111)跳过 else直接到 if 语句之后107(, x, 2, T4)else 分支x2108(:, T4, -, x)赋回 x109(, y, 3, T5)y3110(:, T5, -, y)赋回 y111—if 语句的后续代码四个关键位置要对上101 和 103 的跳转目标都指向 107因为 else 的第一条就是 107106 的跳转目标是 111也就是整个 if 语句结束后的第一条指令而不是 110——写成 110 会让最后一句y:y3被跳过这是最常见的一处错。如果想让卷面更干净可以用短路翻译把T1、T2这类布尔临时量省掉改用「假出口链」# 短路翻译 x0 ∧ y0 的假出口链等价于上面 100~103 四条 # 100 (, x, 0, T1) # 101 (jf, T1, -, 107) # 第一个条件为假整个与式为假 # 102 (, y, 0, T2) # 103 (jf, T2, -, 107) # 第二个条件为假同样跳到 else短路版的语义是第一个条件不成立就没必要算第二个。两种写法在考场上都给分但短路版更贴合「控制流翻译」的题意写的时候顺手在边上注明「假出口统一指向 107」阅卷时一眼就能看到你的链是闭合的。3.3 三元式、四元式、间接三元式的差别一句话说清这三种中间代码常被混着问其实差别只在「结果怎么表示」形式每条指令结果的表示复用中间结果的代价三元式(op, a1, a2)隐式靠指令序号直接引用旧序号但增删指令会让序号全变四元式(op, a1, a2, t)显式临时变量引用临时变量名指令增删不影响间接三元式(op, a1, a2) 执行顺序表隐式序号 一张表序号不动只改执行顺序表三者最需要记住的一句四元式之所以在真实编译器里用得最多就是因为它把结果显式化指令移动时不需要重排所有引用。这句话放在卷面上是拉开档次的地方。4. 文法性质与自顶向下分析二义性、语言描述、First/Follow 与预测表这一章覆盖卷面的第三、第四两题合计 45 分是全卷的分数重心也是最讲究「按套路出牌」的部分。二义性和语言描述考理解First/Follow 和预测表考手的稳定性。4.1 二义性证明找两条不同的最左推导就够了原题给的文法N → SE | ES S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9第一问是「证明文法 G 有二义性」。二义性的定义是存在一个句子它有两棵不同的语法树。证明方法就是构造具体做法是找一个能被两种方式切分成 S 和 E 的串。看文法结构N的两个产生式一个把 E 放右边一个把 E 放左边本文还有配套的精品资源点击获取