1. 编译引论
   1. 编译程序
   2. 源语言，源程序
   3. 目标语言，目标程序
   4. 宿主语言，宿主机
   5. 分类：解释程序，编译程序，汇编程序
   6. 分类：解释执行，编译执行
   7. 编译程序结构
      1. 词法分析
      2. 语法分析
      3. 语义分析和中间代码生成
      4. 代码优化
      5. 目标代码生成
      6. 表格管理
      7. 出错处理
      8. 五个阶段
   8. 遍
      1. 一遍
      2. 多遍
      3. 区别
   9. T型图
      1. 交叉编译
2. 形式语言自动机理论
   1. 文法和语言
      1. 字母表
      2. 字符串
      3. 符号串长度
      4. 符号串子串
      5. 符号串的连接
      6. 符号串的方幂
      7. 符号串集合的乘积
      8. 符号串集合的方幂
      9. 集合的闭包
      10. 文法四元组
      11. 元语言
      12. 推导
          1. 直接推导
          2. 直接推导序列
          3. 最左、最右推导
      13. 句型，句子，规范句型
      14. 文法递归
      15. 语言
      16. 文法等价
   2. 文法表示方法
      1. BNF表示法
      2. 扩充BNF(EBNF)表示法
      3. 语法图表示法
      4. 属于元语言
   3. 文法二义性
      1. 语法分析树
      2. 二义文法
   4. 文法和语言的类型
      1. 0型文法-短语结构文法
      2. 1型文法-上下文有关文法
      3. 2型文法-上下文无关文法
      4. 3型文法-正则文法，线性文法
      5. 从上到下限制越来越严，但描述功能越来越弱
   5. 有限自动机
      1. 确定的有限自动机
         1. 五元组
            1. 状态有限集合
            2. 输入字符的有限集合
            3. 状态转换函数
            4. 唯一初态
            5. 终态集
         2. 化简
            1. 接受状态，拒绝状态
            2. 状态等价，不等价（可区别）
            3. 无关状态
            4. 划分法
            5. 归约有限自动机
      2. 非确定的有限自动机
         1. 五元组
            1. 区别在于后继状态不唯一
      3. 两者区别
         1. 非确定的状态转换函数值是一个状态子集
         2. 非确定的可以带空串转换
      4. 两者等价
         1. 闭包
         2. 子集法
      5. 正规式，正规集
         1. 正规式和有限自动机等价转换算法
3. 词法分析
   1. 输入与输出
      1. 关键字
      2. 常数
      3. 标识符
      4. 运算符
      5. 界限符
      6. 属性字-输出
      7. 单词-输入
   2. 输入与预处理
      1. 输入缓冲区-对半互补
      2. 预处理
         1. 滤掉源程序中的注释
         2. 剔除远程系中的无用字符
         3. 进行宏替换
         4. 实现文件包含的嵌入和条件编译的嵌入
   3. 词法分析器状态转换图构造方法
      1. 对程序的单词按类构造相应的状态转换图
         1. 超前搜索
      2. 对各类状态转换图合并
      3. 程序中心法
      4. 数据中心法
         1. 主表（状态，分表地址），分表
      5. 步骤
      6. 方法
   4. 自动生成器（Lex/Flex）
      1. X-构造能识别正规式描述的单词集
      2. Y-子集法
      3. Z-划分算法
      4. Lex运行
         1. pas.l-Lex编译器-Lex.yy.c
         2. Lex.yy.c-C编译器-a.out
         3. PAS源程序-a.out-PAS语言源程序的词法分析结果
         4. 三个步骤
      5. Lex编译器内部结构
