编译原理期末复习：从DFA到LR分析表的考点全梳理-北京尧图网络

简介面向哈工大及同类课程学习者这份编译原理期末复习PDF完整覆盖课程全部核心模块。内容包括编译系统的定义与结构、语言基本概念串、字母表、克林闭包与文法分类、词法分析中的正则表达式与DFA/NFA、语法分析树、中间代码表示形式三地址码、四元式、间接三元式、目标代码生成与寄存器分配、代码优化方法等采用分节笔记形式呈现适合考前系统梳理与查漏补缺。包体为单个PDF文件大小31.14MB目前已有2311人学习下载。内容基于课堂与教材整理强调概念与推导过程结合对DFA的确定化、子集构造法、四元式生成等易考点给出示例能帮助快速建立编译原理整体框架标注常见考点与典型题型是期末冲刺的高效参考资料。1. 哈工大编译原理期末复习为什么「看懂了」和「做得出」是两回事考前一周把 PPT 和课后题快速过一遍看着 FIRST、FOLLOW、LR 项目集、中间代码每一步都「看懂了」合上材料却发现连一张 DFA 状态转换表都画不利索——这是哈工大编译原理期末最常见的翻车方式。这个标题说的「完整版」不是把目录抄一遍而是把这些散点按考试出题顺序重新串成一条线词法分析、语法分析、语法制导翻译、符号表与运行时、代码优化每一块都落在「考场上要亲手算的表」上。适合谁期末还剩两三周、实验用 C 或 Java 写过词法分析器、但理论考点还零散的人。别急着背题先把下面三张表练熟。2. 词法分析从正规式到 DFA每一步都要能闭卷画出来2.1 先分清「要背」和「要会算」两个层面词法部分的知识点分成两层。第一层是概念正规式与正规集、DFA/NFA 的形式化定义、确定化与最小化、泵引理以及词法单元、模式、词素这几个术语的区分。哈工大期末在这层出题多为选择、判断和简答比如「给出语言描述写正规式」或「写出某个 DFA 的等价正规式」。第二层是手算从正规式构造 NFA、把 NFA 确定化为 DFA、把 DFA 最小化这层几乎每年都占一道大题而且要求你现场画状态转换表。复习建议很直接概念层背到能「讲清楚」就行计算层必须练到「闭卷限时完成」。一个现实的判断标准——拿一张 A4 纸不看任何笔记15 分钟内把某个正规式对应的 DFA 画出来并且能完成最小化收尾才算过关。如果你实验是用 Java 或 C 亲手写的词法分析器正规式到状态机这步会顺很多反过来实验没来得及认真做的考前至少要把 Thompson 构造法和子集构造法各手推三遍。2.2 子集构造法与最小化用一张表把 NFA 转 DFA 走完常见做法是三步走。第一步Thompson 构造法把正规式按运算符拆开每个字符对应一个小 NFA再用 ε 边把并列、选择、闭包连接起来。第二步子集构造法从 NFA 初态的 ε-闭包开始逐个输入符号求 move 集合再对 move 结果求 ε-闭包得到新状态重复到不再出现新状态为止。第三步DFA 最小化把状态先划分为终态组与非终态组再反复检查每组里的状态对每个输入符号是否落到同一个组落不到就继续分裂直到组不再变化。用教材里最常见的正规式 (a|b)abb 走一遍。它的 NFA 结构是状态 0 经 ε 到 1(a|b)的循环体1 可自环 a、b并经 ε 到 22 经 a 到 33 经 b 到 44 经 b 到 5终态。按子集构造法逐行填入下表DFA 状态ε-闭包代表集输入 a输入 b是否终态A{0,1,2}BC否B{1,2,3}BE否C{1,2}BC否E{1,2,4}BG否G{1,2,5}BC是注意填表顺序每填出一个新集合B、C、E、G都要回去把它作为新行继续展开直到所有行的 a、b 两列都只指向已出现的状态为止。move 求的是「读入一个符号后能一步到达的状态集合」ε-闭包则是把「不读任何字符也能到达」的状态全并进来这两步合并写就是表中每一格。最小化这一步初始分成 {A,B,C,E} 和 {G} 两组。检查 E 对 b 到 G终态组而 A、B、C 对 b 都到非终态组所以 E 单独分裂出去。剩下 {A,B,C} 对 a 都到 B、对 b 都到 C不再分裂。最终等价类是 {A,B,C}、{E}、{G}得到 3 个状态的 DFA。很多人在这里默认最小化结果和原状态数差不多其实 (a|b)*abb 最小化后就是 3 态少做一步分裂就会多留状态被扣分。提示期末考试画这张表顺序不能乱——先算 ε-闭包初态再按 a、b 顺序逐个填填完检查有没有没展开的新状态。最忌跳着填跳一步后面全错。2.3 最长匹配与词法错误两道判断题的来源词法还有一个常被小看的知识点——最长匹配原则。词法分析器读输入时不是「能识别一个就停」而是继续读直到不能再匹配更长的词素再回退到最后一个成功匹配的位置。典型错题输入 ifx 不能先匹配到 if 就把 x 留给后面而是要按最长匹配先取整个 ifx查符号表发现不是关键字按标识符处理。反过来if( 中的 if 要被识别成关键字 if而不是标识符 if(。词法错误与语法错误的区分也是高频判断考点。词法错误在字符层就能发现比如出现不合法的字符、字符串常量没有结束符、数字后紧跟字母像 123abc而括号不配对、语句缺分号属于语法错误。复习时可以用编译原理实验里的代码做反例如果你当年写过手写词法分析器多半遇到过「读入和读入怎么处理」的问题那就是最长匹配的第一次踩坑。3. 语法分析LL(1) 与 LR 系列靠手推而不是靠「看解析」3.1 FIRST、FOLLOW 的固定算法顺序与三个易错点先给一个需要手动改造的文法因为它同时覆盖「消除左递归」和「LL(1) 构造」两个考点原文法 E→ET|TT→T*F|FF→(E)|id。哈工大期末很喜欢把带左递归的文法直接丢给你让你改造后构造预测分析表。消除直接左递归后得到E→TEE→TE|εT→FTT→*FT|εF→(E)|idFIRST 集算法按三步走终结符的 FIRST 就是自身对每个产生式 A→X1X2…先把 FIRST(X1) 的非 ε 元素加入 FIRST(A)若 X1 能推 ε继续并入 FIRST(X2)直到某个符号不能推 ε 为止若整个右部都能推 ε把 ε 加入 FIRST(A)。这个顺序要循环跑直到所有 FIRST 集不再变化。FOLLOW 集算法也按三步走开始符号的 FOLLOW 先放 $对形如 A→αBβ 的产生式把 FIRST(β) 去掉 ε 后全部加入 FOLLOW(B)对形如 A→αB 或 A→αBβ 且 β 能推 ε 的产生式把 FOLLOW(A) 整体加入 FOLLOW(B)。同样要循环到不再变化这是最容易被忽略的传递性步骤。上面文法的结果如下表非终结符FIRSTFOLLOWE{ (, id }{ $, ) }E{ , ε }{ $, ) }T{ (, id }{ , $, ) }T{ *, ε }{ , $, ) }F{ (, id }{ *, , $, ) }三个易错点一是 FOLLOW 里绝对不能出现 ε二是 $ 只能从开始符号的 FOLLOW 进入再经传递扩散到其他非终结符上面 E 的 $ 就是从 FOLLOW(E) 传入的三是算 FOLLOW(T) 时容易漏掉 E→TE 这一步——T 后面是 EFIRST(E) 含 ε所以要把 FOLLOW(E){ $, ) } 并入 FOLLOW(T)。3.2 LR(0)、SLR(1)、LR(1)项目集规范族的构造顺序LR 系列的核心是项目集。一个 LR 项目就是产生式右部的某个位置打一个点例如 S→·S、S→a·Sb。点前表示「已经读到的输入」点后表示「期望接下来读到的」。构造项目集规范族按下面顺序机械执行。第一步对每个项目集求闭包若项目 [A→α·Bβ] 在集合中则把 B 的所有产生式 [B→·γ] 也加入直到没有新项目。第二步对每个输入符号 X做 goto 动作把集合中所有 [A→α·Xβ] 的点向右移一位得到新项目再对新项目求闭包。第三步重复 goto直到没有新集合出现初始项目集 I0 是 [S→·S] 的闭包。「移进-归约」的判定则是点后是终结符就移进点后没有东西即完整项目就该归约项目集里同时出现移进和归约就叫移进-归约冲突出现两个归约就叫归约-归约冲突。LR 系列的层次关系也在这里体现LR(0) 不看任何向前看符号SLR(1) 用 FOLLOW 集做归约判定LR(1) 用传播过来的精确后继符号做判定。期末简答「为什么 LR(1) 比 SLR(1) 能力强」就按这个思路答不是算法顺序不同是归约时刻的判定信息粒度不同。SLR 用 FOLLOW(左部) 这个大集合会把本不该共存的移进和归约误判为冲突LR(1) 每个项目自带向前看符号能分辨更多文法。这个区别在构造 SLR 分析表时体现为归约动作要填在 FOLLOW 集合中的所有列上。3.3 从项目集到 SLR 分析表把动作序列推一遍用手能算完的小文法 S→SS→aSb|ε 演示。初始项目集 I0 closure({[S→·S]}) {S→·S, S→·aSb, S→·}。这时候遇到 a 移进遇到 b 和 $因为 FOLLOW(S){b,$}可以按 S→ε 归约。继续推goto(I0, S) 得 I1{S→S·}这是接受状态goto(I0, a) 得 I2{S→a·Sb, S→·aSb, S→·}goto(I2, S) 得 I3{S→aS·b}goto(I3, b) 得 I4{S→aSb·}。SLR 分析表关键部分如下状态action(a)action(b)action($)goto(S)0s2r3r311acc2s2r3r333s44r2r2用输入 ab$ 走一遍分析流程这是期末考试要求写出的「动作序列」步骤状态栈剩余输入动作10ab$查 (0,a)s2移进压状态 220,2b$(2,b)r3按 S→ε 归约压 goto(2,S)330,2,3b$(3,b)s4移进压状态 440,2,3,4$(4,$)r2按 S→aSb 归约弹出 3 个状态压 goto(0,S)150,1$acc第 2 步最容易疑惑归约 S→ε 不弹出状态直接压 S 和 goto 状态因为产生式右部长度为 0。第 4 步弹出 3 个状态对应符号 a、S、b。每一步查表都要写「哪个状态、哪个输入、什么动作」考试按步骤给分跳步会丢过程分。3.4 两张「判断文法类别」的流程和改造常见做法判断一个文法属于哪一类用流程走不要凭感觉。先检查是否二义二义文法既不是 LL 也不是 LR再构造 FIRST/FOLLOW查 LL(1) 条件——同一非终结符的多个产生式右部 FIRST 两两不相交且若某右部能推 ε其 FIRST 与 FOLLOW 不相交最后构造 LR 项目集查分析表有无冲突。层级关系记一条LR(0) 文法 ⊂ SLR(1) 文法 ⊂ LR(1) 文法但注意项目集规范族的大小是反过来的LR(1) 状态数最多。改造文法常见做法是消除左递归和提取左公因子。直接左递归 A→Aα|β 改写为 A→βAA→αA|ε间接左递归要把非终结符排序、逐个替换后再消。提取左公因子用于解决 FIRST 集相交的问题但有两个坑提取左公因子不保证文法变成 LL(1)因为根本冲突可能来自 ε 产生式和 FOLLOW 集改造后必须重新算 FIRST/FOLLOW 和分析表不能沿用改造前的结果。很多人在这里翻车——改完文法直接抄旧表。4. 语法制导翻译属性、中间代码、符号表与回填是一条线4.1 综合属性与继承属性先判类型再决定求值顺序语法制导定义里一个产生式 A→XY 如果语义规则给 A 赋值且值来自 X 或 Y 的属性就是综合属性如果赋值对象是 X 或 Y且值来自 A 或左侧兄弟节点的属性就是继承属性。判断「谁是综合、谁是继承」是一道稳定送分题判据就一句话看箭头指向的节点是谁。综合属性的箭头朝上子节点到父节点继承属性的箭头朝下父节点或左兄弟到当前节点。期末要求做三类事给属性和语义规则能画注释分析树给注释分析树能按依赖图排序求值判断某属性定义是否属于 S-属性定义只有综合属性或 L-属性定义每个继承属性只依赖于左兄弟或父节点属性。S-属性定义用自底向上在归约时求值L-属性定义更适合自顶向下递归下降在递归下降程序里把语义动作插在对应文法符号处。一个典型例子E→E1T 的语义规则 E.val : E1.val T.val 是综合属性因为父节点的值由子节点算出而声明语句 D→T id 里 id.type : T.type把类型信息从左兄弟传给右兄弟是继承属性。考试时把这两类分开列出来再说明求值顺序比只写规则拿分稳。4.2 三地址码与四元式常见语句的翻译模板中间代码阶段要能把语句翻译成四元式。四元式格式是 (op, arg1, arg2, result)期末卷面上通常要求写带行号和临时变量的完整序列。常见翻译模板如下语句四元式序列A : B op C(op, B, C, A)A : B[i]([], B, i, T1) 然后 (:, T1, _, A)if B then S1先翻译 B 的真/假链再按假链跳转绕过 S1while B do S开标签 L1翻译 B 后按假链跳出循环末尾 (j, _, _, L1)说明两点。第一临时变量按 T1、T2 顺序编号考试按编号检查依赖性跳号会被当作错误。第二跳转四元式必须先给出目标行号或「待填」标记行号从 1 或 100 开始都行但整张表行号必须连续错一个后面全对不上。这是中间代码题最吃亏的失分点——不是不会翻是行号不连续导致后续回填全乱。4.3 符号表与作用域嵌套块与遮蔽关系是判断题重灾区符号表分三种常见组织形式线性表查找最慢但结构直观散列表按名字哈希查找快栈式符号表用栈帧对应过程/块的嵌套层次适合处理作用域。期末问「符号表用什么数据结构实现」时要按两个维度答插入/查找的代价以及作用域信息的维护方式。符号表这个考点经常被低估因为它不参与画表但判断题里至少有两道会在作用域上做文章。作用域规则考的也是判断题。典型例子是嵌套块外层声明 x内层再声明 x 则遮蔽外层内层块结束外层 x 重新可见块内可以访问外层名字但不允许反向访问已结束的内层名字。另一道高频题是「动态作用域下的悬挂引用」——块结束后其符号表项已撤销但若地址被保留动态作用域运行时去查就会得到错误结果。静态作用域按词法嵌套结构查动态作用域按调用栈现场查两者结论经常不同题干会用「调用顺序」诱导你按动态作用域答注意分辨。4.4 回填技术跳转目标未知时的标准解法翻译控制流时产生一个经典问题if B goto L但 L 的位置要等后面的语句翻译完才知道。常见做法是「回填」翻译时先给跳转四元式留空把它们的地址记进真列表或假列表等目标确定后统一回填。这也解释了为什么回填需要「链表式」的属性结构而不是单一数字。以布尔表达式 ab or cd 为例翻译成四元式大致为100 (j, a, b, 真链待填)101 (j, _, _, 假链待填)102 (j, c, d, 真链待填)103 (j, _, _, 假链待填)当知道真出口应指向哪条语句后把 100 和 102 的第 4 项填成那个行号即可。这里容易错的是真假列表的合并or 的两个真列表要合并101 和 103 的无条件跳转属于假链的一部分。期末「回填」题只要画清楚真/假链的合并关系基本就稳了。运行时环境的内容也常归在这一块栈式分配、活动记录、静态链/动态链。核心概念就四个——活动记录、栈指针/帧指针、返回地址、嵌套过程的访问链。只需要记住「每个过程调用建立一个活动记录嵌套过程访问外层变量要沿访问链跳」这条主线。5. 期末避坑哈工大试卷上最容易失分的 5 个踩坑现场下面按「现象 → 原因 → 解决」写 5 条都是我复习时真实掉过的坑。5.1 FOLLOW 集算到一半把 ε 混进去了现象检验 LL(1) 条件时发现 FIRST 和 FOLLOW 有交集自以为文法不是 LL(1)实际是算错了。原因FOLLOW 集合的定义里从不包含 ε但算 FOLLOW(B) 时把 FIRST(β) 里的 ε 原样并入了。解决每次并入 FIRST(β) 前先做减法去 ε把「FOLLOW 无 ε」写成一张检查卡算完对着卡查一遍。尤其碰到含 ε 产生式的文法这一步是血泪经验。5.2 LR 项目集闭包漏掉「点后非终结符的产生式」现象构造 SLR 分析表时某列动作缺失对不上或归约-归约冲突判断完全错误。原因闭包操作要求把 [A→α·Bβ] 中 B 的所有产生式以 [B→·γ] 加入。漏了 B 的产生式就缺状态后续 goto 全错整张表作废。解决构造时按「先查点后是不是非终结符是就把该非终结符的全部产生式补进来补的过程中新加项目若还有点后非终结符再继续补」的循环写。每步闭包用铅笔打勾避免漏项。5.3 SLR(1) 与 LR(1) 的区别答成了「LR(1) 更强大」现象简答题问两者关系只写「LR(1) 文法的范围更广」被扣分。原因没答到机制上。判卷老师要的是「为什么」——SLR 用的向前看符号是 FOLLOW 集过于粗糙LR(1) 用传播的精确向前看符号所以能处理的文法更多。解决背这句话——「二者构造顺序相同区别在归约项目处向前看符号的粒度」再补一句「因此 SLR 会把本可处理的归约判定为冲突」。这比单写结论多拿一半分。5.4 接受动作 acc 与归约 S→S 分不清现象分析表里把接受状态所在格填成 r1 而不是 acc。原因I1{S→S·} 是接受状态但不少复习材料把「S→S」当普通归约产生式展示导致混淆。解决记住 acc 只在状态包含增广文法开始产生式 S→S· 且输入为 $ 时出现其他完整项目一律走归约。平时练习时把接受状态单独标记出来不要混在归约里。5.5 把课后习题答案当背诵材料看完以为自己会了现象拿着编译原理第3版-王生原课后习题答案第三章、第四章的题对着答案看一遍觉得全会上考场面对同型题写不出来。原因看答案时大脑走的是「识别」路径不是「生成」路径。编译原理期末考的是生成——从文法生成分析表从语句生成四元式。识别路径在考场上完全失效。解决把课后题当限时练习用先闭卷做再对答案。对完把错题分类记下算错的重算一遍步骤漏的重新抄一遍步骤。答案只能用来核对不能用来预习。6. 考前最后 72 小时用「默写三张表」检验复习有没有到位复习是否到位不看你翻了几遍书看你能不能闭卷完成三张表DFA 最小化前后的状态转换表、LL(1) 预测分析表、LR 项目集规范族与 SLR 分析表。我给自己的标准很简单每张表限时词法 15 分钟LL(1) 20 分钟SLR(1) 40 分钟。能一次画对、中途不看笔记当天就可以把时间匀给选做题画不对的地方把对应算法步骤抄三遍再重新限时一次。另一个技巧是「反向复述」——把算法用三句话讲给自己听。比如最小化「先分终结与非终结再按输入分裂分到不动为止。」讲得出来说明结构在脑子里讲不出来就回章节重读。代码优化那些概念题每种优化常量折叠、代码外提、强度削弱、删除公共子表达式要求自己写一行变换前后的例子光背定义在考场上很容易被换皮的题打懵。最后说一个实际教训我第一次模拟考 SLR 分析表画到一半发现项目集少做了一个闭包后面状态全错整个大题浪费 20 分钟。那之后我把闭包检查写进每道 LR 题的第一步——先查点后的非终结符有没有全部展开。这比多做三套题都管用。希望帮到你。本文还有配套的精品资源点击获取

编译原理期末复习：从DFA到LR分析表的考点全梳理

相关推荐

基于SpringBoot+Vue+MySQL的社区医疗服务可视化管理系统设计

任务描述不清导致执行偏差？五要素写出无歧义说明书

传统酒业如何用排队免单实现线上营销突围

更多资讯

学校工资管理系统数据库设计实战指南

AI模型路由实战：用星链4SAPI化解大模型调用成本失控

人工智能与法律领域深度融合的可行性参考分析

独热编码详解：离散特征处理、稀疏矩阵与哑变量陷阱实战指南

Windows任务栏卡顿修复指南：从资源占用到驱动排查的完整方案

Android bindService深度解析：从Java到Binder驱动的全流程拆解

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？