# 编译原理考前总复习 > 脱离课件复习版：把知识脉络、必背抓手、便携记忆点和自测题放在一起，考前可以只看这一份。 ## 1. 知识脉络 主线：总览 -> 文法 -> 语法制导 -> 词法 -> 语法分析 -> 运行时 -> 中间代码 1. **编译系统总览：阶段、接口和全局支撑** - 核心：编译器把源程序逐步转换为目标程序，典型阶段包括词法、语法、语义、中间代码、优化和目标代码生成；符号表管理和错误处理贯穿全程。 - 对应位置：lecture 1.pptx，第1-10张 2. **简单语法制导翻译器：从文法到翻译动作** - 核心：语法制导翻译把文法规则和语义动作绑定，使语法分析过程同时产生中间表示或计算属性。 - 对应位置：lecture 2a.pptx，第1-10张 3. **语法制导定义与翻译方案：属性依赖和动作时机** - 核心：属性文法关注属性如何依赖和计算，翻译方案关注动作嵌入产生式后的执行顺序。 - 对应位置：lecture 2b.pptx，第1-10张 4. **词法分析基础：token、lexeme、pattern 和缓冲** - 核心：词法分析器从字符流中识别词素并归类为 token，同时去掉空白注释、报告词法错误、向符号表登记必要信息。 - 对应位置：lecture 3a.pptx，第1-10张 5. **正则表达式、NFA、DFA：词法规则的自动机实现** - 核心：正则表达式描述词法模式，NFA/DFA 提供可执行识别机制，二者可相互转换并用于构造词法分析器。 - 对应位置：lecture 3b.pptx、lecture 3c.pptx，第1-10张 6. **自顶向下语法分析：FIRST/FOLLOW 与 LL(1)** - 核心：自顶向下分析从开始符号出发推导输入串，核心是消除不适合预测分析的文法结构并构造 LL(1) 分析表。 - 对应位置：lecture 4a.pptx、lecture 4b.pptx，第1-10张 7. **自底向上语法分析：LR 项目、移进归约和冲突** - 核心：自底向上分析从输入串逐步归约到开始符号，LR 系列方法通过项目集和分析表决定移进、归约、接受或报错。 - 对应位置：lecture 4c.pptx、lecture 4d.pptx、lecture 4e.pptx，第1-10张 8. **运行时环境：活动记录、栈、堆和作用域** - 核心：运行时环境把源语言中的过程调用、局部变量、参数传递和名字访问落实到内存组织。 - 对应位置：lecture 5a.pptx、lecture 5b.pptx、lecture 5c.pptx，第1-10张 9. **中间代码：语法树、DAG、三地址码和控制流** - 核心：中间表示把复杂语法结构转成便于优化和目标代码生成的形式，常见有语法树、DAG、后缀式和三地址码。 - 对应位置：lecture 6a.pptx、lecture 6b.pptx、lecture 6c.pptx，第1-10张 10. **课程综合：从源程序到目标程序的定位索引** - 核心：综合题通常要求把多个阶段串起来：识别词法单元、构造语法树、附加语义动作、生成中间代码并解释运行时支持。 - 对应位置：lecture 1-6 全部课件；思政进课堂（编译原理）.pptx ## 2. 必背抓手 ### 1. 编译系统总览：阶段、接口和全局支撑 - 编译器、解释器、反编译器和转译器的区别。 - 分析-综合模型：前端负责语言结构，后端负责目标机器相关转换。 - 六阶段加两类支撑：词法、语法、语义、中间代码、优化、目标代码，外加符号表和错误处理。 ### 2. 简单语法制导翻译器：从文法到翻译动作 - 编译器前端模型：词法分析器、语法分析器、中间代码生成器和符号表协同工作。 - 上下文无关文法由终结符、非终结符、开始符号和产生式构成。 - 产生式推导与语法树是理解语法结构的两种常用表示。 ### 3. 语法制导定义与翻译方案：属性依赖和动作时机 - 综合属性由子结点向父结点传递，适合自底向上计算。 - 继承属性由父结点或兄弟结点传递，常用于传上下文信息。 - 动作嵌入位置会影响翻译动作何时执行，是写翻译方案的关键。 ### 4. 词法分析基础：token、lexeme、pattern 和缓冲 - token 是类别，lexeme 是源程序中的具体串，pattern 是匹配规则。 - 词法分析需要处理空白、注释、保留字、标识符和常量。 - 输入缓冲和向前看用于高效识别多字符词素。 ### 5. 正则表达式、NFA、DFA：词法规则的自动机实现 - 正则表达式用并、连接、闭包描述词法集合。 - NFA 允许多后继或空转移，DFA 对每个状态和输入只有唯一后继。 - 子集构造和 DFA 最小化是常见构造题入口。 ### 6. 自顶向下语法分析：FIRST/FOLLOW 与 LL(1) - 左递归会导致递归下降无限展开，需要先消除。 - 提取左因子把共同前缀后移，便于根据向前看符号选择产生式。 - FIRST/FOLLOW 集决定预测分析表的填表位置。 ### 7. 自底向上语法分析：LR 项目、移进归约和冲突 - 句柄是每一步应归约的右部，是自底向上分析的核心。 - LR(0)/SLR/LR(1)/LALR 的差异主要在项目和向前看信息精度。 - 移进-归约、归约-归约冲突常来自文法二义性或向前看信息不足。 ### 8. 运行时环境：活动记录、栈、堆和作用域 - 活动记录保存返回地址、控制链、访问链、局部变量和临时量。 - 静态分配、栈式分配、堆式分配对应不同生命周期需求。 - 嵌套过程和作用域访问依赖访问链或显示表等机制。 ### 9. 中间代码：语法树、DAG、三地址码和控制流 - DAG 可合并公共子表达式，减少重复计算。 - 三地址码接近简单指令，常用四元式、三元式或间接三元式表示。 - 数组寻址、布尔表达式和控制流翻译是常见综合题。 ### 10. 课程综合：从源程序到目标程序的定位索引 - 若题目给正则规则，优先定位到 lecture 3a-3c（词法分析与自动机）。 - 若题目给文法和输入串，优先定位到 lecture 4a-4e（语法分析）。 - 若题目要求翻译表达式或控制流，优先定位到 lecture 2a-2b 与 lecture 6a-6c（语法制导与中间代码）。 ## 3. 便携记忆点 - **编译系统总览**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 1.pptx`，用一句话背：编译器把源程序逐步转换为目标程序，典型阶段包括词法、语法、语义、中间代码、优化和目标代码生成；符号表管理和错误处理贯穿全程。 - **简单语法制导翻译器**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 2a.pptx`，用一句话背：语法制导翻译把文法规则和语义动作绑定，使语法分析过程同时产生中间表示或计算属性。 - **语法制导定义与翻译方案**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 2b.pptx`，用一句话背：属性文法关注属性如何依赖和计算，翻译方案关注动作嵌入产生式后的执行顺序。 - **词法分析基础**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 3a.pptx`，用一句话背：词法分析器从字符流中识别词素并归类为 token，同时去掉空白注释、报告词法错误、向符号表登记必要信息。 - **正则表达式、NFA、DFA**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 3b.pptx、lecture 3c.pptx`，用一句话背：正则表达式描述词法模式，NFA/DFA 提供可执行识别机制，二者可相互转换并用于构造词法分析器。 - **自顶向下语法分析**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 4a.pptx、lecture 4b.pptx`，用一句话背：自顶向下分析从开始符号出发推导输入串，核心是消除不适合预测分析的文法结构并构造 LL(1) 分析表。 - **自底向上语法分析**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 4c.pptx、lecture 4d.pptx、lecture 4e.pptx`，用一句话背：自底向上分析从输入串逐步归约到开始符号，LR 系列方法通过项目集和分析表决定移进、归约、接受或报错。 - **运行时环境**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 5a.pptx、lecture 5b.pptx、lecture 5c.pptx`，用一句话背：运行时环境把源语言中的过程调用、局部变量、参数传递和名字访问落实到内存组织。 - **中间代码**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 6a.pptx、lecture 6b.pptx、lecture 6c.pptx`，用一句话背：中间表示把复杂语法结构转成便于优化和目标代码生成的形式，常见有语法树、DAG、后缀式和三地址码。 - **课程综合**：先想“解决什么问题”，再想“靠什么机制”。定位到 `lecture 1-6 全部课件`，用一句话背：综合题通常要求把多个阶段串起来：识别词法单元、构造语法树、附加语义动作、生成中间代码并解释运行时支持。 ## 4. 考前自测（题目 + 答案） ### 自测 1: 编译系统总览：阶段、接口和全局支撑 **题 1：这个考点的核心问题是什么？** 答案：编译器把源程序逐步转换为目标程序，典型阶段包括词法、语法、语义、中间代码、优化和目标代码生成；符号表管理和错误处理贯穿全程。 **题 2：列出这个考点最该背的 3 个抓手。** 答案： - 编译器、解释器、反编译器和转译器的区别。 - 分析-综合模型：前端负责语言结构，后端负责目标机器相关转换。 - 六阶段加两类支撑：词法、语法、语义、中间代码、优化、目标代码，外加符号表和错误处理。 **题 3：这个考点最容易混淆或出错的地方是什么？** 答案：不要只背阶段名称，要能说出阶段之间传递什么：字符流变 token，token 变语法树，语义补类型和作用域，中间表示再服务优化和生成。 ### 自测 2: 简单语法制导翻译器：从文法到翻译动作 **题 4：这个考点的核心问题是什么？** 答案：语法制导翻译把文法规则和语义动作绑定，使语法分析过程同时产生中间表示或计算属性。 **题 5：列出这个考点最该背的 3 个抓手。** 答案： - 编译器前端模型：词法分析器、语法分析器、中间代码生成器和符号表协同工作。 - 上下文无关文法由终结符、非终结符、开始符号和产生式构成。 - 产生式推导与语法树是理解语法结构的两种常用表示。 **题 6：这个考点最容易混淆或出错的地方是什么？** 答案：语法制导不是另外写一套独立翻译程序，而是让语法结构的构造过程顺手完成属性计算或动作执行。 ### 自测 3: 语法制导定义与翻译方案：属性依赖和动作时机 **题 7：这个考点的核心问题是什么？** 答案：属性文法关注属性如何依赖和计算，翻译方案关注动作嵌入产生式后的执行顺序。 **题 8：列出这个考点最该背的 3 个抓手。** 答案： - 综合属性由子结点向父结点传递，适合自底向上计算。 - 继承属性由父结点或兄弟结点传递，常用于传上下文信息。 - 动作嵌入位置会影响翻译动作何时执行，是写翻译方案的关键。 **题 9：这个考点最容易混淆或出错的地方是什么？** 答案：区分 SDD 和 SDT：前者像数学定义属性怎么算，后者像执行脚本规定什么时候算。 ### 自测 4: 词法分析基础：token、lexeme、pattern 和缓冲 **题 10：这个考点的核心问题是什么？** 答案：词法分析器从字符流中识别词素并归类为 token，同时去掉空白注释、报告词法错误、向符号表登记必要信息。 **题 11：列出这个考点最该背的 3 个抓手。** 答案： - token 是类别，lexeme 是源程序中的具体串，pattern 是匹配规则。 - 词法分析需要处理空白、注释、保留字、标识符和常量。 - 输入缓冲和向前看用于高效识别多字符词素。 **题 12：这个考点最容易混淆或出错的地方是什么？** 答案：最容易混的是 token、pattern、lexeme：标识符是 token，字母开头后接字母数字是 pattern，count 是 lexeme。 ### 自测 5: 正则表达式、NFA、DFA：词法规则的自动机实现 **题 13：这个考点的核心问题是什么？** 答案：正则表达式描述词法模式，NFA/DFA 提供可执行识别机制，二者可相互转换并用于构造词法分析器。 **题 14：列出这个考点最该背的 3 个抓手。** 答案： - 正则表达式用并、连接、闭包描述词法集合。 - NFA 允许多后继或空转移，DFA 对每个状态和输入只有唯一后继。 - 子集构造和 DFA 最小化是常见构造题入口。 **题 15：这个考点最容易混淆或出错的地方是什么？** 答案：NFA 看起来更自由，但识别能力与 DFA 等价；考试更看重你能否把“不确定”系统地消掉。 ### 自测 6: 自顶向下语法分析：FIRST/FOLLOW 与 LL(1) **题 16：这个考点的核心问题是什么？** 答案：自顶向下分析从开始符号出发推导输入串，核心是消除不适合预测分析的文法结构并构造 LL(1) 分析表。 **题 17：列出这个考点最该背的 3 个抓手。** 答案： - 左递归会导致递归下降无限展开，需要先消除。 - 提取左因子把共同前缀后移，便于根据向前看符号选择产生式。 - FIRST/FOLLOW 集决定预测分析表的填表位置。 **题 18：这个考点最容易混淆或出错的地方是什么？** 答案：LL(1) 不是背表格，而是理解“栈顶非终结符 + 当前输入符号”唯一决定下一条产生式。 ### 自测 7: 自底向上语法分析：LR 项目、移进归约和冲突 **题 19：这个考点的核心问题是什么？** 答案：自底向上分析从输入串逐步归约到开始符号，LR 系列方法通过项目集和分析表决定移进、归约、接受或报错。 **题 20：列出这个考点最该背的 3 个抓手。** 答案： - 句柄是每一步应归约的右部，是自底向上分析的核心。 - LR(0)/SLR/LR(1)/LALR 的差异主要在项目和向前看信息精度。 - 移进-归约、归约-归约冲突常来自文法二义性或向前看信息不足。 **题 21：这个考点最容易混淆或出错的地方是什么？** 答案：分析表不是死记表格，而是把当前状态和输入符号映射成动作；冲突说明这个映射不够唯一。 ### 自测 8: 运行时环境：活动记录、栈、堆和作用域 **题 22：这个考点的核心问题是什么？** 答案：运行时环境把源语言中的过程调用、局部变量、参数传递和名字访问落实到内存组织。 **题 23：列出这个考点最该背的 3 个抓手。** 答案： - 活动记录保存返回地址、控制链、访问链、局部变量和临时量。 - 静态分配、栈式分配、堆式分配对应不同生命周期需求。 - 嵌套过程和作用域访问依赖访问链或显示表等机制。 **题 24：这个考点最容易混淆或出错的地方是什么？** 答案：运行时环境难在把程序结构翻译成内存位置；递归必须用栈，因为同一过程可能同时存在多个活动记录。 ### 自测 9: 中间代码：语法树、DAG、三地址码和控制流 **题 25：这个考点的核心问题是什么？** 答案：中间表示把复杂语法结构转成便于优化和目标代码生成的形式，常见有语法树、DAG、后缀式和三地址码。 **题 26：列出这个考点最该背的 3 个抓手。** 答案： - DAG 可合并公共子表达式，减少重复计算。 - 三地址码接近简单指令，常用四元式、三元式或间接三元式表示。 - 数组寻址、布尔表达式和控制流翻译是常见综合题。 **题 27：这个考点最容易混淆或出错的地方是什么？** 答案：DAG 与语法树的关键差别是共享：同一表达式出现多次时，DAG 可以只保留一个结点。 ### 自测 10: 课程综合：从源程序到目标程序的定位索引 **题 28：这个考点的核心问题是什么？** 答案：综合题通常要求把多个阶段串起来：识别词法单元、构造语法树、附加语义动作、生成中间代码并解释运行时支持。 **题 29：列出这个考点最该背的 3 个抓手。** 答案： - 若题目给正则规则，优先定位到 lecture 3a-3c（词法分析与自动机）。 - 若题目给文法和输入串，优先定位到 lecture 4a-4e（语法分析）。 - 若题目要求翻译表达式或控制流，优先定位到 lecture 2a-2b 与 lecture 6a-6c（语法制导与中间代码）。 **题 30：这个考点最容易混淆或出错的地方是什么？** 答案：复习时按“输入是什么、输出是什么、依赖哪张表或哪种结构”定位，比按课件文件名死背更稳。 ## 5. 最后一遍怎么背 1. 先顺着知识脉络背一遍标题，确认自己知道每一章在解决什么问题。 2. 再只看“必背抓手”，能口述就过，卡住就回对应位置。 3. 最后做自测题，答案说不完整的地方就是考前最后要补的点。