企业官网建设流程全解析

简介：这份常州工学院编译原理试卷A（doc格式，压缩包约55KB，共1个文件）面向高校计算机专业学生及备考编译原理课程的读者，用于检验和巩固课程核心知识点。试卷内容覆盖正规表达式与有限自动机、逆波兰表示、文法二义性证明、LL(1)文法与预测分析表构造，以及if-then-else语句的四元式翻译等典型题型，并配有具体题目与分值分布，便于自测与查漏补缺。资源以单一doc文档呈现，结构清晰，可直接打印或在线练习。目前已有391人学习下载，适合需要系统复习编译原理、熟悉考试题型与解题思路的学生使用，也可作为教师命题参考。

1. 从一张期末卷看编译原理到底考什么：正规式、LL(1) 与四元式才是拿分主力

编译原理这门课，很多人复习到后期会有一种“玄学”感：平时作业会做，一到卷面就翻车。翻车点往往不在概念背没背，而在形式化推导的步骤是否写全、是否踩中判分点。这份试卷库把考点摊得很直白：正规表达式与最简 DFA、逆波兰与四元式、文法二义性、First/Follow 集与预测分析表、条件语句翻译。整张卷子 100 分里，光正规式加 DFA 就占 30 分，LL(1) 相关占 25 分，四元式序列占 25 分——也就是说，这三块拿稳，及格线基本就踩住了。它适合正在刷期末真题、准备课程补考，或者想用一套卷子把词法、语法、语义、代码生成串起来的人。下面按考点模块拆开讲，每块都配真题答法和易错点。

2. 正规表达式与最简 DFA：30 分的大题怎么一步步拿满

2.1 真题拆解：不以 0 开头但以 11 结尾的串

题目要求在字母表 {0,1} 上，写出所有不以 0 开头、但以 11 结尾的字符串的正规表达式，并构造等价的最简 DFA。这类题通常分两步给分：正规式写对拿一部分，DFA 状态最简再拿一部分。

先分析语言结构。不以 0 开头，意味着首字符只能是 1；以 11 结尾，意味着最后两位固定是 11。中间部分可以是任意 0/1 串。所以正规式可以写成：

1 (0|1)* 1 1

注意这里不能写成1(0|1)*11就完事，还要检查是否覆盖了“长度恰好为 2 的串 11”。当(0|1)*取空串时，1 11得到111，而11本身呢？11首字符是 1，末两位是 11，但它只有两位，中间部分为空，正规式1(0|1)*11展开后最短是111，漏掉了11。所以更严谨的写法是：

11 | 1(0|1)*11

或者等价地写成1(1|0(0|1)*1)?1这类形式。判卷时，只要语言描述正确、能覆盖11和111等边界串，通常都给分。

构造 DFA 时，建议按“首字符校验 → 中间任意 → 末尾匹配 11”三段式设计状态：

• q0：初态，读入 1 转到 q1，读入 0 则进入死状态（因为不能以 0 开头）。
• q1：已经合法开头，读 0 或 1 都留在 q1（中间任意），但一旦读到连续的 1 要记录进度。
• q2：刚读到一个 1，可能是结尾 11 的第一位。
• q3：已经读到 11，接受态。
• 死状态：任何非法输入进入后不再离开。

最简化的关键是把“中间任意”和“末尾匹配”合并考虑。常见做法是设四个有效状态加一个死状态，然后用划分法或填表法合并等价状态。很多同学在这里丢分，是因为死状态没画，或者接受态和中间态混在一起，导致 DFA 接受非法串。

2.2 真题拆解：包含 01 子串的所有串

第二小题 12 分，要求写出包含01子串的所有二进制串的正规表达式。这个相对直接：

(0|1)* 01 (0|1)*

构造 DFA 时，状态可以设计为：

• q0：还没遇到 0，读 0 转到 q1，读 1 留在 q0。
• q1：已经遇到 0 但还没遇到 01，读 0 留在 q1，读 1 转到 q2。
• q2：已经包含 01，接受态，读 0 或 1 都留在 q2。

这个 DFA 只有三个状态，已经是最简。判分点在于：q2 必须是接受态且自环，表示一旦包含 01，后面任意字符都不影响接受性。

2.3 易错点：正规式写对但 DFA 画错

这类题最常见的失分不是不会，而是细节翻车：

