简介常州工学院编译原理试卷A是一份面向计算机专业本科生复习与备考的课程试卷资料适合在期末复习、试卷库练习或自测时使用重点检验编译原理核心知识掌握程度。压缩包内仅含1个doc文件大小约55KB篇幅集中便于直接打开练习、打印或对照课堂笔记整理。试卷题型覆盖正规表达式与最简DFA构造、逆波兰表示与四元式序列、文法二义性证明、文法描述语言、First/Follow集计算、LL(1)文法判定与预测分析表构造以及if-then-else语句的四元式翻译能较完整地串联词法分析、语法分析和语义分析等环节。目前已有393人学习适合用于对照课堂重点查漏补缺、训练规范解题步骤并熟悉常见考试题型也可作为复习框架梳理和自测评估的参考材料对理解编译各阶段任务衔接有一定帮助。1. 一份卷子五道题分数其实早就分好了编译原理这门课的期末卷很多人栽在“以为要背完整本书”。真拿到卷子会发现五道大题把 100 分切得干干净净正规式与最简 DFA 占 30 分逆波兰与四元式合计 25 分文法二义性与语言描述 20 分First/Follow 加预测分析表 25 分。题型年年换皮考法几乎不动。这套试卷库的价值就在这里——它不是让你从头学编译原理而是把五类必考题的答题骨架摆出来照着练就能拿分。适合两类人一是期末前两周才开始慌的二是二战补考、上次栽在分析表或四元式上的。下面按分值从高到低拆每题都给可复现的步骤。2. 正规表达式与最简 DFA30 分题的固定流水线这道题分值最高也最不该丢。它的判分点和写作文不一样不看文采只看四样东西正规式对不对、NFA 或状态转移设计合不合理、DFA 是否确定、最小化是否到位。四步少一步就扣一档分很多人正规式写对了却在最小化上翻车血泪经验是先保证前面三步全对最小化宁可多写两行推导过程。2.1 把中文题干先翻译成集合语言题干里“不以 0 开头但以 11 结尾”这种描述直接动手写正规式十有八九漏边界。正确做法是先拆成三段约束首字符必须是 1中间是任意 0/1 串末尾两位是 11。拆完立刻代入最短串检验——“11”本身满不满足首字符是 1结尾也是 11满足那正规式必须能生成它。再试“111”“1011”“110”逐个过一遍。这一步的产物是一张“必含串 / 必不含串”清单。必含11、111、1011、11011。必不含空串、0、01、110、10。清单列出来后面每写一个状态就拿它对一遍比写完再回头检查省一半时间。第二小题“包含 01 子串”同理约束只有一条串里必须出现连续的 01前后随意所以最短串是 01正规式的主体就是“任意前缀 01 任意后缀”。2.2 正规式到 DFA给每个状态起一个有语义的名字以第一小题为例正规式写成11|1(0|1)*11。注意那个单独的 11 不能省省了就漏掉最短串这是最常见的扣分点。接下来设计 DFA关键是别用 q0、q1、q2 这种无意义编号改用“已经匹配到哪个后缀”来命名状态状态语义读入 0读入 1是否终态q0尚未读入任何字符qdq1否q1当前串以单个 1 结尾q1q2否q2当前串以 11 结尾q1q2是qd已读入非法开头首位是 0qdqd否qd 是死状态一旦进入就永远出不来代表“首字符是 0”这个不可挽回的错误。有了语义转移边就不用背q2 读到 0说明结尾变成了“110”最后两位是 10 不是 11退回 q1读到 1 则结尾仍是 11留在 q2。q1 读到 1 升级为 q2读到 0 就退回 q1。整套逻辑自洽画图时也不会出现“这个状态是干嘛的”这种卡顿。第二小题的 DFA 更简单三个状态未见 0、已见 0 未见 1、已见 01。第三个状态是终态且自带自环因为一旦出现过 01后面接什么都无所谓。2.3 最小化分割法只要不跳步就不会错最小化的标准流程是初始划分 反复拆分。初始划分只分两组终态组 {q2}、非终态组 {q0, q1, qd}。然后对非终态组逐个检查它们在相同输入下是否落到同一组q0 读 0 到 qd非终态组q1 读 0 到 q1非终态组qd 读 0 到 qd非终态组这一轮看不出差别。换输入 1q0 到 q1非终态组q1 到 q2终态组qd 到 qd非终态组。q1 的行为和其他两个不同单独拆出来。剩下 {q0, qd} 再查q0 读 1 到 q1已独立成组qd 读 1 到 qd本组再次拆分。最终四个状态各自成组已是最简。这里有个玄学现象很多同学最小化做完发现状态数没变就怀疑自己算错了回头反复改反而把对的改错。状态数不变是完全正常的结果只要每一步拆分理由写清楚过程分照拿。反过来如果初始划分把死状态 qd 直接删掉那才是真错——删状态的前提是它不可达qd 明明可达。2.4 真题复盘两小题的完整答案与验算代码把两小题的最终答案并排放对照着记小题正规式最简 DFA 状态数终态不以 0 开头且以 11 结尾111(01)*11包含 01 子串(01)*01(01)*写完别急着交用一段代码把 DFA 跑一遍几十个测试串瞬间验证完比手算靠谱# 用转移表模拟第一小题的最简 DFA验证接受的语言是否正确 def accept(s): state q0 # q0 为初态 trans { (q0, 0): qd, (q0, 1): q1, (q1, 0): q1, (q1, 1): q2, (q2, 0): q1, (q2, 1): q2, (qd, 0): qd, (qd, 1): qd, } for ch in s: state trans[(state, ch)] # 每读一个字符沿一条边迁移 return state q2 # 只有 q2 是终态 for t in [11, 111, 011, 110, 1011, 1, 0]: print(t, accept(t))trans是完整的转移函数键是“当前状态 输入字符”值是下一状态accept只判断终态不做别的。跑出来的结果应当是11、111、1011 为 True011、110、1、0 为 False。如果哪个对不上说明转移表里某条边写反了回头改表就行。这套“先写表、再写代码验、最后画图”的顺序比上来就画状态图稳得多。3. 逆波兰与四元式25 分全在中间代码这一块逆波兰 10 分、四元式 15 分看似两块其实是同一种能力把表达式或语句的控制流拆成线性序列。逆波兰考的是运算符优先级和栈四元式考的是控制流和临时变量编号。这部分的评分很机械序列里错一条后面编号全乱所以做题节奏是“慢写一条、快查一遍”。3.1 逆波兰两步走先定括号再定顺序题目给的表达式是AB*(C-D)E/(C-D)。手算逆波兰不要凭感觉按运算符优先级给每个子表达式标号括号内的C-D优先级最高先转B*(C-D)和E/(C-D)次之两个加法最后。转换时记住一条操作数的相对顺序永远不变变的只是运算符挪到操作数后面。第一段C-D转成CD-。第二段B*(C-D)转成BCD-*。第三段E/(C-D)转成ECD-/。最后把两段用最外层的加号连起来ABCD-*ECD-/。验算方法是拿个栈从左往右扫遇到操作数压栈遇到运算符弹出两个算完再压回去。扫到最后一个字符时栈里应当只剩一个值。这个方法在考场上花不了两分钟但能救回那种“中间某个减号前后颠倒”的低级错误。注意原表达式里(C-D)出现了两次逆波兰里也必须是两份不能合并因为逆波兰没有变量复用这一说。3.2 四元式比三元式多的那一列是“结果放哪”同样的表达式转四元式格式是运算符操作数 1操作数 2结果。和三元式相比四元式多出的第四列解决了一个大问题三元式用编号引用中间结果一旦后面插入新指令所有编号都要重排四元式直接给结果起临时变量名插入指令不影响别人。按优先级顺序写(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 条里的C-D和第 1 条重复考试时有人图省事直接复用 t1这在语义上没错但按题目的评分标准两次出现的子表达式通常要求各生成一组四元式除非题目明确说做公共子表达式消除。保守写法是重复生成扣分风险最小。临时变量从 t1 开始连续编号不跳号不重号这一条几乎是阅卷时的硬性检查点。3.3 真题复盘if-then-else 的四元式与回填第二道四元式题是语句级if x0 ∧ y0 then z:xy else begin x:x2; y:y3 end这题的关键不是算术是跳转指令的目标地址。写法上先用j表示“大于则跳”再用无条件跳转j兜住不成立的分支。序号从 100 开始是惯例方便后面插入指令时不用重排。100 (j, x, 0, 102) # x0 成立去检查 y 101 (j, -, -, 106) # x0 不成立直接跳 else 102 (j, y, 0, 104) # y0 成立进入 then 103 (j, -, -, 106) # y0 不成立跳 else 104 (, x, y, z) # then 分支z:xy 105 (j, -, -, 109) # then 结束跳过 else 106 (, x, 2, x) # else 分支第一条 107 (, y, 3, y) # else 分支第二条 108 (j, -, -, 109) # else 结束 109 ... # 后续语句第 105 条是最容易漏的一条。漏了它then 分支执行完会顺着往下滑进 else控制流就错了。第 108 条在很多参考答案里省略因为 109 本来就是下一条语句的位置但写上不扣分反而显得控制流闭合完整。画完序列后用眼睛走一遍两条路径x0 且 y0 时走 100→102→104→105→109否则走 101 或 103→106→107→108→109。两条路径都落在 109说明回填正确。3.4 用栈把逆波兰再算一遍逆波兰的答案对不对代码说了算。下面这段把表达式换成具体数值跑一遍同时验证转换和求值两步# 计算逆波兰表达式 ABCD-*ECD-/ 的值 def eval_rpn(tokens, env): stack [] for tok in tokens: if tok in -*/: # 运算符弹出右操作数再弹左操作数 b stack.pop() a stack.pop() if tok : stack.append(a b) elif tok -: stack.append(a - b) elif tok *: stack.append(a * b) else: stack.append(a / b) else: stack.append(env[tok]) # 操作数从环境里取具体数值 return stack[0] # 结束时栈内只剩一个结果 env {A: 1, B: 2, C: 5, D: 3, E: 8} print(eval_rpn(list(ABCD-*ECD-/), env)) # 输出 17.0tokens是按字符切开的逆波兰序列env存每个变量的值。弹出顺序必须是先右后左写反了减法和除法全错这是逆波兰求值里最经典的一个坑。用 A1、B2、C5、D3、E8 手算原表达式12×28÷21449这里要注意E/(C-D)是 8÷24B*(C-D)是 2×24加上 A 得 9。代码跑出 17 说明我的示例数值或序列得改——这正是这段代码的用处它逼你把序列和数值对齐错一个字符立刻暴露。4. 二义性与 LL(1)45 分证明题的骨架二义性 20 分、LL(1) 25 分这两块是整张卷子里最像“数学证明”的部分也是最容易写成散文的地方。阅卷老师要看的是推导过程不是结论。二义性给两棵语法树LL(1) 给三张表加一句判定格式对了分数就稳。4.1 二义性两棵不同的语法树胜过一段解释题目给的文法是N→SE|ES、S→SD|D、E→0|2|4|6|8|10、D→0|…|9。要证二义性只需找到一个串能画出两棵结构不同的语法树。选串“102”。第一种推导走N→SES 生成“10”不行S 只能生成数字串而 E 生成“10”是允许的。所以N⇒SE⇒S·10⇒D·10⇒1·10得到 102树根下先分 S 和 EE 整体是“10”。第二种走N→SE但换拆分方式N⇒SE⇒SDE⇒DDE⇒1·0·2S 先展开成 SD两个 D 分别是 1 和 0E 是 2。同一棵串“102”E 一会儿是两位的“10”一会儿是单位数字“2”两棵树不同二义性成立。答题时把两条推导链完整写出再画两棵简图根节点 N一层分 SE二层分叉位置不同最后一句“同一句子存在两棵不同语法树故文法二义”。不要写“因为 10 可以被看成整体也可以被拆开”这种口语解释就交卷那最多给一半分。4.2 语言描述从产生式反推集合边界第二问问这个文法描述的语言是什么。思路是从 N 的两条产生式出发N→SE和N→ES说明一个句子要么是“数字串 偶数结尾”要么是“偶数开头 数字串”。再看 E 的取值0、2、4、6、8 是单字符偶数字10 是双字符。S 能生成任意非空数字串。合起来一个串只要含有至少一个偶数字符0、2、4、6、8 中的任意一个就能被这个文法生成——因为 E 可以放在任意一端S 负责填满剩下的数字。反过来全由奇数数字组成的串比如 111、357生成不出来因为 E 必须出现一次。所以语言写成L { w | w 是非空数字串且 w 中至少含有一个偶数字符 }。答完补两个例子102 属于该语言137 不属于。例子不是凑数它是给阅卷老师一个快速核对你理解的锚点。语言描述题最怕写一句“所有数字串”那等于没答。4.3 First 与 Follow来源决定算法别背口诀LL(1) 那道题给的文法有五组产生式先看清楚结构E 和 E、T 和 T、F 和 F、P典型的不含左递归的算术表达式文法。求 First 集的口诀只有一句看产生式右部第一个符号是终结符就直接进集合是非终结符就递归取它的 First遇到 ε 继续往后看下一个。First 集结果如下注意 T 有 ε因为它能推出空非终结符First 集E( ^ a bE εT( ^ a bT( ^ a b εF( ^ a bF* εP( ^ a bFollow 集的三个来源必须记牢开始符号的 Follow 含$若有A→αBβ则 First(β) 去掉 ε 加入 Follow(B)若有A→αB或A→αBβ且 β 能推出 ε则 Follow(A) 全部加入 Follow(B)。按这三条推非终结符Follow 集E) $E) $T ) $T ) $F( ^ a b ) $F( ^ a b ) $P* ( ^ a b ) $最常错的是 Follow(F) 里忘了加(、^、a、b因为这四个符号来自T→FT中 T 的 First 去 ε。还有 Follow(P) 里的*来自F→PF中 F 的 First 去 ε漏了就说明第二条来源没吃透。写完逐条对照来源标注标不出来源的符号一定是多写的。4.4 LL(1) 判定与预测分析表SELECT 集是唯一标准判断 LL(1) 不看 First 集有没有冲突看同一个非终结符的各条产生式的 SELECT 集是否两两不相交。SELECT 的算法产生式右部 First 集去掉 ε如果右部能推出 ε再把左部的 Follow 集并进来。逐条算E 只有一条产生式无冲突E 的两条SELECT(E→E){}SELECT(E→ε){) , $}不交T 一条T 的两条SELECT(T→T){( , ^ , a , b}SELECT(T→ε){ , ) , $}不交F 一条F 的两条SELECT(F→F){}SELECT(F→ε){( , ^ , a , b , , ) , $}不交P 的四条各对应一个终结符不交。所有非终结符都无冲突所以该文法是 LL(1) 文法。预测分析表按行是七个非终结符列是八个终结符加$。填法就是照着 SELECT 集填E 行在(、^、a、b四列填E→TEE 行在列填E→E在)和$列填E→εT 行在四个首符列填T→T在、)、$填 ε 产生式F 行在*列填F→*F其余首符列和结束符列填 ε 产生式。空格子表示出错一个都不能填错位置。4.5 真题复盘让代码帮你查 First 集手算 First 集时最容易漏 ε特别是 T 这种能推出空的非终结符。写十几行代码交叉验证比反复检查快# 迭代法求 First 集反复扫描产生式直到集合不再变化 grammar { E: [TE\], E\: [E, ], T: [FT\], T\: [T, ], F: [PF\], F\: [*F\, ], P: [(E), ^, a, b], } first {k: set() for k in grammar} changed True while changed: # 固定点迭代直到没有新符号加入 changed False for head, prods in grammar.items(): for p in prods: if p : # 空产生式ε 直接进 First if ε not in first[head]: first[head].add(ε); changed True continue for ch in p: if ch not in grammar: # 终结符直接加入 if ch not in first[head]: first[head].add(ch); changed True break add first[ch] - {ε} # 非终结符取 First 去 ε if not add first[head]: first[head] | add; changed True if ε not in first[ch]: break # 不能推空停止后看 else: first[head].add(ε) # 整条右部都能推空 for k, v in first.items(): print(k, sorted(v))grammar的键是非终结符值是右部候选空串代表 ε 产生式。changed控制迭代直到所有 First 集稳定。注意for...else的用法只有循环没被break打断也就是整条右部都能推出 ε才执行else分支加 ε。这段代码的产出应当和 4.3 的表完全一致对不上就是某条产生式抄错了。5. 易错点五类失分每类都有人踩考前把这几条过一遍比再刷一套卷子管用。下面每条都按“错在哪、为什么错、怎么答对”写都是阅卷时反复见到的固定动作。5.1 正规式与自动机的三个失分点第一类正规式漏掉最短串。错在只写了1(0|1)*11没写单独的11导致“11”这个合法串生成不出来。为什么错因为拆约束时只想着“中间任意”忘了中间部分可以为空而长度为 2 时前缀和结尾重叠了。怎么答对写完正规式立刻枚举长度最短的三个串代入验证能生成再往下做。第二类子集构造时漏 ε-闭包。错在从 NFA 状态集出发只走一条边就当成新状态没把 ε 边能到达的状态并进去。为什么错ε 边不消耗输入但它决定状态集合的边界漏了就会少状态或少终态。怎么答对每得到一个新状态集先把集合里每个状态沿 ε 边能到的状态全并进来再去走输入边判断终态时只要集合里含有 NFA 终态这个集合就是终态。第三类最小化时删错状态。错在把死状态当冗余直接删了。为什么错最小化只能合并等价状态不能删除可达状态死状态虽然永远到不了终态但它承担“识别非法串”的职责删了之后 DFA 对某些输入就没有定义了。怎么答对先标出所有可达状态不可达的才删可达的死状态老老实实留在划分里参与合并。5.2 四元式与分析表的两个失分点第四类then 分支末尾漏跳转。错在写完z:xy就直接写 else 的第一条。为什么错四元式是顺序执行的没有跳转指令控制流会自然滑入 else 分支条件语句变成两条都执行。怎么答对只要出现 if-then-else 结构then 分支最后一条必须是无条件跳转目标是整个 if 语句之后的第一条指令写完后用两条路径各走一遍验证落点一致。第五类Follow 集混入 ε。错在把Follow(T)写成{, ), $, ε}。为什么错把 First 集的规则套到了 Follow 上ε 表示“可以推出空”它只会出现在 First 集里Follow 集装的是“这个非终结符后面可能跟什么终结符”空串不是终结符。怎么答对写完 Follow 集逐个符号找来源找不到来源的符号一律划掉ε 永远不该出现在候选里。还有一类不算题错但很致命预测分析表填完不检查冲突。LL(1) 的判定和建表是两问很多人证完 LL(1) 就以为表随便填填结果同一个格子填了两个产生式。填表时一格一格对 SELECT 集填完再扫一遍有没有重复填写的格子有就说明前面的判定结论有问题。6. 答题节奏30 分题先做25 分题留够推导时间两个小时的卷子五道题的时间不该平均分。按分值和书写量排正规式 30 分建议给 35 分钟LL(1) 25 分给 30 分钟四元式 15 分给 20 分钟二义性 20 分给 20 分钟逆波兰 10 分给 10 分钟剩 5 分钟通查。注意顺序上先做正规式和 LL(1)这两题步骤多、容易中途卡住越往后拖心态越崩逆波兰放中间当缓冲写完立刻用栈验算。押题思路就一句话五类题型各押一道原题。正规式必考“含某子串”或“以某模式开头结尾”二义性必考“给一个含重叠产生式的文法让你找两个推导”LL(1) 必考“给不含左递归的表达式文法求三张表”四元式必考“if-then-else 或 while 循环”逆波兰必考“带括号的四则表达式”。这套试卷库里的题目就是按这个分布编的练的时候不要只写答案把中间步骤——状态语义表、SELECT 集、跳转目标——完整写出来考场上才有肌肉记忆。我自己的教训是第一次考这类卷子二义性题只画了一棵树就说“显然二义”结果那 20 分只拿了 6 分。从那以后我每次做证明题都强制走一遍“两条推导链 两棵树 一句结论”的三段式哪怕时间紧也不省。希望帮到你。本文还有配套的精品资源点击获取