尧图网页设计 
简介西安交通大学2022年《编译原理》作业考核试题是一份面向编译原理课程学习者的选择题练习文档内容围绕文法与句子、算符优先文法、程序基本块、无二义文法、Chomsky文法分类、LR(0)分析、符号表、中间代码生成等核心考点展开也涉及Pascal语言特性、上下文无关语言与自动机、静态分派等容易被忽视的细节适合期末复习、考研复试或面试前快速自测。压缩包共1个文件为docx文档大小约13KB打开即可使用。目前已有214人学习。题目后多处已标注正确选项可快速核对答案整套题覆盖编译器从词法分析、语法分析到目标代码生成的完整流程作为浓缩练习资料能帮助读者发现知识盲区并强化对抽象概念的理解整体轻量、便于碎片时间完成一轮针对性复习。1. 2022年西安交通大学编译原理作业考核试题不只是刷题是把你逼到能动手写编译器看到这个标题估计很多人的第一反应是“又是哪年的期末题”。但如果你真把西安交大这份 2022 年编译原理作业考核试题当成普通题库去刷那多半会吃亏。它名义上是“作业考核”实际内核是把编译原理里最劝退的几块硬骨头——词法分析、语法分析、中间代码生成、甚至局部优化——串成一条需要你亲手实现的完整链路。考的不是“LR(1) 项目集规范族怎么画”而是“给你一段代码你能不能说出它该怎么被翻译成三地址码、符号表怎么组织、冲突怎么消解”。这份题的价值恰恰在于它把“会做题”和“会做编译器”之间的那道坎给你划出来了。适合谁一是正在准备考研复试或面试、需要把编译原理从“背概念”提升到“能推导”的人二是想把手头课程设计做成一个真正能跑的词法语法分析器、但不知道考核重点在哪的本科生三是工作后回头看形式语言和自动机、想用一份高质量试题做自测的一线开发者。它不能给你一个能编译 C 语言的编译器但它能帮你检验自己离“写出一个玩具编译器”还差哪些环节。下面我按自己的经验把这份题背后真正要考的东西一层层拆给你看并给出可复现的落地做法。2. 词法分析与有限自动机试题背后真正的“手工构造”能力2.1 词法分析为什么总考 Thompson 构造法与子集化算法西安交大这套题里词法分析部分几乎绕不开两个东西从正则表达式到 NFA 的 Thompson 构造法以及把 NFA 确定化为 DFA 的子集构造法。很多人觉得这俩算法简单但一落到试卷上就露馅——不是忘了怎么给连接运算符加显式的·就是合并等价状态时把终态标志丢了。我一般会建议把词法分析当成“用代码实现一个正则引擎”来复习而不是当自动机理论来背。具体到做题有一类高频题型是“给定正则式(a|b)*abb画出最小 DFA”。这里有个血泪经验如果你直接用子集构造法得到 DFA先别急着画状态图先检查有没有等价状态可以合并。以(a|b)*abb为例构造出的 DFA 往往有 56 个状态但最小化之后只剩 4 个。考试扣分点通常就在这没做最小化、或者把接受状态和非接受状态错误合并。如果要动手验证我建议用 Python 写一个极简的 Thompson 构造脚本只处理|、*、连接三个运算符然后把 NFA 跑一遍子集构造。下面是一个可以直接跑的最小实现框架# 用字典表示 NFAtrans[(state, char)] set(states) def thompson(regex): # 这里省略 shunting-yard 或递归下降解析正则的代码 # 核心返回 nfa_start, nfa_end, nfa_trans pass def subset_construction(nfa_start, nfa_end, nfa_trans, alphabet): dfa_start frozenset(e_closure({nfa_start}, nfa_trans)) dfa_states {dfa_start} dfa_trans {} dfa_accept set() unmarked [dfa_start] while unmarked: state_set unmarked.pop() if nfa_end in state_set: dfa_accept.add(state_set) for ch in alphabet: move_result set() for s in state_set: move_result | nfa_trans.get((s, ch), set()) next_state frozenset(e_closure(move_result, nfa_trans)) if next_state not in dfa_states: dfa_states.add(next_state) unmarked.append(next_state) dfa_trans[(state_set, ch)] next_state return dfa_start, dfa_states, dfa_trans, dfa_accept这段代码里e_closure是用栈实现的空串闭包计算frozenset是为了让 DFA 状态能被哈希。关键参数是nfa_end你必须在 Thompson 构造时保留唯一的终态否则子集化时无法判断新 DFA 状态是否接受。另一个容易踩坑的点是unmarked列表的弹出顺序——用 LIFO 还是 FIFO 不影响最终结果但会影响中间状态下标的编号考试时如果要求按教材顺序写出状态集就得统一用队列方式处理。2.2 从试题反推手工构造词法分析器时的三个边界坑这份题不会只让你画自动机大概率还会让你“为某种语言写词法分析器的状态转换图”。常见的是 C 语言子集标识符、关键字、无符号整数、关系运算符、!、、。这里有三个边界情况几乎每次考核都会出现第一个是“最长匹配”与“关键字优先”的冲突。比如输入intabc如果词法分析器先识别关键字int就会错误地把它拆成int和abc。正确的做法是标识符的匹配优先级高于关键字等读完整串后查符号表判断是否是关键字。考试里如果给的是 DFA 状态图就得把识别标识符的终态同时标成“可能为关键字”后续再查表。第二个是运算符的“贪心读入”。比如遇到不能读入就立即返回得再看下一个字符是否为。对应到状态转换图就是是一个中间状态读到才进入终态。很多同学把这个中间状态画成终态导致输入被拆成和这是典型扣分点。第三个是“无符号整数”的边界。如果语言规定整数不能有前导零那么09应该报错而不是返回两个数若不规定则09可以识别为 9。试题里通常会把这条规则写进说明做题前先看清楚。我见过不少人在这上面翻车原因是默认了 C 的规则但题目给的可能是 Pascal 或自定义语言规则。3. 语法分析从 LL(1) 到 LR(1)考试真正想让你掌握的冲突消解3.1 用 FIRST 与 FOLLOW 集快速构造预测分析表手工推导技巧语法分析在西安交大这份题里绝对是重头戏。最常见的题型是“给定文法判断是否为 LL(1)若不是则消除左递归并构造预测分析表”。这里有一条非常实用的做题顺序比死磕定义高效得多第一步先检查有没有直接左递归或间接左递归。有的话先消消完再算 FIRST 与 FOLLOW。第二步计算 FIRST 集时从下往上、从右往左推计算 FOLLOW 集时从上往下、从左往右推。第三步对每个产生式A → α把FIRST(α)中所有终结符除了空串 ε填入M[A][终结符]若ε ∈ FIRST(α)则把FOLLOW(A)中所有终结符填入M[A][终结符]。如果某个表项被重复填入那就不是 LL(1) 文法。这里有个容易忽略的细节消左递归后的文法会产生新的空串产生式进而把 FOLLOW 集的计算搞复杂。比如经典文法E → E T | T要先变成E → T E和E → T E | ε然后计算FOLLOW(E)时必须考虑FOLLOW(E)会传导过来。做题时建议每步都写清楚“因为谁导致了谁”这样即使结果错了也能拿到推导过程分。如果你想验证自己做对了可以写个小脚本自动计算 FIRST 和 FOLLOW。这个脚本很适合考试前自测因为它能快速对比你的手算结果。from collections import defaultdict def compute_first(grammar): # grammar: dict, 如 {E: [[T, E]], E: [[, T, E], [ε]]} first defaultdict(set) changed True while changed: changed False for lhs, productions in grammar.items(): for prod in productions: before set(first[lhs]) # 追踪能否推导出空串 nullable True for symbol in prod: if symbol ε: first[lhs].add(ε) break elif symbol.isupper(): first[lhs] | (first[symbol] - {ε}) if ε not in first[symbol]: nullable False break else: # 终结符 first[lhs].add(symbol) nullable False break if nullable: first[lhs].add(ε) if first[lhs] ! before: changed True return dict(first)这段代码初看能跑但有个坑它用isupper()判断非终结符如果你的文法符号是带下划线的E或Expr就会判错。考试时手算没问题写脚本自测时建议把终结符和非终结符用两个集合显式区分而不是靠大小写。另一个参数注意点产生式的右部如果同一个非终结符出现多次比如A → B B上面的循环会重复计算但因为用的是set合并结果不会出错只是效率低一点。语法分析章节在试卷里占比约 25%~30%这一块拿分的关键是“稳定计算不跳步”。3.2 SLR(1) 与 LR(1) 的分析表构造项目集族的闭包计算别跳步如果说 LL(1) 是送分题那 LR 系列就是真正的分水岭。西安交大的作业考核题很喜欢考“给定文法构造 LR(0) 项目集族并判断是否为 SLR(1)”进阶一点会考 LR(1) 项目集的继承与搜索符传播。很多同学在看懂教材例题后觉得自己会了一做新题就卡。问题几乎都出在闭包运算上。计算 LR(0) 项目集闭包时遇到A → α · B β要把所有B → γ的项加入闭包这个大家都会但到 LR(1) 时还需要为这些新加入的项目添加搜索符。搜索符的计算公式是FIRST(β)若β能推导出空串则还要加上原项目A → α · B β的搜索符。这里最容易犯的错是把FOLLOW(B)当搜索符加进去。SLR(1) 规约时要看FOLLOW(A)但 LR(1) 项目里的搜索符只来自FIRST(β)或继承两者完全不同。我见过有人把这两个概念混在一起构造出来的 LR(1) 自动机比教材少一半状态还自信满满地以为找到了“更优解”。做题时我习惯给每个项目显式标注搜索符比如[A → α · B β, a/b]如果β为空就直接继承原搜索符。当同一个状态里出现“移进-规约冲突”时用FOLLOW判断是否 SLR(1) 可解如果冲突消不掉再看是不是需要更精确的 LR(1) 搜索符。这套判断路径是考试的核心逻辑也是工作中写语法分析器生成器如 yacc/bison 类工具时真正会用到的思想。4. 从语法树到中间代码试题里的语义分析与三地址码生成4.1 属性文法怎么考继承属性与综合属性的传递顺序拿到这份题你会发现它不会停留在语法分析而是往下延伸到语义分析。典型题目是“为赋值语句x : y z * 2构造带属性标注的语法树”或“给定一个产生式写出它的语义动作”。这类题的本质是考察属性文法中的依赖关系。综合属性用于从子节点向父节点传递信息继承属性用于从父节点向子节点传递上下文。做题时有一条铁律先画语法树再按自底向上的顺序标综合属性最后按自顶向下标继承属性。由于考试时间有限不需要写出每一步属性计算的具体值而是要能识别“这个属性依赖哪个兄弟或父节点”。举个例子对于产生式E → E1 E2若需要生成三地址码通常用继承属性code来拼接代码列表用综合属性addr来存放结果变量名。若 E1 的addr是t1E2 的addr是t2则语义动作是生成新临时变量t3 t1 t2并令E.addr t3。这里有一个高频考点临时变量编号是全局计数器不是局部变量。很多人做题时把每个子表达式的临时变量都从t1重新编号导致三地址码冲突。正确做法是全程累加每生成一个新临时变量就temp_index 1这也是后续代码优化题里判断“活跃变量”的基础。4.2 用三地址码生成中间表示局部优化前必须懂的 DAG 合并中间代码生成之后接下来的考核点经常是基本块划分与 DAG 优化。这部分题目的实战性很强——给一段三地址码让你划分基本块、构造 DAG、再重构优化后的四元式。题目通常给这样一段代码t1 : a * b t2 : t1 c t3 : t1 * b t4 : t2 t3划分基本块的规则很简单遇到跳转指令或跳转目标就切开。但这道题没有跳转所以它是一个基本块。构造 DAG 时我一般用“值编号”方法每个节点代表一个运算符相同左右子树结构的节点合并。上例中t1 : a * b与t3 : t1 * b不是同一个表达式因为t1与a不同但若后面有t5 : a * b则t1和t5可以复用同一个 DAG 节点这就是公共子表达式删除。做题的步骤是先把每条语句拆成节点然后从下往上合并相同的子树。合并时注意如果左操作数是一个临时变量而该变量的赋值语句在更早位置且之间没有重新赋值则可以安全替换。考试里有个坑DAG 重构后生成的三地址码顺序不唯一只要保证依赖关系正确即可。有些同学发现“自己和标准答案顺序不同”就开始怀疑其实没必要只要每条指令使用的结果在最迟使用点的前面定义就行。关于省时技巧我建议在草稿纸上先画 DAG 节点编号不要直接重写四元式。这样即使时间不够也能得大部分分数。可视化工具方面可以用 Graphviz 的 dot 语言来画 DAG但考试时手绘更直击要点重点是别把 DAG 画成抽象语法树——DAG 是合并了公共子表达式的图节点可能有多个父节点。5. 类型检查与符号表作业题里最容易被低估的“软件工程”考点5.1 符号表的作用域栈与嵌套结构理解后才知道为什么叫“作业考核”西安交大这份题里有个很有意思的现象它不会直接问“符号表是什么”而是给你一段带嵌套作用域的代码让你画出符号表的查找过程。比如int x; void f() { int x; x 1; { int y; x 2; } }问在里层x 2时符号表如何查到正确的x。这背后的知识点是作用域栈 每层作用域独立符号表。查找时从栈顶往下找找到的第一个同名条目就是当前可见定义。这是几乎所有高级语言编译器的标准做法。很多人会栽在“何时入栈、何时出栈”上。块语句{}进入时创建新作用域并压栈离开时弹栈函数定义则需要把函数名插入当前作用域同时为函数参数建立全新的作用域。考试里容易混的点是“函数体内部能否访问外部变量”——能因为作用域链会继续向外层查找。这条特性在写解释器、实现静态作用域时非常关键。我在实际做编译器实验时很少用线性表存符号表而是用链表嵌套结构每个节点是一个dict。代码大概长这样class Scope: def __init__(self, parentNone): self.parent parent self.symbols {} def lookup(self, name): current self while current: if name in current.symbols: return current.symbols[name] current current.parent return None def insert(self, name, info): self.symbols[name] info这个数据结构虽然简单但已经足够支持大多数课程级编译器的语义分析。注意点insert时如果当前作用域已有同名变量不同语言有不同策略——C 语言是内层遮蔽外层但允许内层重复声明实际不允许但某些方言允许而 Python 这类动态语言则直接绑定新的。试题如果考语义检查通常会给你规则说明不要自己脑补。5.2 类型检查的隐式类型转换与错误报告两种策略的取舍类型检查是语义分析的另一个重头戏。考试题型包括“给定表达式判断能否通过类型检查”和“写出类型检查的翻译方案”。常见考点是整数与浮点数的隐式转换以及赋值语句的类型相容性。试题可能会故意设陷阱比如real x; int y; x : y合法而y : x不合法除非有强制转换。这类问题的核心是“类型相容”的定义。有些语言采用“相等”型相容有些采用“强制的隐式转换”型相容。做题时先看题目给的语言定义再判断。另一个常考点是数组越界不是类型错误——类型错误只在类型结构不匹配时报错。这看似简单但考试里有同学把A[i]的 i 不是整数也当成越界这是概念混淆。i 必须是整数类型如果 i 是浮点型那就是类型错误如果 i 是整型但值可能越界那是运行时错误编译器在静态阶段无法一概拒绝。这个区分在编译原理课程里属于“静态检查 vs 动态检查”但作业考核里经常把它藏在类型检查的大题中需要你写出错误报告的位置。6. 避坑与自查清单从西安交大这套题总结出的 4 个高频失分点6.1 坑 1FIRST 集与 FOLLOW 集的“空串传递”漏算现象手算文法S → A B; A → a | ε; B → b | ε的 FOLLOW 集时习惯性认为FOLLOW(S)只是$导致后续预测分析表构造出错。 原因A可以推导出空串所以FIRST(B)会并入FOLLOW(A)同时B也可以为空所以FOLLOW(S)也传播到FOLLOW(A)。漏掉任何一个空串传播整个 FOLLOW 集就错了。 解决计算 FOLLOW 时明确使用三步法——先看产生式右部该符号之后的部分若之后可空则加入左部非终结符的 FOLLOW最后不要忘了开始符号的 FOLLOW 里有$。每做完一步就回头检查是否有尚未处理的“可空链条”。这个坑在我复习时踩了不止一次几乎每次卡住都在空串上。6.2 坑 2LR(1) 项目集的搜索符在“β 为空”时没有继承原搜索符现象构造A → α · B的项目闭包时给B → γ加搜索符只加了FOLLOW(B)导致项目集数量比正确结果少。 原因把 SLR(1) 的规则误用到了 LR(1)。SLR(1) 是在规约时看FOLLOW而 LR(1) 在项目构造时就把上下文信息搜索符带进去了。若β为空B的搜索符应继承项目[A → α · B, a]中的a而不是FOLLOW(B)。 解决每次写 LR(1) 闭包时先问“.后面的字符串能推出空串吗”不能的话用FIRST(β)能的话用FIRST(β)并上原搜索符。检查结果时数一下项目个数如果跟教材标准答案差一个体量基本就是这里出了问题。6.3 坑 3符号表作用域用“函数级”而非“块级”现象在处理局部变量时只维护一个函数级符号表导致同函数内两个不同块里的变量名互相污染。 原因课程设计里图省事把insert和lookup都做在单个 dict 上忘了块结构需要栈式作用域。 解决用上面Scope类实现每进入一个{}就new Scope(current_scope)离开时current_scope current_scope.parent。这不仅是考试中的推导题需要写编译器实验时也推荐这么做。注意有些语言里for循环的初始化变量也具有块级作用域不能只对函数体建作用域。6.4 坑 4四元式与 DAG 重构时临时变量的生命周期想当然现象重构后的四元式里某些临时变量被提前覆盖导致计算结果错误。 原因DAG 优化允许删除公共子表达式但删除后必须检查该临时变量是否还被引用。例如t1 : a b后面用到t2 : t1 c如果优化时把后面用到的t1替换成t1的新版本就错了。 解决对每个临时变量记录“定义点”和“使用点”。DAG 重构时若该变量在基本块内被重新定义原变量名不可再用于新值必要时重命名临时变量。考试中如果题目没有特殊说明默认临时变量只在本基本块内有效跨基本块的使用需要额外标注。7. 把试题当测试用例用一份最小编译器工程验证你的掌握程度如果你不只是想应付考核而是想检验自己对编译原理的整体手感我建议你把这个思想转化为一个“最小编译器”实验用 300 行 Python 实现一个能处理let x 1 2 * 3这种表达式的解释器或翻译器。你不用做完整优化但要覆盖词法、语法、语义、中间代码四层。具体做法是先写一个递归下降语法分析器文法用expr → term expr | term这种左递归消解后的版本每个产生式对应一个函数返回值是“该表达式的中间代码列表”。例如term解析完返回一个临时变量名expr函数中把左右临时变量拼成新的四元式。这里有一个非常实用的技巧让每个语法分析函数同时返回“值”和“代码列表”这样就不需要单独画属性语法树直接边分析边生成代码。def parse_expr(): left_info parse_term() left_code, left_val left_info if peek() : match() right_info parse_expr() right_code, right_val right_info new_temp new_temp_var() code left_code right_code [(, left_val, right_val, new_temp)] return (code, new_temp) else: return (left_code, left_val)这个实现里parse_term是并行函数但实际项目中我倾向于让parse_expr调用parse_term而不是互相递归因为后者的递归深度受输入长度限制在 Python 里容易栈溢出。参数方面new_temp_var用全局计数器每次调用自增 1这样生成的临时变量名不会重复。这个实验做完后你可以回头重做西安交大那份 2022 年作业考核试题里的语法树题——你会发现书上的属性标注只是这个代码的另一种表达方式。如果时间充裕可以再加一步对生成的四元式做一个简单的 DAG 优化然后输出优化前后的指令数对比。这种验证方法比单纯刷题更能暴露问题。我自己的教训是当年课程设计写词法分析器时偷懒用正则库硬拆结果遇到/*注释嵌套就翻车后来老老实实按状态机重写才算理解为什么说“手工构造词法分析器”是编译原理的基本功。这份试题里没有直接考注释处理但如果你连注释状态转换图都不会画遇到它也就是迟早的事。希望这套“从试题到实现”的路径能帮到你。把每一道题当成一个编译器模块的行为规格而不是一道孤立的选择题你自然能看出西安交大这份作业考核的真正分量。本文还有配套的精品资源点击获取 西安交大2022编译原理作业考核：从词法分析到中间代码的完整链路
简介西安交通大学2022年《编译原理》作业考核试题是一份面向编译原理课程学习者的选择题练习文档内容围绕文法与句子、算符优先文法、程序基本块、无二义文法、Chomsky文法分类、LR(0)分析、符号表、中间代码生成等核心考点展开也涉及Pascal语言特性、上下文无关语言与自动机、静态分派等容易被忽视的细节适合期末复习、考研复试或面试前快速自测。压缩包共1个文件为docx文档大小约13KB打开即可使用。目前已有214人学习。题目后多处已标注正确选项可快速核对答案整套题覆盖编译器从词法分析、语法分析到目标代码生成的完整流程作为浓缩练习资料能帮助读者发现知识盲区并强化对抽象概念的理解整体轻量、便于碎片时间完成一轮针对性复习。1. 2022年西安交通大学编译原理作业考核试题不只是刷题是把你逼到能动手写编译器看到这个标题估计很多人的第一反应是“又是哪年的期末题”。但如果你真把西安交大这份 2022 年编译原理作业考核试题当成普通题库去刷那多半会吃亏。它名义上是“作业考核”实际内核是把编译原理里最劝退的几块硬骨头——词法分析、语法分析、中间代码生成、甚至局部优化——串成一条需要你亲手实现的完整链路。考的不是“LR(1) 项目集规范族怎么画”而是“给你一段代码你能不能说出它该怎么被翻译成三地址码、符号表怎么组织、冲突怎么消解”。这份题的价值恰恰在于它把“会做题”和“会做编译器”之间的那道坎给你划出来了。适合谁一是正在准备考研复试或面试、需要把编译原理从“背概念”提升到“能推导”的人二是想把手头课程设计做成一个真正能跑的词法语法分析器、但不知道考核重点在哪的本科生三是工作后回头看形式语言和自动机、想用一份高质量试题做自测的一线开发者。它不能给你一个能编译 C 语言的编译器但它能帮你检验自己离“写出一个玩具编译器”还差哪些环节。下面我按自己的经验把这份题背后真正要考的东西一层层拆给你看并给出可复现的落地做法。2. 词法分析与有限自动机试题背后真正的“手工构造”能力2.1 词法分析为什么总考 Thompson 构造法与子集化算法西安交大这套题里词法分析部分几乎绕不开两个东西从正则表达式到 NFA 的 Thompson 构造法以及把 NFA 确定化为 DFA 的子集构造法。很多人觉得这俩算法简单但一落到试卷上就露馅——不是忘了怎么给连接运算符加显式的·就是合并等价状态时把终态标志丢了。我一般会建议把词法分析当成“用代码实现一个正则引擎”来复习而不是当自动机理论来背。具体到做题有一类高频题型是“给定正则式(a|b)*abb画出最小 DFA”。这里有个血泪经验如果你直接用子集构造法得到 DFA先别急着画状态图先检查有没有等价状态可以合并。以(a|b)*abb为例构造出的 DFA 往往有 56 个状态但最小化之后只剩 4 个。考试扣分点通常就在这没做最小化、或者把接受状态和非接受状态错误合并。如果要动手验证我建议用 Python 写一个极简的 Thompson 构造脚本只处理|、*、连接三个运算符然后把 NFA 跑一遍子集构造。下面是一个可以直接跑的最小实现框架# 用字典表示 NFAtrans[(state, char)] set(states) def thompson(regex): # 这里省略 shunting-yard 或递归下降解析正则的代码 # 核心返回 nfa_start, nfa_end, nfa_trans pass def subset_construction(nfa_start, nfa_end, nfa_trans, alphabet): dfa_start frozenset(e_closure({nfa_start}, nfa_trans)) dfa_states {dfa_start} dfa_trans {} dfa_accept set() unmarked [dfa_start] while unmarked: state_set unmarked.pop() if nfa_end in state_set: dfa_accept.add(state_set) for ch in alphabet: move_result set() for s in state_set: move_result | nfa_trans.get((s, ch), set()) next_state frozenset(e_closure(move_result, nfa_trans)) if next_state not in dfa_states: dfa_states.add(next_state) unmarked.append(next_state) dfa_trans[(state_set, ch)] next_state return dfa_start, dfa_states, dfa_trans, dfa_accept这段代码里e_closure是用栈实现的空串闭包计算frozenset是为了让 DFA 状态能被哈希。关键参数是nfa_end你必须在 Thompson 构造时保留唯一的终态否则子集化时无法判断新 DFA 状态是否接受。另一个容易踩坑的点是unmarked列表的弹出顺序——用 LIFO 还是 FIFO 不影响最终结果但会影响中间状态下标的编号考试时如果要求按教材顺序写出状态集就得统一用队列方式处理。2.2 从试题反推手工构造词法分析器时的三个边界坑这份题不会只让你画自动机大概率还会让你“为某种语言写词法分析器的状态转换图”。常见的是 C 语言子集标识符、关键字、无符号整数、关系运算符、!、、。这里有三个边界情况几乎每次考核都会出现第一个是“最长匹配”与“关键字优先”的冲突。比如输入intabc如果词法分析器先识别关键字int就会错误地把它拆成int和abc。正确的做法是标识符的匹配优先级高于关键字等读完整串后查符号表判断是否是关键字。考试里如果给的是 DFA 状态图就得把识别标识符的终态同时标成“可能为关键字”后续再查表。第二个是运算符的“贪心读入”。比如遇到不能读入就立即返回得再看下一个字符是否为。对应到状态转换图就是是一个中间状态读到才进入终态。很多同学把这个中间状态画成终态导致输入被拆成和这是典型扣分点。第三个是“无符号整数”的边界。如果语言规定整数不能有前导零那么09应该报错而不是返回两个数若不规定则09可以识别为 9。试题里通常会把这条规则写进说明做题前先看清楚。我见过不少人在这上面翻车原因是默认了 C 的规则但题目给的可能是 Pascal 或自定义语言规则。3. 语法分析从 LL(1) 到 LR(1)考试真正想让你掌握的冲突消解3.1 用 FIRST 与 FOLLOW 集快速构造预测分析表手工推导技巧语法分析在西安交大这份题里绝对是重头戏。最常见的题型是“给定文法判断是否为 LL(1)若不是则消除左递归并构造预测分析表”。这里有一条非常实用的做题顺序比死磕定义高效得多第一步先检查有没有直接左递归或间接左递归。有的话先消消完再算 FIRST 与 FOLLOW。第二步计算 FIRST 集时从下往上、从右往左推计算 FOLLOW 集时从上往下、从左往右推。第三步对每个产生式A → α把FIRST(α)中所有终结符除了空串 ε填入M[A][终结符]若ε ∈ FIRST(α)则把FOLLOW(A)中所有终结符填入M[A][终结符]。如果某个表项被重复填入那就不是 LL(1) 文法。这里有个容易忽略的细节消左递归后的文法会产生新的空串产生式进而把 FOLLOW 集的计算搞复杂。比如经典文法E → E T | T要先变成E → T E和E → T E | ε然后计算FOLLOW(E)时必须考虑FOLLOW(E)会传导过来。做题时建议每步都写清楚“因为谁导致了谁”这样即使结果错了也能拿到推导过程分。如果你想验证自己做对了可以写个小脚本自动计算 FIRST 和 FOLLOW。这个脚本很适合考试前自测因为它能快速对比你的手算结果。from collections import defaultdict def compute_first(grammar): # grammar: dict, 如 {E: [[T, E]], E: [[, T, E], [ε]]} first defaultdict(set) changed True while changed: changed False for lhs, productions in grammar.items(): for prod in productions: before set(first[lhs]) # 追踪能否推导出空串 nullable True for symbol in prod: if symbol ε: first[lhs].add(ε) break elif symbol.isupper(): first[lhs] | (first[symbol] - {ε}) if ε not in first[symbol]: nullable False break else: # 终结符 first[lhs].add(symbol) nullable False break if nullable: first[lhs].add(ε) if first[lhs] ! before: changed True return dict(first)这段代码初看能跑但有个坑它用isupper()判断非终结符如果你的文法符号是带下划线的E或Expr就会判错。考试时手算没问题写脚本自测时建议把终结符和非终结符用两个集合显式区分而不是靠大小写。另一个参数注意点产生式的右部如果同一个非终结符出现多次比如A → B B上面的循环会重复计算但因为用的是set合并结果不会出错只是效率低一点。语法分析章节在试卷里占比约 25%~30%这一块拿分的关键是“稳定计算不跳步”。3.2 SLR(1) 与 LR(1) 的分析表构造项目集族的闭包计算别跳步如果说 LL(1) 是送分题那 LR 系列就是真正的分水岭。西安交大的作业考核题很喜欢考“给定文法构造 LR(0) 项目集族并判断是否为 SLR(1)”进阶一点会考 LR(1) 项目集的继承与搜索符传播。很多同学在看懂教材例题后觉得自己会了一做新题就卡。问题几乎都出在闭包运算上。计算 LR(0) 项目集闭包时遇到A → α · B β要把所有B → γ的项加入闭包这个大家都会但到 LR(1) 时还需要为这些新加入的项目添加搜索符。搜索符的计算公式是FIRST(β)若β能推导出空串则还要加上原项目A → α · B β的搜索符。这里最容易犯的错是把FOLLOW(B)当搜索符加进去。SLR(1) 规约时要看FOLLOW(A)但 LR(1) 项目里的搜索符只来自FIRST(β)或继承两者完全不同。我见过有人把这两个概念混在一起构造出来的 LR(1) 自动机比教材少一半状态还自信满满地以为找到了“更优解”。做题时我习惯给每个项目显式标注搜索符比如[A → α · B β, a/b]如果β为空就直接继承原搜索符。当同一个状态里出现“移进-规约冲突”时用FOLLOW判断是否 SLR(1) 可解如果冲突消不掉再看是不是需要更精确的 LR(1) 搜索符。这套判断路径是考试的核心逻辑也是工作中写语法分析器生成器如 yacc/bison 类工具时真正会用到的思想。4. 从语法树到中间代码试题里的语义分析与三地址码生成4.1 属性文法怎么考继承属性与综合属性的传递顺序拿到这份题你会发现它不会停留在语法分析而是往下延伸到语义分析。典型题目是“为赋值语句x : y z * 2构造带属性标注的语法树”或“给定一个产生式写出它的语义动作”。这类题的本质是考察属性文法中的依赖关系。综合属性用于从子节点向父节点传递信息继承属性用于从父节点向子节点传递上下文。做题时有一条铁律先画语法树再按自底向上的顺序标综合属性最后按自顶向下标继承属性。由于考试时间有限不需要写出每一步属性计算的具体值而是要能识别“这个属性依赖哪个兄弟或父节点”。举个例子对于产生式E → E1 E2若需要生成三地址码通常用继承属性code来拼接代码列表用综合属性addr来存放结果变量名。若 E1 的addr是t1E2 的addr是t2则语义动作是生成新临时变量t3 t1 t2并令E.addr t3。这里有一个高频考点临时变量编号是全局计数器不是局部变量。很多人做题时把每个子表达式的临时变量都从t1重新编号导致三地址码冲突。正确做法是全程累加每生成一个新临时变量就temp_index 1这也是后续代码优化题里判断“活跃变量”的基础。4.2 用三地址码生成中间表示局部优化前必须懂的 DAG 合并中间代码生成之后接下来的考核点经常是基本块划分与 DAG 优化。这部分题目的实战性很强——给一段三地址码让你划分基本块、构造 DAG、再重构优化后的四元式。题目通常给这样一段代码t1 : a * b t2 : t1 c t3 : t1 * b t4 : t2 t3划分基本块的规则很简单遇到跳转指令或跳转目标就切开。但这道题没有跳转所以它是一个基本块。构造 DAG 时我一般用“值编号”方法每个节点代表一个运算符相同左右子树结构的节点合并。上例中t1 : a * b与t3 : t1 * b不是同一个表达式因为t1与a不同但若后面有t5 : a * b则t1和t5可以复用同一个 DAG 节点这就是公共子表达式删除。做题的步骤是先把每条语句拆成节点然后从下往上合并相同的子树。合并时注意如果左操作数是一个临时变量而该变量的赋值语句在更早位置且之间没有重新赋值则可以安全替换。考试里有个坑DAG 重构后生成的三地址码顺序不唯一只要保证依赖关系正确即可。有些同学发现“自己和标准答案顺序不同”就开始怀疑其实没必要只要每条指令使用的结果在最迟使用点的前面定义就行。关于省时技巧我建议在草稿纸上先画 DAG 节点编号不要直接重写四元式。这样即使时间不够也能得大部分分数。可视化工具方面可以用 Graphviz 的 dot 语言来画 DAG但考试时手绘更直击要点重点是别把 DAG 画成抽象语法树——DAG 是合并了公共子表达式的图节点可能有多个父节点。5. 类型检查与符号表作业题里最容易被低估的“软件工程”考点5.1 符号表的作用域栈与嵌套结构理解后才知道为什么叫“作业考核”西安交大这份题里有个很有意思的现象它不会直接问“符号表是什么”而是给你一段带嵌套作用域的代码让你画出符号表的查找过程。比如int x; void f() { int x; x 1; { int y; x 2; } }问在里层x 2时符号表如何查到正确的x。这背后的知识点是作用域栈 每层作用域独立符号表。查找时从栈顶往下找找到的第一个同名条目就是当前可见定义。这是几乎所有高级语言编译器的标准做法。很多人会栽在“何时入栈、何时出栈”上。块语句{}进入时创建新作用域并压栈离开时弹栈函数定义则需要把函数名插入当前作用域同时为函数参数建立全新的作用域。考试里容易混的点是“函数体内部能否访问外部变量”——能因为作用域链会继续向外层查找。这条特性在写解释器、实现静态作用域时非常关键。我在实际做编译器实验时很少用线性表存符号表而是用链表嵌套结构每个节点是一个dict。代码大概长这样class Scope: def __init__(self, parentNone): self.parent parent self.symbols {} def lookup(self, name): current self while current: if name in current.symbols: return current.symbols[name] current current.parent return None def insert(self, name, info): self.symbols[name] info这个数据结构虽然简单但已经足够支持大多数课程级编译器的语义分析。注意点insert时如果当前作用域已有同名变量不同语言有不同策略——C 语言是内层遮蔽外层但允许内层重复声明实际不允许但某些方言允许而 Python 这类动态语言则直接绑定新的。试题如果考语义检查通常会给你规则说明不要自己脑补。5.2 类型检查的隐式类型转换与错误报告两种策略的取舍类型检查是语义分析的另一个重头戏。考试题型包括“给定表达式判断能否通过类型检查”和“写出类型检查的翻译方案”。常见考点是整数与浮点数的隐式转换以及赋值语句的类型相容性。试题可能会故意设陷阱比如real x; int y; x : y合法而y : x不合法除非有强制转换。这类问题的核心是“类型相容”的定义。有些语言采用“相等”型相容有些采用“强制的隐式转换”型相容。做题时先看题目给的语言定义再判断。另一个常考点是数组越界不是类型错误——类型错误只在类型结构不匹配时报错。这看似简单但考试里有同学把A[i]的 i 不是整数也当成越界这是概念混淆。i 必须是整数类型如果 i 是浮点型那就是类型错误如果 i 是整型但值可能越界那是运行时错误编译器在静态阶段无法一概拒绝。这个区分在编译原理课程里属于“静态检查 vs 动态检查”但作业考核里经常把它藏在类型检查的大题中需要你写出错误报告的位置。6. 避坑与自查清单从西安交大这套题总结出的 4 个高频失分点6.1 坑 1FIRST 集与 FOLLOW 集的“空串传递”漏算现象手算文法S → A B; A → a | ε; B → b | ε的 FOLLOW 集时习惯性认为FOLLOW(S)只是$导致后续预测分析表构造出错。 原因A可以推导出空串所以FIRST(B)会并入FOLLOW(A)同时B也可以为空所以FOLLOW(S)也传播到FOLLOW(A)。漏掉任何一个空串传播整个 FOLLOW 集就错了。 解决计算 FOLLOW 时明确使用三步法——先看产生式右部该符号之后的部分若之后可空则加入左部非终结符的 FOLLOW最后不要忘了开始符号的 FOLLOW 里有$。每做完一步就回头检查是否有尚未处理的“可空链条”。这个坑在我复习时踩了不止一次几乎每次卡住都在空串上。6.2 坑 2LR(1) 项目集的搜索符在“β 为空”时没有继承原搜索符现象构造A → α · B的项目闭包时给B → γ加搜索符只加了FOLLOW(B)导致项目集数量比正确结果少。 原因把 SLR(1) 的规则误用到了 LR(1)。SLR(1) 是在规约时看FOLLOW而 LR(1) 在项目构造时就把上下文信息搜索符带进去了。若β为空B的搜索符应继承项目[A → α · B, a]中的a而不是FOLLOW(B)。 解决每次写 LR(1) 闭包时先问“.后面的字符串能推出空串吗”不能的话用FIRST(β)能的话用FIRST(β)并上原搜索符。检查结果时数一下项目个数如果跟教材标准答案差一个体量基本就是这里出了问题。6.3 坑 3符号表作用域用“函数级”而非“块级”现象在处理局部变量时只维护一个函数级符号表导致同函数内两个不同块里的变量名互相污染。 原因课程设计里图省事把insert和lookup都做在单个 dict 上忘了块结构需要栈式作用域。 解决用上面Scope类实现每进入一个{}就new Scope(current_scope)离开时current_scope current_scope.parent。这不仅是考试中的推导题需要写编译器实验时也推荐这么做。注意有些语言里for循环的初始化变量也具有块级作用域不能只对函数体建作用域。6.4 坑 4四元式与 DAG 重构时临时变量的生命周期想当然现象重构后的四元式里某些临时变量被提前覆盖导致计算结果错误。 原因DAG 优化允许删除公共子表达式但删除后必须检查该临时变量是否还被引用。例如t1 : a b后面用到t2 : t1 c如果优化时把后面用到的t1替换成t1的新版本就错了。 解决对每个临时变量记录“定义点”和“使用点”。DAG 重构时若该变量在基本块内被重新定义原变量名不可再用于新值必要时重命名临时变量。考试中如果题目没有特殊说明默认临时变量只在本基本块内有效跨基本块的使用需要额外标注。7. 把试题当测试用例用一份最小编译器工程验证你的掌握程度如果你不只是想应付考核而是想检验自己对编译原理的整体手感我建议你把这个思想转化为一个“最小编译器”实验用 300 行 Python 实现一个能处理let x 1 2 * 3这种表达式的解释器或翻译器。你不用做完整优化但要覆盖词法、语法、语义、中间代码四层。具体做法是先写一个递归下降语法分析器文法用expr → term expr | term这种左递归消解后的版本每个产生式对应一个函数返回值是“该表达式的中间代码列表”。例如term解析完返回一个临时变量名expr函数中把左右临时变量拼成新的四元式。这里有一个非常实用的技巧让每个语法分析函数同时返回“值”和“代码列表”这样就不需要单独画属性语法树直接边分析边生成代码。def parse_expr(): left_info parse_term() left_code, left_val left_info if peek() : match() right_info parse_expr() right_code, right_val right_info new_temp new_temp_var() code left_code right_code [(, left_val, right_val, new_temp)] return (code, new_temp) else: return (left_code, left_val)这个实现里parse_term是并行函数但实际项目中我倾向于让parse_expr调用parse_term而不是互相递归因为后者的递归深度受输入长度限制在 Python 里容易栈溢出。参数方面new_temp_var用全局计数器每次调用自增 1这样生成的临时变量名不会重复。这个实验做完后你可以回头重做西安交大那份 2022 年作业考核试题里的语法树题——你会发现书上的属性标注只是这个代码的另一种表达方式。如果时间充裕可以再加一步对生成的四元式做一个简单的 DAG 优化然后输出优化前后的指令数对比。这种验证方法比单纯刷题更能暴露问题。我自己的教训是当年课程设计写词法分析器时偷懒用正则库硬拆结果遇到/*注释嵌套就翻车后来老老实实按状态机重写才算理解为什么说“手工构造词法分析器”是编译原理的基本功。这份试题里没有直接考注释处理但如果你连注释状态转换图都不会画遇到它也就是迟早的事。希望这套“从试题到实现”的路径能帮到你。把每一道题当成一个编译器模块的行为规格而不是一道孤立的选择题你自然能看出西安交大这份作业考核的真正分量。本文还有配套的精品资源点击获取