预测分析与四元式生成)
简介：常州工学院编译原理试卷A是一份覆盖编译原理核心考点的期末真题，面向该校计算机专业学生及考研复习者。试卷聚焦词法分析、语法分析与中间代码生成等关键模块，包含正规表达式与最简DFA构造、逆波兰表示转换、文法二义性证明、First集与Follow集计算、LL(1)文法判定与预测分析表构建，以及条件语句的四元式序列翻译，适合考前自测与题型训练。资源为1个doc文档，压缩包仅55KB，内容为完整卷面，含试卷头、装订线等真实版式，可直接打印或导入笔记软件使用。目前已有391人学习，是快速熟悉常州工学院编译原理出题风格的高性价比资料。通过研读本卷并动手重做每道大题，可有效串联词法规则描述、语法分析表构造和中间代码生成流程，帮助查漏补缺、强化应试能力。
1. 编译原理试卷复盘：从正规式到四元式的考点串联
如果你正在啃编译原理，或者处在考研、期末的冲刺阶段，刷题是最能暴露真实水平的校验方式。这份试卷没有停留在概念背诵，而是把词法分析（正规式、最简 DFA）、语法分析（文法二义性、LL(1) 预测分析表）和中间代码生成（逆波兰、四元式）串成了一条完整的编译流水线。它适合三类人：一是考研想自测薄弱环节的同学；二是教学中用来当模拟卷的；三是想通过具体题目反推编译器工作过程的开发者。它解决的问题很直接——看书觉得自己懂了，做题发现根本无从下笔，尤其在一堆推导规则和跳转地址面前犯迷糊。
2. 正规表达式构造与最简 DFA：先定状态再谈优化
这章聚焦试卷第一道大题：为特定字符串集合构造正规表达式，并画出等价的最简 DFA。这是词法分析的核心基本功，也是后面自动生成词法分析器的理论前提。
2.1 第一题正解：不以 0 开头但以 11 结尾
先看题目要求：字母表 {0,1} 上，不以 0 开头但以 11 结尾的所有字符串。
这类题很容易踩进“先写正则再画图”的惯性里，但更稳的做法是先想清楚字符串的结构。不以 0 开头，意味着第一个字符只能是 1；以 11 结尾，意味着末尾必须是连续的两个 1。那么整体结构就是：第一个字符1+ 中间任意长度的 {0,1} 串 + 末尾11。中间部分可以为空，所以正规式可以写成：
1(0|1)*11但这里有个隐蔽的坑：如果字符串本身就是11，它满足“以 11 结尾”，但中间部分是空串，上面的式子能匹配。可如果你最开始写成1(0|1)*?11这种带非贪婪的写法，反而会把问题复杂化。词法分析器用的是正则表达式代数，非贪婪在这里会引入歧义。
根据这个正规式构造 NFA，再用子集构造法转 DFA，最后做最小化。我一般不会手搓最小化算法，而是直接写一段 Python 来验证等价性，常见做法是构造出 DFA 之后，对所有状态做可达性遍历，再合并等价状态。这里给出一个验证用的纯 Python 脚本，不依赖第三方库：
def simulate_dfa(transition, start, accept, word): state = start for ch in word: if ch not in transition.get(state, {}): return False state = transition[state][ch] return state in accept # 手工推导后得到的最简 DFA # 状态 0 是起始状态，状态 1 表示“已读入开头 1”，状态 2 表示“已读入第一个 1 且正在积累中间串” # 状态 3 是接受状态（已经看到 11 结尾） trans = { 0: {'1': 1}, 1: {'0': 1, '1': 2}, 2: {'0': 1, '1': 3}, 3: {'0': 1, '1': 3}, } start = 0 accept = {3} # 自测用例 cases = { "11": True, "111": True, "1011": True, "00011": False, # 以 0 开头 "110": False, # 不以 11 结尾 "1": False, } for w, expected in cases.items(): result = simulate_dfa(trans, start, accept, w) print(f"{w}: {result}, expected {expected}")逻辑说明：状态转移表里，状态 0 只读入 1 进入状态 1，这就从源头拒绝了以 0 开头的字符串。状态 1 遇到 0 还是留在状态 1，因为中间部分可以任意长；遇到 1 则进入状态 2。状态 2 再遇到 1 就进入终态 3，如果继续读入 0 说明末尾不是 11，要回到状态 1 重新积累。参数说明：transition字典的 key 是当前状态，value 是字符到下一状态的映射。start和accept需要根据你自己推导的状态图调整，这段脚本的目的是让你在考试估算完状态图之后，还有一次机械的验证机会。
2.2 第二题正解：包含 01 子串的所有字符串
这个条件翻译成正则表达式，最直观的写法是(0|1)*01(0|1)*。因为“包含 01 子串”等价于在任意位置之前和之后各接一个任意串。
构造 DFA 时，核心是记录“已经看到了几位 01 前缀”。起始状态读入 0 进入中间状态，读入 1 则留在原地，因为 1 不可能是 01 结构的开头。一旦在中间状态读到 1，立刻进入接受状态；此后无论读什么，都继续留在接受状态。
这里有一个易错点：很多人在初始状态读到 0 时，会错误地转移到中间状态，却又在中间状态读到 0 时回到初始状态。这在大多数情况下是对的，但要注意，如果字符串是001，你在初始状态读到 0 进入中间，再读 0 如果回到初始，就会漏掉这个已经看到的 0。正确做法是中间状态读 0 仍然留在中间，因为单个 0 已经满足 01 的前缀，再来一个 0 并不会破坏这个前缀。
验证脚本与上面类似，只需要改变状态转移表：
trans2 = { 0: {'0': 1, '1': 0}, 1: {'0': 1, '1': 2}, 2: {'0': 2, '1': 2}, } start2 = 0 accept2 = {2} check_cases = { "01": True, "001": True, "01010": True, "111000": False, "0": False, } for w, expected in check_cases.items(): print(f"{w}: {simulate_dfa(trans2, start2, accept2, w)}, expected {expected}")参数说明：这里的trans2就是第二个 DFA 的完整状态登记表。状态 0 是起始，状态 1 是看到了0前缀，状态 2 是终态。实际考试中，你只需要画出状态图，不需要真的跑代码，但养成“画完之后假想几个边界输入走一圈”的习惯，能拦截大部分丢分。
3. LL(1) 文法判定与预测分析表：从 First、Follow 到无冲突推导
这章对应试卷第三、四题。二义性证明考的是对推导树的理解，LL(1) 分析表考的是 FIRST 集和 FOLLOW 集的计算边界。把这两个题吃透，语法分析的自顶向下部分基本就稳了。
3.1 证明文法二义性：找到两个不同的最左推导
题目已知文法 G，开始符号为 N：
N -> S E | E S S -> S D | D E -> 0|2|4|6|8|10 D -> 0|1|2|3|4|5|6|7|8|9证明二义性最直接的方法，就是找到一个字符串，它能对应两个不同的最左推导。我通常先从终结符的组合规律入手。这里注意 E 可以是数字 0、2、4、6、8，也可以是两位数 10，D 是单个数字。
考虑字符串020。 第一个最左推导是：
N -> S E -> S D E -> D D E -> 0 2 0即先展开 S 产生第一个数字，再让 S 派生出一个额外的 D，最后 E 补上末尾数字。 第二个最左推导是：
N -> E S -> E S D -> E D D -> 0 2 0这里先用 E 产生开头 0，S 派生成长度为 2 的串20，因为 S 可以展开成 S D，最终 D D 得到 2 和 0。
因为同一个终结符串020对应两个不同的最左推导，说明文法 G 存在二义性。这道题的得分点在于：不要只写“存在两种语法树”，必须把两个推导序列完整列出来。
那么这文法描述的语言是什么？观察发现，S 产生一个非空数字串，E 产生一个偶数（0、2、4、6、8 或 10）。N 把 S 和 E 拼接起来，顺序交换都可以。所以它描述的语言是“一个非空数字串后跟一个偶数，或一个偶数后跟一个非空数字串”。更精确地说，是所有由数字组成的、其中一部分可以是两位整数 10、且整体由两部分拼接起来的字符串。
3.2 计算 First 集和 Follow 集：按依赖链逐层展开
第二个重点题是求出给定文法每个非终结符的 FIRST 集和 FOLLOW 集，并证明是 LL(1) 文法。题目文法为：
E -> T E' E' -> + E | ε T -> F T' T' -> T | ε F -> P F' F' -> * F' | ε P -> ( E ) | ^ | a | b计算 FIRST 集要从最底层的 P 往上推。P 有三个候选式，所以 FIRST(P) = { (, ^, a, b }。F 产生 P F'，因此 FIRST(F) 也等于 { (, ^, a, b }。T 同理，FIRST(T) = { (, ^, a, b }。E 也是同样的集合。对于带 ε 的候选式，E' 的 FIRST 是 { +, ε }，T' 的 FIRST 是 FIRST(T) ∪ { ε }，也就是 { (, ^, a, b, ε }，F' 的 FIRST 是 { *, ε }。
FOLLOW 集的计算要格外小心三条规则：开始符号的 FOLLOW 一定包含 $；A->αBβ 时，FOLLOW(B) 要并入 FIRST(β) 去掉 ε；A->αB 或 A->αBβ 且 β 能推导出 ε 时，FOLLOW(B) 并入 FOLLOW(A)。
FOLLOW(E) 包含 $ 和右括号 )，因为 P->(E)。E' 后面紧跟 E 的 FOLLOW，所以 FOLLOW(E') 也是 { $, ) }。T 出现在 E 的候选式 T E' 中，它后面跟着 E'，E' 能推导出 ε，因此 FOLLOW(T) 需要并入 FOLLOW(E) 以及 FIRST(E') 去掉 ε 后的 { + }，最终是 { $, ), + }。T' 的 FOLLOW 跟 T 一样。
我把计算结果整理成一张表，方便考试时快速对照：
| 非终结符 | FIRST 集 | FOLLOW 集 |
|---|---|---|
| E | { (, ^, a, b } | { $, ) } |
| E' | { +, ε } | { $, ) } |
| T | { (, ^, a, b } | { $, ), + } |
| T' | { (, ^, a, b, ε } | { $, ), + } |
| F | { (, ^, a, b } | { $, ), +, (, ^, a, b } |
| F' | { *, ε } | { $, ), +, (, ^, a, b } |
| P | { (, ^, a, b } | { $, ), +, (, ^, a, b, * } |
注意 F 和 P 的 FOLLOW 集里会带上 FIRST 集里的内容，这是因为 T' 和 F' 都可能推导出 ε，导致 F 后面直接跟 T 或 E 的后继符号。很多同学在这里漏项，我一般会写一个小脚本用迭代法核对 FOLLOW 集，但卷面上只需要写出最终结果。
3.3 构造预测分析表并确认无冲突
证明 LL(1) 的关键，在于检查每个产生式选择分支的 FIRST 集和 FOLLOW 集是否冲突。以 E' 为例，它的候选式有 +E 和 ε。当输入符号是 + 时，选择 +E；当输入符号是 ) 或 $ 时，选择 ε。因为 FIRST(+E) 和 FOLLOW(E') 交集为空，所以无冲突。
构造预测分析表时，规则是：对产生式 A->α，把 A->α 填到 FIRST(α) 中每个终结符对应的表格位置；如果 α 能推导出 ε，则把 A->α 填到 FOLLOW(A) 中每个终结符对应的位置。
这个文法的预测分析表核心部分如下：
| 非终结符 | + | * | ( | ) | a/b/^ | $ |
|---|---|---|---|---|---|---|
| E | E->TE' | E->TE' | ||||
| E' | E'->+E | E'->ε | E'->ε | |||
| T | T->FT' | T->FT' | ||||
| T' | T'->ε | T'->T | T'->ε | T'->T | T'->ε | |
| F | F->PF' | F->PF' | ||||
| F' | F'->ε | F'->*F' | F'->ε | F'->ε | F'->ε | F'->ε |
| P | P->(E) | P->a/b/^ |
表格中每个单元格有且只有一个产生式，这就是 LL(1) 文法的定义。如果某个格子出现了两个产生式，就需要消除左递归或提取左因子。
4. 常见避坑指南：中间代码生成的 5 条血泪经验
中间代码生成部分，包含逆波兰（后缀表达式）和四元式序列，是很多人的丢分重灾区。这章就聊几个我在这类题目上见过的高频翻车现场，每条都按“现象→原因→解决”来拆。
4.1 逆波兰转写时丢失运算符优先级
现象：把 A+B*(C-D)+E/(C-D) 转后缀，写成 ABCD-*+ECD-/ +，结果运算顺序出错。
原因：做后缀转换时没有始终盯着运算符栈，处理到第二个 + 和末尾的 / 时，没有把栈内优先级更高的运算符先弹出去。
解决：严格模拟运算符栈操作，遇到右括号就一直弹出栈顶运算符直到左括号；遇到优先级低于栈顶的运算符，先弹出栈顶再入栈。最终得到的结果应该是：
A B C D - * + E C D - / +验证方法是把后缀式重新用栈模拟一遍：遇到操作数压栈，遇到运算符弹出两个操作数计算，再压回。只要模拟过程和平时的中缀求值顺序一致，就是对的。
4.2 四元式临时变量编号混乱
现象：写四元式时临时变量 T1、T2 跳来跳去，后面引用时对不上。
原因：没有养成“每生成一个中间结果就立刻分配一个新临时变量”的习惯。很多人喜欢复用 T1，结果把前一个值覆盖掉。
解决：按顺序递增临时变量编号，表达式 A+B*(C-D)+E/(C-D) 的四元式序列应该是：
( -, C, D, T1 ) ( *, B, T1, T2 ) ( +, A, T2, T3 ) ( -, C, D, T4 ) ( /, E, T4, T5 ) ( +, T3, T5, T6 )注意中间的每个二元运算都对应一个新临时变量，即使 C-D 重复出现，也要用一个新编号 T4 重新计算，因为编译器的标准做法是不做冗余表达式消除时的逐次翻译。
4.3 条件语句四元式跳转地址没有回填
现象：把 if 语句翻译成四元式时，跳转指令的目标地址一开始不知道，就随手写死一个，最后和实际代码块错位。
原因：没有理解回填技术。条件语句的跳转目标是后面才确定的，翻译过程中需要先保留占位，再后续补充。
解决：经典做法是先写成带编号的顺次指令，跳转的目标用一个待填标签表示。对于题目中的 if x>0 and y>0 then z＝x＋y else x＝x+2; y＝y+3，我先写出各分支的代码块，再填充跳转地址：
100: (j>, x, 0, 104) # x>0 为真，则进入 then 块 101: (j, _, _, 107) # 否则进入 else 块 102: (j>, y, 0, 104) # y>0 为真，则进入 then 块 103: (j, _, _, 107) # 否则进入 else 块 104: (+, x, y, T1) # then 块：z=x+y 105: (=, T1, _, z) 106: (j, _, _, 110) # then 执行完，跳过 else 块 107: (+, x, 2, T2) # else 块：x=x+2 108: (=, T2, _, x) 109: (+, y, 3, T3) # y=y+3 110: (=, T3, _, y)参数说明：j> 是一元条件跳转，后面跟两个操作数和目标行号；j 是无条件跳转。回填是指先把 106 这样的地址留空，等 else 块的长度确定后再写上 110。
4.4 把 10 当成两个字符处理
现象：第三题里 E->0|2|4|6|8|10，很多人在推导二义性时把 10 拆成 1 和 0，导致推导序列凭空多出几步。
原因：没有注意 10 是文法的终结符整体，它代表十进制整数 10，不是字符 ‘1’ 跟 ‘0’。
解决：遇到这种题目，先把所有终结符圈出来。10 作为一个整体终结符，不能在推导过程中拆开。二义性证明中我用到的020字符串，就是刻意避免出现 10 这个终结符，省得绕进终结符内部的细节。
4.5 FIRST 集计算时把 ε 漏掉
现象：计算 T' 的 FIRST 集时写成 { (, ^, a, b }，忘记 T'->ε，后面判断 LL(1) 时误以为冲突。
原因：看到 T'->T 就很兴奋，忽略了另一个候选式 ε。
解决：凡是右边是 ε 的产生式，必须把 ε 计入 FIRST 集。如果不确定，就按依赖链从最底层逐层标出所有能推导出 ε 的非终结符。这里的 E'、T'、F' 都能推导出 ε，它们对应的 FIRST 集全部要包含 ε。
5. 用这套试卷做“体检”：验证 DFA 最小化和 LL(1) 表的一小时自查法
到了最后，说一个我每次复习编译原理都会用的具体技巧：把试卷当体检表，用一小时做三轮对照自查。
第一轮做闭卷限时。只给自己 60 分钟，把正规式、DFA、FIRST/FOLLOW、预测分析表和四元式全部写一遍。写完先不对答案，而是用自己的验证逻辑走一遍。比如 DFA 部分，不要只盯着状态图看，而是要挑几个边界输入走一遍转移路径。如果状态图丢了，可以用前面那种纯 Python 的表驱动模拟器现场建表，但我更推荐纸面上画出转移矩阵，因为考试时你面对的就是一张白纸。
第二轮对照标准答案，重点看每个“我以为会但没写”的部分。编译原理的题目设计往往非常刁钻：一个不以 0 开头的约束，就要在起始状态上多画一条自环；一个包含 01 子串的条件，就要多设计一个中间状态。如果发现自己漏状态，不要急着改图，先回看正规表达式，检查是不是把连接和闭包的关系搞混了。
第三轮是反向验证预测分析表。我会把预测分析表当成一个模拟器来用，拿一个输入串，比如a+a，从 E 开始，手写栈的每一步。栈顶是 E，输入是 a，查表应该是 E->TE'，于是弹掉 E，压入 E' T。接着再看 T，继续查表展开。这个过程能暴露出很多查表时忽视的冲突点，比如 T' 在遇到 a 时应该选 T'->T 而不是误填入 ε。
最后说一个我从这套题里学到的硬核习惯：如果一个文法的 FIRST 和 FOLLOW 集算完发现有交集，比如 FIRST(A) 和 FOLLOW(A) 都包含同一个终结符，那它不是 LL(1)，不要硬造预测分析表。唯一能做的就是把文法改写，提取左因子或者引入新的非终结符，而不是在表里塞两个产生式假装无冲突。从那以后，我每次做完文法分析题，都强制自己重算一遍 FIRST 和 FOLLOW，再检查交集，最后才去填表，这个顺序一次都没乱过。希望帮到你。
本文还有配套的精品资源，点击获取