4. 语法分析
   1. 构造
      1. 源程序串L
      2. 源程序的文法G
      3. 识别出的语法范畴表示
   2. 自上而下分析
      1. 综述
         1. 功能：编译程序的核心
         2. 分析方法
            1. 自上而下分析
            2. 产生
            3. 面向目标
            4. 推导过程
            5. 自下而上分析
            6. 辨认
            7. 基于目标
            8. 归约过程
      2. 不确定自上而下语法分析
         1. 一般-试探推导-回溯
         2. 左递归
            1. 直接左递归
            2. 间接左递归
         3. 左公因子
         4. 回溯
            1. First集
      3. LL(1)分析
         1. 分析器构造
            1. 总控程序
            2. LL(1)分析表
            3. 分析栈
         2. 分析表构造
            1. Follow集
            2. 判断唯一候选条件
         3. LL(1)文法
            1. 任何LL(1)文法都无二义性
            2. 含有左递归的文法必然是非LL(1)文法
            3. 非LL(1)语言存在
            4. 存在算法判断任一文法是LL(1)文法
            5. 存在算法判断两个LL(1)文法是否产生相同语言
            6. 不存在算法判定上下文无关语言能否由LL(1)文法产生
   3. 自下而上分析
      1. 移进-归约的自下而上分析
         1. 采取分析动作：移进，归约，接受或报错
            1. 判断栈顶字符串的可规约性
            2. 决定选用文法中的哪条规则进行归约
            3. 自下而上分析的关键问题
         2. 短语
         3. 直接短语
         4. 句柄-最左直接短语
      2. 算符优先分析
         1. 优先关系-低于，高于，等于
         2. 算符优先文法
            1. 算符文法
            2. 算符优先文法
            3. 算法优先表
            4. 任何句型都不会含两个连续非终结符
         3. FirstVT和LastVT集合
         4. 素短语
            1. 最左素短语
         5. 优先函数表的构造
            1. 引入原因
            2. 终结符N个，优先关系表大小（N+1）^2
            3. 终结符N个，优先函数表大小2*（N+1）
         6. 算符优先分析器
            1. 总控程序
            2. 分析栈
            3. 优先函数表
            4. 组成
      3. LR分析
         1. 最常用，最有效的一种分析方法
            1. 理论上比较完善
            2. 适用性强，对G的限定少
            3. 便于自动生成
         2. 输入串-分析对象
         3. 下推分析栈
            1. 状态符号
            2. 文法符号
            3. 历史-展望信息
            4. 内容
         4. LR分析总控程序
         5. LR分析表
            1. 动作表
            2. 依据-栈顶当前状态和当前输入符号
            3. 移进
            4. 归约
            5. 接受
            6. 出错
            7. 动作
            8. 状态转换表
            9. 依据-栈顶状态和面临的符号
         6. LR文法
            1. LR(K)文法
            2. 任何LR(K)文法都是无二义性文法，任何二义性文法都不是LR(K)文法
         7. LR(0)分析
            1. 实现思想
            2. 活前缀
            3. 活前缀中已含有句柄的全部符号-特殊-可归前缀
            4. 活前缀中只含有句柄的一部分符号
            5. 活前缀中不包含句柄的任何符号
            6. 活前缀与句柄之间关系
            7. LR(0)项目
            8. 归约项目
            9. 接受项目
            10. 移进项目
            11. 待约项目
            12. · 表示栈顶和源程序串的分界点
            13. 构造识别所有活前缀的非确定有限自动机
            14. 开始符号的第一个产生式为NFA的唯一初态
            15. 令所有LR(0)项目为NFA的一个状态，归约项目为终态
            16. 圆点只差一个位置的两个项目中间连接一条弧
            17. 待约符号需要求出闭包
            18. LR(0)项目分类
            19. LR(0)项目集规范族
            20. GO函数
            21. LR(0)文法
            22. 即含移进项目又含归约项目
            23. 含有多个归约项目
            24. 识别可归约前缀DFA的每一个状态不存在
         8. SLR(1)分析
            1. Follow集
            2. SLR(1)文法
         9. LR(1)分析
            1. 搜索符
         10. LALR(1)分析
             1. 同心项目集
             2. 项目集中的LR(0)相同
             3. 搜索符不同
         11. 判断文法
             1. LR(0)
             2. SLR(1)
             3. LR(1)
             4. LALR(1)
             5. 从上到下，依次判断，LR(1)可能性最大
         12. 常识
             1. 任何一个二义文法都不是一个LR文法
             2. 二义文法会导致语法分析的二义性
         13. 逻辑结构
      4. LR分析中错误与恢复
         1. 错误种类
            1. 词法错误
            2. 语法错误
            3. 语义错误
            4. 违反环境限制错误
         2. 错误恢复
            1. 紧急恢复方式
            2. 短语级恢复
            3. 出错产生式
            4. 全局纠正
