简介：常州工学院编译原理试卷A是一份面向计算机专业本科生复习与教师命题参考的课程试卷，覆盖正规表达式与最简DFA构造、逆波兰表示、文法二义性判定及语言描述、LL(1)文法的First/Follow集与预测分析表构造，以及条件语句翻译为四元式序列等核心考点。压缩包内共1个doc文件，约55KB，为单份试卷文档，适合打印练习或课堂测验使用。该资源已有393人学习，可作为期末复习、考研专业课梳理和编译原理阶段测试的对照材料。通过逐题演算，读者可系统检查词法分析、语法分析与语义分析等环节的掌握情况，并借助完整题目训练正规式设计、分析表构建和中间代码生成能力。
1. 翻一份编译原理试卷，多数人盯错了地方
翻一份编译原理试卷，多数人会先盯着最后那道 15 分的语句翻译题，觉得前面那些正规表达式、FIRST/FOLLOW 只是套公式的计算活。反过来才对：那些看起来像算术题的部分，才是整条编译前端流水线的地基。一份典型的期末卷面通常考五件事——正规表达式到最简 DFA、逆波兰与四元式、文法二义性、LL(1) 预测分析表、条件语句的中间代码翻译——它们正好串起词法识别、语法判定、分析表构造、中间代码生成这条主干。搞清这五步之间谁依赖谁，比背下每种题的解法有用得多。下面就把这份试卷拆开，讲清每道题背后在考什么机制、为什么必须这么设计，以及手工推导时最容易在哪一步翻车。
2. 正规表达式到最简 DFA：子集构造为什么能消灭“不确定”
2.1 从题目文字到正规式：1(0|1)*11 漏掉了什么
试卷第一题问的是：在字母表 {0,1} 上，写出“不以 0 开头但以 11 结尾”的所有字符串的正规表达式。直觉会写成1(0|1)*11——第一个字符固定是 1，中间任意，最后两个是 1。这个式子确实只生成长度不小于 3 的串，问题在于它把11自己漏掉了：这个串以 1 开头、以 11 结尾，却没法从1(0|1)*11里推出来，因为它要求开头那个 1 和结尾两个 1 是三个不同的位置。
正确的写法是11 | 1(0|1)*11，或者等价地写成1(1 | (0|1)*11)：第一个 1 之后，要么直接接一个 1 收尾（总长 2），要么中间塞任意串再接 11。
同一题的第二问“包含 01 子串”就直白得多：(0|1)*01(0|1)*。它和第一问的差别值得留意——第一问约束的是“首字符”和“尾字符”两个端点，端点约束在写正规式时最容易丢；第二问约束的是“存在某个子串”，用前后各一个(0|1)*夹住就行。
正规式的写法从来不唯一，11|1(0|1)*11和1(1|(0|1)*11)描述的是同一个语言。所以出题人说“最简”，考的其实不是式子长短，而是后面那个 DFA 的状态数最少——这是两个不同的最简概念。
2.2 Thompson 构造与 ε-闭包：不确定性是从哪来的
正规式到 DFA 之间通常垫一步 NFA。常见的实现思路是 Thompson 构造：给每种基本正规式配一个小片段，连接靠首尾相接，选择靠新起一个状态分叉出两条 ε 边，闭包靠把片段的首尾用 ε 边接回去。整个过程是纯结构递归，NFA 的状态数和正规式长度成线性关系，这是它最大的价值——不会爆炸。
代价是引入了 ε 边。ε 边意味着“不吃任何输入也能走”，于是 NFA 在某一时刻不再处于单一状态，而是同时处于一个状态集合。这就是“不确定”的准确含义：不是随机，而是并行的多条路径。
处理它的工具是 ε-闭包：ε-closure(S)等于 S 本身，加上从 S 出发只沿 ε 边走能到达的所有状态。这个操作必须做传递闭包，而不是只看一步——A 沿 ε 到 B、B 沿 ε 到 C，那么 C 也在闭包里。手工推导时最常犯的错就是只展开一层，状态一多就漏。
2.3 子集构造：把一个状态集合当成一个新状态
子集构造是这套流程里最漂亮的一步：既然 NFA 跑起来本来就是一个状态集合，那就干脆把这个集合直接定义成 DFA 的一个状态。转移函数写成 δ(S, a) = ε-closure(∪ move(s, a))，其中 s 遍历 S 里的每个状态。代码大致长这样：
def subset_construct(nfa_states, alphabet, eps, move, start, finals): """eps: {state: set(state)} 表示 ε 边；move: {(state, ch): set(state)} 表示符号边""" def eclose(states): stack, seen = list(states), set(states) while stack: # 栈式传递闭包，不是只展开一层 s = stack.pop() for t in eps.get(s, ()): if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) # frozenset 才能当 dict 的键 start_set = eclose({start}) dfa, work, trans, dfa_final = {start_set: 0}, [start_set], {}, set() while work: cur = work.pop() if cur & finals: # 集合里只要含一个 NFA 接受态就是接受态 dfa_final.add(dfa[cur]) for ch in alphabet: nxt = eclose(set().union(*[move.get((s, ch), set()) for s in cur])) if not nxt: # 空集不建状态，留成“不完整 DFA” continue if nxt not in dfa: dfa[nxt] = len(dfa) work.append(nxt) trans[(dfa[cur], ch)] = dfa[nxt] return dfa, trans, dfa_finaleclose用显式栈做闭包，避免递归层数受状态数影响；frozenset是因为集合本身不可哈希，不能当状态编号字典的键；if not nxt: continue那一行是刻意的取舍——空集不建状态，得到的是一个“不完整 DFA”，遇到非法输入直接报词法错误。这在真实词法分析器里是标准做法，但到了最小化那一步就必须补一个死状态，否则等价类划分会算错，这是后话。
拿第一题验证一下。起点读 1 进“已合法开头”，读 0 直接进死路；读到第一个 1 之后，再看一个 1 就进入接受态。最后得到的转移表是：
| 状态 | 读 0 | 读 1 | 含义 |
|---|---|---|---|
| →q0 | d | q1 | 起始，还没读到开头那个 1 |
| q1 | q1 | q2 | 开头合法，但末尾不是 11 |
| *q2 | q1 | q2 | 末尾两位是 11，接受 |
| d | d | d | 以 0 开头的非法串 |
q2 读 1 仍停在 q2，因为末尾两位还是 11；读 0 退回 q1，因为末尾变成了 10。q1 的语义是“已经合法开头，但当前不满足结尾条件”，所以它读 0 停在原地、读 1 前进。死状态 d 是不可省的，它承载了“这个串已经废了”这个信息。
2.4 最小化：状态为什么可以合并，又凭什么不能再少
最小化的本质是找一个等价关系：两个状态等价，当且仅当对所有可能的输入后缀，它们要么都接受、要么都不接受。这个定义是“对所有后缀”的全称量化，所以不能用枚举验证，只能用归纳法证明——Hopcroft 划分就是干这个的。
初始划分只有两块：接受态集合和是否定态集合。然后反复检查，如果同一块里的两个状态读到某个字符后落进了不同的块，就把它们拆开，直到这一轮不再产生新块。道理很直白：如果一个状态读 a 后能接受、另一个读 a 后不能，它们就不可能等价；这条判据一路归纳下去，最终得到的就是“任意长度后缀行为一致”的划分。
手工验证最小性有个笨但可靠的办法：对每两个状态各找一条区分串。在上面那张表里，q1 和 q2 用空串就能区分（一个接受一个不接受）；d 和 q1 用1区分（q1 读到接受态，d 读到 d，而 d 再接什么都出不来）；q0 和 d 用1区分（q0 读 1 到 q1，再读 1 接受；d 读 1 还是 d）。四类状态两两可区分，所以 4 个状态已经是最少。
这一步在纸面上是纯计算，在工程上却是实打实的性能问题。词法分析器一般实现成状态转移表加一个大 switch 或者二维数组，表里的每个状态都要占一行，状态数从几十降到十几个，表就小一半，缓存也更友好。
3. 逆波兰与四元式：中间代码为什么必须“无括号”
3.1 调度场算法：运算符栈里到底存了什么
第二题要求把A+B*(C-D)+E/(C-D)写成逆波兰表示。逆波兰（后缀式）的核心性质是：只要知道每个运算符要几个操作数，从左往右扫一遍就能算完，永远不需要括号，也不需要回退。
把中缀转后缀的标准做法是调度场算法。它维护两个容器：输出队列装已经排好序的操作数和运算符，运算符栈装“还没确定什么时候该出栈”的运算符。一条运算符能不能出栈，取决于栈顶运算符的优先级是否不低于当前运算符——>=这个等号就是左结合性的落点，因为同级运算符要先出栈，才能保证a-b-c被算成(a-b)-c：
def to_rpn(tokens): prec = {'+': 1, '-': 1, '*': 2, '/': 2} out, ops = [], [] for t in tokens: if t.isalnum(): out.append(t) # 操作数直接进输出队列 elif t == '(': ops.append(t) # 左括号当哨兵，优先级视为最低 elif t == ')': while ops and ops[-1] != '(': out.append(ops.pop()) ops.pop() # 弹出并丢弃左括号 else: while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[t]: out.append(ops.pop()) # 左结合用 >=，右结合改成 > ops.append(t) while ops: out.append(ops.pop()) # 收尾：把栈里剩的全部吐出 return outprec表决定了运算符优先级，左括号当哨兵是为了挡住“(还没有配对时被弹栈”的情况，循环末尾的 while 负责处理表达式结束时栈里残留的运算符。如果语言里有右结合运算符（比如幂运算或者赋值），只需要把>=放宽成>，逻辑不变。
对A+B*(C-D)+E/(C-D)走一遍，得到A B C D - * + E C D - / +。注意两个加法是左结合的，第一个+必须在第二个+入栈之前出栈，否则表达式就变成了A+(B*(C-D)+(E/(C-D)))，虽然这里加法结合性不影响结果，但对减法和除法就是致命错误。
后缀式还有一个经常被忽略的性质：它的最大栈深度等于表达式语法树的深度。这个数字在寄存器分配里直接对应需要的临时寄存器数量，Sethi-Ullman 编号就是为了求这个最少寄存器数而设计的。
3.2 三元式与四元式：序号引用为什么是后悔药
同一道题还要写三元式或四元式序列。三元式的格式是(op, arg1, arg2)，结果不写出来，而是用这条指令的序号隐式表示——第 (1) 条的结果就叫 (1)。四元式多一个字段：(op, arg1, arg2, result)，结果显式写成 T1、T2 这样的临时变量。
这个多出来的字段是设计上的关键分水岭。三元式的引用全部是“第几条指令”，一旦中间代码要插入删除、重排顺序，所有引用都得跟着改，改漏一处就是错。四元式用临时变量名引用，指令随便挪位置，引用关系不变。做过指令调度或者局部优化的人都明白这个差别意味着什么：优化本来就是不停地增删和搬家，如果每搬一次都要重算一遍引用，优化器根本没法写。
A+B*(C-D)+E/(C-D)的四元式序列是：
| 序号 | op | arg1 | arg2 | result |
|---|---|---|---|---|
| 1 | - | C | D | T1 |
| 2 | * | B | T1 | T2 |
| 3 | + | A | T2 | T3 |
| 4 | / | E | T1 | T4 |
| 5 | + | T3 | T4 | T5 |
第 4 条直接用 T1，是手写时主动做的公共子表达式复用：(C-D)算一次就够。而如果让程序从后缀式机械生成，就会得到六条指令、算两遍C-D——这正好说明“有后缀式不等于有优化”，公共子表达式消除是单独一趟要做的活。
3.3 if-then-else 的四元式：回填与短路求值
第五题要把if x>0 and y>0 then z:=x+y else x:=x+2; y:=y+3翻译成四元式。这题真正考的不是表达式翻译，而是控制流的跳转目标怎么定。
麻烦在于：生成第一条指令的时候，你根本不知道 else 分支从第几条开始。机器码是顺序生成的，未来的地址在现在这一刻还不存在。常见的解法是回填：先在这些位置填一个占位符，同时把“所有等着填这个目标的地方”串成一条链记下来，等目标地址确定，顺链子一次性补上。条件为假就跳走的jf
本文还有配套的精品资源，点击获取
