# 编译原理知识点复习大纲

> 知识主线：总览 -> 文法 -> 语法制导 -> 词法 -> 语法分析 -> 运行时 -> 中间代码

## 使用说明

- 每个知识点后都标注了对应课件位置。
- PDF 课件用页码定位；PPT/PPTX 或旧版 PPT 用幻灯片范围/讲次定位。
- 后续如果提供考试重点，可直接按这些标题或位置做高亮。

## 1. 编译系统总览：阶段、接口和全局支撑

**来源位置：** lecture 1.pptx，第1-10张

**总结：** 编译器把源程序逐步转换为目标程序，典型阶段包括词法、语法、语义、中间代码、优化和目标代码生成；符号表管理和错误处理贯穿全程。

**重要知识点：**

- 编译器、解释器、反编译器和转译器的区别（位置：lecture 1.pptx，第2-7张）。
- 分析-综合模型：前端负责语言结构，后端负责目标机器相关转换（位置：lecture 1.pptx，第8-9张）。
- 六阶段加两类支撑：词法、语法、语义、中间代码、优化、目标代码，外加符号表和错误处理（位置：lecture 1.pptx，第9-10张）。

**难点拆解：** 不要只背阶段名称，要能说出阶段之间传递什么：字符流变 token，token 变语法树，语义补类型和作用域，中间表示再服务优化和生成。

**通俗例子：** 翻译文章也是先分词、再看句法、再理解含义，最后换成另一种语言表达。

## 2. 简单语法制导翻译器：从文法到翻译动作

**来源位置：** lecture 2a.pptx，第1-10张

**总结：** 语法制导翻译把文法规则和语义动作绑定，使语法分析过程同时产生中间表示或计算属性。

**重要知识点：**

- 编译器前端模型：词法分析器、语法分析器、中间代码生成器和符号表协同工作（位置：lecture 2a.pptx，第2-3张）。
- 上下文无关文法由终结符、非终结符、开始符号和产生式构成（位置：lecture 2a.pptx，第4-7张）。
- 产生式推导与语法树是理解语法结构的两种常用表示（位置：lecture 2a.pptx，第6-10张）。

**难点拆解：** 语法制导不是另外写一套独立翻译程序，而是让语法结构的构造过程顺手完成属性计算或动作执行。

**通俗例子：** 表达式 E -> E + T 的值可以由左边 E 的值和 T 的值综合出来。

## 3. 语法制导定义与翻译方案：属性依赖和动作时机

**来源位置：** lecture 2b.pptx，第1-10张

**总结：** 属性文法关注属性如何依赖和计算，翻译方案关注动作嵌入产生式后的执行顺序。

**重要知识点：**

- 综合属性由子结点向父结点传递，适合自底向上计算（位置：lecture 2b.pptx，第1-4张）。
- 继承属性由父结点或兄弟结点传递，常用于传上下文信息（位置：lecture 2b.pptx，第4-7张）。
- 动作嵌入位置会影响翻译动作何时执行，是写翻译方案的关键（位置：lecture 2b.pptx，第7-10张）。

**难点拆解：** 区分 SDD 和 SDT：前者像数学定义属性怎么算，后者像执行脚本规定什么时候算。

**通俗例子：** 做菜配方里的“混合后加热”和“边加热边搅拌”结果相近，但动作时机不同。

## 4. 词法分析基础：token、lexeme、pattern 和缓冲

**来源位置：** lecture 3a.pptx，第1-10张

**总结：** 词法分析器从字符流中识别词素并归类为 token，同时去掉空白注释、报告词法错误、向符号表登记必要信息。

**重要知识点：**

- token 是类别，lexeme 是源程序中的具体串，pattern 是匹配规则（位置：lecture 3a.pptx，第1-4张）。
- 词法分析需要处理空白、注释、保留字、标识符和常量（位置：lecture 3a.pptx，第4-7张）。
- 输入缓冲和向前看用于高效识别多字符词素（位置：lecture 3a.pptx，第7-10张）。

**难点拆解：** 最容易混的是 token、pattern、lexeme：标识符是 token，字母开头后接字母数字是 pattern，count 是 lexeme。

**通俗例子：** 身份证号的格式规则是 pattern，某个人的号码是 lexeme，身份证号这个类别是 token。

## 5. 正则表达式、NFA、DFA：词法规则的自动机实现

**来源位置：** lecture 3b.pptx、lecture 3c.pptx，第1-10张

**总结：** 正则表达式描述词法模式，NFA/DFA 提供可执行识别机制，二者可相互转换并用于构造词法分析器。

**重要知识点：**

- 正则表达式用并、连接、闭包描述词法集合（位置：lecture 3b.pptx，第1-4张）。
- NFA 允许多后继或空转移，DFA 对每个状态和输入只有唯一后继（位置：lecture 3b.pptx，第4-10张）。
- 子集构造和 DFA 最小化是常见构造题入口（位置：lecture 3c.pptx，第1-10张）。

**难点拆解：** NFA 看起来更自由，但识别能力与 DFA 等价；考试更看重你能否把“不确定”系统地消掉。

