从正规式到最简DFA：编译前端可判定链路解析

简介这份常州工学院编译原理课程试卷A文档面向计算机专业本科生、考研复习者及任课教师可用于课程结课自测、期末复习与命题参考。内容围绕编译原理核心知识展开涵盖正规表达式构造与最简DFA、逆波兰表示、文法二义性证明及语言描述、First集与Follow集计算、LL(1)文法判定、预测分析表构造以及if-then-else语句的四元式序列翻译等典型题型能够帮助读者按词法分析、语法分析、语义分析与代码生成几个阶段梳理考点。压缩包内共1个doc文件大小约55KB轻量便于下载、打印和二次整理。目前已有393人学习适合需要借助完整试卷检验知识掌握程度、查漏补缺的读者使用。1. 一张编译原理试卷考的其实是「可判定」编译原理的试卷上最容易被低估的一题往往不是推导而是「为以下字符集写出正规表达式并构造与之等价的最简 DFA」。很多人能在纸上凑出一个能跑的式子,却在「最简」两个字上翻车:NFA 转 DFA 是机械活,真正考的是状态爆炸之后你还知不知道怎么把机器合回去。这份卷子把前端四个阶段各切了一刀:正规式与最简 DFA 对应词法,逆波兰与四元式对应中间表示,二义性与语言描述对应文法本身的性质,First/Follow 与预测分析表对应自顶向下分析。它真正想问的是——从高级语言到机器码这条链,每一环靠什么形式化工具把「模糊的意图」压成「可判定的问题」。想明白这条链,比背熟十道题的答案值钱得多。2. 正规式到最简 DFA状态爆炸之后怎么把机器合回去词法分析是整个前端唯一真正做到「工业级自动化」的部分给定一组正规式工具能自动吐出一个状态转移表。这背后是一条已经闭合的数学链路——正规式 → NFA → DFA → 最简 DFA每一步都有确定的算法不需要人的直觉。卷子把这道题放在 30 分的位置就是在确认你是否真的走过这条链路而不只是记住结论。2.1 正规式为什么必须落到自动机上正规式是「声明式」的你只说这个语言长什么样没说怎么识别它。而词法分析器需要的是「命令式」的当前读到第几个字符、下一步走哪条边、什么时候接受。这两者之间的桥就是有限自动机。这条桥之所以存在是因为正规式定义的语言类正则语言恰好等于有限自动机能识别的语言类而且这个等价是可构造的——不是存在性证明是给你一个能跑出来的算法。实际工程里词法分析器生成器干的就是这件事把.l文件里的正规式批量转成一张二维表状态 × 字符再压成一段跳转代码。常见实现里这张表会被进一步压成等价类表和压缩矩阵因为状态数每多一个常驻内存的表就大一截。关键点在于老师要你求「最简」不是刁难。词法分析器是每次编译都启动的常驻代码状态表的大小直接影响缓存命中最小化不是学术洁癖是工程习惯。2.2 Thompson 构造与 ε 闭包那堆空转移到底在做什么Thompson 构造是自底向上的每个基本正规式单个字符给一个两状态的小机器然后按「连接、选择、闭包」三种组合方式把机器拼起来。拼的方式非常规整——连接就是把前一个的终态用 ε 边接到后一个的初态选择就是加一个新的初态用 ε 边分叉闭包就是把终态 ε 回连到初态。ε 边看着多余其实是把「结构」和「控制流」解耦的代价。拼接的时候你不需要知道子机器内部长什么样只要接一条 ε 边就行代价是运行时必须先把 ε 边能到达的所有状态一次性算出来这就是 ε 闭包。没有 ε 闭包非确定性就没法被正确处理——你可能停在一个「看起来不能接受、但沿 ε 边再走两步就能接受」的状态上。我一般会这么理解ε 边是编译期的「胶水」ε 闭包是运行前的「胶水溶解」。溶解完NFA 就退化成一个状态集合上的确定转移。2.3 子集构造把「状态集合」当成一个新状态确定化的核心思想只有一句话NFA 的不确定性体现在「同一时刻可能处在多个状态」那就把「多个状态的集合」直接定义成 DFA 的一个状态。复杂度是指数级的最坏 2^n但实际正规式几乎不会触发最坏情况。# NFA 表示trans[(state, sym)] {后继状态集合}ε 边用 作 sym # 子集构造DFA 的每个状态 NFA 状态集合的 ε 闭包 def eps_closure(states, trans): 沿 ε 边做可达性搜索返回闭包frozenset 可哈希能当字典键 stack, closure list(states), set(states) while stack: s stack.pop() for t in trans.get((s, ), ()): # 只走 ε 边 if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construct(start, alphabet, trans, finals): s0 eps_closure({start}, trans) dfa_id, dfa_trans, work {s0: 0}, {}, [s0] while work: cur work.pop() for ch in alphabet: # 先 move吃掉一个字符再 ε 闭包把胶水溶解干净 moved {t for s in cur for t in trans.get((s, ch), ())} nxt eps_closure(moved, trans) if not nxt: # 空集 死状态显式保留更安全 continue if nxt not in dfa_id: dfa_id[nxt] len(dfa_id) work.append(nxt) dfa_trans[(dfa_id[cur], ch)] dfa_id[nxt] dfa_finals {i for s, i in dfa_id.items() if s finals} return dfa_id, dfa_trans, dfa_finalseps_closure里用frozenset而不是set是因为子集构造要用状态集合当字典的键来做去重可变集合不可哈希。moved那一步做了两件事先对所有当前状态求同一个字符的后继这一步体现「同时处在多个状态」再统一做闭包这一步把新引入的 ε 路径补全。死状态要不要显式保留是一个真实的取舍——省掉它表更小但转移函数就不再是全函数后续最小化和模拟器都得加空值判断。2.4 最小化划分法合并的是「未来的行为」最小化的判据不是「长得像」而是「对任意输入串行为一致」。所以划分法的做法是先把状态按「是不是终态」劈成两组然后不断检查——如果两个状态读同一个字符会落进不同的组那它们就不同类得拆开。反复拆到不再变化为止。def minimize(n_states, trans, finals, alphabet): 经典的 Moore 划分法收敛条件是分组数不再增加 part {s: (1 if s in finals else 0) for s in range(n_states)} while True: sig {} for s in range(n_states): # 签名 (自己所在组, 读每个字符后落进的组)-1 表示转移缺失 sig[s] (part[s],) tuple(part.get(trans.get((s, ch)), -1) for ch in alphabet) groups {} for s, g in sig.items(): groups.setdefault(g, set()).add(s) new_part {s: i for i, g in enumerate(groups.values()) for s in g} if len(set(new_part.values())) len(set(part.values())): return new_part # 组数不变 已是最粗划分 part new_part签名里的第一项part[s]必须带上否则会出现「两个状态虽然历史不同、但一步之后恰好重合」的误合并——等价关系要求的是自反和传递不能只比对后继。收敛判断用「组数不再增加」而不是「分区不再变化」因为编号会变但划分可能已经稳定比编号会误判成死循环。一个常被忽略的事实死状态不能随便删。它和「非终态」是否同类要由后续细分决定删掉它会让某些状态少一条出边最小化时签名里的-1就会造成假区分。2.5 两道题的完整推导第一题字母表 {0,1} 上不以 0 开头但以 11 结尾的所有串。分解成三段就清楚了——首位必须是 1中间随意尾部固定 11。正规式是1(0|1)*11注意(0|1)*可以为空所以11本身也被覆盖不需要额外写并集。对应的 DFA 用「首字符是否合法」「末尾连续 1 的个数」两个维度设计状态状态含义读 0读 1q0起始还没读字符qDq1q1首字符 1末尾连续 1 的个数为 1q3q2q2首字符 1末尾连续 1 的个数 ≥ 2接受q3q2q3首字符 1末尾是 0q3q1qD首字符为 0死状态qDqD这五个状态两两可区分qD 永远到不了接受态q3 读11才能接受q1 读一个1就接受q2 本身接受q0 和 q3 在「读 0 之后是 qD 还是 q3」上分道扬镳。所以它就是最简形式5 个状态。第二题包含 01 子串的所有串。正规式(0|1)*01(0|1)*状态只需要三个——「还没见到 01 且末尾不是 0」「末尾是 0 且还没见到 01」「已经见到 01」。状态含义读 0读 1p0未出现 01末尾非 0p1p0p1未出现 01末尾是 0p1p2p2已出现 01接受p2p2三状态且两两可区分不需要再合并。这两道题放在一起是有意为之第一题考「设计」第二题考「识别模式」——一个是结构约束一个是模式匹配正好是词法规则的两大来源。3. 逆波兰与四元式表达式被拉平之后优先级藏到哪里去了表达式AB*(C-D)E/(C-D)在源码里是一棵树到了机器上必须变成一串线性的指令。这个「树 → 序列」的转换是编译前端最漂亮的一步它把「优先级和结合性」这种二维信息压缩进了一维序列的「位置关系」里。搞懂这一步后面所有中间代码生成都是同一套思路的变体。3.1 中缀表达式麻烦在哪中缀表示的问题是它需要「上下文」才能解析看到AB*C你得先知道*比优先级高才知道B*C要先算。这意味着一台只读的机器没法从左到右直接求值必须反复回退或维护复杂的优先级栈。后缀逆波兰表示把这件事彻底解决了一个纯粹的栈机从左往右读遇到操作数压栈遇到运算符弹出两个算一下再压回去全程不需要任何优先级知识。信息没有消失只是从「符号的语义」搬到了「符号的位置」——运算符出现在它的两个操作数之后就天然表达了「先算子节点」。所以中缀转后缀本质就是表达式树的后序遍历。这句话听着像套话但它解释了一个关键现象后缀序列里永远不会出现括号。括号在中缀里的作用是「强制优先」而在树结构里优先关系本来就是结构不需要额外标记。3.2 手工做一遍栈与优先级表def infix_to_postfix(expr): 调度场算法的简化版operand 直接输出operator 按优先级弹栈 prec {: 1, -: 1, *: 2, /: 2} # 数字越大优先级越高 out, stack [], [] for tok in expr: if tok.isalnum(): out.append(tok) # 操作数立刻进入输出序列 elif tok (: stack.append(tok) # 左括号无条件压栈屏蔽内部优先级 elif tok ): while stack and stack[-1] ! (: out.append(stack.pop()) # 弹出到左括号为止 stack.pop() # 丢掉左括号它不进输出 else: # 左结合栈顶优先级 当前优先级就弹出保证同级从左到右算 while stack and stack[-1] ! ( and prec[stack[-1]] prec[tok]: out.append(stack.pop()) stack.append(tok) while stack: out.append(stack.pop()) # 收尾清空剩余运算符 return out这个符号是左结合的体现。如果换成A-B-C会被解析成A-(B-C)减法就从左结合变成了右结合。这是手写调度场算法最容易翻车的地方笔试时看不太出来一到实际表达式求值就出问题。把卷子里的式子喂进去过程是A输出压栈B输出*优先级高于压栈(压栈C、D输出读到)弹出-然后*遇到第二个时被弹出……最终得到A B C D - * E C D - / 。注意中间那个是在第一个子表达式完全结束后才被弹出来的这正是「左结合」在序列上的物理表现。3.3 四元式为什么不用后缀而用三地址码后缀表达式能算但没法优化也没法表达控制流。真正的编译器中间表示需要满足三个要求一每条指令只做一件事便于局部优化二指令有编号便于跳转和回填三结果有名字便于公共子表达式消除。四元式正好是这四个域(op, arg1, arg2, result)。它比三元式多一个 result 域好处是临时变量有了「名字」而不是「编号引用」——三元式里引用第 i 条指令的结果一旦指令位置因为优化而移动所有引用都要改四元式里临时变量只是一个符号挪位置不影响引用。这是一个典型的用一点存储空间换优化自由的取舍。卷子里那个表达式的四元式序列按「先叶子后根」的顺序生成序号oparg1arg2result100-CDT1101*BT1T2102AT2T3103-CDT4104/ET4T5105T3T5T6C-D出现了两次但这里生成了两条减法指令。这不是错而是给优化留的口子——后续跑一遍公共子表达式消除103 就会被识别成冗余并本文还有配套的精品资源点击获取