5. 语义分析和中间代码生成
   1. 语义分析概念
      1. 任务：进行语义处理和检查，产生相应中间代码或目标代码
      2. 中间代码：介于源语言和目标代码之间的一种代码
         1. 方便生成目标代码
         2. 便于移植
         3. 便于优化
         4. 引入中间代码作用
   2. 语法制导翻译
      1. 任务-按照语法范畴进行语义处理，翻译成相应的中间代码
      2. 属性翻译文法
      3. 分析树
         1. 继承属性
         2. 综合属性
         3. 一个结点的属性值是通过子结点的属性值得到的
         4. 一个结点的属性值是由父亲结点或兄弟结点得到的
   3. 中间语言
      1. 逆波兰式表示
         1. 表达式中不带括号，计算顺序表示清晰
         2. 运算处理方便
         3. 优点
      2. N-元式表示
         1. 三元式
            1. 三元式顺序编号-NO
            2. 操作符-OP
            3. ARG1-第一操作数，ARG2-第二操作数
            4. 组成
         2. 间接三元式
            1. 用间接码表单独给出三元式的执行顺序
         3. 四元式
            1. OP-操作符
            2. ARG1-第一操作数，ARG2-第二操作数
            3. RESULT-计算结果操作数
      3. 图表示
         1. 三元式-一棵子树
         2. OP-子树根
         3. ARG1-子树左叶结点
         4. ARG2-子树右叶结点
   4. 中间代码生成
      1. 说明类语句翻译
         1. 常理定义语句翻译
         2. 简单数据类型变量说明语句翻译
         3. 记录结构型数据说明翻译
      2. 赋值语句和表达式翻译
         1. 赋值语句翻译
         2. 算术表达式翻译
         3. 逻辑表达式翻译
      3. 控制流语句翻译
         1. 控制流语句特点
         2. 语句标号与拉链返填技术
            1. 语句标号处理
            2. 先定义后引用
            3. 先引用后定义
            4. 定义性出现 L:S
            5. 使用性出现 goto L
            6. 标号表
            7. 标号名
            8. 定义与否标志
            9. 0-使用性出现
            10. 1-定义性出现
            11. 地址
            12. 组成
            13. 语句标号
            14. 显式-位于源语句之前
            15. 隐式-内含与源语句之中，且在源程序中未标识
            16. 拉链返填技术
            17. 链头在代码区的四元式中
            18. 链尾在标号表中
            19. 链在与同一语句相关的跳转代码中
         3. 条件语句翻译
         4. 循环语句翻译
         5. 多分支语句翻译
      4. 数组元素引用
         1. 信息向量表
         2. 数组存储方式
            1. 按行
            2. 按列
         3. 数组元素地址计算
         4. 数组元素引用目标结构
         5. 动态数组
            1. 产生此部分代码，静态数组元素引用
      5. 函数翻译
         1. 处理调用
         2. 处理说明
6. 运行环境
   1. 存储组织和分配
      1. 过程
      2. 活动
      3. 生存期
      4. 存储空间
         1. 静态
            1. 过程的定义
            2. 名字的声明
            3. 声明的作用域
            4. 符号表
         2. 动态
            1. 过程的活动
            2. 名字的绑定
            3. 绑定的生存期
            4. 活动记录
         3. 声明
         4. 绑定
      5. 运行环境
         1. 环境-状态的区别
         2. 环境与语言特性相关
      6. 变量与值的映射
         1. 名字-存储位置-值
            1. 环境-绑定
            2. 状态-赋值
            3. 区别
            4. 赋值改变状态，不改变环境
            5. 环境与语言特性相关
      7. 存储分配策略
         1. 静态存储分配
            1. 对语言的限制
            2. 数据对象的长度和它在内存中位置的限制必须在编译时知道
            3. 不允许递归过程
            4. 数据结构不能动态建立
         2. 动态存储分配
            1. 栈式存储分配
            2. 堆式存储分配
         3. 存储分配过程的活动记录AR
         4. 存储区保存的对象
            1. 生成的目标代码
            2. 目标代码运行时的数据空间
            3. 记录过程活动的控制栈
   2. 基于栈的存储分配
      1. 静态链
      2. 存取链SL
      3. 控制链SP/DL
      4. 嵌套层次显示表DISPLAY
      5. 函数所需的数据空间
         1. 生存期在本过程本次活动中的数据对象
         2. 管理过程活动的记录信息
      6. 主程序在第0层
   3. 基于堆的存储分配
   4. 静态，栈，堆关系
      1. 可以静态分配的数据可以栈分配
      2. 可以静态和栈分配的数据可以堆分配
