编译原理
编写人：2022级 计算机科学与技术 张植翔
上课学期：2025 春季
教师：谭添
课程简介
基本上课程 ppt 足够 survive，我自己在学习的时候只做了一部分章节的内容补充，其中我个人认为需要好好理解的是第九章“机器无关优化”相关的内容，这个如果你上过秋季学期李樾、谭添两位老师的软件分析的话应该会学得比较轻松。
复习提纲
Note
此为笔者自己总结，实际的考试内容以你们那一年的内容为准，可能有出入（缺漏/多余）
- 词法分析
- 功能和作用
- 相关概念：字母表、串、语言等
- 正则表达式、状态转换图
- 有穷自动机：确定 (DFA) vs. 不确定 (NFA)
- NFA和DFA识别串的模拟
- 正则表达式 → NFA → DFA
- 最小化算法
- 语法分析
- 功能和作用
- 相关概念：文法 (上下文无关文法)、推导 (最左和最右)、语法分析树等
- 二义性、左递归及其消除
- 自顶向下分析技术
- 递归下降
- 预测分析：FIRST和FOLLOW、预测分析表、分析流程、LL(1)文法
- 自底向上分析技术
- 句柄、移入-归约的分析框架
- LR分析技术：项、项集、项集闭包、项集规范族、增广文法、语法分析表 (ACTION表、GOTO表)
- SLR(1)分析表的构造 (LR(0)项)
- 规范LR(1)分析表的构造 (LR(1)项)
- LALR分析、与SLR和LR分析的比较
- 二义性文法的分析
- 错误恢复（恐慌模式、短语层次的恢复）
- 语法制导的翻译方案
- 语法制导的定义
- 属性 (综合属性、继承属性)、语义规则、属性求值
- 注释语法分析树、求值顺序、依赖图
- S属性定义、L属性定义
- 语法制导的定义 → 翻译方案
- 中间代码生成
- 中间代码的形式
- DAG图、抽象语法树、三地址代码
- 类型声明
- 类型表达式、类型等价、类型的声明、局部变量的存储布局、记录和类
- 表达式的翻译
- 数组元素的寻址、数组引用的翻译
- 控制流语句的翻译
- 控制流语句、布尔表达式、非回填 vs. 回填
- 运行时刻环境
- 存储组织
- 三种方式及其特点
- 栈式存储分配
- 活动树、活动记录 (布局)
- 过程的调用及返回
- 非局部数据的访问 (不支持嵌套过程 vs. 支持嵌套过程)
- 堆存储分配：垃圾回收
- 可达性、引用计数、基于跟踪的回收
- 代码生成
- 目标语言、指令寻址
- 目标代码中的地址
- 静态分配、栈分配
- 对中间代码进行局部优化
- 基本块和流图、基本块的优化
- 代码生成器
- 寄存器和地址描述符、代码生成算法、寄存器分配
- 机器无关的代码优化
- 优化的机会
- 全局公共子表达式、复制传播、死代码消除、代码移动、归纳变量和强度削减
- 数据流分析
- 到达定值、活跃变量、可用表达式
- 懒惰代码移动
- 流图中的循环
- 支配结点树、回边、自然循环