简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考编译原理课程的读者用于检验词法分析、语法分析、语义分析与代码生成等核心章节的掌握程度。试卷内容覆盖正规表达式与最简DFA构造、逆波兰表示与三元式序列、文法二义性证明及语言描述、First集与Follow集计算、LL(1)文法判定与预测分析表构造以及if-then-else语句的四元式翻译等典型题型知识点分布完整适合作为期末复习、自测与课堂练习的参考材料。目前已有388人学习下载读者可借助它梳理编译流程各阶段的解题思路对照题目查漏补缺熟悉考试常见问法与作答规范也可作为教师命题或习题课选材的参考。1. 常州工学院编译原理试卷A一份卷子能暴露多少工程盲区如果你正在搜“常州工学院编译原理试卷A”大概率不是单纯想对答案。更常见的场景是期末临近老师划了范围但没给题型或者你正在准备考研复试的编译原理笔试想拿一份真实期末卷当模拟再或者你是个已经工作两三年的后端突然发现当年编译原理课设里写的词法分析器跟现在做 DSL、写 SQL 解析器、搞配置校验完全是同一套东西想回头把基础补扎实。这份卷子的价值不在于“常州工学院”四个字而在于它是一份典型的本科编译原理期末试卷。这类卷子通常覆盖词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成这几大块题型稳定选择题、填空题、简答题、计算题、构造题。计算题里必考 LL(1) 分析表构造、LR 项目集规范族、算符优先关系表构造题里常考 NFA 转 DFA、正规式转 NFA、三地址码生成。把这些题型吃透比刷十套来路不明的模拟题都管用。这篇文章不打算给你一份“答案速查表”而是把这份卷子背后对应的知识模块拆开告诉你每个模块在工程里长什么样、怎么用代码复现、参数怎么调、哪里最容易翻车。适合正在备考的学生也适合想用编译原理补内功的工程师。读完你至少能自己动手写一个能跑通表达式求值的微型编译器前端而不是只会背“移进-归约”。2. 从试卷题型反推词法分析与语法分析到底考什么2.1 词法分析正规式、NFA、DFA 三件套的工程映射试卷里词法分析部分几乎必考一道“给定正规式构造 NFA再确定化为 DFA最后最小化”。很多同学背了子集构造法的步骤但一到最小化就乱。工程里这套东西对应的是 tokenizer 的自动生成比如 lex/flex 的底层逻辑。你手写一个词法分析器时其实是在手动模拟 DFA 的状态转移。先看一个最小可复现的例子识别标识符和整数。正规式是letter(letter|digit)*和digit。用 Python 写一个不依赖任何库的 DFA 模拟器比背算法更直观。# 一个极简 DFA 模拟器识别标识符和整数 # 状态定义0起始1标识符中2整数中3接受并结束 def tokenize(s): state 0 tokens [] buf for ch in s : # 末尾加空格触发最后一个 token 的收尾 if state 0: if ch.isalpha() or ch _: state 1 buf ch elif ch.isdigit(): state 2 buf ch elif ch.isspace(): continue else: raise ValueError(f非法字符: {ch}) elif state 1: if ch.isalnum() or ch _: buf ch else: tokens.append((ID, buf)) buf state 0 # 回退一格重新处理当前字符 if ch.isdigit(): state 2 buf ch elif not ch.isspace(): raise ValueError(f非法字符: {ch}) elif state 2: if ch.isdigit(): buf ch else: tokens.append((NUM, buf)) buf state 0 if ch.isalpha() or ch _: state 1 buf ch elif not ch.isspace(): raise ValueError(f非法字符: {ch}) return tokens print(tokenize(abc123 456def _x9)) # 输出: [(ID, abc123), (NUM, 456), (ID, def), (ID, _x9)]这段代码的关键在于状态 1 和状态 2 的“回退”处理。DFA 本身没有回退但手写扫描器时遇到不属于当前 token 的字符必须把它留给下一个 token。参数上state就是 DFA 的状态编号buf是当前累积的 lexeme。如果你在试卷上做子集构造法得到的 DFA 状态表跟这里的state是一一对应的。区别在于试卷要求你写出所有状态和转移而工程里你只关心“能不能正确切分”。常见坑很多同学在最小化 DFA 时把“死状态”和“接受状态”混在一起。死状态是那些无法到达接受状态的陷阱状态最小化时必须先删除。工程里对应的是错误处理分支——你的 tokenizer 遇到非法字符是直接抛异常还是跳过试卷里通常要求你画出完整的 DFA包括死状态但实际写代码时死状态就是raise。2.2 语法分析LL(1) 与 LR 的选型分水岭试卷里语法分析通常出两道题一道 LL(1) 分析表构造一道 LR(1) 或 LALR(1) 项目集规范族。很多同学搞不清什么时候用 LL(1)什么时候用 LR。简单说LL(1) 是自顶向下从左到右扫描、最左推导要求文法无左递归、无回溯LR 是自底向上从左到右扫描、最右推导的逆过程能处理左递归但状态机更复杂。工程里手写递归下降解析器LL 风格适合语法简单、需要精细错误恢复的场景比如 JSON 解析、配置文件解析。而 Yacc/Bison 生成的 LALR(1) 解析器适合语法复杂、运算符优先级多的场景比如 SQL、编程语言编译器。试卷里让你构造 LL(1) 分析表核心是求 FIRST 集和 FOLLOW 集。求 FOLLOW 集时最容易漏掉“如果 A 能推导出空串则 FOLLOW(A) 包含 FOLLOW(左部)”这条规则。用一张表把 LL(1) 和 LR 的试卷考点与工程对应关系列清楚对比项LL(1)LR(1)/LALR(1)推导方向最左推导自顶向下最右推导的逆自底向上左递归必须消除可以直接处理分析表规模较小较大LALR 合并同心项目集后适中试卷常见题型求 FIRST/FOLLOW构造预测分析表构造项目集规范族画 DFA填 ACTION/GOTO 表工程对应递归下降、Pratt 解析器Yacc/Bison、ANTLR、JavaCC错误恢复容易实现精细恢复较难通常靠 error token如果你在试卷上遇到“判断某文法是否为 LL(1) 文法”步骤是先消除左递归和左公因子再求 FIRST 和 FOLLOW最后检查每个非终结符的候选式 FIRST 集是否相交以及是否与 FOLLOW 集相交。只要有一个相交就不是 LL(1)。这个判断在工程里对应的是“你的递归下降解析器是否需要回溯”。需要回溯就说明不是 LL(1)得改文法或者换解析策略。2.3 用 Python 跑通 LL(1) 分析表的自动构造光背规则没用写一遍代码就记住了。下面这个脚本输入一个消除左递归后的文法自动计算 FIRST、FOLLOW 并生成预测分析表。你可以拿试卷上的文法直接喂进去验证。# LL(1) 分析表自动构造输入文法产生式输出 FIRST、FOLLOW 和分析表 grammar { E: [[T, E]], E: [[, T, E], [ε]], T: [[F, T]], T: [[*, F, T], [ε]], F: [[(, E, )], [id]] } non_terms set(grammar.keys()) terms set() for prods in grammar.values(): for p in prods: for sym in p: if sym not in non_terms and sym ! ε: terms.add(sym) FIRST {nt: set() for nt in non_terms} FOLLOW {nt: set() for nt in non_terms} FOLLOW[E].add($) # 开始符号的 FOLLOW 包含结束符 def first_of_seq(seq): 求一个符号串的 FIRST 集 result set() for sym in seq: if sym in terms: result.add(sym) return result elif sym ε: result.add(ε) return result else: result | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: return result result.add(ε) return result # 迭代求 FIRST 直到不动点 changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: f first_of_seq(p) if not f.issubset(FIRST[nt]): FIRST[nt] | f changed True # 迭代求 FOLLOW 直到不动点 changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: for i, sym in enumerate(p): if sym in non_terms: rest p[i1:] f first_of_seq(rest) if rest else {ε} add f - {ε} if ε in f or not rest: add | FOLLOW[nt] if not add.issubset(FOLLOW[sym]): FOLLOW[sym] | add changed True # 构造预测分析表 table {} for nt, prods in grammar.items(): for p in prods: f first_of_seq(p) for t in f - {ε}: table[(nt, t)] p if ε in f: for t in FOLLOW[nt]: table[(nt, t)] p print(FIRST:, {k: sorted(v) for k, v in FIRST.items()}) print(FOLLOW:, {k: sorted(v) for k, v in FOLLOW.items()}) print(分析表:) for (nt, t), p in sorted(table.items()): print(f M[{nt}, {t}] { .join(p)})这段代码的核心是first_of_seq和两个不动点迭代。参数说明grammar字典的 key 是非终结符value 是产生式列表每个产生式是符号列表空串用ε表示。FIRST和FOLLOW初始为空集通过反复扫描所有产生式直到不再变化。分析表构造时对于每个产生式如果其 FIRST 集包含终结符t就把该产生式填入M[nt, t]如果 FIRST 包含ε则对 FOLLOW 集中的每个终结符也填入该产生式。跑完这个脚本你拿试卷上的文法对照输出就能验证自己手算的 FIRST/FOLLOW 对不对。常见翻车点忘记处理ε产生式导致 FOLLOW 集算错或者把$写成了#虽然不影响逻辑但跟试卷答案对不上。工程里这个表就是递归下降解析器的“路由表”——每个非终结符遇到不同 lookahead 时走哪条产生式。3. 语义分析与中间代码试卷里的计算题怎么变成可运行代码3.1 语法制导翻译从属性文法到三地址码试卷里语义分析部分通常考“给出语法制导定义写出表达式或语句的三地址码”。比如a b c * d生成四元式。很多同学会背“先乘后加”但一到带括号、赋值、数组引用就乱。工程里这对应的是编译器前端的 IR 生成阶段。你写一个简单的表达式求值器其实就是在做语法制导翻译。三地址码的常见形式是四元式(op, arg1, arg2, result)。下面用 Python 写一个递归下降的翻译器把中缀表达式转成四元式序列。它同时完成了语法分析和语义动作。# 递归下降翻译器中缀表达式 - 四元式 # 文法已消除左递归 # E - T E # E - T E | ε # T - F T # T - * F T | ε # F - ( E ) | id class Translator: def __init__(self, tokens): self.tokens tokens self.pos 0 self.temp_count 0 self.quads [] def new_temp(self): self.temp_count 1 return ft{self.temp_count} def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else None def match(self, expected): tok self.peek() if tok expected: self.pos 1 return tok raise SyntaxError(f期望 {expected}实际 {tok}) def parse_E(self): place self.parse_T() while self.peek() : self.match() place2 self.parse_T() new_place self.new_temp() self.quads.append((, place, place2, new_place)) place new_place return place def parse_T(self): place self.parse_F() while self.peek() *: self.match(*) place2 self.parse_F() new_place self.new_temp() self.quads.append((*, place, place2, new_place)) place new_place return place def parse_F(self): tok self.peek() if tok (: self.match(() place self.parse_E() self.match()) return place elif tok is not None and tok.isidentifier(): self.pos 1 return tok else: raise SyntaxError(f非法因子: {tok}) # 测试a b c * d 的右部表达式 tokens [b, , c, *, d] t Translator(tokens) result t.parse_E() print(f最终结果在: {result}) for q in t.quads: print(f {q[0]} {q[1]} {q[2]} {q[3]}) # 输出: # 最终结果在: t2 # * c d t1 # b t1 t2这段代码的关键是new_temp()生成临时变量quads列表按顺序记录四元式。参数上tokens是词法分析输出的 token 列表pos是当前扫描位置。parse_E处理加减parse_T处理乘除parse_F处理括号和标识符。注意这里没有处理左递归因为文法已经改写成了右递归形式。试卷上让你写三地址码时临时变量的编号顺序必须跟语法树的求值顺序一致——先算c*d得到t1再算bt1得到t2。如果你先算加法四元式顺序就错了。常见坑很多同学在试卷上把a b c * d的三地址码写成t1 b c; t2 t1 * d这是典型的优先级翻车。递归下降的层次结构天然保证了*比先归约所以四元式顺序一定是先乘后加。工程里如果你用 Yacc 写优先级靠%left声明手写递归下降就靠函数调用层次。3.2 符号表管理试卷简答题里的“黑匣子”试卷里符号表通常以简答题出现“简述符号表的作用和常见实现方式”。很多同学背了“符号表用于记录标识符的属性如类型、作用域、存储位置”但没写过。工程里符号表是语义分析的核心数据结构。你写一个支持嵌套作用域的符号表就能理解为什么试卷要考它。常见实现是哈希表 作用域栈。每个作用域是一个字典进入作用域时压栈退出时弹栈。查找时从栈顶往下找。下面是一个最小实现# 支持嵌套作用域的符号表 class SymbolTable: def __init__(self): self.scopes [{}] # 栈底是全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() else: raise RuntimeError(不能退出全局作用域) def declare(self, name, type_info): if name in self.scopes[-1]: raise ValueError(f重复声明: {name}) self.scopes[-1][name] type_info def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise NameError(f未声明: {name}) # 测试 st SymbolTable() st.declare(x, int) st.enter_scope() st.declare(x, float) # 内层遮蔽外层 st.declare(y, int) print(st.lookup(x)) # float st.exit_scope() print(st.lookup(x)) # int参数说明scopes列表的每个元素是一个字典declare只检查当前作用域是否重复lookup从最内层往外找。试卷里常考“符号表在编译的哪个阶段建立和使用”——答案是词法分析后开始建立语法分析时插入声明语义分析时查询类型代码生成时读取存储分配信息。工程里符号表还负责作用域嵌套、重载解析、类型检查。如果你在试卷上遇到“画出符号表在嵌套作用域下的内容变化”就按这个栈模型画。4. 常州工学院编译原理试卷A的避坑与排查清单4.1 避坑一FIRST 集和 FOLLOW 集混用导致分析表冲突现象构造 LL(1) 分析表时某个单元格填入了两个产生式或者该填的地方空着。原因求 FIRST 集时漏掉了“如果非终结符能推导出 ε则 FIRST 包含 ε”求 FOLLOW 集时漏掉了“如果产生式右部某个非终结符后面可以推导出 ε则 FOLLOW 包含左部的 FOLLOW”。解决写一个自动计算脚本如 2.3 节把试卷文法喂进去对照输出逐项检查。手算时先标记所有能推导出 ε 的非终结符再求 FIRST 和 FOLLOW。4.2 避坑二LR 项目集规范族里把“移进”和“归约”项目搞混现象画 LR(1) 项目集 DFA 时状态里的项目形式写错导致 ACTION 表填错。原因分不清A - α·Bβ和A - α·的区别。前者是移进项目点后面是符号后者是归约项目点在最右。解决记住“点”表示当前分析位置。移进项目要读下一个符号归约项目表示右部已识别完。如果同一个状态里既有移进项目又有归约项目且 lookahead 集合相交就是冲突。试卷里通常考 LALR(1)需要先构造 LR(1) 项目集再合并同心项目集。4.3 避坑三三地址码生成时临时变量编号顺序错乱现象试卷上写出的四元式顺序跟标准答案不一致虽然逻辑对但扣分。原因没有严格按照语法树的求值顺序生成临时变量。解决先画语法树后序遍历每遇到一个运算符就分配一个新临时变量。工程里递归下降的代码结构天然保证顺序但如果你用栈式求值就要注意弹栈顺序。参数上临时变量编号从 1 开始递增不要跳号。4.4 避坑四NFA 转 DFA 时忘记处理空串闭包现象子集构造法得到的 DFA 状态数比答案少或者转移缺失。原因没有计算 ε-闭包。解决每次从 NFA 状态集出发先求 ε-闭包再对每个输入符号求转移后的 ε-闭包。试卷上通常要求写出完整的状态转移表ε-闭包列必须单独列出。工程里如果你用 Thompson 构造法生成 NFA再转 DFA空串闭包是自动处理的但手算时最容易漏。4.5 避坑五优化部分把“局部优化”和“全局优化”搞反现象简答题里问“基本块内的优化属于哪类”答成全局优化。原因没分清优化范围。解决基本块内是局部优化如常量折叠、公共子表达式消除、死代码消除跨基本块是全局优化如循环不变代码外提、强度削弱。试卷里常考“给出一个基本块做常量折叠和公共子表达式消除”你只需要在基本块内按顺序扫描遇到可计算的常量就合并遇到重复表达式就替换成第一次的结果。5. 用试卷文法跑通一个微型编译器前端5.1 把词法、语法、语义串成一条流水线试卷上的题目是分块的但工程里它们是一条流水线。我一般会写一个main函数把 2.1 的 tokenizer、2.3 的 LL(1) 分析表、3.1 的翻译器串起来输入一个表达式输出四元式。这样你就能直观看到每个阶段的数据结构怎么传递。# 微型编译器前端流水线词法 - 语法 - 语义四元式 def compile_expression(expr): # 阶段1词法分析 tokens [] i 0 while i len(expr): ch expr[i] if ch.isspace(): i 1 elif ch.isalpha() or ch _: j i while j len(expr) and (expr[j].isalnum() or expr[j] _): j 1 tokens.append(expr[i:j]) i j elif ch.isdigit(): j i while j len(expr) and expr[j].isdigit(): j 1 tokens.append(expr[i:j]) i j elif ch in -*/(): tokens.append(ch) i 1 else: raise ValueError(f非法字符: {ch}) # 阶段23语法分析 语义翻译 t Translator(tokens) result t.parse_E() return result, t.quads # 测试 result, quads compile_expression(b c * d) print(f结果: {result}) for q in quads: print(f {q[0]} {q[1]} {q[2]} {q[3]})这个流水线里tokens是词法分析的输出Translator同时做语法分析和语义动作。参数上expr是输入字符串tokens列表里的每个元素要么是标识符、数字要么是运算符。如果你把试卷上的表达式换成(a b) * (c - d)流水线会生成正确的四元式序列。注意parse_E只处理了和*实际试卷可能考-和/你只需要在parse_E和parse_T里加分支即可。5.2 用试卷真题验证从“会背”到“会写”拿一道典型试卷题给定文法E - E T | TT - T * F | FF - (E) | id要求消除左递归并构造 LL(1) 分析表。你先用 2.3 的脚本把消除左递归后的文法输进去看输出的 FIRST、FOLLOW 和分析表是否跟手算一致。然后拿一个输入串id id * id用分析表模拟分析过程看是否接受。最后用 3.1 的翻译器生成四元式。这一套走下来这道题你就彻底拿下了。我自己的习惯是每做一道试卷题就写一个对应的最小可运行脚本。脚本不用长二三十行就够但必须能跑。跑通一次比背十遍规则都管用。编译原理这门课试卷上的计算题和构造题本质上都是算法的手动执行。你写代码让机器执行一遍就知道自己哪一步想错了。5.3 参数怎么调从试卷答案到工程实现的差异试卷答案追求“标准形式”工程实现追求“能跑就行”。比如 DFA 最小化试卷要求你画出完整的状态转移图包括死状态工程里你直接删掉死状态遇到非法输入抛异常。再比如三地址码试卷要求临时变量从t1开始连续编号工程里你可能用 SSA 形式每个变量只赋值一次编号不连续。理解这些差异你就能在考试和实战之间自由切换。提示如果你在试卷上遇到“写出表达式的逆波兰表示”直接用后序遍历语法树即可。工程里逆波兰表示对应的是栈式虚拟机的指令序列比如 JVM 的字节码。希望帮到你。本文还有配套的精品资源点击获取