• 漏掉空串或最短串。比如第一题漏掉11，第二题漏掉01本身。
• DFA 没有死状态。不以 0 开头的语言，读入 0 必须进入死状态，否则会接受非法串。
• 最简 DFA 没有真正化简。有些同学画了五六个状态就交卷，其实可以合并到三四个。
• 接受态标记错误。包含 01 的串，一旦进入接受态就应永远接受，不能因为后续字符跳出。

提示：DFA 最简化的判分很看过程，建议在卷面上写出“初始 DFA → 划分等价类 → 最简 DFA”三步，即使最后状态图有小错，过程分也能拿到。

3. 逆波兰、四元式与二义性：中间代码和文法分析的得分套路

3.1 逆波兰表示与四元式序列

题目要求写出A+B*(C-D)+E/(C-D)的逆波兰表示及四元式序列。逆波兰表示就是后缀表达式，按运算符优先级和括号展开：

A B C D - * + E C D - / +

四元式序列则要把每一步运算拆成(op, arg1, arg2, result)的形式。注意C-D出现了两次，可以复用同一个临时变量：

( -, C, D, T1 ) ( *, B, T1, T2 ) ( +, A, T2, T3 ) ( /, E, T1, T4 ) ( +, T3, T4, T5 )

这里 T5 就是最终结果。判分点在于：临时变量命名一致、运算顺序正确、重复子表达式是否复用。有些同学把C-D算两次，虽然结果对，但四元式数量多了，可能被扣优化分。

3.2 文法二义性证明与语言描述

题目给出文法 G：

N → SE | E S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

要求证明二义性并描述语言。二义性证明的标准做法是：找到同一个句子有两棵不同的语法树。比如句子00，可以走N → SE → DE → 0E → 00，也可以走N → SE → SD → DD → 00。两条推导路径不同，说明文法二义。

语言描述则要观察文法生成什么：E 是偶数（0,2,4,6,8,10），D 是数字 0-9，S 由 D 或 SD 组成，N 由 SE 或 E 组成。整体看，这个文法生成的是以偶数结尾的数字串，也就是所有末位为偶数的十进制数。注意10作为 E 出现，说明语言里包含以 10 结尾的串，但本质上还是偶数结尾。

3.3 易错点：二义性证明只写一句话

很多同学证明二义性时只写“因为有两棵语法树”，但不画出两棵树或写出两条推导，这是拿不到分的。正确做法是：

• 先选一个具体句子，比如00或02。
• 写出两条不同的最左推导或画出两棵语法树。
• 明确指出“同一句子有两种不同推导，故文法二义”。

语言描述也要用自然语言说清，不能只写“偶数结尾”，最好补一句“所有末位为 0、2、4、6、8 或 10 的十进制数字串”。

4. LL(1) 文法与预测分析表：25 分的硬骨头怎么啃

4.1 First 集和 Follow 集的计算

题目给出文法：

E → TE' E' → +E | ε T → FT' T' → T | ε F → PF' F' → *F' | ε P → (E) | ^ | a | b

计算 First 集时，从终结符开始往上推：

