简介：这份常州工学院编译原理课程试卷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_finals

eps_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 的个数」两个维度设计状态：

这五个状态两两可区分：qD 永远到不了接受态；q3 读11才能接受；q1 读一个1就接受；q2 本身接受；q0 和 q3 在「读 0 之后是 qD 还是 q3」上分道扬镳。所以它就是最简形式，5 个状态。

第二题：包含 01 子串的所有串。正规式(0|1)*01(0|1)*，状态只需要三个——「还没见到 01 且末尾不是 0」「末尾是 0 且还没见到 01」「已经见到 01」。

三状态且两两可区分，不需要再合并。这两道题放在一起是有意为之：第一题考「设计」，第二题考「识别模式」——一个是结构约束，一个是模式匹配，正好是词法规则的两大来源。

3. 逆波兰与四元式：表达式被拉平之后，优先级藏到哪里去了

表达式A+B*(C-D)+E/(C-D)在源码里是一棵树，到了机器上必须变成一串线性的指令。这个「树 → 序列」的转换，是编译前端最漂亮的一步：它把「优先级和结合性」这种二维信息，压缩进了一维序列的「位置关系」里。搞懂这一步，后面所有中间代码生成都是同一套思路的变体。

3.1 中缀表达式麻烦在哪

中缀表示的问题是它需要「上下文」才能解析：看到A+B*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 条指令的结果，一旦指令位置因为优化而移动，所有引用都要改；四元式里临时变量只是一个符号，挪位置不影响引用。这是一个典型的用一点存储空间换优化自由的取舍。

卷子里那个表达式的四元式序列，按「先叶子后根」的顺序生成：

C-D出现了两次，但这里生成了两条减法指令。这不是错，而是给优化留的口子——后续跑一遍公共子表达式消除，103 就会被识别成冗余并

本文还有配套的精品资源，点击获取