**通俗例子：** 多条岔路都试一遍是 NFA，把所有可能位置打包成一个集合状态就是 DFA 化。

## 6. 自顶向下语法分析：FIRST/FOLLOW 与 LL(1)

**来源位置：** lecture 4a.pptx、lecture 4b.pptx，第1-10张

**总结：** 自顶向下分析从开始符号出发推导输入串，核心是消除不适合预测分析的文法结构并构造 LL(1) 分析表。

**重要知识点：**

- 左递归会导致递归下降无限展开，需要先消除（位置：lecture 4a.pptx，第1-4张）。
- 提取左因子把共同前缀后移，便于根据向前看符号选择产生式（位置：lecture 4a.pptx，第4-7张）。
- FIRST/FOLLOW 集决定预测分析表的填表位置（位置：lecture 4b.pptx，第1-10张）。

**难点拆解：** LL(1) 不是背表格，而是理解“栈顶非终结符 + 当前输入符号”唯一决定下一条产生式。

**通俗例子：** 先看路线总图，再根据当前路标决定展开哪条支路。

## 7. 自底向上语法分析：LR 项目、移进归约和冲突

**来源位置：** lecture 4c.pptx、lecture 4d.pptx、lecture 4e.pptx，第1-10张

**总结：** 自底向上分析从输入串逐步归约到开始符号，LR 系列方法通过项目集和分析表决定移进、归约、接受或报错。

**重要知识点：**

- 句柄是每一步应归约的右部，是自底向上分析的核心（位置：lecture 4c.pptx，第1-5张）。
- LR(0)/SLR/LR(1)/LALR 的差异主要在项目和向前看信息精度（位置：lecture 4d.pptx，第1-10张）。
- 移进-归约、归约-归约冲突常来自文法二义性或向前看信息不足（位置：lecture 4e.pptx，第1-10张）。

**难点拆解：** 分析表不是死记表格，而是把当前状态和输入符号映射成动作；冲突说明这个映射不够唯一。

**通俗例子：** 拼积木时先把小零件组合成局部结构，再逐步归约成整件模型。

## 8. 运行时环境：活动记录、栈、堆和作用域

**来源位置：** lecture 5a.pptx、lecture 5b.pptx、lecture 5c.pptx，第1-10张

**总结：** 运行时环境把源语言中的过程调用、局部变量、参数传递和名字访问落实到内存组织。

**重要知识点：**

- 活动记录保存返回地址、控制链、访问链、局部变量和临时量（位置：lecture 5a.pptx，第1-10张）。
- 静态分配、栈式分配、堆式分配对应不同生命周期需求（位置：lecture 5b.pptx，第1-10张）。
- 嵌套过程和作用域访问依赖访问链或显示表等机制（位置：lecture 5c.pptx，第1-10张）。

**难点拆解：** 运行时环境难在把程序结构翻译成内存位置；递归必须用栈，因为同一过程可能同时存在多个活动记录。

**通俗例子：** 每次函数调用都像开一张临时会议记录表，会议结束后表可以撤销。

## 9. 中间代码：语法树、DAG、三地址码和控制流

**来源位置：** lecture 6a.pptx、lecture 6b.pptx、lecture 6c.pptx，第1-10张

**总结：** 中间表示把复杂语法结构转成便于优化和目标代码生成的形式，常见有语法树、DAG、后缀式和三地址码。

**重要知识点：**

- DAG 可合并公共子表达式，减少重复计算（位置：lecture 6a.pptx，第1-10张）。
- 三地址码接近简单指令，常用四元式、三元式或间接三元式表示（位置：lecture 6b.pptx，第1-10张）。
- 数组寻址、布尔表达式和控制流翻译是常见综合题（位置：lecture 6c.pptx，第1-10张）。

**难点拆解：** DAG 与语法树的关键差别是共享：同一表达式出现多次时，DAG 可以只保留一个结点。

**通俗例子：** a+b+a+b 可先算 tmp=a+b，再复用 tmp，而不是重复生成两棵相同子树。

## 10. 课程综合：从源程序到目标程序的定位索引

**来源位置：** lecture 1-6 全部课件；思政进课堂（编译原理）.pptx

**总结：** 综合题通常要求把多个阶段串起来：识别词法单元、构造语法树、附加语义动作、生成中间代码并解释运行时支持。

**重要知识点：**

- 若题目给正则规则，优先定位到 lecture 3a-3c（词法分析与自动机）。
- 若题目给文法和输入串，优先定位到 lecture 4a-4e（语法分析）。
- 若题目要求翻译表达式或控制流，优先定位到 lecture 2a-2b 与 lecture 6a-6c（语法制导与中间代码）。

**难点拆解：** 复习时按“输入是什么、输出是什么、依赖哪张表或哪种结构”定位，比按课件文件名死背更稳。

**通俗例子：** 看到 FIRST/FOLLOW 就去语法分析，看到 token/lexeme 就去词法分析，看到活动记录就去运行时环境。