• First(E) = First(T) = First(F) = First(P) = { (, ^, a, b }
• First(E') = { +, ε }
• First(T') = First(T) ∪ { ε } = { (, ^, a, b, ε }
• First(F') = { *, ε }

Follow 集要从开始符号 E 出发，Follow(E) = { $, ) }，因为 E 后面可能跟)或结束符。Follow(E') = Follow(E) = { $, ) }。Follow(T) = First(E') \ {ε} ∪ Follow(E) = { +, $, ) }。Follow(T') = Follow(T) = { +, $, ) }。Follow(F) = First(T') \ {ε} ∪ Follow(T) = { (, ^, a, b, +, $, ) }。Follow(F') = Follow(F)。Follow(P) = First(F') \ {ε} ∪ Follow(F) = { *, (, ^, a, b, +, $, ) }。

4.2 证明 LL(1) 与构造预测分析表

证明 LL(1) 的关键是：对每个非终结符，其各产生式的 First 集互不相交；若某产生式可推出 ε，则 First 集与 Follow 集不相交。检查一遍：

• E 只有一个产生式，无冲突。
• E' 的两个产生式 First 分别是 {+} 和 {ε}，且 Follow(E') = {$,)} 与 {+} 不相交。
• T 只有一个产生式。
• T' 的 First 是 {(,^,a,b} 和 {ε}，Follow(T') = {+,$,)} 与前者不相交。
• F 只有一个产生式。
• F' 的 First 是 {} 和 {ε}，Follow(F') 与 {} 不相交。
• P 的四个产生式 First 分别是 {(}、{^}、{a}、{b}，互不相交。

所以该文法是 LL(1) 文法。

预测分析表按行是非终结符，列是输入符号。每个单元格填入产生式编号。比如 E 行在(、^、a、b列都填E → TE'；E' 行在+列填E' → +E，在$和)列填E' → ε。构造时注意ε 产生式只填在 Follow 集对应的列，这是最容易错的地方。

4.3 易错点：Follow 集漏掉$或)

LL(1) 这块的失分点非常集中：

• Follow 集忘记加入$。开始符号的 Follow 一定包含$。
• Follow 集忘记传递。比如 Follow(T) 要包含 Follow(T')，因为 T' 可能推出 ε。
• 预测分析表把 ε 填错列。ε 只能填在 Follow 集对应的列，不能填在 First 集列。
• 证明 LL(1) 时只写“没有冲突”，不逐条检查 First 和 Follow 的交集。

提示：预测分析表建议先画空表，再逐行填，填完检查每行是否有重复填项。如果有重复，说明文法不是 LL(1)，或者你算错了。

5. 条件语句翻译成四元式：15 分的控制流题怎么不丢分

5.1 真题拆解：if-then-else 的四元式序列

题目要求把：

if x > 0 y > 0 then z := x + y else begin x := x + 2; y := y + 3 end;

翻译成四元式序列。这类题的标准做法是：先翻译条件，再翻译 then 分支，再翻译 else 分支，最后回填跳转地址。

四元式序列可以写成：

( >, x, 0, T1 ) ( >, y, 0, T2 ) ( and, T1, T2, T3 ) ( j=, T3, _, 5 ) ( j, _, _, 8 ) ( +, x, y, T4 ) ( :=, T4, _, z ) ( j, _, _, 12 ) ( +, x, 2, T5 ) ( :=, T5, _, x ) ( +, y, 3, T6 ) ( :=, T6, _, y )

这里第 4 条j=, T3, _, 5表示如果 T3 为真，跳到第 5 条开始执行 then 分支；否则继续执行第 5 条j, _, _, 8跳到 else 分支。第 8 条j, _, _, 12是 then 分支执行完后跳过 else 分支。

5.2 易错点：跳转地址回填错误

条件语句翻译的失分点几乎全在跳转地址上：

• 条件为假时跳转地址写错，导致 then 和 else 都执行或都不执行。
• then 分支结束后忘记跳过 else 分支。
• 临时变量命名混乱，T1、T2 重复使用导致语义错误。
• 复合语句 begin-end 里的多条赋值没有按顺序翻译。

提示：做这类题时，先在草稿纸上标出行号，再写四元式。跳转地址用行号表示，最后统一检查一遍控制流是否闭合。

6. 考前一周怎么练：从真题到答题模板的落地方法

如果你手里只有这一套卷子，别急着背答案，按下面这个顺序练三遍，效果比刷十套题都稳。

第一遍，按考点分块做。先只做正规式和 DFA 那 30 分，做完对照上面的分析检查：正规式有没有漏边界串，DFA 有没有死状态，最简有没有合并到位。然后单独做 LL(1) 那 25 分，重点检查 First/Follow 集有没有漏$和)，预测分析表有没有把 ε 填错列。最后做四元式那 25 分，检查跳转地址和临时变量。

第二遍，限时整套做。给自己 90 分钟，模拟考场节奏。做完后不要只看分数，把每道题的判分点列出来：正规式写对给几分，DFA 状态图画对给几分，最简再给几分。这样你才知道自己丢的是哪一步的分。

第三遍，只做错题和易错点。把上面提到的易错点整理成一张检查表：

这张表考前每天过一遍，比翻书有用。我自己的血泪经验是：编译原理的卷面分不是靠“看懂”拿的，是靠“写全步骤”拿的。正规式写出来只是第一步，DFA 状态图画出来才是第二步，最简化写清楚才是第三步。每一步都有分，少一步就少一截。

从那以后我每次做编译原理题，都强制走一遍“先写语言描述 → 再写正规式 → 再画 DFA → 再化简 → 最后检查边界串”的流程，哪怕题目再简单也不跳步。希望这套卷子的考点拆解和答题模板，能帮你在考场上少翻一次车。

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