简介面向高校计算机专业学生及编译原理课程复习备考者常州工学院编译原理试卷A提供一套完整的课程考核样卷适合期末自测、题型梳理与查漏补缺。试卷覆盖正规表达式与有限自动机、逆波兰表示、文法二义性、LL(1)文法与预测分析表、条件语句四元式序列等核心知识点可检验从词法分析、语法分析到语义分析与代码生成的掌握程度。资源包共1个doc文件大小约55KB轻量易取便于打印或在线作答。已有392人学习说明其在同类课程资料中具有一定参考价值。逐题演练时读者可熟悉构造最简DFA、证明文法二义性、计算First/Follow集、构造预测分析表以及翻译中间代码的常见思路适合作为考前集中训练和课堂配套练习的补充材料。1. 一句中文描述到一台状态机这张卷子到底在考什么把「不以 0 开头、以 11 结尾的二进制串」翻译成正则绝大多数人第一次写都会漏掉最短的那个11——因为脑子里想的是「先有个开头 1再有一堆任意最后 11」。这说明编译原理真正的难点从来不是记住 Thompson 构造的步骤而是把一句自然语言精确地钉死成一个形式化对象再让机器去验证它。词法分析、语法分析、中间代码生成三个阶段本质上都在做同一件事把模糊的人话压缩成无歧义的结构。这张卷子的五道题恰好卡在这几条分界线上每道题都埋着一个「写对了但想错了」的陷阱把编译原理的底层机制从头到尾串起来值得认真拆一拆。2. 正规表达式到最简 DFA为什么「不以 0 开头、以 11 结尾」会漏掉一个串词法分析的整个理论栈是三层正则表达式描述模式NFA 识别模式DFA 高效执行识别最后由最小化把状态数压到理论下界。这条链条上的每一步都有明确的数学保证但写在卷面上的第一道题卡住人的往往不是理论而是「语言边界」的判断。2.1 从中文描述到正则先把边界串列出来题目是字母表 {0,1} 上、不以 0 开头、以 11 结尾的所有字符串。做这类题有一个血泪经验不要直接写正则先把所有「边界情况」列出来——最短串、空串、只差一个字符的串。最短的候选是长度 2 的11它以 11 结尾首字符是 1符合条件。长度 3 的111也符合。长度 4 的1011、1111都符合。现在看一个常见的错误答案1(0|1)*11。它的最短串是1 空 11111长度 3。11不在里面。这就是漏串1(0|1)*11强制要求「开头那个 1」和「结尾那两个 1」之间至少隔一层如果开头那个 1 本身就是结尾 11 的第一个 1这个正则就描述不出来。正确的写法要把这两种情况并起来11 | 1(0|1)*11前一项覆盖「整个串就是 11」后一项覆盖「开头 1 与结尾 11 分离」。也可以写成等价的1((0|1)*1)?1含义是首字符 1中间是「任意串接一个 1」或者什么都没有末字符 1。这里的设计动机值得说清楚正则表达式是「并、连接、闭包」三种运算的封闭代数它的表达能力刚好等于有限自动机。所谓「闭包」本质是允许某一个子结构重复零次——(0|1)*里的*就是这个零次。漏串的根源几乎总是「某个本该允许零次的位置被写成了至少一次」。第二小题「包含 01 子串的所有字符串」犯的是镜像错误(0|1)*01(0|1)*这里01两侧的闭包一个都不能少。少了左边就只覆盖以 01 开头的串少了右边就只覆盖以 01 结尾的串。包含子串是一个「存在某个位置」的性质翻译成正则就是「任意前缀 目标 任意后缀」两侧必须都是(0|1)*。2.2 Thompson 构造与子集构造NFA 是中间产物不是终点正则写对以后卷面要求「构造与之等价的最简 DFA」中间必须经过 NFA。Thompson 构造的规则非常机械每个正则运算对应一种固定的状态拼接模板字符对应两个状态一条边连接对应 ε 边串联并对应分叉闭包对应回头边。以11 | 1(0|1)*11为例直接手搓 NFA 会画出一大坨 ε 边但真正有价值的是后面那一步子集构造subset construction。子集构造的核心思想只有一句话NFA 在某一时刻可能同时处于多个状态那就把「可能的状态集合」整体当成 DFA 的一个状态。加上 ε 闭包从集合中任一状态出发只走 ε 边能到达的所有状态作为预处理一个 NFA 就变成了一个状态数是 2^n 上界的 DFA。常见的实现思路是维护一个待处理队列def subset_construction(nfa_states, alphabet, move, eps_closure, start, accept): 把 NFA 转成 DFA。 move(s, ch): NFA 中从状态 s 读入 ch 后直接到达的状态集合 eps_closure(S): 集合 S 的 ε 闭包 返回的 DFA 状态就是 frozenset天然去重 start_set frozenset(eps_closure({start})) dfa_states {start_set} queue [start_set] trans {} while queue: cur queue.pop(0) for ch in alphabet: # 先走字符边再补 ε 闭包这是子集构造的标准两步 nxt set() for s in cur: nxt | move(s, ch) nxt frozenset(eps_closure(nxt)) trans[(cur, ch)] nxt if nxt not in dfa_states: dfa_states.add(nxt) queue.append(nxt) dfa_accept {S for S in dfa_states if S accept} return dfa_states, trans, start_set, dfa_accept这段代码里有两个容易忽略的细节。第一nxt可能是空集。空集也是子集构造的合法产物它对应「陷阱态」——一旦进入就再也出不来、也不接受任何串的状态。如果不把空集放进dfa_states得到的 DFA 就是「部分定义」的转移表里会缺项。第二eps_closure必须作用在「走完字符边之后的集合」上而不是在走之前。顺序反了会把不该连通的路径连通得到一个接受多余串的 DFA。2.3 最小化陷阱态为什么不能随便合并子集构造得到的 DFA 通常远大于必要。最小化的本质是「状态等价类划分」两个状态等价当且仅当对任意输入串从它们出发要么都接受要么都拒绝。Moore 划分法是实现这个判断最直接的算法——先按「接受 / 非接受」切一刀然后不断细化同一个块内的两个状态如果读入某个字符后落到了不同的块就把它们拆开直到划分不再变化。def minimize(states, alphabet, trans, accept): Moore 划分法。 trans 必须是完全 DFA每个 (状态, 字符) 都有定义缺失的补陷阱态 # 第 0 轮只区分「接受」和「不接受」这是最粗的等价关系 blocks [set(accept), set(states) - set(accept)] blocks [b for b in blocks if b] while True: idx {s: i for i, b in enumerate(blocks) for s in b} new_blocks [] for b in blocks: buckets {} for s in b: # 签名 读入每个字符后落到哪个块签名相同即当前不可区分 sig tuple(idx[trans[(s, ch)]] for ch in alphabet) buckets.setdefault(sig, set()).add(s) new_blocks.extend(buckets.values()) if len(new_blocks) len(blocks): break # 划分稳定收敛 blocks new_blocks rep {s: min(b) for b in blocks for s in b} new_trans {(rep[s], ch): rep[trans[(s, ch)]] for (s, ch) in trans} return blocks, new_trans回到第一题如果按「是否以 11 结尾、末尾连续 1 的个数」来设计状态会得到这样一组状态含义读 0读 1A未读入任何字符陷阱CB末字符为 0BCC末尾恰好一个 1BDD以 11 结尾接受BDE陷阱首字符为 0 或其它非法EE接受态只有 D。验证一下11走 A→C→D接受011在 A 读 0 进 E拒绝1011走 A→C→B→C→D接受1101走 A→C→D→B末态非接受正确——1101确实不以 11 结尾。最小化阶段的关键判断是E 能不能和别的状态合并答案是不能。因为 A、B、C、D 都有「读某个字符后能到达接受态」的路径而 E 对任何输入都回到自己永远到不了接受态。等价关系要求「对任意输入串行为完全一致」E 和任何人都对不上它自成一类。这就是陷阱态的价值它让 DFA 变成完全函数从而让最小化算法有统一的输入格式。手工画图时很多人会省略陷阱态卷面上看起来更干净但一旦做最小化或者写代码建表「某个转移不存在」就要在每一处单独处理反而是负担。2.4 一个反直觉的结论最小化之后的状态数并不是「越少越好」的美学指标它是语言的 Myhill-Nerode 等价类数量的直接体现。换句话说状态数少到这个程度就说明你已经把「这个语言需要记住多少历史信息」压到了理论下限。第一题的语言需要记住三件事是否已读到合法首字符、末字符是不是 1、末尾是不是已经有连续两个 1。三件事组合出四个有效状态加上陷阱态就是五个——这就是它不能更少的根本原因。3. 逆波兰式与四元式同一个表达式为什么要存两遍表达式AB*(C-D)E/(C-D)在卷面上要写两遍一遍是逆波兰后缀表示一遍是四元式序列。很多人觉得这是重复劳动其实这两个东西服务的是完全不同的消费者。3.1 逆波兰式给栈机器看的线性序列逆波兰式的生成规则只有一条运算符的优先级低于栈顶、或者是右括号、或者输入结束就弹出栈顶输出。用调度场算法shunting-yard实现本质是「用输出序列替代递归」def to_rpn(tokens): tokens 已经过词法分析如 [A,,B,*,(,C,-,D,),...] prec {: 1, -: 1, *: 2, /: 2} out, stack [], [] for t in tokens: if t in prec: # 左结合栈顶优先级 当前就先让它出去 while stack and stack[-1] in prec and prec[stack[-1]] prec[t]: out.append(stack.pop()) stack.append(t) elif t (: stack.append(t) elif t ): while stack[-1] ! (: out.append(stack.pop()) stack.pop() # 丢掉左括号 else: out.append(t) # 操作数直接输出 out.extend(reversed(stack)) return out对AB*(C-D)E/(C-D)跑一遍进栈遇到*优先级更高进栈括号内的-被括号隔开)触发弹出-输出C D -接着弹出*输出B C D - *然后第一个遇到第二个同优先级左结合弹出前一个。最终结果A B C D - * E C D - / 逆波兰式的设计动机非常纯粹它消除了括号和优先级任何一个前缀合法的后缀序列都可以用一个栈在线性时间内求值——遇到操作数压栈遇到运算符弹出两个、压回一个。这正是 JVM 字节码、PostScript、以及大量计算器内部采用的形式。它的消费者是「栈式求值器」不需要知道变量名只需要一个后进先出的容器。但逆波兰式有一个致命缺陷它只有线性顺序没有「结果存在哪」这个概念。你没法在序列里标注「这个C-D的结果后面还要用」。3.2 四元式的字段设计为什么必须是 (op, arg1, arg2, result)四元式补上了这个缺口。它的字段是固定的四个槽(op, arg1, arg2, result)对同一个表达式不做任何优化时四元式序列是(1) (-, C, D, T1) (2) (*, B, T1, T2) (3) (, A, T2, T3) (4) (-, C, D, T4) (5) (/, E, T4, T5) (6) (, T3, T5, T6)注意第 (4) 条和第 (1) 条算的是同一个C-D。这不是错是「朴素翻译」的必然结果语法树里C-D出现了两个节点逐个节点翻译就会算两次。识别它们是公共子表达式、把 (4) 换成(, T1, -, T4)或者干脆让 (5) 直接引用 T1那是优化阶段的活不是翻译阶段的活。四元式的字段设计有三个考量。第一定长。每条四元式占同样多的槽可以直接下标寻址适合放进数组做后续分析活跃变量分析、到达定值分析都是对这张表扫来扫去。第二结果显式命名。result这一栏让「值的流向」变成数据而不是位置关系。三元式用的是(op, arg1, arg2)操作数通过「第几条三元式的编号」来引用看起来省了一个字段代价是致命的一旦你为了优化要删除或移动某条三元式所有引用它的编号全部失效得整体重编号。四元式用临时变量名做引用移动一条指令不影响别人这是它能支撑优化阶段重排的根本原因。第三间接三元式是两者的折中三元式表本身不动另建一张指针表指示执行顺序重排只动指针。这套设计在一些教学编译器和早期的优化器里出现过取舍点在于「重排的代价」和「引用解析的代价」谁更贵。第三题的条件语句翻译四元式的优势会更明显因为跳转目标本质上就是一个可以后填的槽。3.3 布尔表达式与控制流回填为什么必须存在卷面最后一道题要翻译的是if x 0 and y 0 then z : x y else begin x : x 2; y : y 3 end卷面上x0和y0之间没有写连接词按最常见的理解是逻辑与并且是短路求值——x0为假时不应该再去算y0。这一点很重要如果y的求值有副作用或者会触发除零非短路翻译就是错的。翻译成四元式时会碰到一个经典的鸡生蛋问题生成(j, x, 0, ?)这条指令的时候你并不知道「真出口」在哪因为后面的代码还没翻译。教材上的标准解法是回填backpatching先填一个占位符比如 0把所有指向同一个未知目标的指令串成一条链等目标确定后一次性回填。100 (j, x, 0, 102) # x0 为真跳过短路跳转 101 (j, -, -, 106) # 短路x0 直接去 else 段 102 (j, y, 0, 104) # 两个条件都真去 then 段 103 (j, -, -, 106) 104 (, x, y, z) # then 段z : x y 105 (j, -, -, 109) # 跳过 else 段 106 (, x, 2, Tx) # else 段x : x 2 107 (, y, 3, y) # else 段y : y 3 108 (j, -, -, 109) 109 ... # if 语句之后的第一条看第 100、102、104 这三条条件的「真出口」直接写成后继指令编号是因为在这个例子里真出口恰好就是紧邻的下一条翻译时可以当场确定。真正需要回填的是第 101、103 这两条「假出口」——它们都要跳到 else 段的起点 106而 106 这个编号只有在 then 段全部翻译完之后才知道。短路求值的语义就藏在这两条无条件跳转里。如果没有 101x0时程序会顺序执行到 102 去算y0那就是非短路语义。这个差别在布尔表达式嵌套深的时候会被放大是「翻车」高发区。还有一个细节第 106 条我写的是(, x, 2, Tx)而不是(, x, 2, x)。这两种写法在真实编译器里都存在——前者引入新的临时变量赋值语义交给后续的寄存器分配后者直接覆盖更接近机器码。卷面上通常接受前者因为它保持了「一个临时变量只被定值一次」的性质这对后面做 SSA 化或者数据流分析更友好。顺序上还有一个容易忽略的点x : x 2和y : y 3必须严格按源码顺序生成不能因为两条指令互不依赖就调换。中间代码生成阶段不做重排重排是优化阶段的事而且必须经过依赖分析才能做。4. 二义性与 LL(1)文法性质的两端卷子中间两道大题一道要求证明文法有二义性并说出它描述的语言另一道要求算 First/Follow、证明是 LL(1)、构造预测分析表。这两道题看起来方向相反——一个说「这个文法不好」一个说「这个文法好」——但它们用的是同一套工具推导和 FIRST 集。4.1 二义性两条不同的推导就足够题目给的文法是这样的开始符号 NN → SE | E S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9要证明二义性标准做法是找到一个串给出两棵不同的语法树或者两条最左推导。这里的关键是E的产生式里那个10。先看整体结构S是左递归的S → SD | D它能生成任意长度的数字串D生成单个数字E生成一个「偶数结尾」。N → SE的含义是「一串数字 一个偶数结尾」N → E兜住了「整个串只有一个字符」的情况。所以这个文法想描述的语言是以偶数数字结尾的十进制数字串。二义性出在E → 10上。如果10被当成两个字符即产生1和0两个终结符那么E产生的串长度可以是 1也可以是 2。考虑串110推导一N ⇒ SE ⇒ DDE ⇒ 1DE ⇒ 11E ⇒ 110S展开成两个DE用一个字符0推导二N ⇒ SE ⇒ DE ⇒ 1E ⇒ 110S展开成一个DE用10两条推导产生的串完全相同但边界划分不同第一条把「11」给S、「0」给E第二条把「1」给S、「10」给E。两棵语法树不同二义性成立。这里有一个非常值得说的点二义性的定义是「存在某个串有两棵以上不同的语法树」它不要求所有串都有歧义。大部分串比如124只有一种划分但这不影响文法整体被判为二义。4.2 这个10到底该怎么读如果你把E → 0 | 2 | 4 | 6 | 8 | 10里的10理解成「教材上代表偶数的记号实际应为单个偶数数字」那么E只能产生一个字符S和E的边界就被长度唯一确定了N → SE生成的串长度至少 2最后一个字符归E其余全归S。这种情况下文法是无二义的语言仍然是「以偶数结尾的数字串」但二义性证明就无从下手——你无法构造出两条不同的推导。这是这类卷子最典型的「卷面歧义」题目本身在形式化上不严谨。处理方式不是猜出题人意图而是把两种解读都写清楚然后分别给出结论。真正搞懂机制的人在这种地方反而不会被扣分因为他展示的是「我看出了这个产生式的双重解释」。顺带说一句N → SE | E里的E分支其实是可以省掉的——N → SE在S取最短推导时也能生成两个字符的串但生成不了单字符。所以那个E分支的作用是兜住「整串只有一个数字」的边界情况。这类「为了覆盖边界而多加的一条产生式」正是文法变得难以分析的主要来源之一。4.3 二义性为什么不能靠改解析器救有人会想既然二义性是文法的问题那我写个解析器遇到分叉时按优先级选一条不就行了这个想法在工程上确实存在——很多手写解析器用「优先级爬升」或者「先算后判」的方式绕开文法层面的歧义。但它带来两个无法回避的后果。第一语义不再由文法定义而由解析器的实现细节定义。同一段源码换一个解析器甚至换一个版本就可能得到不同的语法树这对需要长期维护的语言是灾难。第二二义性会污染下游。语法树是后续所有阶段的输入如果树的结构不唯一那么类型检查、优化、代码生成全都失去了确定性基础。哪怕只有万分之一的分支不确定也没人敢在上面做激进的优化。所以工程上的正确做法是「改造文法消除二义性」而不是「在解析器里打补丁」。这也解释了为什么 LL(1)、LR(1) 这些文法类会被反复强调——它们把「无二义」写进了文法本身的约束条件里而不是留给实现去处理。4.4 First 集不动点迭代在算什么第二道文法题长这样E → T E E → E | ε T → F T T → T | ε F → P F F → *F | ε P → (E) | ^ | a | bFirst 集的定义是「非终结符能推导出的所有串的首终结符集合若可推导出空串则包含 ε」。计算的关键在于它可能是递归定义的First(T)依赖First(T)而First(T)又依赖First(F)First(F)依赖First(P)First(P)里有(E)又绕回First(E)。标准解法是迭代到不动点def compute_first(grammar, terminals): grammar: {A: [[B, C], [d], []]}空列表表示 ε 产生式 first {A: set() for A in grammar} changed True while changed: # 一直迭代到没有集合再变大 changed False for A, prods in grammar.items(): for prod in prods: if not prod: # A → ε if ε not in first[A]: first[A].add(ε); changed True continue nullable_prefix True for sym in prod: if sym in terminals: if sym not in first[A]: first[A].add(sym); changed True nullable_prefix False break else: # 非终结符吸收它的 First add first[sym] - {ε} if not add first[A]: first[A] | add; changed True if ε not in first[sym]: nullable_prefix False break if nullable_prefix and ε not in first[A]: first[A].add(ε); changed True return first按这个算法跑一遍结果是非终结符First 集E( ^ a bE εT( ^ a bT( ^ a b εF( ^ a bF* εP( ^ a b注意T的 First 集里既有四个首终结符又有 ε这是因为T → T | ε走两个分支都能成立。这个「同时含 ε 和普通终结符」的状态是后面判断 LL(1) 时的关键信号。4.5 Follow 集为什么需要「继承」和「传递」Follow 集回答的是另一个问题某个非终结符后面可能紧跟哪些终结符。它的计算依赖三条规则。第一条开始符号的 Follow 里必然有结束符$这里因为E后面还会跟)所以E的 Follow 是) $。第二条如果有产生式A → αBβ那么First(β) - {ε}全部进入Follow(B)。这是「继承」B后面紧跟的东西就是β能打头的东西。第三条如果β能推导出 ε或者β根本不存在即A → αB那么Follow(A)全部进入Follow(B)。这是「传递」B后面没有东西了那A后面跟什么B后面就跟什么。第三条规则是 Follow 集计算里最容易漏的。以本题为例T → F T中T在末尾所以Follow(T)要并入Follow(T)F → P F同理Follow(F)并入Follow(F)。算完的结果非终结符Follow 集E) $E) $T ) $T ) $F( ^ a b ) $F( ^ a b ) $P* ( ^ a b ) $F的 Follow 集里为什么会有(、^、a、b因为T → T而T展开成F TF后面跟的是TT的 First 集里包含那四个符号。这条链走通之后才能理解Follow 集不是「语法上紧邻的下一个字符」而是「所有可能的后继首字符」。4.6 LL(1) 判定与预测分析表LL(1) 的判定条件有两条缺一不可。第一条对同一个非终结符的任意两条不同产生式A → α和A → βFirst(α)和First(β)不能有交集。第二条如果α能推导出 ε那么First(β)不能和Follow(A)有交集。第二条的意义是当解析器看到当前输入符号时如果它既可能来自β的开头又可能是A结束后紧跟的符号那它就无法决定是展开β还是用A → ε收尾。这就是 LL(1) 里那个「1」的含义——只看一个向前看符号就必须能做出唯一决策。逐条检查本题E → E | εFirst(E) {}First(ε) {ε}不相交且{} ∩ Follow(E) {} ∩ {) $} ∅通过。T → T | εFirst(T) {( ^ a b}与{ε}不相交{( ^ a b} ∩ Follow(T) {( ^ a b} ∩ { ) $} ∅通过。F → *F | ε{*} ∩ Follow(F) {*} ∩ {( ^ a b ) $} ∅通过。P → (E) | ^ | a | b四条产生式的 First 集两两不相交通过。所以这个文法是 LL(1) 的。预测分析表按「A行、终结符列、格子里填产生式」的规则构造对每条A → α把α填进First(α)的每一列若α可推导 ε再把α填进Follow(A)的每一列。()^ab*$EE→TEE→TEE→TEE→TEEE→εE→EE→εTT→FTT→FTT→FTT→FTTT→TT→εT→TT→TT→TT→εT→εFF→PFF→PFF→PFF→PFFF→εF→εF→εF→εF→εF→εF→*FF→εPP→(E)P→^P→aP→b表里没有一格出现两条产生式这就是「无冲突」的具体含义。任何一个格子填了两条就说明这个文法不是 LL(1)必须做左公因子提取或者左递归消除。但这里有一个必须点出来的问题T → T这条产生式在语义上是不对的。正常的算术表达式文法里这一条应该是T → *F T | ε。写成T → T之后T可以推导出TT又推导出F T于是T能生成F F F ...这样一串并列的因子。按这张表去分析a b解析器会愉快地接受它——但a b在算术表达式的语境下根本不是合法输入。为什么表能建出来因为 LL(1) 检查的是「First 集不相交」而不是「语义正确」。T → T的 First 集是{( ^ a b}T → ε的贡献是 Follow 集{ ) $}两者确实不相交形式上完全合规。形式化方法能保证「分析过程确定」但不能保证「分析的东西是你想要的」。这是编译原理里一个深刻的取舍文法的形式性质LL(1)、无二义和文法的语义正确性是两个正交的维度。你可以写出一个完美 LL(1) 却毫无意义的文法也可以写出一个语义精确但没法用 LL(1) 分析的文法。卷面上这道题的字面答案是「本文还有配套的精品资源点击获取