7. 代码优化
   1. 概述
      1. 代码优化定义
      2. 优化整体过程
         1. 等价-不改变程序的执行效果
         2. 变换-引起程序形式上的变动
      3. 改进，提供程序途径
         1. 改进算法
         2. 在源程序级上等价变换
         3. 利用系统提供的程序库
         4. 编译时优化
      4. 优化的目的-产生高效的目标代码
         1. 空间-程序及数据所占空间尽可能少
         2. 时间-源程序运行时间尽可能短
         3. 高效
      5. 优化技术分类
         1. 全局优化
         2. 局部优化
         3. 循环优化
      6. 优化阶段
         1. 中间代码级优化
         2. 目标代码级优化
      7. 优化具体实现
         1. 常量合并与传播
         2. 公共子表达式删除
         3. 死代码删除
         4. 无用转移语句删除
         5. 循环不变量或不变代码外提
         6. 函数嵌套
         7. 循环转换
         8. 其他
      8. 优化编译程序的组织
         1. 控制流分析
         2. 数据流分析
         3. 代码变换
   2. 局部优化
      1. 基本块
         1. 基本块特点
         2. 基本块划分
            1. 入口语句
            2. 程序的第一个语句
            3. 由条件转移语句或无条件转移语句转移到的语句
            4. 紧跟在条件转移语句和无条件转移语句后面的语句
         3. 基本块确定
            1. 由该入口语句和下一个入口语句之间的所有语句构成的一个基本块
            2. 由该入口语句到一转移语句之间的所有语句构成的基本块
            3. 由该入口语句到程序中的停止或暂停语句之间的语句序列构成一个基本块
      2. 程序的控制流图
         1. 流图的所有结点组成的集合
         2. 流图的首节点
         3. 流图的所有有向边组成的集合
         4. 组成
      3. DAG
         1. 组成
            1. 叶节点-标识符或常量
            2. 内部结点-运算符标记或计算值
            3. 标识符-一个结点上可以有多个
         2. 类型
            1. 0型-定值语句
            2. 1型-单目运算且定值
            3. 2型-双目运算，取数组元素且定值
   3. 循环查找
      1. 循环条件
         1. 强连通性
         2. 入口惟一
      2. 必经结点
         1. 自反性
         2. 传递性
         3. 反对称性
         4. 满足偏序关系
      3. 必经结点集
      4. 回边
         1. 利用回边求循环
   4. 数据流分析
      1. 点
      2. 通路
      3. 定值点
      4. 定值方式
         1. 赋值语句
         2. 输入语句
         3. 函数调用的形参与实参结合
      5. 引用点
         1. i=i+1；前面为定值点，后面为引用点
         2. i++;既是定值点也是引用点
      6. 到达-定值
      7. ud链-引用-定值链
         1. 相对于引用点的定值情况
      8. 活跃变量
      9. du链-定值-引用链
         1. 相对于定值点的引用情况
   5. 循环优化
      1. 循环前置结点
      2. 代码外提
         1. 不变运算
         2. 限制条件
            1. A所在的结点是所有出口结点的必经结点
            2. 在L对A不止一次定值情况下不允许外提
            3. L中的所有A引用点只有S中的定值点才能到达
      3. 强度削弱
      4. 删除归纳变量
         1. 基本归纳变量
         2. 归纳变量
         3. 顺序
            1. 寻找归纳变量
            2. 强度削弱
            3. 删除归纳变量
            4. 从上往下执行
      5. 循环展开，合并