简介这份资料面向北京工业大学北工大修读编译原理课程的学生针对期末一纸开卷考试场景整理帮助考生在有限篇幅内快速定位高频考点、梳理答题框架。内容围绕编译程序工作过程展开覆盖词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成五个阶段并重点讲解自顶向下分析中的回溯与左递归问题及其消除方法、语法制导翻译、LL(1)含义、二义性判定、参数传递方式、自展与交叉编译、前端后端结构划分等核心概念同时配有简答题式的要点归纳便于直接对照复习。资源包共1个doc文件约1.01MB为纯文档型复习总结结构紧凑、便于打印携带。目前已有789人学习下载适合需要系统梳理知识脉络、查漏补缺并快速记忆关键结论的备考学生使用。1. 北工大编译原理一纸开卷这份复习总结到底能帮你省多少时间如果你正在搜“北京工业大学编译原理考试一纸开卷”大概率你手里已经拿到了一张 A4 纸的额度却不知道该往上抄什么。这门课最折磨人的地方在于概念多、算法碎、题型固定但覆盖面广从词法分析的有限自动机一路考到 LR(1) 项目集闭包中间还夹着语法制导翻译和运行时存储分配。这份复习总结把北工大期末反复出现的 18 个简答考点、4 道典型计算例题、以及选择填空的高频判断整理在了一起本质上是一份“开卷索引”——它不教你从零学编译原理而是帮你在考场上快速定位到对应知识块的标准表述。适合已经过了一遍教材、但知识点还是散装状态的同学也适合时间紧、需要把复习范围压缩到最小可行集的场景。下面我按“这份资料怎么用 → 核心考点怎么拆 → 计算题怎么套 → 开卷怎么排”的顺序把里面真正能打的内容拆开讲。2. 从词法分析到目标代码编译程序五阶段与前端后端怎么切2.1 五阶段划分的底层逻辑编译程序的工作过程被切成五个阶段词法分析、语法分析、语义分析与中间代码产生、代码优化、目标代码生成。这个划分不是随便定的它对应的是“从字符流到机器指令”这条翻译链上不同抽象层级的转换。词法分析把字符流切成单词符号语法分析把单词符号串组织成语法单位语义分析给语法单位赋予含义并生成中间代码优化让中间代码更高效目标代码生成把中间代码映射到具体机器的指令集。考试里常考的一个点是为什么词法分析和语法分析要分成两个阶段总结里给了三条理由——结构更简洁清晰、提高效率、增强可移植性。这三条不是背诵题而是理解题。词法分析用有限自动机就能搞定语法分析用下推自动机两者的计算模型不同混在一起写会让编译器代码变成一团乱麻。分开之后换一种源语言只需要改词法规则换一种目标机器只需要改后端中间部分可以复用。提示开卷时如果遇到“编译程序结构”相关简答先把前端后端的边界写清楚——前端与源语言有关但与目标语言无关包括词法、语法、语义分析与中间代码产生后端与目标语言有关包括优化和目标代码生成。后端只依赖中间语言不依赖源语言。2.2 前端与后端的实际分界很多同学背了“前端后端”的定义但一到具体题目就分不清某个模块该归哪边。判断标准很简单看这个模块处理的信息是否还保留着源语言的语法结构。词法分析输出的 token 流还带着源语言的标识符名字和关键字语法分析输出的语法树还保留着源语言的表达式结构语义分析生成的中间代码虽然已经脱离了具体语法但仍然是一种抽象机上的指令序列。到了优化阶段如果做的是与机器无关的优化比如常量折叠、公共子表达式消除它其实还偏前端如果做的是寄存器分配、指令调度那就彻底是后端的事了。总结里把“语义分析与中间代码产生”放在前端把“优化与目标代码生成”放在后端这是教材上的标准切法。考试时如果题目问“编译前端包括哪些部分”直接按这个切法答不要自己发挥。2.3 表格管理与出错处理容易被忽略的第六、第七部分一个典型的编译程序除了五个阶段还必须包括表格管理和出错处理。表格管理指的是符号表的维护——变量名、类型、作用域、存储地址这些属性都存在符号表里。出错处理指的是编译器在发现源程序错误时要能给出有意义的错误信息并且尽量继续分析下去而不是一遇到错误就崩溃。为什么符号表管理这么重要因为编译过程中几乎每个阶段都要和符号表打交道词法分析识别出标识符后要查表或填表语法分析在建立语法树时可能要引用符号表里的类型信息语义分析要往符号表里写类型和地址代码生成要从符号表里读存储分配信息。符号表的存取方法直接影响目标程序的效率——如果符号表用线性查找编译速度会随变量数量线性下降如果用哈希表查找接近常数时间。注意开卷考试里如果出现“为什么将变量名保存在符号表中”这类简答核心答题点是变量名用于识别、用于变量名与存储空间的绑定、用于类型和作用域等属性的设置与获取。不要只写“方便查找”太单薄。3. 自顶向下与自底向上LL(1) 分析表和 SLR 分析表的构造套路3.1 自顶向下分析的两个核心障碍自顶向下的语法分析要解决的问题是根据当前输入符号判断将栈顶的非终结符号替换成哪条规则的右部。这个过程中有两个绕不开的障碍——回溯和左递归。回溯的产生是因为文法中可能存在多个候选式都能匹配当前输入符号的开头部分但只有一个能最终匹配成功。比如文法A → aB | aC当前输入是a你选aB还是aC如果选错了就要退回来重选这就是回溯。回溯浪费分析时间而且分析不成功时难以找到出错位置。左递归的问题更严重。如果文法有A → Aα | β这样的直接左递归自顶向下分析时会把A替换成Aα然后栈顶又是A又替换成Aα陷入无限循环。间接左递归同理A → BαB → Aβ推导下去也是无休止。解决办法总结里写得很清楚提取公共左因子消除回溯消除直接及间接左递归。提取左因子的做法是把A → aB | aC改写成A → aAA → B | C。消除直接左递归的做法是把A → Aα | β改写成A → βAA → αA | ε。3.2 LL(1) 分析表的构造步骤LL(1) 的含义是第一个 L 表示从左到右扫描输入串第二个 L 表示最左推导1 表示分析时每一步只需向前查看一个符号。构造 LL(1) 分析表需要计算 FIRST 集和 FOLLOW 集。以总结里的例题为例文法D → TLT → int | realL → id RR → , id R | ε。先算 FIRST 集FIRST(D) FIRST(T) {int, real}FIRST(L) {id}FIRST(R) {,, ε}。再算 FOLLOW 集FOLLOW(D) FOLLOW(L) {#}FOLLOW(T) {id}FOLLOW(R) {#}。构造分析表时对每个产生式A → α如果a在FIRST(α)中就把A → α填入M[A, a]如果ε在FIRST(α)中则对FOLLOW(A)中的每个符号b把A → α填入M[A, b]。# LL(1) 分析表构造伪代码 def build_ll1_table(grammar, first_sets, follow_sets): table {} # table[(non_terminal, terminal)] production for production in grammar: A production.left alpha production.right for a in first_sets[alpha]: if a ! ε: table[(A, a)] production if ε in first_sets[alpha]: for b in follow_sets[A]: table[(A, b)] production return table这段代码的逻辑是对于每条产生式先看右部 FIRST 集里的终结符把产生式填到对应格子如果右部能推出空串再看左部非终结符的 FOLLOW 集把产生式填到那些格子里。参数说明grammar是产生式列表first_sets和follow_sets是预先算好的字典。实际考试时不需要写代码但理解这个流程能帮你在填表时不出错。3.3 SLR 分析表与移进-归约冲突的消解自底向上分析的代表是 LR 分析法。LR(0) 项目集规范族的构造、识别活前缀的 DFA、SLR 分析表的填写这三步是连在一起的。总结里的例题 4 给了一个典型场景文法S → aS | bS | a拓广为S → SS → aSS → bSS → a。构造 LR(0) 项目集时状态 I1 里同时存在S → a·S和S → a·前者是移进项目后者是归约项目这就是移进-归约冲突。SLR 的解决方法是计算FOLLOW(S)如果FOLLOW(S)和可移进符号集{S, a, b}的交集为空冲突就可以解决。具体判断规则是当前输入符号x属于可移进符号集就移进属于FOLLOW(S)就归约否则报错。# SLR 移进-归约冲突消解判断 def resolve_shift_reduce(shift_symbols, follow_set, current_input): if current_input in shift_symbols: return shift elif current_input in follow_set: return reduce else: return error参数说明shift_symbols是当前项目集中所有可移进项对应的符号集合follow_set是所有可归约项左部非终结符的 FOLLOW 集current_input是当前读到的输入符号。这个判断逻辑在考试里经常以“给定分析表某一行判断动作”的形式出现。提示LR(1) 比 SLR(1) 分析能力更强的原因在于SLR 只在遇到冲突时才看 FOLLOW 集而 LR(1) 在构造 DFA 状态时就为每个项目附带了后继符信息对后继符的利用更精细。答题时抓住“SLR 对后继符信息利用有限LR(1) 在状态构造时就考虑后继符”这个核心区别。4. 语法制导翻译与运行时存储属性计算和活动记录怎么答不丢分4.1 属性文法与翻译模式的联系和区别属性文法可以看作是关于语言翻译的高级规范说明它把语法规则和语义规则分开写隐去了实现细节。翻译模式则给出了使用语义规则进行计算的次序把某些实现细节表示出来。两者的联系是都基于上下文无关文法都用属性来描述语义信息。区别是属性文法更抽象适合做规范说明翻译模式更具体适合指导实际实现。考试里常考的一道题是给出一个文法要求写出语法制导定义输出配对括号个数。总结里的例题 3 给了标准答案S → (L)时S.h : L.h 1S → a时S.h : 0L → L1, S时L.h : L1.h S.hL → S时L.h : S.h最后S → S时print(S.h)。这道题的答题关键是属性h代表配对括号个数每遇到一对括号就加一逗号分隔的列表把各部分的h相加。开卷时如果遇到类似题目先确定属性代表什么再根据产生式的结构写语义规则。4.2 活动记录与临时变量分配在栈式存储管理中活动记录为一次过程调用的局部数据提供存储空间。活动记录随过程调用被分配随过程调用结束而释放。临时变量通常用于保存表达式计算中的中间结果在活动记录中为临时变量分配空间可以保证该空间随过程调用被分配随活动记录的释放被自动释放。为什么不在全局区分配临时变量因为递归调用时每一层调用的临时变量必须独立否则内层调用会覆盖外层的中间结果。活动记录的栈式分配天然支持递归这是它比静态分配更适合临时变量的根本原因。4.3 静态存储分配与动态存储分配的区别静态存储分配对一个变量固定分配一个地址以后不管在哪一层对此变量做改动都是对此地址中的实际对象做的改动。动态存储分配没有对一个变量固定分配地址空间而是随着子程序调用动态地分配不同的空间子程序执行完毕后空间被收回改动不会被保留。这个区别在考试里经常以“为什么动态存储分配更适合递归”的形式出现。答题时抓住“固定地址 vs 动态分配、改动保留 vs 改动不保留”这两组对比。4.4 参数传递的四种方式高级程序设计语言参数传递有四种常用方式传值、传地址、传值结果、传名。传值是计算实参并将其右值传递给被调用过程传地址是调用过程将实参地址传递给被调用过程传值结果是传值和传地址的结合传名只有在被调用过程中用到形参时才动态地建立起它与实参的联系。这四种方式的区别在考试里经常以选择题形式出现问“哪种方式可以实现形参和实参的双向传递”。答案是传地址和传值结果。传名比较特殊它类似于宏替换每次用到形参都重新求值实参。注意开卷时如果遇到“为什么在活动记录内为临时变量分配空间”这类简答核心答题点是临时变量保存表达式计算的中间结果活动记录随过程调用分配和释放保证临时变量的生命周期与过程调用一致递归时各层独立。5. 开卷考试避坑从符号表到 LR 项目集的五个血泪教训5.1 符号表属性写不全现象简答题问“符号表中保存变量名的作用”只写了“方便查找变量”。原因没有从编译各阶段对符号表的使用角度去答。解决符号表保存变量名及其各种属性用于变量的识别、变量名与存储空间的绑定、类型和作用域等属性的设置与获取。答题时至少写三个用途。5.2 LL(1) 分析表填错 FOLLOW 集现象构造 LL(1) 分析表时遇到空产生式不知道往哪些格子填。原因忘记空产生式要看左部非终结符的 FOLLOW 集。解决空产生式A → ε填入M[A, b]的条件是b在FOLLOW(A)中而不是在FIRST(ε)中。FIRST(ε)只有ε不能直接用来填表。5.3 左递归消除后忘记验证现象消除了直接左递归但文法仍然有间接左递归分析时还是死循环。原因只处理了直接左递归没有检查间接左递归。解决消除左递归后重新计算 FIRST 集和 FOLLOW 集验证FIRST(A) ∩ FOLLOW(A)是否为空。如果不为空说明文法不是 LL(1) 的需要进一步改写。5.4 LR 项目集闭包漏项现象构造 LR(0) 项目集规范族时闭包里的项目漏了。原因没有对圆点后面的非终结符展开。解决闭包运算的规则是如果项目A → α·Bβ在闭包中且B是非终结符则对B的每条产生式B → γ把B → ·γ加入闭包。这个过程要反复进行直到闭包不再增大。5.5 规范归约和规范推导搞反现象题目问“规范归约的序列条件”答成了最左推导。原因混淆了规范推导和规范归约的方向。解决规范推导是最右推导规范归约是最左归约两者互为逆过程。规范归约的序列αn, αn-1, ..., α0满足αn x且αn αn-1 ... α0 S其中α0是开始符号。6. 把 18 个简答压成一张 A4我的开卷排版与检索技巧开卷考试的核心矛盾是你有一张 A4 纸的额度但知识点覆盖了整本书。我的做法是把 A4 纸分成四个区域左上角放编译程序五阶段和前端后端划分右上角放 LL(1) 和 LR 分析表的构造步骤左下角放语法制导翻译和属性文法的模板右下角放运行时存储和参数传递的对比。每个区域用不同颜色的笔写方便考场上快速定位。具体到这份总结里的 18 个简答我按“必考指数”做了分级。第一梯队是编译五阶段、LL(1) 含义、左递归和回溯的解决、规范归约和规范推导、LR(1) 比 SLR(1) 强的原因这五个几乎每年都出现必须一字不差地抄在 A4 纸上。第二梯队是语法制导翻译、属性文法和翻译模式的区别、参数传递四种方式、静态和动态存储分配的区别这些以选择题或简答题形式出现抄关键词即可。第三梯队是标识符和名字的区别、自展和交叉编译、活动记录临时变量分配这些偶尔考抄一句话概括。计算题部分LL(1) 分析表的构造和 SLR 分析表的构造是必考题型。我的习惯是在 A4 纸上画一个空白的 LL(1) 分析表模板行是非终结符列是终结符考试时直接往模板里填 FIRST 集和 FOLLOW 集的结果。SLR 分析表同理但要多留一列给状态编号。移进-归约冲突的消解判断规则用一行字写在模板旁边FOLLOW(A) ∩ 可移进符号集 ∅则可解。提示开卷时不要带太多张纸一张 A4 正反面足够。写太多反而找不到。用荧光笔标出每个区域的标题考场上先看题目问的是哪个区域再翻到对应位置找答案。从那以后我每次带开卷考试都强制自己提前三天把 A4 纸写好然后做两套真题验证能不能在纸上找到所有答案。如果有一道题在纸上找不到就说明排版有盲区立刻补上。这个习惯让我在考场上从来没因为翻不到知识点而慌过。希望帮到你。本文还有配套的精品资源点击获取
