简介2022年西安交通大学编译原理作业考核试题是一份面向编译原理课程学习者与备考者的选择题练习文档。内容覆盖文法与句子、算符优先文法、程序基本块、无二义文法、Chomsky文法分类、LR(0)分析表、符号表、中间代码生成、Pascal语言特性等核心知识点并附有正确项标注适合期末自测、章节巩固和考研复习。资源为单个docx文档资源包仅13KB轻量便于快速下载阅读目前已有213人学习下载适合需要按考点查漏补缺的读者。通过完成这份试题可系统梳理编译程序从词法分析、语法分析到目标代码生成的各阶段要点理解上下文无关语言、活前缀、静态分派等易混淆概念对掌握编译原理主干知识有直接帮助也可作为教师组卷或出题的参考。1. 为什么一份作业考核试题比课件更值得逐行读先把结论放这儿编译原理这门课真正拉开差距的从来不是期末卷面而是作业考核里那些“让你亲手写一个词法分析器、手推一遍LL(1)分析表”的硬任务。西安交通大学这份2022年作业考核试题表面看是评分依据实际上是一份被压缩过的考点地图——它把正则表达式、DFA最小化、FIRST/FOLLOW集、LR分析表、中间代码生成这些核心知识点全部塞进了具体题目语境里比任何“编译原理第三版答案”都更能暴露你的真实掌握程度。针对准备面试、复习备考、或者想补实验短板的开发者这篇文章会按“理论先立住、再动手能复现”的思路把这份试题背后最常见的考点拆解成可执行的复习路径和学习方法。你不需要拿到原题也能根据下面的章节自己构建一套完整的编译原理实战训练方案。特别是那些卡在“上课听得懂、做题就手生”状态的人这篇文章给你的是一份可以直接抄的作业。2. 从正则到DFA词法分析试题背后的等价变换逻辑2.1 为什么词法分析总爱考“正则转DFA”词法分析是编译前端的第一关也是作业考核中出现频率最高的题型。基本的套路很固定——给你一个正则表达式要求构造NFA再转DFA最后最小化。但真正能区分“背答案”和“真理解”的是你能不能说清楚这三个步骤之间为什么要保留等价性。正则表达式描述的是“合法的单词集合”NFA是“带猜测的识别器”DFA是“确定性执行的识别器”三者描述的是同一种语言只是执行模型不同。作业考核里要求你画出状态转换图本质是在考察你是否理解这个等价链条。实际写代码时我一般会用一个最小实现来做转换验证。比如下面这个Python片段用字典维护状态转移表直接模拟DFA对输入串的识别过程def run_dfa(dfa, start, accept, input_str): state start for ch in input_str: if state not in dfa or ch not in dfa[state]: return False state dfa[state][ch] return state in accept # DFA: 识别 (a|b)*abb # 状态0是开始状态3是接受态 trans { 0: {a: 1, b: 0}, 1: {a: 1, b: 2}, 2: {a: 1, b: 3}, 3: {a: 1, b: 0} } print(run_dfa(trans, 0, {3}, aabb))这段代码的逻辑是逐字符驱动状态跳转如果某一步找不到对应转移说明输入串不合法全串走完落在接受状态才算匹配成功。参数说明dfa的键是当前状态值是一个字典字典的键是输入字符值是下一状态start是初态accept是接受状态集合用集合是为了支持多个终态。改造成自己的词法规则时只需要替换trans这个表就行。2.2 手工构造与子集构造法的边界在哪里作业考核中常见的要求是“用子集构造法将NFA确定化”这一步有明确的算法步骤但有一个非常容易踩的坑子集构造法产出的DFA状态数可能指数级膨胀。考试题通常选简单的正则所以手工能推完但实际写词法分析器时状态膨胀会让你的自动机难以调试。常见的工程做法是先构造NFA再对NFA做ε-闭包计算最后用哈希表对状态集合做去重编号。下面是一个简化的实现框架def epsilon_closure(nfa, states): stack list(states) closure set(states) while stack: s stack.pop() for t in nfa.get(s, {}).get(ε, []): if t not in closure: closure.add(t) stack.append(t) return closure def subset_construction(nfa, start, alphabet): start_closure frozenset(epsilon_closure(nfa, {start})) dfa_states {start_closure: 0} dfa_trans {} queue [start_closure] while queue: current queue.pop(0) for ch in alphabet: moved set() for s in current: moved.update(nfa.get(s, {}).get(ch, [])) if not moved: continue next_closure frozenset(epsilon_closure(nfa, moved)) if next_closure not in dfa_states: dfa_states[next_closure] len(dfa_states) queue.append(next_closure) dfa_trans[(dfa_states[current], ch)] dfa_states[next_closure] return dfa_states, dfa_transepsilon_closure负责从一组状态出发把所有能通过ε边到达的状态都收进来subset_construction外层循环遍历所有未处理的DFA状态集合内层循环逐个字符计算转移。参数说明nfa的每个状态映射到一个字典键是输入字符或ε值是下一状态列表alphabet是终结符集合。你需要留意这里的frozenset用法——用不可变集合做字典键是因为Python的可变集合不能哈希。这个细节在考试里体现为“状态集合的表示方法”在工程里体现为“去重与编号的实现”。2.3 状态最小化作业考核里最容易被跳过的步骤很多人在复习时会自动忽略DFA最小化觉得“能识别就行”。但作业考核试题一旦出现“化简下列DFA”你如果只做确定化不做最小化直接扣掉一半分。最小化的核心是划分法先把状态分成接受态和非接受态两组然后反复分裂直到每组内的状态在所有输入字符下都指向同一组为止。这里的“同一组”指的是目标状态所属的分组而不是具体的状态编号。初始分组是“接受态 vs 非接受态”因为这两者语义上不可能等价。后续分裂的条件是当前分组内的两个状态在读入某个字符后跳转到的状态位于不同分组则必须分开。做题时我会用一张表来跟踪分裂过程状态组用字母编号每轮分裂后更新字母编号直到不再变化。代码验证时可以用哈希表记录“状态 → 分组编号”的映射然后循环更新直到收敛。这个算法写起来不难真正容易错的是把初始分组搞错——非接受态内部也可能继续分裂比如一个非接受态在输入‘a’后进入接受态另一个非接受态在输入‘a’后进入非接受态两者必须分开。3. 语法分析LL(1)与LR(1)的考核侧重点不一样3.1 从FIRST/FOLLOW集计算到LL(1)判定语法分析在作业考核里占的分值通常最大因为它同时考察计算能力和理解深度。LL(1)类题型的第一小步永远是算FIRST集和FOLLOW集这两步算错后面的预测分析表全崩。FIRST集的定义一个符号串能推导出的所有终结符开头。计算时要反复迭代直到集合不再变化。FOLLOW集稍复杂某个非终结符在推导过程中可能紧跟其后的终结符集合。这里有一个常错点——产生式右部末尾的非终结符其FOLLOW集要把左部非终结符的FOLLOW集并进来。我做题时会写一个小脚本来验证手算结果尤其是处理左递归文法时手算特别容易漏迭代轮次def compute_first(grammar, nonterms, terms): first {nt: set() for nt in nonterms} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: for sym in rhs: if sym in terms: if sym not in first[lhs]: first[lhs].add(sym) changed True break elif sym in nonterms: before len(first[lhs]) first[lhs] | (first[sym] - {ε}) if len(first[lhs]) ! before: changed True if ε not in first[sym]: break else: if ε not in first[lhs]: first[lhs].add(ε) changed True return first这段代码的关键是while changed循环——FIRST集的计算是一个不动点迭代直到集合不再增长才算收敛。参数说明grammar是字典键是左部非终结符值是产生式右部的列表每个右部是一个符号元组nonterms和terms分别是非终结符与终结符集合。ε用字符串表示空串。如果你手算结果和这个脚本不一致优先检查是不是漏了“某个右部全部符号都能推导出ε才能把ε加入左部FIRST集”这个条件。FOLLOW集的计算和FIRST类似但多一个“把左部FOLLOW集传递给右部末尾非终结符”的规则。考试题型里最常见的搭配是给一个文法要求判断是否为LL(1)文法——判定条件是对同一个非终结符的多个产生式它们的FIRST集两两不相交且如果某个产生式能推导出ε该非终结符的FOLLOW集与其他产生式的FIRST集也不相交。这里需要特别小心“能推导出ε”的判断通常要借助“非终结符是否能推导出空串”的辅助计算。3.2 SLR(1)与LR(1)的差异作业考核常考的项目集闭包LR类题型的核心是构造LR(0)项目集族作业考核里经常要求你画出完整的项目集转换图。这部分的计算量很大但考察点非常固定项目集的闭包计算、goto函数的构造、SLR(1)分析表的填写。一个最常被忽略的细节构造闭包时如果圆点后面是一个非终结符要把该非终结符的所有产生式以“圆点在最左端”的形式加入当前项目集如果这些产生式里又有圆点后面是非终结符的继续加入直到不再有新项目。SLR(1)和LR(1)的核心区别在于归约时使用的向前看符号——SLR(1)用的是FOLLOW集LR(1)用的是特定上下文中的向前看符号集合。作业考核如果出“说明该文法为什么不是SLR(1)但可能是LR(1)”你需要在分析表里找冲突同一个项目集里某个状态下既存在移进项目又存在归约项目且归约项目对应的FOLLOW集包含移进符号就会产生移进-归约冲突。这种冲突出现的根本原因是FOLLOW集过于宽泛包含了实际上下文中不会出现的符号。我在复习时会把同一道题分别用SLR(1)和LR(1)各推一遍对照差异加深对向前看符号作用的理解。下面是一个LR(0)项目集闭包计算的示例代码def closure(items, grammar): result set(items) stack list(items) while stack: item stack.pop() lhs, rhs, dot item if dot len(rhs) and rhs[dot] in grammar: symbol rhs[dot] for production in grammar[symbol]: new_item (symbol, production, 0) if new_item not in result: result.add(new_item) stack.append(new_item) return resultitem用三元组表示左部、右部、圆点位置。闭包计算的逻辑和前面FIRST集迭代类似——新加入的项目可能触发更多项目加入所以要维护一个栈来持续扩展。参数说明grammar的值是产生式右部列表每个右部是一个符号元组。考试时你手推闭包代码则帮你验证。注意dot len(rhs)的条件——只有当圆点后确实是符号时才需要判断是否为非终结符并展开。如果圆点在末尾说明这是归约项目不参与闭包扩展。3.3 预测分析表与LR分析表填表规则背后的冲突点LL(1)预测分析表的填表规则对每个产生式A → α把FIRST(α)中的每个终结符填入M[A][a]位置如果α能推导出ε再把FOLLOW(A)中的每个终结符填入M[A][b]。这个规则本身不难难点在于表里出现多重入口时说明文法不是LL(1)的这时候题目会接着问“如何改造文法”——常见的两个手段是提取左公因子和消除左递归。提取左公因子不能保证把文法变成LL(1)这是一个高频易错点。LR分析表的填表规则对每个移进项目A → α·aβ在状态i和终结符a对应的表项填s_jj 是经过a转移到的状态对每个归约项目A → α·在状态i和FOLLOW(A)中的每个终结符填r_kk 是产生式编号。当你发现某个表项同时被移进和归约占据或者被两个不同产生式的归约占据冲突就产生了。考试里最典型的SLR(1)冲突场景是表达式文法中的E → E T | T这类结构。我在实际做题时会在填完表后用一条长输入串完整走一遍分析过程检查每一步栈顶状态和剩余输入是否与分析表一致。这一步看似费时却特别能暴露你对“状态栈”和“符号栈”两个栈同步变化的理解是否到位——很多人在模拟分析过程时只盯符号栈忘了状态栈导致半路推不下去。4. 语义分析与中间代码从属性文法到三地址码4.1 综合属性与继承属性的判定方法语义分析在作业考核中的典型题型是给定一个属性文法要求标注综合属性和继承属性并画出给定输入串的属性依赖图。综合属性的计算顺序是自底向上的由子节点的属性计算父节点的属性继承属性的计算顺序是自顶向下或从左到右由父节点或左兄弟节点的属性计算当前节点的属性。两者本质区别在于依赖方向综合属性只依赖子节点的属性继承属性依赖父节点、左兄弟或自身其他属性。判断一个属性是不是综合属性只需要看产生式左部非终结符的属性定义是否只使用右部符号的属性。判断继承属性则看产生式右部符号的属性定义是否使用左部或其他右部符号的属性。这个判定方法看起来简单实际操作时容易犯的错是把依赖图中边的方向搞反——综合属性的依赖边从子节点指向父节点继承属性的依赖边从父节点指向子节点或从左兄弟指向右兄弟。L属性文法在作业考核里是一个高频点核心要求是每个产生式的每个继承属性只依赖于左部继承属性、左兄弟属性或该产生式右部符号自身属性且每个综合属性只依赖右部属性。判断一个属性文法是否为L属性文法必须逐条产生式检查——漏掉任何一条结论就错了。S属性文法相对简单只含综合属性计算时只需要一次自底向上的遍历。实际做题时我建议先把所有属性和它们的依赖源列一张表再对照L属性文法的定义逐条核查不要凭感觉判断。4.2 三地址码生成的常见指令模式中间代码生成题通常要求把一段赋值语句或控制流语句翻译成三地址码题型比较固定赋值语句、if语句、while循环、数组引用。这里的关键是临时变量的引入以及回填backpatching技术的使用。没有掌握回填技术的人写出来的三地址码会带一堆“待填地址”标记而考试要求的是完整可执行序列。一个典型的while循环三地址码长这样100: if a b goto 103 101: t1 0 102: goto 107 103: t2 c d 104: a t2 105: t3 a - 1 106: goto 100 107: ...这段代码的逻辑第100行是条件跳转如果满足条件跳到循环体第101-102行是不满足条件时的语句第103-104行是循环体第105行更新循环变量第106行无条件跳回循环入口。回填发生在第102行和第106行——这两行的目标地址是在后续翻译过程中才确定的初始时留空等知道确切地址后再填入。语义分析在作业考核中的另一个高频考点是声明语句的类型检查通常结合属性文法来出题声明一个变量时用综合属性记录其类型后续使用该变量时要检查类型是否匹配。这部分的实用价值在面试里体现得很直接——很多编译原理面试题会问“如何实现类型检查”本质就是属性文法和符号表的协同应用。如果你在作业考核阶段把属性计算顺序理清楚了面试时能直接给出符号表的结构设计和类型检查的递归遍历方案。4.3 符号表作用域块结构语言的插入与查找符号表在作业考核里很少单独出大题但经常作为语义分析题目的前置条件出现。比如题目给一段带嵌套块的类C代码要求说明符号表在进入和退出块时如何插入和删除条目。常见做法是采用栈式符号表每进入一个块压入一层新的作用域每退出一个块弹出整层作用域。查找变量时从栈顶往下逐层查找找到即返回。手工模拟时我会画一张表按代码执行顺序一行行记录符号表的层次变化尤其注意同名的内层变量遮蔽外层变量——查找时先命中内层。这里的坑是“弹出时忘记恢复外层符号的可见性”实际代码实现时如果符号表条目带作用域编号弹出后只需要把当前作用域编号递减即可不需要物理删除条目。5. 从作业考核到面试一套可复用的备考与答题方法论5.1 高频考点的优先级排序与复习节奏如果你复习时间有限优先攻克词法分析正则转DFA、最小化和语法分析FIRST/FOLLOW计算、LL(1)判定、LR分析表构造这两块占作业考核分值的比重通常在60%以上。语义分析考概念理解中间代码考翻译能力优先级稍低。一个可行的复习节奏是第一轮按“词法→语法→语义→中间代码”顺序过知识点每章都动手做两道真题型第二轮专门修炼手算能力比如计时完成一个DFA最小化题或者一个带冲突判定的LR(1)分析表构造第三轮把重点题目整理成错题本重点记录自己踩坑的判断点比如FOLLOW集计算时漏了末尾非终结符传递、判定LL(1)时遗漏ε产生式条件。5.2 考试答题时的顺序与检查清单做题顺序建议先易后难先做正则和DFA题再做FIRST/FOLLOW计算然后写分析表最后做语义和中间代码。原因是计算型题目需要头脑清醒适合优先处理概念型题目放在后面即使时间紧张也不会损失太多分数。交卷前用下面这个检查清单过一遍检查项具体内容FIRST集是否包含ε终结符是否完整是否反复迭代到稳定FOLLOW集是否包含结束符$右部末尾非终结符是否传递左部FOLLOW集LL(1)判定是否检查了“能推导出ε的产生式与FOLLOW集相交”条件LR项目集闭包是否完整goto是否有遗漏归约项目是否标全三地址码临时变量编号是否连续跳转目标是否回填这份清单直接对应作业考核的失分重灾区检查一遍大约需要五分钟但往往能救回5-10分。5.3 把作业题改造成面试模拟题的技巧最后一个技巧把作业考核里的计算题反向改造成面试问答题。比如“正则转DFA”这道题面试官大概率会问“NFA与DFA的区别是什么”“为什么实际词法分析器不用NFA直接匹配”等问题。你提前在作业题旁边标注对应面试题复习时就能一鱼两吃。类似地“LR(1)分析表构造”对应的问题是“SLR与LR(1)的区别”“什么时候用LALR”中间代码生成对应“什么是三地址码”“SSA与三地址码的关系”。我在准备阶段会把每道作业题对应的面试问题抄在题目旁边形成一份“题-问对照表”复习一遍等于同时准备了作业和面试。最终你会发现把作业考核的每道题吃透到能手推、能讲清原理这比刷十套试卷都更有价值——因为你的知识结构从“会做题”变成了“能解释”而后者才是面试官真正考察的能力。本文还有配套的精品资源点击获取 
长河君 · 2026/9/19 1:35:38 · 阅读 1.2k 编译原理作业考核全解析：从词法分析到LR分析表的手写实战指南
简介2022年西安交通大学编译原理作业考核试题是一份面向编译原理课程学习者与备考者的选择题练习文档。内容覆盖文法与句子、算符优先文法、程序基本块、无二义文法、Chomsky文法分类、LR(0)分析表、符号表、中间代码生成、Pascal语言特性等核心知识点并附有正确项标注适合期末自测、章节巩固和考研复习。资源为单个docx文档资源包仅13KB轻量便于快速下载阅读目前已有213人学习下载适合需要按考点查漏补缺的读者。通过完成这份试题可系统梳理编译程序从词法分析、语法分析到目标代码生成的各阶段要点理解上下文无关语言、活前缀、静态分派等易混淆概念对掌握编译原理主干知识有直接帮助也可作为教师组卷或出题的参考。1. 为什么一份作业考核试题比课件更值得逐行读先把结论放这儿编译原理这门课真正拉开差距的从来不是期末卷面而是作业考核里那些“让你亲手写一个词法分析器、手推一遍LL(1)分析表”的硬任务。西安交通大学这份2022年作业考核试题表面看是评分依据实际上是一份被压缩过的考点地图——它把正则表达式、DFA最小化、FIRST/FOLLOW集、LR分析表、中间代码生成这些核心知识点全部塞进了具体题目语境里比任何“编译原理第三版答案”都更能暴露你的真实掌握程度。针对准备面试、复习备考、或者想补实验短板的开发者这篇文章会按“理论先立住、再动手能复现”的思路把这份试题背后最常见的考点拆解成可执行的复习路径和学习方法。你不需要拿到原题也能根据下面的章节自己构建一套完整的编译原理实战训练方案。特别是那些卡在“上课听得懂、做题就手生”状态的人这篇文章给你的是一份可以直接抄的作业。2. 从正则到DFA词法分析试题背后的等价变换逻辑2.1 为什么词法分析总爱考“正则转DFA”词法分析是编译前端的第一关也是作业考核中出现频率最高的题型。基本的套路很固定——给你一个正则表达式要求构造NFA再转DFA最后最小化。但真正能区分“背答案”和“真理解”的是你能不能说清楚这三个步骤之间为什么要保留等价性。正则表达式描述的是“合法的单词集合”NFA是“带猜测的识别器”DFA是“确定性执行的识别器”三者描述的是同一种语言只是执行模型不同。作业考核里要求你画出状态转换图本质是在考察你是否理解这个等价链条。实际写代码时我一般会用一个最小实现来做转换验证。比如下面这个Python片段用字典维护状态转移表直接模拟DFA对输入串的识别过程def run_dfa(dfa, start, accept, input_str): state start for ch in input_str: if state not in dfa or ch not in dfa[state]: return False state dfa[state][ch] return state in accept # DFA: 识别 (a|b)*abb # 状态0是开始状态3是接受态 trans { 0: {a: 1, b: 0}, 1: {a: 1, b: 2}, 2: {a: 1, b: 3}, 3: {a: 1, b: 0} } print(run_dfa(trans, 0, {3}, aabb))这段代码的逻辑是逐字符驱动状态跳转如果某一步找不到对应转移说明输入串不合法全串走完落在接受状态才算匹配成功。参数说明dfa的键是当前状态值是一个字典字典的键是输入字符值是下一状态start是初态accept是接受状态集合用集合是为了支持多个终态。改造成自己的词法规则时只需要替换trans这个表就行。2.2 手工构造与子集构造法的边界在哪里作业考核中常见的要求是“用子集构造法将NFA确定化”这一步有明确的算法步骤但有一个非常容易踩的坑子集构造法产出的DFA状态数可能指数级膨胀。考试题通常选简单的正则所以手工能推完但实际写词法分析器时状态膨胀会让你的自动机难以调试。常见的工程做法是先构造NFA再对NFA做ε-闭包计算最后用哈希表对状态集合做去重编号。下面是一个简化的实现框架def epsilon_closure(nfa, states): stack list(states) closure set(states) while stack: s stack.pop() for t in nfa.get(s, {}).get(ε, []): if t not in closure: closure.add(t) stack.append(t) return closure def subset_construction(nfa, start, alphabet): start_closure frozenset(epsilon_closure(nfa, {start})) dfa_states {start_closure: 0} dfa_trans {} queue [start_closure] while queue: current queue.pop(0) for ch in alphabet: moved set() for s in current: moved.update(nfa.get(s, {}).get(ch, [])) if not moved: continue next_closure frozenset(epsilon_closure(nfa, moved)) if next_closure not in dfa_states: dfa_states[next_closure] len(dfa_states) queue.append(next_closure) dfa_trans[(dfa_states[current], ch)] dfa_states[next_closure] return dfa_states, dfa_transepsilon_closure负责从一组状态出发把所有能通过ε边到达的状态都收进来subset_construction外层循环遍历所有未处理的DFA状态集合内层循环逐个字符计算转移。参数说明nfa的每个状态映射到一个字典键是输入字符或ε值是下一状态列表alphabet是终结符集合。你需要留意这里的frozenset用法——用不可变集合做字典键是因为Python的可变集合不能哈希。这个细节在考试里体现为“状态集合的表示方法”在工程里体现为“去重与编号的实现”。2.3 状态最小化作业考核里最容易被跳过的步骤很多人在复习时会自动忽略DFA最小化觉得“能识别就行”。但作业考核试题一旦出现“化简下列DFA”你如果只做确定化不做最小化直接扣掉一半分。最小化的核心是划分法先把状态分成接受态和非接受态两组然后反复分裂直到每组内的状态在所有输入字符下都指向同一组为止。这里的“同一组”指的是目标状态所属的分组而不是具体的状态编号。初始分组是“接受态 vs 非接受态”因为这两者语义上不可能等价。后续分裂的条件是当前分组内的两个状态在读入某个字符后跳转到的状态位于不同分组则必须分开。做题时我会用一张表来跟踪分裂过程状态组用字母编号每轮分裂后更新字母编号直到不再变化。代码验证时可以用哈希表记录“状态 → 分组编号”的映射然后循环更新直到收敛。这个算法写起来不难真正容易错的是把初始分组搞错——非接受态内部也可能继续分裂比如一个非接受态在输入‘a’后进入接受态另一个非接受态在输入‘a’后进入非接受态两者必须分开。3. 语法分析LL(1)与LR(1)的考核侧重点不一样3.1 从FIRST/FOLLOW集计算到LL(1)判定语法分析在作业考核里占的分值通常最大因为它同时考察计算能力和理解深度。LL(1)类题型的第一小步永远是算FIRST集和FOLLOW集这两步算错后面的预测分析表全崩。FIRST集的定义一个符号串能推导出的所有终结符开头。计算时要反复迭代直到集合不再变化。FOLLOW集稍复杂某个非终结符在推导过程中可能紧跟其后的终结符集合。这里有一个常错点——产生式右部末尾的非终结符其FOLLOW集要把左部非终结符的FOLLOW集并进来。我做题时会写一个小脚本来验证手算结果尤其是处理左递归文法时手算特别容易漏迭代轮次def compute_first(grammar, nonterms, terms): first {nt: set() for nt in nonterms} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: for sym in rhs: if sym in terms: if sym not in first[lhs]: first[lhs].add(sym) changed True break elif sym in nonterms: before len(first[lhs]) first[lhs] | (first[sym] - {ε}) if len(first[lhs]) ! before: changed True if ε not in first[sym]: break else: if ε not in first[lhs]: first[lhs].add(ε) changed True return first这段代码的关键是while changed循环——FIRST集的计算是一个不动点迭代直到集合不再增长才算收敛。参数说明grammar是字典键是左部非终结符值是产生式右部的列表每个右部是一个符号元组nonterms和terms分别是非终结符与终结符集合。ε用字符串表示空串。如果你手算结果和这个脚本不一致优先检查是不是漏了“某个右部全部符号都能推导出ε才能把ε加入左部FIRST集”这个条件。FOLLOW集的计算和FIRST类似但多一个“把左部FOLLOW集传递给右部末尾非终结符”的规则。考试题型里最常见的搭配是给一个文法要求判断是否为LL(1)文法——判定条件是对同一个非终结符的多个产生式它们的FIRST集两两不相交且如果某个产生式能推导出ε该非终结符的FOLLOW集与其他产生式的FIRST集也不相交。这里需要特别小心“能推导出ε”的判断通常要借助“非终结符是否能推导出空串”的辅助计算。3.2 SLR(1)与LR(1)的差异作业考核常考的项目集闭包LR类题型的核心是构造LR(0)项目集族作业考核里经常要求你画出完整的项目集转换图。这部分的计算量很大但考察点非常固定项目集的闭包计算、goto函数的构造、SLR(1)分析表的填写。一个最常被忽略的细节构造闭包时如果圆点后面是一个非终结符要把该非终结符的所有产生式以“圆点在最左端”的形式加入当前项目集如果这些产生式里又有圆点后面是非终结符的继续加入直到不再有新项目。SLR(1)和LR(1)的核心区别在于归约时使用的向前看符号——SLR(1)用的是FOLLOW集LR(1)用的是特定上下文中的向前看符号集合。作业考核如果出“说明该文法为什么不是SLR(1)但可能是LR(1)”你需要在分析表里找冲突同一个项目集里某个状态下既存在移进项目又存在归约项目且归约项目对应的FOLLOW集包含移进符号就会产生移进-归约冲突。这种冲突出现的根本原因是FOLLOW集过于宽泛包含了实际上下文中不会出现的符号。我在复习时会把同一道题分别用SLR(1)和LR(1)各推一遍对照差异加深对向前看符号作用的理解。下面是一个LR(0)项目集闭包计算的示例代码def closure(items, grammar): result set(items) stack list(items) while stack: item stack.pop() lhs, rhs, dot item if dot len(rhs) and rhs[dot] in grammar: symbol rhs[dot] for production in grammar[symbol]: new_item (symbol, production, 0) if new_item not in result: result.add(new_item) stack.append(new_item) return resultitem用三元组表示左部、右部、圆点位置。闭包计算的逻辑和前面FIRST集迭代类似——新加入的项目可能触发更多项目加入所以要维护一个栈来持续扩展。参数说明grammar的值是产生式右部列表每个右部是一个符号元组。考试时你手推闭包代码则帮你验证。注意dot len(rhs)的条件——只有当圆点后确实是符号时才需要判断是否为非终结符并展开。如果圆点在末尾说明这是归约项目不参与闭包扩展。3.3 预测分析表与LR分析表填表规则背后的冲突点LL(1)预测分析表的填表规则对每个产生式A → α把FIRST(α)中的每个终结符填入M[A][a]位置如果α能推导出ε再把FOLLOW(A)中的每个终结符填入M[A][b]。这个规则本身不难难点在于表里出现多重入口时说明文法不是LL(1)的这时候题目会接着问“如何改造文法”——常见的两个手段是提取左公因子和消除左递归。提取左公因子不能保证把文法变成LL(1)这是一个高频易错点。LR分析表的填表规则对每个移进项目A → α·aβ在状态i和终结符a对应的表项填s_jj 是经过a转移到的状态对每个归约项目A → α·在状态i和FOLLOW(A)中的每个终结符填r_kk 是产生式编号。当你发现某个表项同时被移进和归约占据或者被两个不同产生式的归约占据冲突就产生了。考试里最典型的SLR(1)冲突场景是表达式文法中的E → E T | T这类结构。我在实际做题时会在填完表后用一条长输入串完整走一遍分析过程检查每一步栈顶状态和剩余输入是否与分析表一致。这一步看似费时却特别能暴露你对“状态栈”和“符号栈”两个栈同步变化的理解是否到位——很多人在模拟分析过程时只盯符号栈忘了状态栈导致半路推不下去。4. 语义分析与中间代码从属性文法到三地址码4.1 综合属性与继承属性的判定方法语义分析在作业考核中的典型题型是给定一个属性文法要求标注综合属性和继承属性并画出给定输入串的属性依赖图。综合属性的计算顺序是自底向上的由子节点的属性计算父节点的属性继承属性的计算顺序是自顶向下或从左到右由父节点或左兄弟节点的属性计算当前节点的属性。两者本质区别在于依赖方向综合属性只依赖子节点的属性继承属性依赖父节点、左兄弟或自身其他属性。判断一个属性是不是综合属性只需要看产生式左部非终结符的属性定义是否只使用右部符号的属性。判断继承属性则看产生式右部符号的属性定义是否使用左部或其他右部符号的属性。这个判定方法看起来简单实际操作时容易犯的错是把依赖图中边的方向搞反——综合属性的依赖边从子节点指向父节点继承属性的依赖边从父节点指向子节点或从左兄弟指向右兄弟。L属性文法在作业考核里是一个高频点核心要求是每个产生式的每个继承属性只依赖于左部继承属性、左兄弟属性或该产生式右部符号自身属性且每个综合属性只依赖右部属性。判断一个属性文法是否为L属性文法必须逐条产生式检查——漏掉任何一条结论就错了。S属性文法相对简单只含综合属性计算时只需要一次自底向上的遍历。实际做题时我建议先把所有属性和它们的依赖源列一张表再对照L属性文法的定义逐条核查不要凭感觉判断。4.2 三地址码生成的常见指令模式中间代码生成题通常要求把一段赋值语句或控制流语句翻译成三地址码题型比较固定赋值语句、if语句、while循环、数组引用。这里的关键是临时变量的引入以及回填backpatching技术的使用。没有掌握回填技术的人写出来的三地址码会带一堆“待填地址”标记而考试要求的是完整可执行序列。一个典型的while循环三地址码长这样100: if a b goto 103 101: t1 0 102: goto 107 103: t2 c d 104: a t2 105: t3 a - 1 106: goto 100 107: ...这段代码的逻辑第100行是条件跳转如果满足条件跳到循环体第101-102行是不满足条件时的语句第103-104行是循环体第105行更新循环变量第106行无条件跳回循环入口。回填发生在第102行和第106行——这两行的目标地址是在后续翻译过程中才确定的初始时留空等知道确切地址后再填入。语义分析在作业考核中的另一个高频考点是声明语句的类型检查通常结合属性文法来出题声明一个变量时用综合属性记录其类型后续使用该变量时要检查类型是否匹配。这部分的实用价值在面试里体现得很直接——很多编译原理面试题会问“如何实现类型检查”本质就是属性文法和符号表的协同应用。如果你在作业考核阶段把属性计算顺序理清楚了面试时能直接给出符号表的结构设计和类型检查的递归遍历方案。4.3 符号表作用域块结构语言的插入与查找符号表在作业考核里很少单独出大题但经常作为语义分析题目的前置条件出现。比如题目给一段带嵌套块的类C代码要求说明符号表在进入和退出块时如何插入和删除条目。常见做法是采用栈式符号表每进入一个块压入一层新的作用域每退出一个块弹出整层作用域。查找变量时从栈顶往下逐层查找找到即返回。手工模拟时我会画一张表按代码执行顺序一行行记录符号表的层次变化尤其注意同名的内层变量遮蔽外层变量——查找时先命中内层。这里的坑是“弹出时忘记恢复外层符号的可见性”实际代码实现时如果符号表条目带作用域编号弹出后只需要把当前作用域编号递减即可不需要物理删除条目。5. 从作业考核到面试一套可复用的备考与答题方法论5.1 高频考点的优先级排序与复习节奏如果你复习时间有限优先攻克词法分析正则转DFA、最小化和语法分析FIRST/FOLLOW计算、LL(1)判定、LR分析表构造这两块占作业考核分值的比重通常在60%以上。语义分析考概念理解中间代码考翻译能力优先级稍低。一个可行的复习节奏是第一轮按“词法→语法→语义→中间代码”顺序过知识点每章都动手做两道真题型第二轮专门修炼手算能力比如计时完成一个DFA最小化题或者一个带冲突判定的LR(1)分析表构造第三轮把重点题目整理成错题本重点记录自己踩坑的判断点比如FOLLOW集计算时漏了末尾非终结符传递、判定LL(1)时遗漏ε产生式条件。5.2 考试答题时的顺序与检查清单做题顺序建议先易后难先做正则和DFA题再做FIRST/FOLLOW计算然后写分析表最后做语义和中间代码。原因是计算型题目需要头脑清醒适合优先处理概念型题目放在后面即使时间紧张也不会损失太多分数。交卷前用下面这个检查清单过一遍检查项具体内容FIRST集是否包含ε终结符是否完整是否反复迭代到稳定FOLLOW集是否包含结束符$右部末尾非终结符是否传递左部FOLLOW集LL(1)判定是否检查了“能推导出ε的产生式与FOLLOW集相交”条件LR项目集闭包是否完整goto是否有遗漏归约项目是否标全三地址码临时变量编号是否连续跳转目标是否回填这份清单直接对应作业考核的失分重灾区检查一遍大约需要五分钟但往往能救回5-10分。5.3 把作业题改造成面试模拟题的技巧最后一个技巧把作业考核里的计算题反向改造成面试问答题。比如“正则转DFA”这道题面试官大概率会问“NFA与DFA的区别是什么”“为什么实际词法分析器不用NFA直接匹配”等问题。你提前在作业题旁边标注对应面试题复习时就能一鱼两吃。类似地“LR(1)分析表构造”对应的问题是“SLR与LR(1)的区别”“什么时候用LALR”中间代码生成对应“什么是三地址码”“SSA与三地址码的关系”。我在准备阶段会把每道作业题对应的面试问题抄在题目旁边形成一份“题-问对照表”复习一遍等于同时准备了作业和面试。最终你会发现把作业考核的每道题吃透到能手推、能讲清原理这比刷十套试卷都更有价值——因为你的知识结构从“会做题”变成了“能解释”而后者才是面试官真正考察的能力。本文还有配套的精品资源点击获取