编译原理试卷A实战拆解：从DFA到四元式的工程验证

简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考编译原理的学习者用于检验词法分析、语法分析、语义分析与代码生成等核心章节的掌握程度。试卷涵盖正规表达式与最简DFA构造、逆波兰表示及四元式序列、文法二义性证明与语言描述、First集与Follow集计算、LL(1)文法判定及预测分析表构造以及if-then-else语句的四元式翻译等典型题型知识点覆盖全面适合作为期末复习、自测与查漏补缺的练习材料。资源包体量轻巧单份doc文档便于打印与批注可配合教材同步使用。目前已有391人学习下载参考价值较高能帮助读者熟悉常工院命题风格与难度快速定位薄弱环节提升解题与应试能力。1. 从一份“编译原理试卷A”说起为什么我建议你把它当项目拆一遍如果你正在搜“编译原理试卷A”大概率不是想找一份题来背答案而是想搞清楚一件事这些题到底在考什么、我能不能自己动手把答案推出来、推出来之后怎么验证对不对。我见过太多人把编译原理当成纯理论课期末前背一遍First集、Follow集、四元式考完就忘。但真正做过编译器前端的人都知道这套东西是实打实的工程技能——词法分析、语法分析、中间代码生成每一步都有明确的输入输出和可验证的结果。这份试卷覆盖了编译原理最核心的五个模块正规表达式与DFA构造、逆波兰表示与三元式/四元式、文法二义性证明、LL(1)文法与预测分析表、条件语句的四元式翻译。它本质上是一份编译器前端全流程的微型项目清单。我打算把它当成一个可复现的工程任务来拆每一道题对应一个可运行的算法步骤每一步都能用代码或手工推导验证。适合正在学编译原理的学生、准备考试但不想死记硬背的人以及想复习前端流程的从业者。接下来我会按“题目要求→推导逻辑→可执行步骤→验证方法”的顺序把这份试卷拆成能抄作业的实战笔记。2. 正规表达式到最简DFA两道题的完整推导链2.1 第一题不以0开头但以11结尾的二进制串题目要求在字母表 {0,1} 上构造正规表达式并画出等价的最简DFA。先拆语言特征不以0开头意味着首字符必须是1以11结尾意味着最后两个字符固定是1。中间部分可以是任意二进制串。正规表达式我一般这样写1(0|1)*11解释一下开头的1保证不以0开头(0|1)*表示中间任意长度的0和1组合结尾的11锁定最后两位。注意这里有个容易翻车的地方——如果字符串长度恰好是2比如11那么(0|1)*匹配空串整体仍然成立。所以这个表达式是正确的。接下来构造DFA。我习惯先画NFA再确定化但更快的做法是直接按状态含义设计DFA。定义状态q0初始状态还没读到任何字符q1已读到首字符1且当前不以11结尾q2已读到结尾的1即当前串以1结尾但还没确认第二个1q3已读到结尾的11接受状态转移表如下当前状态输入0输入1q0死状态q1q1q1q2q2q1q3q3q1q2这里q3是接受状态。注意q2读到1进入q3q3读到1回到q2——因为如果已经以11结尾再读一个1最后两位变成11仍然接受。最简DFA需要合并等价状态。检查一下q1和q3在输入0时都到q1输入1时q1到q2、q3到q2行为一致但q3是接受状态而q1不是所以不能合并。q2和q3在输入0时都到q1输入1时q2到q3、q3到q2行为不同一个到接受态一个到非接受态也不能合并。所以这个DFA已经是最简的共4个状态。提示画DFA时先确定接受状态再反向推导哪些状态等价。很多人在确定化之后忘了最小化结果状态数多了一倍。2.2 第二题包含01子串的所有二进制串这题更简单只要串里出现过连续的01就行。正规表达式(0|1)*01(0|1)*DFA设计思路用三个状态追踪“是否已经看到01”。s0还没看到01当前也没有以0结尾s1当前以0结尾但还没看到01s2已经看到过01接受状态转移表当前状态输入0输入1s0s1s0s1s1s2s2s2s2s2是接受状态且一旦进入就永远停留——因为只要出现过01后面加任何字符都仍然包含01。这个DFA只有3个状态已经最简。2.3 用Python验证DFA是否正确手工推导容易出错我一般写个小脚本穷举验证。以第一题为例def dfa_accepts(s): # 状态: 0q0, 1q1, 2q2, 3q3 state 0 for ch in s: if state 0: if ch 0: return False # 死状态 state 1 elif state 1: state 2 if ch 1 else 1 elif state 2: state 3 if ch 1 else 1 elif state 3: state 2 if ch 1 else 1 return state 3 # 穷举长度1到8的所有二进制串 import itertools for n in range(1, 9): for bits in itertools.product(01, repeatn): s .join(bits) expected s.startswith(1) and s.endswith(11) assert dfa_accepts(s) expected, f失败: {s} print(全部通过)这段代码的逻辑很直接模拟DFA的转移过程最后检查是否停在接受状态。穷举验证能覆盖所有短串比手工画图可靠得多。参数方面range(1, 9)控制测试长度实际调试时可以加到12或更长但注意指数增长——长度20以上就不适合穷举了。注意写正规表达式时不要漏掉空串的情况。比如第一题中1(0|1)*11已经包含了11本身因为(0|1)*可以匹配空串。如果你写成1(0|1)11就会漏掉11这个最短串。3. 逆波兰表示与四元式表达式翻译的两种中间形式3.1 逆波兰表示的手工推导与栈算法题目要求把AB*(C-D)E/(C-D)转成逆波兰表示后缀表达式。手工推导时按运算符优先级和结合性逐步加括号原始表达式A B*(C-D) E/(C-D)先处理括号和乘法A (B*(C-D)) (E/(C-D))再处理加法左结合((A (B*(C-D))) (E/(C-D)))从最内层开始转后缀C-D→CD-B*(C-D)→BCD-*A B*(C-D)→ABCD-*E/(C-D)→ECD-/整体 →ABCD-*ECD-/用栈算法验证从左到右扫描中缀表达式遇到操作数直接输出遇到运算符则弹出栈顶优先级不低于它的运算符再入栈。括号特殊处理。我写个Python实现def infix_to_postfix(expr): prec {: 1, -: 1, *: 2, /: 2} output [] stack [] tokens expr.replace((, ( ).replace(), ) ).split() for tok in tokens: if tok.isalpha(): output.append(tok) elif tok (: stack.append(tok) elif tok ): while stack and stack[-1] ! (: output.append(stack.pop()) stack.pop() # 弹出左括号 else: while stack and stack[-1] ! ( and prec.get(stack[-1], 0) prec[tok]: output.append(stack.pop()) stack.append(tok) while stack: output.append(stack.pop()) return .join(output) print(infix_to_postfix(A B * ( C - D ) E / ( C - D ))) # 输出: A B C D - * E C D - / 参数说明prec字典定义运算符优先级tokens通过空格分割处理多字符操作数。注意这里假设操作数都是单字母实际编译器中需要词法分析器支持多字符标识符。3.2 四元式序列的生成规则四元式格式是(op, arg1, arg2, result)。对于同一个表达式按运算顺序生成( -, C, D, T1 ) ( *, B, T1, T2 ) ( , A, T2, T3 ) ( -, C, D, T4 ) ( /, E, T4, T5 ) ( , T3, T5, T6 )注意C-D出现了两次但四元式里生成了两个临时变量T1和T4。实际编译器会做公共子表达式消除把第二个C-D直接引用T1。但试卷通常要求按原始表达式逐项翻译不优化。这里有个坑临时变量编号要连续且不重复T1到T6依次分配。3.3 三元式与四元式的区别三元式格式是(op, arg1, arg2)结果用指令位置引用。同一个表达式的三元式0: ( -, C, D ) 1: ( *, B, (0) ) 2: ( , A, (1) ) 3: ( -, C, D ) 4: ( /, E, (3) ) 5: ( , (2), (4) )区别在于四元式有显式result字段三元式用序号隐式引用。四元式更适合优化阶段重排指令三元式更紧凑但重排困难。考试里如果题目说“四元式”就别写三元式反之亦然——这是血泪经验格式错了直接扣分。4. 文法二义性与LL(1)从证明到预测分析表4.1 证明文法二义性的标准套路题目给的文法GN → 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或ES可以生成SD或D。对于句子00可以这样推导路径一N ⇒ SE ⇒ DE ⇒ 0E ⇒ 00S用D替换E用0替换路径二N ⇒ SE ⇒ SD ⇒ D0 ⇒ 00S用SD替换D用0替换最后一个D用0替换两棵语法树结构不同所以文法二义。4.2 文法描述的语言这个文法生成的是什么E生成偶数0,2,4,6,8,10D生成数字0-9。S生成一个或多个数字组成的串因为S → SD | D递归生成至少一位数字。N生成SE或E即“数字串后跟偶数”或“单个偶数”。所以语言是所有以偶数结尾的数字串或者单个偶数。注意10也是偶数所以像110这样的串也属于该语言S生成11E生成0。4.3 First集和Follow集计算题目第四题给了另一个文法E → TE E → E | ε T → FT T → T | ε F → PF F → *F | ε P → (E) | ^ | a | b先算First集非终结符First集E{ (, ^, a, b }E{ , ε }T{ (, ^, a, b }T{ (, ^, a, b, ε }F{ (, ^, a, b }F{ *, ε }P{ (, ^, a, b }Follow集非终结符Follow集E{ ), $ }E{ ), $ }T{ , ), $ }T{ , ), $ }F{ , ), $, (, ^, a, b }F{ , ), $, (, ^, a, b }P{ *, , ), $, (, ^, a, b }计算Follow集时注意F的Follow集包含F的Follow集因为F → PFF后面可能跟F后面能跟的东西。同时F → *F所以F的Follow也传给自身。4.4 证明LL(1)并构造预测分析表LL(1)的条件是对于每个非终结符的多个产生式其First集不相交如果某个产生式能推导ε则其First集与Follow集不相交。检查E产生式E → E的First是{}E → ε的First是{ε}Follow(E)是{), $}。{}与{), $}不相交满足。检查TT → T的First是{(, ^, a, b}T → ε的First是{ε}Follow(T)是{, ), $}。不相交满足。检查FF → *F的First是{*}F → ε的First是{ε}Follow(F)是{, ), $, (, ^, a, b}。不相交满足。所以文法是LL(1)的。预测分析表按行是非终结符列是输入符号。填表规则对每个产生式 A → α对First(α)中每个终结符a填A→α如果α能推导ε对Follow(A)中每个符号b填A→ε。非终结符()*^ab$EE→TEE→TEE→TEE→TEEE→εE→EE→εTT→FTT→FTT→FTT→FTTT→TT→εT→εT→TT→TT→TT→εFF→PFF→PFF→PFF→PFFF→εF→εF→εF→*FF→εF→εF→εF→εPP→(E)P→^P→aP→b提示填表时最容易漏掉的是ε产生式对应的Follow集列。比如E→ε要填在)和$两列因为Follow(E)包含这两个符号。5. 条件语句的四元式翻译if-then-else的控制流5.1 翻译方案与回填技术题目要求把if x0 y0 then z:xy else begin x:x2; y:y3 end;翻译成四元式。注意条件里x0 y0应该是x0 and y0的笔误按逻辑与处理。四元式翻译的核心是回填先生成跳转指令但目标地址留空等确定位置后再填回去。标准翻译模式( , x, 0, T1 ) ( j, T1, _, 3 ) # 如果T1为假跳到else分支 ( , y, 0, T2 ) ( j, T2, _, 5 ) # 如果T2为假跳到else分支 ( , x, y, T3 ) ( :, T3, _, z ) ( j, _, _, 8 ) # 跳过else分支 ( , x, 2, T4 ) # else分支开始 ( :, T4, _, x ) ( , y, 3, T5 ) ( :, T5, _, y )这里j表示条件为假时跳转j表示无条件跳转。地址3、5、8是四元式序号从0开始计数。实际写答案时可以用标号代替绝对地址更清晰。5.2 用Python模拟四元式执行为了验证翻译结果我写个简单的四元式解释器def execute_quadruples(quads, variables): pc 0 while pc len(quads): op, arg1, arg2, result quads[pc] if op : variables[result] 1 if variables[arg1] variables[arg2] else 0 elif op : variables[result] variables[arg1] variables[arg2] elif op :: variables[result] variables[arg1] elif op j: if variables[arg1] 0: pc result continue elif op j: pc result continue pc 1 return variables # 测试用例 quads [ (, x, 0, T1), (j, T1, None, 3), (, y, 0, T2), (j, T2, None, 5), (, x, y, T3), (:, T3, None, z), (j, None, None, 8), (, x, 2, T4), (:, T4, None, x), (, y, 3, T5), (:, T5, None, y), ] vars1 {x: 1, y: 2, z: 0} execute_quadruples(quads, vars1) print(vars1) # z3, x1, y2 vars2 {x: -1, y: 2, z: 0} execute_quadruples(quads, vars2) print(vars2) # x1, y5, z0参数说明variables字典存储变量值pc是程序计数器。j指令在条件为假时跳转j无条件跳转。注意四元式序号从0开始所以第3条指令的索引是3。5.3 常见错误与修正我见过最常见的错误是跳转地址算错。比如j跳到else分支的第一条指令但else分支前面还有一条j跳过else的指令。正确顺序是then分支结束后放无条件跳转跳过else然后才是else分支。如果顺序反了then分支执行完会直接掉进else。另一个坑是条件表达式的短路求值。x0 and y0中如果x0不应该再计算y0。上面的四元式已经实现了短路——第一个j直接跳到else跳过了y的判断。如果题目要求不短路则需要先算两个条件再与。6. 用脚本批量验证试卷答案我的复习习惯手工推导完所有题目后我习惯写一个综合验证脚本把每道题的答案用代码跑一遍。这样做的好处是考试时如果记不清某个步骤可以快速用代码验证自己的推导。以LL(1)预测分析表为例写个简单的分析器def parse_ll1(tokens, table, startE): stack [$, start] pos 0 while stack: top stack.pop() if top $ and pos len(tokens): return True if top tokens[pos]: pos 1 elif top in table and tokens[pos] in table[top]: production table[top][tokens[pos]] if production ! ε: for sym in reversed(production): stack.append(sym) else: return False return False # 预测分析表简化版 table { E: {(: TE, ^: TE, a: TE, b: TE}, E\: {): ε, : E, $: ε}, T: {(: FT, ^: FT, a: FT, b: FT}, T\: {(: T, ): ε, : ε, ^: T, a: T, b: T, $: ε}, F: {(: PF, ^: PF, a: PF, b: PF}, F\: {(: ε, ): ε, : ε, *: *F, ^: ε, a: ε, b: ε, $: ε}, P: {(: (E), ^: ^, a: a, b: b}, } # 测试几个串 for s in [a, ab, a*b, (ab)*a, a*b^]: tokens list(s) [$] print(s, parse_ll1(tokens, table))这个分析器直接模拟了LL(1)的栈操作。注意E在Python字符串里要写成E\或E用双引号。测试串a*b^应该返回True因为^是合法操作数。对于DFA和四元式前面已经写了验证代码。我一般把这些脚本放在一个文件里考前跑一遍确认所有手工推导的答案都能通过程序验证。这个习惯帮我抓出过好几次跳转地址算错、Follow集漏符号的问题。从那以后我每次复习编译原理都强制自己把每道题的答案用代码跑一遍——手工推导会骗自己但代码不会。希望帮到你。本文还有配套的精品资源点击获取