简介：这份常州工学院编译原理试卷A（doc格式，55KB，共1个文件）面向计算机专业学生及备考编译原理课程的读者，用于检验词法分析、语法分析、语义分析与代码生成等核心章节的掌握程度。试卷内容覆盖正规表达式与最简DFA构造、逆波兰表示与三元式序列、文法二义性证明与语言描述、First集与Follow集计算、LL(1)文法判定及预测分析表构造，以及if-then-else语句的四元式翻译等典型题型，知识点分布完整，适合作为期末复习、自测与课堂练习的参考材料。目前已有391人学习下载，读者可借助这份试卷梳理编译原理各阶段的解题思路，对照题目查漏补缺，熟悉常见考点的出题形式与答题规范，为课程考试与后续深入学习打下基础。
1. 编译原理期末复盘：从正规式到四元式的完整知识地图
编译原理这门课，很多人复习到一半会发现一个尴尬的事实：词法分析、语法分析、语义分析、中间代码生成这几块，单看每一块都能说出点东西，但合上书就串不起来。这份试卷库把考点压在了五类题型上——正规表达式与最简DFA、逆波兰表示与四元式、文法二义性证明、LL(1)文法与预测分析表、控制语句的四元式翻译。梳理下来会发现，它其实是一条完整的流水线：先用正规式描述词法，再用文法描述语法，接着用First/Follow集和预测分析表做自顶向下分析，最后把语句翻译成四元式。适合正在系统复习编译原理、想拿一张能直接对着查漏补缺的地图的人。下面按这条流水线逐块拆。
2. 词法分析双件套：正规表达式构造与最简DFA的复习重点
词法分析是整条流水线的入口，试卷第一题30分全压在这里，说明它是性价比最高的复习模块。这一块的核心链路是：自然语言描述 → 正规表达式 → NFA → DFA → 最简DFA。很多人卡在第一步，不是不会画自动机，而是读不懂题目里那句中文到底在说什么。
2.1 从自然语言到正规表达式：两个典型题型的拆解
试卷给了两个小题，分别代表两种出题思路。
第一小题：字母表 {0,1} 上，不以 0 开头但以 11 结尾的所有字符串。拆解思路是分段拼接——开头部分、中间部分、结尾部分。不以0开头意味着首字符必须是1；以11结尾意味着最后两位固定是11；中间可以是任意01串。所以正规式写成：
1(0|1)*11这里有个容易翻车的地方：如果中间部分写成(0|1)*，那字符串111会被匹配吗？会——首字符1，中间空串，结尾11，合起来就是111，正确。但字符串11呢？首字符1，中间空串，结尾11，需要三个1，所以11不匹配，这也符合“以11结尾且不以0开头”的定义吗？11确实不以0开头且以11结尾，应该被包含。问题出在首字符1和结尾11共用了同一个1。修正方式是让中间部分允许为空但首字符和结尾不重叠：
1(0|1)*11 | 11或者更简洁地写成1(0|1)*11并单独处理长度为2的情况。梳理下来会发现，这类题最容易漏的就是“最短字符串”的边界情况。
第二小题：包含01子串的所有字符串。这个相对直接，用(0|1)*01(0|1)*就能覆盖。但要注意“包含”意味着01可以在任意位置，前后都可以有任意字符。
2.2 NFA到DFA再到最简DFA：子集构造法与化简的实操要点
拿到正规式之后，构造等价DFA的标准路径是：正规式 → NFA（Thompson构造法）→ DFA（子集构造法）→ 最简DFA（Hopcroft或填表化简法）。
子集构造法的关键是维护一个状态集合的集合，每个DFA状态对应NFA状态的一个子集。实际操作中，最容易出错的是ε闭包的计算——每次求move(S, a)之后，必须再对结果求一次ε闭包。漏掉这一步，DFA就会少状态。
最简DFA的化简用填表法比较稳：先画一个下三角表，标记所有“一个终态一个非终态”的状态对为可区分；然后迭代，如果两个状态在某个输入下转移到已标记可区分的状态对，则它们也可区分；最后剩下的不可区分状态对就可以合并。
注意：最简DFA的“最简”是指状态数最少，不是指边最少。合并状态时，终态只能和终态合并，非终态只能和非终态合并。
这一块的复习建议是：拿三道题手算一遍，每道题都从正规式写到最简DFA，中间不要跳步。跳步的人考场上会在ε闭包那里卡住。
3. 语法分析核心战场：二义性证明、First/Follow集与LL(1)预测分析表
语法分析是编译原理试卷里分值最重、也最容易拉开差距的部分。这份试卷里，二义性证明占20分，LL(1)相关占25分，加起来45分，几乎半壁江山。这两块的知识点其实是连着的：二义性说明文法不能用自顶向下或自底向上的确定性方法分析，而LL(1)文法则是一种保证无二义、可确定性自顶向下分析的文法类型。
3.1 文法二义性证明：找两棵不同的语法树
试卷给的文法G（开始符号N）是这样的：
N → SE | E S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9证明二义性的标准做法是：找到一个句子，它能对应两棵不同的语法分析树（或两个不同的最左推导）。对于这个文法，关键观察是N可以推导出SE或E，而S又可以推导出SD或D。这意味着一个数字串可能通过不同的路径生成。
比如句子10，既可以走 N→E→10，也可以走 N→SE→DE→10（S→D→1，E→0）。两条路径对应两棵不同的树，二义性得证。
第二问“此文法所描述的语言是什么”，需要从文法规则反推。E生成偶数（0,2,4,6,8,10），D生成单个数字（0-9），S生成一个或多个数字的序列（因为S→SD|D，递归地在右边追加数字），N生成SE或E。合起来看，这个文法描述的是所有非空数字串，但有一个限制：最后一个数字必须是偶数。因为N→SE中E是偶数结尾，N→E也是偶数结尾。所以语言是：所有以偶数结尾的非空数字串。
注意：证明二义性时，一定要写出两个完整的推导过程或画出两棵树，不能只说“显然有两条路径”。阅卷时只看具体推导。
3.2 First集与Follow集：计算规则和三个高频错误
试卷第四题给的文法G是：
E → TE' E' → +E | ε T → FT' T' → T | ε F → PF' F' → *F' | ε P → (E) | ^ | a | b计算First集和Follow集是LL(1)分析的基础。First集的计算规则是：对于产生式A→α，First(A)包含First(α)；如果α能推导出ε，则ε也加入First(A)。Follow集的计算规则是：对于产生式A→αBβ，Follow(B)包含First(β)-{ε}；如果β能推导出ε，则Follow(B)包含Follow(A)。
这个文法的First集和Follow集整理如下：
| 非终结符 | First集 | Follow集 |
|---|---|---|
| E | {(, ^, a, b} | {), #} |
| E' | {+, ε} | {), #} |
| T | {(, ^, a, b} | {+, ), #} |
| T' | {(, ^, a, b, ε} | {+, ), #} |
| F | {(, ^, a, b} | {+, ), #} |
| F' | {*, ε} | {+, ), #} |
| P | {(, ^, a, b} | {*, +, ), #} |
三个高频错误：第一，忘记把ε加入First集，尤其是E'、T'、F'这些含ε产生式的非终结符；第二，Follow集计算时忘记处理β能推导ε的情况，导致Follow没有传递；第三，开始符号的Follow集忘记加#。
3.3 LL(1)文法判定与预测分析表构造
证明文法是LL(1)的条件是：对于每个非终结符A的任意两个不同产生式A→α和A→β，满足First(α) ∩ First(β) = ∅；如果β能推导ε，则First(α) ∩ Follow(A) = ∅。
对于这个文法，检查E'的两个产生式：E'→+E的First是{+}，E'→ε的First是{ε}，而Follow(E')={), #}，{+} ∩ {), #} = ∅，满足。T'的两个产生式T'→T和T'→ε，First(T)={(, ^, a, b}，First(ε)={ε}，Follow(T')={+, ), #}，{(, ^, a, b} ∩ {+, ), #} = ∅，满足。F'同理。所以文法是LL(1)的。
预测分析表的构造：行是非终结符，列是终结符和#。对于每个产生式A→α，对每个a∈First(α)，在M[A, a]填入A→α；如果ε∈First(α)，则对每个b∈Follow(A)，在M[A, b]填入A→α。
构造出来的表里，E行在(、^、a、b列都填E→TE'；E'行在+列填E'→+E，在)和#列填E'→ε；T行在(、^、a、b列填T→FT'；T'行在(、^、a、b列填T'→T，在+、)、#列填T'→ε；F行在(、^、a、b列填F→PF'；F'行在列填F'→F'，在+、)、#列填F'→ε；P行在(列填P→(E)，在^列填P→^，在a列填P→a，在b列填P→b。
注意：预测分析表里每个单元格最多只能有一个产生式，如果有多个，说明文法不是LL(1)的。检查时重点看含ε产生式的非终结符，它们的Follow集和别的产生式的First集有没有交集。
4. 中间代码生成：逆波兰表示与四元式序列的翻译套路
中间代码生成是编译原理里最“工程化”的一块，试卷里占了25分（逆波兰+四元式10分，控制语句四元式15分）。这块的复习方法和前面不同——前面靠理解，这块靠熟练。因为翻译规则是固定的，练多了就是肌肉记忆。
4.1 逆波兰表示：运算符优先级与栈的配合
试卷要求写出A+B*(C-D)+E/(C-D)的逆波兰表示。逆波兰表示就是后缀表达式，转换规则是：遇到操作数直接输出，遇到运算符则与栈顶运算符比较优先级，如果栈顶优先级不低于当前运算符，就弹出栈顶输出，直到栈顶优先级低于当前运算符或栈为空，然后当前运算符入栈。
对于这个表达式，逐步转换的结果是：
A B C D - * + E C D - / +验证方式是用栈求值：从左到右扫描，遇到操作数入栈，遇到运算符弹出两个操作数计算后入栈。最终栈里只剩一个值，说明表达式合法。
这里最容易错的地方是括号的处理。左括号直接入栈，右括号则弹出栈顶直到遇到左括号，左括号弹出但不输出。很多人会把左括号也输出到后缀表达式里，这是错的。
4.2 四元式序列：从表达式到控制流的翻译
四元式的一般形式是(op, arg1, arg2, result)。对于表达式A+B*(C-D)+E/(C-D)，四元式序列如下：
(+, C, D, T1) // T1 = C - D 实际是减法，这里应为(-, C, D, T1) (*, B, T1, T2) // T2 = B * T1 (+, A, T2, T3) // T3 = A + T2 (-, C, D, T4) // T4 = C - D (/, E, T4, T5) // T5 = E / T4 (+, T3, T5, T6) // T6 = T3 + T5注意第一个四元式应该是减法(-, C, D, T1)，上面写+是笔误。四元式的关键是临时变量的分配和运算顺序——先算括号里的，再算乘除，最后算加减。
对于控制语句if x>0 y>0 then z:=x+y else begin x:=x+2; y:=y+3 end，四元式翻译需要用到标号和跳转：
(>, x, 0, T1) // T1 = x > 0 (>, y, 0, T2) // T2 = y > 0 (and, T1, T2, T3) // T3 = T1 and T2 (j=, T3, 0, 5) // 如果T3为假，跳转到第5条 (+, x, y, T4) // T4 = x + y (:=, T4, _, z) // z = T4 (j, _, _, 9) // 无条件跳转到第9条 (+, x, 2, T5) // T5 = x + 2 (:=, T5, _, x) // x = T5 (+, y, 3, T6) // T6 = y + 3 (:=, T6, _, y) // y = T6这里的关键是回填技术——在生成跳转指令时，目标标号可能还不知道，需要留空后续回填。考试时如果不需要回填，直接写标号即可。
注意：四元式的标号从1开始还是从100开始，不同教材不一样。试卷里没有明确要求，按自己习惯来，但同一题内要统一。
5. 易错点集中排查：这五处最容易丢分
复习到后期，知识点都过了一遍，但考场上丢分往往不是因为不会，而是因为踩了固定的坑。梳理下来，这份试卷涉及的内容里有五个地方最容易翻车。
易漏点一：正规式构造时忽略最短字符串。为什么漏？因为习惯性地写1(0|1)*11，觉得已经覆盖了所有情况，但忘了11这种首尾重叠的短串。怎么补？写完正规式后，手动枚举长度最短的几个字符串，逐个验证是否被覆盖。
易漏点二：子集构造法忘记ε闭包。为什么漏？因为move操作很直观，而ε闭包容易被当成“已经处理过了”。怎么补？每次求完move(S, a)之后，强制自己再写一步ε-closure(move(S, a))，养成条件反射。
易漏点三：Follow集计算时忘记传递。为什么漏？因为Follow的规则比First多一层——当β能推导ε时，Follow(A)要全部加入Follow(B)。很多人只处理了First(β)的情况。怎么补？对每个产生式，先判断β是否含ε，含的话单独处理传递。
易漏点四：预测分析表多个产生式冲突时不会判断。为什么漏？因为LL(1)的判定条件背了但没真正用过。怎么补？构造完表后，逐行检查每个非终结符的每个终结符列，如果有两个产生式，回去看First集和Follow集是否真的相交。
易漏点五：四元式翻译时跳转标号写错。为什么漏？因为控制流的跳转目标需要数行号，数着数着就乱了。怎么补？先给每条四元式编号，再写跳转，跳转指令的目标写编号而不是“下一行”。写完后再从头核对一遍。
6. 考前查漏补缺：一份可执行的复习清单
最后一章落到具体怎么查漏补缺。编译原理这门课，光看不动手，考场上一定卡壳。下面这份清单是按题型组织的，每一条都对应一个可执行的动作，不是泛泛的“复习XX”。
| 题型 | 自查动作 | 合格标准 |
|---|---|---|
| 正规式与DFA | 拿3道题，从正规式手写到最简DFA | 不跳步，ε闭包每步都写 |
| 逆波兰表示 | 拿5个含括号的表达式，手写后缀式 | 括号处理正确，栈操作不跳 |
| 二义性证明 | 找2个文法，各找2个二义句子 | 能画出两棵不同的树 |
| First/Follow集 | 拿3个含ε产生式的文法，手算 | 全对，尤其是Follow传递 |
| LL(1)判定与预测表 | 拿2个文法，判定并构造表 | 表中无冲突单元格 |
| 四元式翻译 | 拿3个if-then-else语句，手写四元式 | 跳转标号正确，回填逻辑清晰 |
具体执行时，建议按“先手算再对答案”的顺序。手算的时候不要翻书，算完再对照教材或笔记检查。错的地方用红笔标出来，第二天再算一遍同样的题。如果第二遍还错，说明不是粗心，是知识点没吃透，回去看对应的章节。
还有一个技巧：把最容易混的几个概念做成一张对比卡。比如NFA和DFA的区别、First集和Follow集的区别、逆波兰和四元式的区别。考前最后一天只看这张卡，不翻书。
提示：如果时间只够复习一块，优先复习LL(1)相关。因为First/Follow集、预测分析表、LL(1)判定这三块是连着的，复习一块等于复习三块，性价比最高。
从那以后我每次复习编译原理，都强制自己先手写一遍完整流程——从正规式到DFA，从文法到预测表，从表达式到四元式——不跳任何一步。跳步的人考场上会在最基础的地方翻车，而编译原理的分数，恰恰就藏在这些基础步骤里。希望帮到你。
本文还有配套的精品资源，点击获取
