引论
编程语言的演化
- 机器语言 -> 汇编语言 -> 高级语言
- 各种典型语言的特征
编译器的结构
- 前端和后端的划分
- 各组成部分及其作用
编译器 V.S. 解释器
词法分析
token, pattern, lexeme, string, language
Grammar calculation: 并，连接，Kleene闭包，正闭包
正则表达式及正则语言
有限自动机
- NFA：非确定有限自动机
- DFA：确定有限自动机
两个关键算法
- 正则表达式转NFA（Thompson构造法）
- NFA转DFA（子集构造法）
语法分析
上下文无关文法及上下文无关语言：终结符、非终结符、产生式
推导 (derivation)：最左最右推导
文法的句型 (sentential form)
文法的句子 (sentence)
语法分析树 (parse tree)
抽象语法树 (abstract syntax tree)
文法的二义性
正则表达式 V.S. 上下文无关文法：正则语言 V.S. 上下文无关语言
语法分析技术
自顶向下分析方法
- 递归下降语法分析 (Recursive-descent parsing)
- LL(1)文法及预测分析表的构造
- 非递归表格驱动的语法分析
自底向上分析方法
- 移入-归约语法分析框架 (Shift-reduce parsing)
- LR语法分析器及分析算法
- SLR方法 (尤其是LR(0) 项集族构造)
- CLR、LALR算法细节不考，但三种LR算法的基本原理和优劣需要了解
语法制导的翻译
语法制导定义 (Syntax-directed definitions)
语法制导的翻译方案 (Syntax-directed translation schemes)
属性：合成属性和继承属性
语义规则 (semantic rules) 和 语义动作(semantic actions)
语法制导定义属性值的计算顺序：依赖图
S属性的语法制导定义、L属性的语法制导定义
中间代码生成
三地址码指令及其表示方法：四元式、三元式、间接三元式
类型检查
- 类型表达式
- 类型等价：名等价、结构等价
- 强类型、弱类型
数组元素相对地址计算
- 行优先布局
- 列优先布局
类型转化：拓宽、窄化
控制流翻译中的回填技术（了解基本思想、不考细节）
运行时刻环境
运行时刻内存的逻辑构成（代码区、堆区、栈区等）
方法调用
- 活动树（activation tree）
- 活动记录（activation record）
- 方法调用栈
- 调用代码序列和返回代码序列的作用
内存管理
- 内存的分配和回收
- 程序局部性现象
- 内存碎片化现象
代码生成
如何为方法调用及返回生成代码
- 静态分配
- 栈式分配
基本块和控制流图
- 基本块切分算法
- 控制流图构造算法
控制流图中的循环
寄存器分配
- 寄存器描述符和地址描述符的作用
- 寄存器分配算法（掌握基本原则即可）
代码优化
常见局部优化技术
- 局部公共子表达式消除
- 死代码消除
- 代数恒等式的应用
数据流分析框架及经典问题（到达定值）