编译原理试卷五关：正则DFA、逆波兰、LL(1)与四元式解析

简介：常州工学院编译原理试卷A面向计算机专业本科生及考研复习者，用于检验词法分析、语法分析与中间代码生成等核心章节的掌握程度。压缩包内仅含1个doc文件，大小约55KB，虽体量精简，但题目覆盖正规表达式与最简DFA构造、逆波兰表示、文法二义性证明、LL(1)判定、First/Follow集及预测分析表、if-then-else四元式翻译等典型考点。已有392人浏览学习，适合作为期末自测、课堂练习或考前查漏补缺的试卷样本。读者可借助完整题干梳理编译原理各阶段的分析流程，对照分值分配把握复习重点，并针对证明与构造类题型训练规范书写和推导思路。

1. 一份编译原理试卷能当什么用：从正则到四元式的五道关卡

期末周前一周，某高校实验室的桌上摊着一份编译原理试卷，五道大题从正规表达式一路排到四元式，页脚印着装订线，翻久了边角起毛。多数人拿到手第一反应是对答案，其实这份卷子更像一张检查表：正则到最简 DFA 考的是建模，逆波兰考的是栈，二义性考的是找反例，First/Follow 与 LL(1) 预测分析表考的是机械推导的准确度，最后的 if-then-else 四元式考的是控制流落标号。它适合三类人：期末前想系统过一遍的、面试前要复习编译前端的、带课设需要出题素材的。下面按五道题的顺序拆，每一步都给能直接跑的校验脚本。

2. 正规表达式到最简 DFA：两道题的建模与状态编号

字母表都是 {0,1}，但两道题的约束类型完全不同。第一道“不以 0 开头但以 11 结尾”是结构约束，首字符和尾串都要管；第二道“包含 01 子串”是模式出现，只需要记住“见了什么、还差什么”。建模思路分清楚，状态数就不会乱涨。

2.1 先把自然语言拆成“首字符 + 中间任意 + 尾串”

“不以 0 开头”等价于首字符必须是 1；“以 11 结尾”等价于最后两位固定是 11。中间部分在 {0,1} 上任意，写成1(0|1)*11。这里有个最容易漏的边界：长度最短的合法串是11本身，而1(0|1)*11至少生成三位。所以正规表达式必须显式并上最短串：

(11) | (1(0|1)*11)

写成1(0|1)*(11)?是错的，可选部分不取时10、1都会被接受，首字符对了但尾串没管住。另一类错误是把(0|1)*放在最前面，那011也能生成，直接违反“不以 0 开头”。

拿几个边界串过一遍，心里就有数了：

这张表不要省，后面写 DFA 转移时，每个状态的语义都从表里反推出来。

2.2 Thompson 构造、子集构造、最小化：三步一步都不能省

从正规表达式到 DFA 的标准路径是三段：Thompson 构造把正则变成带 ε 边的 NFA，子集构造把 NFA 确定化成 DFA，最小化把等价状态合并。考场上很多人只画到 NFA 就交卷，或者确定化后不化简，状态数直接翻倍。

这道题其实可以跳过前两步，直接按语义设状态。设 q0 为起点，q1 表示“已读入若干字符、末尾不是 11”，q2 表示“末尾是 11”（终态），qd 是读到首字符 0 之后的死状态：

最小化按 Hopcroft 划分走一遍：初始把 {q2} 和 {q0,q1,qd} 分开。检查 {q0,q1,qd}，读 1 时 q1 去 q2（终态组），q0 去 q1、qd 去 qd（非终态组），于是 q1 单独成组，得到 {q1}、{q0,qd}、{q2}。再查 {q0,qd}：q0 读 1 去 q1，qd 读 1 去 qd，分属不同组，拆开。最终四个状态，已经最小，没有可合并的对。

写完之后拿脚本验一遍，比盯着纸面看可靠：

import re from itertools import product # 手写 DFA：q0 起点，q1 末尾不是 11，q2 末尾是 11（接受），qd 死状态 TRANS = { 'q0': {'0': 'qd', '1': 'q1'}, 'q1': {'0': 'q1', '1': 'q2'}, 'q2': {'0': 'q1', '1': 'q2'}, 'qd': {'0': 'qd', '1': 'qd'}, } ACCEPT = {'q2'} def dfa_accept(s: str) -> bool: st = 'q0' for ch in s: st = TRANS[st][ch] # 转移表必须覆盖全部输入符号，否则 KeyError return st in ACCEPT # 同一语言的正规表达式：11 单独列出，否则最短串会被漏掉 PAT = re.compile(r'^(?:11|1[01]*11)$') def re_accept(s: str) -> bool: return PAT.fullmatch(s) is not None # 必须 fullmatch，match 会放过前缀 # 枚举长度 0..9 的全部串做交叉验证 bad = [] for n in range(10): for tup in product('01', repeat=n): s = ''.join(tup) if dfa_accept(s) != re_accept(s): bad.append(s) print('不一致串数量:', len(bad), '样例:', bad[:10])

