简介：这份常州工学院编译原理试卷资料面向高校计算机专业学生及备考者，用于课程复习、考前自测与题型训练。内容围绕编译原理核心考点展开，涵盖正规表达式与最简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 | 读入 1 |
|---|---|---|---|
| q0 | 起始状态 | qd | q2 |
| q1 | 末尾连续 1 的个数为 0 | q1 | q2 |
| q2 | 末尾连续 1 的个数为 1 | q1 | q3 |
| q3 | 末尾连续 1 的个数 ≥ 2（终态） | q1 | q3 |
| qd | 死状态（读到过前导 0） | qd | qd |
状态语义这么设计，是因为「是否以 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 | 读入 1 |
|---|---|---|---|
| p0 | 尚未出现 01，且上一个字符不是 0 | p1 | p0 |
| p1 | 尚未出现 01，但上一个字符是 0 | p1 | p2 |
| p2 | 已经出现过 01（终态） | p2 | p2 |
注意 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', repeat=n): 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 逆波兰式与三元式：A+B*(C-D)+E/(C-D) 的完整手算
原题：
写出表达式 A+B*(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 x>0 y>0 then z:=x+y else begin x:=x+2; y:=y+3 end;
题面里的x>0 y>0是x>0 ∧ y>0的排版脱落，按逻辑与处理。这类题的核心不是算术，而是控制流的跳转目标必须算准：then 分支末尾要有一条无条件的j跳过 else，否则程序会把两个分支都执行一遍。
先按教科书习惯从 100 开始编号，答案如下：
| 序号 | 四元式 | 含义 |
|---|---|---|
| 100 | (>, x, 0, T1) | 计算 x>0 |
| 101 | (jf, T1, -, 107) | T1 为假，跳到 else 的第一条 |
| 102 | (>, y, 0, T2) | 计算 y>0 |
| 103 | (jf, T2, -, 107) | T2 为假，同样跳到 else |
| 104 | (+, x, y, T3) | then 分支：x+y |
| 105 | (:=, T3, -, z) | 赋给 z |
| 106 | (j, -, -, 111) | 跳过 else，直接到 if 语句之后 |
| 107 | (+, x, 2, T4) | else 分支：x+2 |
| 108 | (:=, T4, -, x) | 赋回 x |
| 109 | (+, y, 3, T5) | y+3 |
| 110 | (:=, T5, -, y) | 赋回 y |
| 111 | — | if 语句的后续代码 |
四个关键位置要对上：101 和 103 的跳转目标都指向 107，因为 else 的第一条就是 107；106 的跳转目标是 111，也就是整个 if 语句结束后的第一条指令，而不是 110——写成 110 会让最后一句y:=y+3被跳过，这是最常见的一处错。
如果想让卷面更干净，可以用短路翻译，把T1、T2这类布尔临时量省掉，改用「假出口链」：
# 短路翻译 x>0 ∧ y>0 的假出口链，等价于上面 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 放左边；
本文还有配套的精品资源，点击获取
