简介这份哈工大编译原理期末复习资料以PDF形式打包发布主要面向计算机专业本科生、考研复习者以及需要系统梳理编译原理知识框架的读者。内容完整覆盖编译系统结构、语言及其文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成和代码优化等核心模块并对DFA/NFA、正则表达式、文法分类与分析树、三地址码与四元式等高频考点做了条理化整理适合期末冲刺和考前查漏补缺。压缩包共1个文件单份PDF约31.14MB排版规整便于在电脑或平板上按章节翻阅。这份资料发布以来已有2311人学习下载是结合课程讲义与教材要点凝练出的完整复习指南。1. 编译原理期末复习考前一周怎么把整门课串成一张可执行的图很多学校的编译原理期末复习最难受的不是题难而是不知道这门课到底在考什么。两周前还能看懂词法分析一周前语法分析开始发懵临考前发现语义分析、中间代码、代码生成全混在一起背了一堆术语却连不上一条流水线。这份复习清单把整门课按前端、中间、后端三层拆开从正则表达式到 DFA从 LL(1) 到 LR 家族从属性文法到三地址码再落到存储布局、代码生成和优化。每个环节都给了能直接照着算的步骤、验证用的小代码和丢分点。它适合期末冲刺的本科生也适合考研复试前想快速重拾体系的人。我写它时默认你已经上过课、能看懂基本概念只是缺一个把散点连成网的主心骨。2. 词法分析复习提分点正则、NFA、DFA 的顺序与最小实现2.1 正则表达式、NFA、DFA 一张表理清考法词法分析在卷面上占分不算多但它是第一道能稳定拿分的大题。几乎所有学校都考同一件事给一个正则表达式用 Thompson 构造法画出 NFA再用子集构造法转成 DFA有时还要最小化。最容易踩的坑是一上来就背状态转换图而不知道这三层结构之间的顺序关系。我的建议是先记住一条主线正则表达式是给人看的需求NFA 是机器容易生成的中间表示DFA 是机器真正执行的状态机最小化是让执行器更省内存的后期优化。考试如果问“为什么不用 NFA 直接识别”标准答案要落在两点上NFA 有 ε 边且同一输入可能进入多个状态模拟时要做不确定搜索DFA 的每个状态对每个输入只有唯一后继识别过程是线性的不回溯。按这条主线复习Thompson 构造法、子集构造法、DFA 最小化三个大题就不会串台。下表是我考前贴在桌面上的对照表三者的关系看一眼就能回忆起来。表示形式怎么生成状态数量典型考法正则表达式需求的文字描述无状态写正则、判断等价NFAThompson 构造法近似产生式长度画状态图、识别 ε 边DFA子集构造法指数级但通常可控画转移表、识别串最小化 DFA状态合并最少合并等价状态、判断终态这一节有个大家常忽略的细节Thompson 构造法为每个运算符引入新状态连接运算符直接把两个片段串起来选择运算符引入两个 ε 边分支闭包运算符引入一条回到起点的 ε 边和一个新的终态。画 NFA 时如果总是少状态多半是闭包的 ε 边没画全。考试时可以用“每条边都要能从起点走到终态”做一次反向检查。2.2 用 Python 手写子集构造法验证手算不出错子集构造法的核心操作只有两个ε-闭包和 move。手算 NFA 转 DFA 翻车九成问题出在漏掉 ε 闭包。我建议考前把下面这段代码对着标准教材的经典例子跑一遍再用输出结果去对你自己手算的转移表。判断一个手算结果对不对这个办法特别快。nfa { S: {a: {A}, : {B}}, A: {b: {S}}, B: {a: {C}, : {S}}, C: {b: {D}}, } alphabet [a, b] def eps_closure(states, nfa): 返回 states 沿任意条 ε 边能到达的全部状态 stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.get(s, {}).get(, set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure def move(states, symbol, nfa): 返回 states 读入 symbol 一步能到达的状态 result set() for s in states: result | nfa.get(s, {}).get(symbol, set()) return result def build_dfa(nfa, alphabet, startS): dfa {} start_set frozenset(eps_closure({start}, nfa)) seen {start_set} queue [start_set] while queue: cur queue.pop() for sym in alphabet: nxt frozenset(eps_closure(move(cur, sym, nfa), nfa)) if not nxt: continue dfa[(cur, sym)] nxt if nxt not in seen: seen.add(nxt) queue.append(nxt) return dfa, seen dfa, states build_dfa(nfa, alphabet) for (src, sym), dst in dfa.items(): print(sorted(src), --, sym, --, sorted(dst))逻辑说明NFA 用嵌套字典表示第一层键是状态名第二层键是输入符号值是目标状态集合用空字符串表示 ε 边。eps_closure用栈做一次图遍历把从当前状态出发经过任意条 ε 边可到达的状态全部收进集合move把当前状态集合读入一个符号后能到达的所有状态并起来build_dfa从初始状态的 ε 闭包出发对字母表里的每个符号计算目标闭包形成 DFA 的一条边直到没有新的状态集出现。输出里的每个 frozenset 就是 DFA 的一个状态对应教材上的{S,B}或{A,D}这种编号。参数说明start是 NFA 的初态名默认写Salphabet必须手动给全漏掉符号就不会生成对应的转移用frozenset做 key是因为 set 本身不可哈希直接当字典键会报错。跑完对答案时如果你手算的 DFA 少了某个状态集多半是某次 ε 闭包漏了内部的 ε 边如果你多了状态集多半是没做闭包就急着对符号转移。2.3 DFA 最小化与词法错误恢复5 个必背考点DFA 最小化的考法是给出一个 DFA要求合并等价状态。标准步骤先把状态划成终结态组和非终结态组然后反复检查每个组如果组内两个状态在某个输入符号下进入的组不同就分裂。这个过程要一直做到所有组稳定。复习时有一个必考的易错点合并只看行为是否一致不看状态的“历史”。两个状态哪怕来的路完全不同只要对每个输入符号都落在同类型组里就能合并反过来两个状态都能到达终态但读同一个符号一个进终态、一个进普通状态也不能合并。词法部分的记忆性考点也要打包复习免得在小分上丢分。我一般把下面 5 条作为考前默写清单正则运算符有优先级闭包最高连接次之选择最低写正则时括号优先级必须正确词法识别用最长匹配两个规则同时匹配时取最长串而不是先写先得关键字和标识符的区分依赖优先级通常把关键字列为单独的规则并放在标识符规则之前符号表用从标识符名到类型的映射常用哈希表实现支持插入和查找两种操作词法错误恢复常见策略有删除多余字符、插入猜测字符、跳过字符直到输入重新与某规则同步。这 5 条几乎每张卷子都会碰到。3. 语法分析复习攻防LL(1) 与 LR 家族手算表不丢分3.1 为什么 FIRST 和 FOLLOW 值得先花一小时语法分析是《编译原理》期末卷面的主战场一张卷子三分之一的分值常压在这里。复习顺序我建议是先算 FIRST 和 FOLLOW再判断文法是否是 LL(1)然后画预测分析表如果考题走 LR 路线就按 LR(0) 项目集、SLR(1) 分析、LR(1) 项目分类一步步推。FIRST 和 FOLLOW 是后面所有表的根不会算它们后面一切无从下手。FIRST 的计算规则可以压缩成三句话产生式右部以终结符开头这个终结符进 FIRST以非终结符开头递归取这个非终结符的 FIRST非终结符能推出 εFIRST 里加 ε并且要“穿透”到下一个符号继续取。FOLLOW 的规则更绕也更容易错开始符号的 FOLLOW 里一定有结束标记$产生式A - α B β中β 以终结符开头这个终结符进 FOLLOW(B)β 以非终结符开头则把 FIRST(β) 中除 ε 之外的全进 FOLLOW(B)若 β 能推出 ε 还要继续把 FOLLOW(A) 也进 FOLLOW(B)产生式A - α B以 B 结尾时FOLLOW(A) 的所有元素进 FOLLOW(B)。这一条很多时候被漏掉因为题目里的产生式往往不是刚好以 B 结尾的形式需要替换展开才能看到。我复习时把 FIRST 和 FOLLOW 称作“两个路由器”FIRST 决定某非终结符在某终结符上能派生出什么FOLLOW 决定这个非终结符后面可能跟着什么。考试手算时最好每题都做一遍自检对每个产生式左部相同的组检查是否存在两个产生式的 FIRST 集合相交如果相交这个文法就不是 LL(1)继续算下去没有意义。3.2 用 Python 计算 FIRST/FOLLOW对答案手算 FIRST/FOLLOW 出错率很高尤其是含 ε 的文法。我复习时把教材里的经典算术文法翻译成下面这段 Python跑出来的结果直接当标准答案用它与自己手算的对照很快就能定位到是哪条产生式漏了。这段代码也能用来验证你自己构造的文法是否满足 LL(1) 条件。grammar { E: [[T, X]], X: [[, T, X], [ε]], T: [[F, Y]], Y: [[*, F, Y], [ε]], F: [[(, E, )], [i]], } def compute_first(grammar): nonterms set(grammar) FIRST {nt: set() for nt in nonterms} changed True while changed: changed False for nt in nonterms: for prod in grammar[nt]: before len(FIRST[nt]) if ε in prod: FIRST[nt].add(ε) else: for sym in prod: if sym in nonterms: FIRST[nt] | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: break else: FIRST[nt].add(sym) break else: FIRST[nt].add(ε) if len(FIRST[nt]) before: changed True return FIRST def compute_follow(grammar, FIRST, startE): nonterms set(grammar) FOLLOW {nt: set() for nt in nonterms} FOLLOW[start].add($) changed True while changed: changed False for nt in nonterms: for prod in grammar[nt]: for i, sym in enumerate(prod): if sym not in nonterms: continue before len(FOLLOW[sym]) if i 1 len(prod): beta prod[i 1:] seen_eps True for bsym in beta: if bsym in nonterms: FOLLOW[sym] | (FIRST[bsym] - {ε}) if ε not in FIRST[bsym]: seen_eps False break else: FOLLOW[sym].add(bsym) seen_eps False break if seen_eps: FOLLOW[sym] | FOLLOW[nt] else: FOLLOW[sym] | FOLLOW[nt] if len(FOLLOW[sym]) before: changed True return FOLLOW FIRST compute_first(grammar) FOLLOW compute_follow(grammar, FIRST) for nt in sorted(FIRST): print(fFIRST({nt}) , sorted(FIRST[nt])) print() for nt in sorted(FOLLOW): print(fFOLLOW({nt}) , sorted(FOLLOW[nt]))逻辑说明compute_first用不动点迭代对所有非终结符的所有产生式反复扫描直到集合不再增长。处理产生式右部时遇到终结符直接加入 FIRST 并停止遇到非终结符就把它当前的 FIRST 全部并入去掉 ε只有这个非终结符能推出 ε 时才看下一个符号所有符号都能推出 ε 时给当前非终结符补 ε。compute_follow同样用不动点迭代核心是遍历每个产生式中的每个非终结符看它后面跟的是终结符还是非终结符、是否位于末尾按上一节说的规则更新。参数说明grammar的格式是“非终结符 - 产生式列表”每个产生式是符号列表ε用字符串表示代码里用ε in prod判断该产生式是否包含 ε。注意这个版本的 FIRST 计算对产生式右部含 ε 且右部还有其他符号的混合情况做了简化处理遇到那种带注释的练习文法时把手动推导结果与代码输出对比差异大的地方就是你没掌握的部分。3.3 LL(1) 判定预测分析表与三个条件LL(1) 判定的标准结论要背熟一个文法是 LL(1)当且仅当对每个非终结符 A 的任意两个不同产生式 A-α 和 A-β下面两个条件同时满足。第一FIRST(α) 与 FIRST(β) 不相交第二如果 α 或 β 中有一个能推出 ε那么它的 FIRST 集合去掉 ε 后与另一个产生式的 FIRST以及 FOLLOW(A) 的交集都为空。画预测分析表时行的意义是当前栈顶的非终结符列的意义是当前读到的输入终结符。对产生式 A-α把A - α填入 FIRST(α) 中每个终结符对应列若 α 能推出 ε还要把A - α填入 FOLLOW(A) 的每个终结符对应列。这个“ε 产生式要填到 FOLLOW 列”的规则手算时最容易漏一漏就会在推导串时找不到可用产生式。3.4 LR 家族LR(0)、SLR(1)、LR(1)、LALR(1) 的选择逻辑LR 部分的复习难点在于四种分析器的关系。死背也可以但用下面的对照表会记得更牢LR(0) 只看项目集本身不看后面一个输入符号SLR(1) 在归约冲突时用对应非终结符的 FOLLOW 集合来裁决LR(1) 给每个项目加上展望符能力最强LALR(1) 把同心的 LR(1) 项目集合并表规模大幅缩小但可能引入归约-归约冲突。考试常问“LALR(1) 和 LR(1) 谁的语言类更大”答案是 LALR(1) 能处理的只是 LR(1) 的一个真子集合并同心项目集后出现冲突的文法不能用。分析器项目形式冲突判定依据说明LR(0)无展望符项目集内直接冲突能力最弱表最大SLR(1)无展望符FOLLOW 集合实现简单多数文法可用LR(1)带展望符展望符集合能力最强表爆炸LALR(1)合并同心集展望符合并后判定表大小与 SLR 接近能力接近 LR(1)这部分有个考试高频小问为什么说 LR 分析比 LL 分析能力更强我一般这样答LR 分析用的是自底向上归约它利用了整个栈的内容和未来输入符号而 LL 分析在当前非终结符产生式选择上只看了固定个数的前瞻符号所以 LL(k) 不能处理的左递归或更复杂文法LR 常常能处理。3.5 手算 LR 项目集的检查清单LR 项目集的手算题丢分点很集中我总结了 5 条自检项做题时按顺序过一遍。给文法后先写增广产生式S - S它是 0 号项目集唯一的初始项目求闭包时圆点后面如果是非终结符必须把这个非终结符的所有产生式都以“圆点在最前”的形式加进项目集漏了任何一个产生式都是硬伤求 goto 时圆点跨过一个符号 X得到新项目A - αX.β新项目的集合也要再做闭包检查冲突时先找移进-归约冲突一个项目归约、另一个项目移进再找归约-归约冲突两个项目都要归约但左部不同如果用 SLR(1)归约动作只填在 FOLLOW(左部) 对应的输入列上而不是所有列。最后一条我总是用“归约看左部移进看符号”来提醒自己写完表再整体复查一遍。4. 语义分析复习属性文法、符号表与中间代码生成4.1 综合属性与继承属性先分清楚再谈求值语义分析在期末卷面上通常不是独立的大题而是选择题、填空题加一个语法制导翻译的小题。这里的难点不是算法本身而是概念辨析。综合属性是从子节点向上计算的值只依赖于子节点和自身的属性继承属性是从父节点或兄弟节点横向传入的计算时要用到语法树上层或旁边的信息。判定方法很简单如果一个属性在计算时需要用到父节点或兄弟节点的属性值它就是继承属性只用到自己和子节点的属性值就是综合属性。复习语法制导部分我建议不要死背每种属性文法而是记住两条求值策略。自底向上的分析过程天然适合综合属性归约时子节点的值已经在栈里直接算出父节点的值继承属性在 L 属性文法中可以通过深度优先、从左到右的遍历求值前提是要保证每个继承属性的值在使用它的子节点处理前先算好。考试给你一个翻译模式让你标综合/继承属性、写出注释分析树时先画一棵简化的语法树在边上标注每条属性的产生位置再选求值顺序十拿九稳。4.2 用 Python 生成三地址码一个能跑的迷你示例三地址码是期末必考内容给一段赋值语句翻译成三地址码、画 DAG、做基本块划分都是常见题型。考试默认手算但我建议考前用代码把基本规则跑通一次因为手算时临时变量编号最容易数错。下面这段代码处理后缀表达式展示了最核心的规则每遇到一个运算符生成一条三地址指令把结果存进新临时变量。temp_count 0 code [] def new_temp(): global temp_count temp_count 1 return ft{temp_count} def emit(op, arg1, arg2, result): code.append(f{result} {arg1} {op} {arg2}) def convert_postfix(tokens): stack [] for tok in tokens: if tok.isdigit(): stack.append(tok) else: right stack.pop() left stack.pop() t new_temp() emit(tok, left, right, t) stack.append(t) return stack.pop() result convert_postfix([a, b, c, , *]) print(\n.join(code)) print(result , result)逻辑说明输入[a, b, c, , *]对应后缀表达式a b c *。标识符和数字直接压栈遇到运算符时从栈里弹出两个操作数生成tN left op right这条指令再把临时变量名压回栈。整个流程模拟的是自底向上归约过程中每归约一次就生成一条三地址指令的机制。参数说明tokens列表中的每一项要么是标识符或常量要么是单字符合法运算符temp_count是全局临时变量计数器从 1 开始编号code保存指令序列最后按顺序输出就是三地址码。这个示例只支持二元运算遇到一元负号、赋值语句、数组下标时要按教材扩展赋值语句通常先生成右侧的三地址码再把结果存入左侧变量数组下标要先生成地址偏移计算指令再生成取元素指令。扩展方向正是期末填空题常考的变体。4.3 符号表与类型检查高频选择题的送分点符号表与类型检查是期末考试喜欢出选择题的地方花半小时就能把分拿稳。符号表在词法分析阶段开始建立在语法分析和语义分析阶段不断填充属性和类型信息考试常问“符号表什么时候创建、什么时候填类型”答案一般是词法阶段创建标识符表项语义阶段回填类型与作用域信息。符号表最常用的实现是哈希表要求支持插入、查找、删除作用域内表项三种操作压栈式符号表处理嵌套作用域就是靠每进入一个块压入一层退出时弹出一层。类型检查部分背四个点类型等价分成名字等价与结构等价考试给两个类型表达式让你判断属于哪一种名字等价要求两个类型是同一个名字声明的结构等价只看结构是否相同重载按参数个数与参数类型区分返回值不参与重载区分类型不匹配属于静态语义错误不属于语法错误若语言支持强制类型转换转换规则要结合运算符表记忆。这些点单独看都简单但组合在选择题里很容易绕我复习时把它们抄成一张小表考前只扫这张表。4.4 中间代码的几种形式后缀式、三地址码、DAG 的关系中间代码的复习主线是“表达能力的等价变换”后缀式牺牲可读性换来最简单求值三地址码每个指令最多三个地址接近多数机器的实际指令DAG 在三地址码基础上合并公共子表达式用有向无环图表达共享。考试会问“DAG 与语法树的区别是什么”标准答法就是 DAG 中相同子树只保留一份可以重复引用所以 DAG 能直观表现公共子表达式消除后的结果。三地址码的具体表示也要记四元式(op, arg1, arg2, result)三元式(op, arg1, arg2)间接三元式在三元式上加一层执行表。写翻译结果时我建议统一用四元式因为判卷老师最容易按行对也能避免你的三元式编号与标答不一致导致误判。5. 编译原理期末复习避坑最容易丢分的 5 个翻车点5.1 词法层翻车最长匹配与优先级顺序搞反现象给关键字if和标识符两条规则输入串是ifx有的同学直接答“识别为关键字 if”被扣分。原因词法分析器默认最长匹配ifx整体比if长应该按标识符处理。很多同学把教材里“关键字规则写在标识符之前”误当成“关键字优先匹配”。解决答题时先声明最长匹配原则再谈规则书写顺序。只要输入串长度能继续匹配就继续读无法继续时才回退到已匹配的最长规则。与并列时同理按最长匹配优先。5.2 文法层翻车只消直接左递归没处理间接左递归现象文法有A - S b和S - A a直接套用A - Aα | β的消除公式结果推导时仍然进入循环。原因间接左递归需要先把非终结符排序再把排在后面的产生式替换到前面把间接左递归变成直接左递归然后才能套公式。解决我一般用手工排序法对非终结符编号按编号从 1 到 n 遍历对每个编号 i 的非终结符把编号小于 i 的非终结符的产生式带入它右部之后所有直接左递归统一消除。做完后检查一遍所有产生式确认右部首符不再是编号小于等于自身的非终结符。5.3 FIRST/FOLLOW 手算翻车ε 穿透传播被漏掉现象算FIRST(B C)时只取了 B 的 FIRST 就停止导致 C 的 FIRST 没进结果后面预测分析表少填了几列。原因FIRST 计算有一条穿透规则非终结符能推出 ε 时必须继续算下一个符号的 FIRST直到遇到终结符或全部符号都能推 ε。解决手算时给每个非终结符标出“能否推出 ε”的属性遇到能推出 ε 的就画一个箭头穿过它继续向后。这道题我见过很多同学栽在同一处E - T XX - T X | ε算 FIRST(E) 时 T 的 FIRST 是(和i就以为完了其实 T 不能推 ε这里确实不用继续但题目稍一改动T 变成能推 ε 的文法立刻出错。只要有 ε就按穿透规则完整走一遍。5.4 语义层翻车继承属性求值顺序写反现象语法制导翻译题里子节点的继承属性在子节点尚未被分析时就使用导致属性值拿不到。原因继承属性的求值顺序有硬约束必须先算能用到的父节点或兄弟节点属性再轮到子节点自底向上分析中继承属性天然不占优势需要借助标记非终结符或语义动作插入位置来调整。解决做题先画注释分析树在树上标注每个属性产生的位置和取值的边。检查每条边的方向综合属性边朝上继承属性边朝下或横着。只要有一条继承属性的指向是“从还没生成的子节点来”就是顺序反了。5.5 优化层翻车基本块入口只找跳转目标漏了其他两类现象给一段三地址码划分基本块只把跳转目标当成新基本块入口结果把顺序执行的代码拆错或把跳转指令算进前一块。原因基本块入口有三类第一类是第一句第二类是可以作为跳转目标的语句第三类是任何跳转指令的后继语句。漏掉第三类是常见翻车原因。解决动手前先给三类入口各画一种记号标记完再切块。切块后检查跳转指令自己一定是基本块的最后一条任何入口语句都不能落在某条语句中间。画控制流图时跳转边从跳转指令所在基本块指向目标入口所在基本块顺序边则连接相邻基本块。6. 考前 48 小时验证法用一道综合题检查全部考点与其考前刷十套零散题不如把一套综合题反复做三轮。我建议你选一个带左递归的算术表达式文法比如E - E T | T、T - T * F | F、F - (E) | i用它完成下面这张表里的 7 个任务。每完成一项就勾掉整个流程走完基本覆盖了期末卷面 80% 的考点。任务对应章节自查标准消除左递归语法分析新文法不含直接与间接左递归计算 FIRST 与 FOLLOW语法分析与教材标准答案一致判断是否为 LL(1)语法分析说明判定条件不只是写“是”画出预测分析表语法分析所有非终结符与终结符交叉处有内容推导i i * i的最左推导语法分析每一步替换都对应分析表动作把赋值语句翻译成三地址码语义分析临时变量编号连续无跳转缺失划分基本块并画控制流图优化三类入口全部标记跳转边正确48 小时的时间分配我一般是第一天的上午做一遍完整流程下午只看做错的和卡壳超过五分钟的环节第二天只针对这些环节回到对应章节重新推原理再换一个(i i) * i之类的等价式子做第二遍。如果你连续做两道题都卡在同一个地方说明那不是背题能补的漏洞要回去把那一节的概念重新读一遍而不是记住某道题的答案。这套做法还有一个额外好处它把“背书”变成了“画图 手算 对答案”复习效率比我当年对照着教材目录背定义要高得多。我最后一次期末复习最亏的一件事就是考前把精力放在刷小题上没有完整地从头到尾推过一遍流水线等到考场上遇到综合大题才发现各部分之间的衔接根本没吃透。希望帮到你。考试时遇到编译原理的大题先画流水线再定位它属于哪一层你会发现整张卷子其实就是一条生产线。本文还有配套的精品资源点击获取