这段代码干的事很直接：一边用状态机跑，一边用正则匹配，枚举所有长度不超过 9 的二进制串，两边结果必须完全一致。TRANS用字典嵌套而不是二维数组，是为了让状态名可读，改状态时不容易错位；fullmatch是硬性要求，match只匹配开头，10会被误判成通过。枚举到长度 9 一共 1023 个串，跑完不到一秒，够覆盖这道题的所有边界。如果两边出现不一致，先查正则里的并集有没有漏最短串，再查 DFA 里 q2 读 1 是不是留在了 q2。

2.3 包含 01 子串：三个状态就够，别画成五个

第二道题的正规表达式是(0|1)*01(0|1)*，前导任意、中间固定 01、后缀任意。DFA 只需要记三件事：还没见到 01、上一个字符是 0 正在等 1、已经命中 01。

最小性很好证：q0 读 1 还在 q0，q1 读 1 进终态，两者可区分；q2 是终态，与前两个都不同。三个状态各自有区分串，不能再合并。

常见翻车是给 q0 读 1 加一个新状态 q3，理由是“读了个 1 总得记一下吧”。不用记，因为1既不是 01 的开头，也不改变“尚未命中”的事实，留在 q0 就行。状态一多，最小化那步就容易漏，最后画出来的图自己都不敢确认。

还有个更快的自查角度：不含 01 子串的串长什么样？一旦出现 0，后面就不能再出现 1，所以补集语言是1*0*。它的 DFA 只有两个活状态加一个死状态，把接受态取反就得到本题的 DFA。用补集反推，比正着画更容易发现漏边。这个方法在考场上很省时间：先写补集的正则，再取反，状态数通常一眼就能看出来。

2.4 从 DFA 反推正则：用状态消去法做最后一道校验

画完图别急着下一题，花两分钟做一次反向推导。状态消去法的规则是：对每个非终态，把它所有入边和出边两两组合，边上的标签做连接，遇到自环就加闭包。以本题的三个状态为例，先消 q1：q1 的自环是 0，入边来自 q0 的 0，出边是到 q2 的 1，组合后得到 q0 到 q2 的边00*1；q0 原有到 q2 的路径不存在，所以合并后 q0 到 q2 是00*1；q0 自环是 1，q2 自环是 (0|1)，最终表达式为1*(00*1)(0|1)*。这个式子与(0|1)*01(0|1)*等价，只是把“01 之前不能有 0 后接 1”这个约束显式写了出来。

反推出来的式子跟正面写的不一样，是正常的，正规表达式本来就不唯一。关键是两边描述的语言要一致，拿 2.2 的脚本改一下正则再跑一遍枚举，能对上就说明 DFA 没画错。这一步在考场上不用写进答题纸，但草稿上做一次，能挡住大部分状态转移写反的问题。

提示：状态命名用语义而不是 q0、q1、q2 混着来，最小化时不容易把两个语义不同的状态合到一起。写答题纸时再换回 q 编号，草稿和卷面分开。

3. 逆波兰与四元式：把 A+B*(C-D)+E/(C-D) 手工推一遍再让脚本复核

这道题给的是A+B*(C-D)+E/(C-D)，两个加号同级，中间夹着乘法和两个括号。看着简单，但减法除法的操作数顺序一翻就全错，而且C-D出现了两次，很容易在四元式里多算或少算一遍。先手工推，再用脚本对，最后用求值器验结果。

3.1 调度场算法：优先级、结合性、括号三件事

转逆波兰的标准做法是调度场算法：操作数直接进输出队列，运算符进栈，遇到优先级不高于栈顶的运算符就先弹出栈顶，遇到右括号就弹到左括号为止。这里的“不高于”对应左结合，写成严格大于就会把a-b-c转成a b c - -，减法顺序反了。

最终结果是A B C D - * + E C D - / +。手工核对一遍：B*(C-D)变成B C D - *，前面接A +，得到A B C D - * +；E/(C-D)变成E C D - /；两段再做一次+。顺序没错。

同样的逻辑落到代码里：

def to_rpn(expr: str) -> list[str]: prec = {'+': 1, '-': 1, '*': 2, '/': 2} # 数字越大优先级越高 out, ops = [], [] for ch in expr: if ch.isalnum(): # 单字符操作数 A~E out.append(ch) elif ch == '(': ops.append(ch) elif ch == ')': while ops[-1] != '(': out.append(ops.pop()) ops.pop() # 左括号只弹出不输出 else: # 左结合：栈顶优先级 >= 当前就弹出，不能用 > while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[ch]: out.append(ops.pop()) ops.append(ch) while ops: out.append(ops.pop()) return out print(' '.join(to_rpn('A+B*(C-D)+E <p> <a href="https://download.csdn.net/download/JonHans/2411143" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>