第1章 编译器概述
1.1 为什么要学习编译技术
1.2 编译器和解释器
1.3 编译器的功能分解和组织结构
1.4 编译器的伙伴
1.5 编译器的复杂性
1.6 编译器的设计与实现
1.7 编译器的测试与维护
第2章 一个微型编译器
2.1 基础知识
2.2 ToyL语言
2.3 ToyL语言词法分析器
2.4 ToyL语言语法分析器
2.5 ToyL语言解释器
2.6 ToyL语言编译器
第3章 有穷自动机与词法分析
3.1 词法分析基础
3.1.1 词法分析器的功能
3.1.2 单词识别
3.1.3 词法分析的复杂性
3.1.4 字符串
3.1.5 保留字处理
3.1.6 空格符?回车符?换行符
3.1.7 括号类配对预检
3.1.8 词法错误修正
3.1.9 词法分析独立化的意义
3.2 有穷自动机
3.2.1 确定有穷自动机的定义
3.2.2 确定有穷自动机的实现
3.2.3 非确定有穷自动机
3.2.4 NFA到DFA的转换
*3.2.5 确定有穷自动机的极小化
*3.2.6 自动机状态转换表的实现
3.3 正则表达式
3.3.1 正则符号串集
3.3.2 正则表达式的定义
3.3.3 正则表达式的局限性
3.3.4 正则定义
3.3.5 正则表达式到有穷自动机的转换
*3.4 词法分析器的构造
3.4.1 用DFA人工构造词法分析器
3.4.2 词法分析器的生成器Lex
练习
第4章 文法与语法分析
4.1 语法分析
4.1.1 语法分析器的输入
4.1.2 语法分析的任务
4.1.3 语法分析方法分类
4.2 文法和文法分析
4.2.1 上下文无关文法和语言
4.2.2 最左推导和最右推导
4.2.3 语法分析树与二义性
4.2.4 文法分析算法
4.2.5 自顶向下方法概述
4.2.6 自底向上方法概述
4.3 递归下降法——自顶向下分析
4.3.1 递归下降法原理
4.3.2 消除公共前缀
4.3.3 代入
4.3.4 消除左递归
4.4 LL分析方法——自顶向下分析
4.4.1 LL(1)文法
4.4.2 LL(1)分析表
4.4.3 LL(1)分析的驱动器
4.4.4 LL(1)中的If-Then-Else问题
*4.4.5 LL(1)分析器的自动生成器LLGen
*4.4.6 LL(1)分析法与递归下降法的比较
*4.4.7 正则文法
4.5 LR方法——自底向上分析
4.5.1 句柄
4.5.2 活前缀
4.5.3 归约活前缀识别器——LR(0)自动机
4.5.4 LR(0)文法及其分析算法
4.5.5 SLR(1)文法及其分析算法
4.5.6 LR(1)文法
4.5.7 LALR(1)文法
4.5.8 二义性文法的处理
4.5.9 另一种Shift-Reduce分析技术:简单优先法
*4.5.10 LL(1)和LALR(1)方法比较
4.6 LR分析器的生成器
4.6.1 LALR分析器的生成器YACC
4.6.2 LALR分析器的生成器LALRGen
*4.7 语法错误处理
4.7.1 错误恢复和修复
4.7.2 递归下降分析的错误恢复
4.7.3 LL分析的错误恢复
4.7.4 LR分析的错误恢复
练习
第5章 语义分析
5.1 语义分析基础
5.1.1 语义分析内容
5.1.2 标识符信息的内部表示
5.1.3 类型信息的内部表示
5.1.4 运行时值的表示
5.2 符号表
5.2.1 符号表查找技术
5.2.2 符号表的局部化
5.2.3 二叉式局部符号表
5.2.4 散列式全局符号表
5.2.5 嵌套式全局符号表
5.2.6 符号表界面函数
5.3 类型分析
5.3.1 类型的等价性和相容性
5.3.2 类型分析的总控算法
5.3.3 类型名分析
5.3.4 枚举类型分析
5.3.5 数组类型分析
5.3.6 记录类型分析
5.3.7 联合类型分析
5.3.8 指针类型分析
5.3.9 递归类型分析
5.4 声明的语义分析
5.4.1 声明的语法结构
*5.4.2 标号声明部分的语义分析
5.4.3 常量声明部分的语义分析
5.4.4 类型声明部分的语义分析
5.4.5 变量声明部分的语义分析
5.4.6 过程?函数声明的语义分析
5.5 执行体的语义分析
5.5.1 执行体的语义分析
5.5.2 带标号语句和转向语句的语义分析
5.5.3 赋值语句的语义分析
5.5.4 条件语句的语义分析
5.5.5 while循环语句的语义分析
5.5.6 for循环语句的语义分析
5.5.7 过程调用语句的语义分析
5.5.8 表达式的语义分析
5.5.9 变量的语义分析
练习
第6章 运行时的存储环境
6.1 运行时的存储空间结构与分配
6.1.1 运行时的存储空间基本结构
6.1.2 静态区的存储分配
6.1.3 栈区的存储分配
*6.1.4 堆区的存储分配
*6.1.5 堆区空间管理
6.2 过程活动记录与栈区组织结构
6.2.1 过程活动记录
6.2.2 活动记录的填写
6.2.3 栈区组织结构——AR链
6.3 运行时的变量访问环境
6.3.1 可访问活动记录
6.3.2 局部Display表方法
6.3.3 静态链方法
6.3.4 全局Display表方法和寄存器方法
6.3.5 无嵌套时的AR及访问环境
*6.4 分程序和动态数组空间
6.4.1 无动态数组时的分程序空间
6.4.2 动态数组空间
练习
第7章 面向语法的语义描述
7.1 动作文法
7.1.1 动作文法定义
7.1.2 动作文法的递归实现
*7.1.3 动作文法的LL实现
7.1.4 动作文法的LR实现
7.2 动作文法应用
7.2.1 用动作文法描述表达式计算
*7.2.2 用动作文法描述表达式抽象树的构造
*7.2.3 用动作文法描述语句抽象树的构造
7.3 抽象动作文法及其应用
7.3.1 抽象变量
7.3.2 抽象动作文法
*7.3.3 栈式LL动作文法驱动器
*7.3.4 抽象动作文法到栈式LL动作文法的转换
*7.3.5 栈式LR动作文法驱动器
*7.3.6 抽象动作文法到栈式LR动作文法的转换
7.4 属性文法
7.4.1 属性文法定义
7.4.2 属性语法树和属性依赖图
7.4.3 计算顺序
7.4.4 属性值的计算方法
*7.4.5 拷贝型属性文法
7.5 属性文法在编译器设计中的应用
7.5.1 类型树的属性文法描述
7.5.2 表达式中间代码的属性文法描述
*7.5.3 变量中间代码的属性文法描述
*7.5.4 语句中间代码的属性文法描述
*7.5.5 正则表达式到自动机转换的属性文法描述
7.6 S-属性文法及其属性计算
7.6.1 S-属性文法
*7.6.2 S-属性文法的递归实现
*7.6.3 S-属性文法的LR实现
7.7 L-属性文法及其属性计算
7.7.1 L-属性文法
*7.7.2 L-属性文法的递归实现
*7.7.3 L-属性文法的LR(1)实现
*7.8 语义分析器的自动生成系统
7.8.1 YACC
7.8.2 LALRGen
7.8.3 Accent 系统
练习
第8章 中间代码生成
8.1 中间代码
8.1.1 中间代码的种类
8.1.2 后缀式中间代码
8.1.3 三地址中间代码
8.1.4 抽象语法树和无环有向图
8.1.5 多元式中间代码
8.1.6 中间代码分量ARG结构
8.2 表达式的中间代码生成
8.2.1 表达式的语义信息
8.2.2 表达式的中间代码
8.2.3 变量的中间代码
8.2.4 表达式的中间代码生成
8.2.5 变量的中间代码生成
8.2.6 布尔表达式的短路中间代码
8.3 原子语句的中间代码生成
8.3.1 输入/输出语句的中间代码生成
8.3.2 goto 语句和标号定位语句的中间代码生成
8.3.3 return 语句的中间代码生成
8.3.4 赋值语句的中间代码生成
8.3.5 函数(过程)调用的中间代码生成
8.4 结构语句的中间代码生成
8.4.1 条件语句的中间代码生成
8.4.2 while语句的中间代码生成
8.4.3 repeat语句的中间代码生成
8.4.4 for语句的中间代码生成
8.4.5 case语句的中间代码生成
8.4.6 函数声明的中间代码生成
练习
第9章 中间代码优化
9.1 引言
9.1.1 优化的目标和要求
9.1.2 优化的必要性
9.1.3 优化的内容
9.1.4 局部优化和全局优化
9.1.5 基本块和程序流图
9.2 常表达式优化
9.2.1 常表达式的局部优化
9.2.2 基于常量定值分析的常表达式全局优化
9.2.3 常量定值分析
9.3 公共表达式优化
9.3.1 基于相似性的公共表达式局部优化
9.3.2 基于值编码的公共表达式局部优化
9.3.3 基于活跃代码分析的公共表达式全局优化
9.3.4 活跃运算代码分析
9.4 程序流图循环
9.4.1 循环的基本概念
9.4.2 支撑结点
9.4.3 自然循环
9.4.4 可归约程序流图
9.4.5 基于文本的循环及其处理
9.5 循环不变代码外提
9.5.1 代码外提的基本概念
9.5.2 循环不变代码的判定
9.5.3 循环不变代码外提的条件
9.5.4 基于文本循环和定值表的不变代码外提
*9.5.5 一种简单的外提优化方案
*9.5.6 别名分析
*9.5.7 过程与函数的副作用分析
*9.6 循环内归纳表达式的优化
9.6.1 归纳变量
9.6.2 归纳变量计算的优化算法原理
练习
第10章 目标代码生成
10.1 目标代码
10.1.1 虚拟机代码
10.1.2 目标机代码
*10.1.3 窥孔优化
10.2 临时变量
10.2.1 临时变量的特点
10.2.2 临时变量的存储空间
10.2.3 临时变量的存储分配
10.2.4 变量状态描述
10.3 寄存器
10.3.1 寄存器分类及其使用准则
10.3.2 寄存器分配单位
10.3.3 寄存器状态描述
10.3.4 寄存器分配算法
10.4 基于三地址中间代码的目标代码生成
10.4.1 目标地址生成
10.4.2 间接目标地址的转换
10.4.3 表达式中间代码的目标代码生成
10.4.4 赋值中间代码的目标代码生成
10.4.5 其他寄存器分配法
10.4.6 标号和goto语句中间代码的目标代码生成
10.4.7 return中间代码的目标代码生成
10.4.8 变量中间代码的目标代码生成
10.4.9 函数调用中间代码的目标代码生成
10.5 基于AST的代码生成
10.5.1 三地址中间代码到AST的转换
10.5.2 标记需用寄存器个数
10.5.3 从带寄存器个数标记的AST生成代码
*10.6 基于DAG的代码生成
10.6.1 从AST到DAG的转换
10.6.2 DAG排序和虚寄存器
10.6.3 从带序号和虚寄存器标记的DAG生成代码
*10.7 代码生成器的自动生成
10.7.1 代码生成器的自动化
10.7.2 基于指令模板匹配的代码生成技术
10.7.3 基于语法分析的代码生成技术
练习
第11章 对象式语言的实现
11.1 引言
*11.2 SOOL语法
11.2.1 程序
11.2.2 分程序
11.2.3 类声明
11.2.4 类型
11.2.5 变量声明
11.2.6 函数声明和方法声明
11.2.7 语句
11.2.8 变量
11.2.9 表达式
11.2.10 程序示例
*11.3 SOOL语义
11.3.1 声明的作用域
11.3.2 Class声明的语义
11.3.3 语句的语义
*11.4 SOOL语义分析
11.4.1 标识符的符号表项
11.4.2 符号表结构
11.4.3 符号表的局部化
*11.5 SOOL目标代码
11.5.1 对象空间
11.5.2 当前对象——self
11.5.3 活动记录
11.5.4 成员变量的目标地址
11.5.5 表达式的目标代码
11.5.6 Offset原理
11.5.7 类的多态性
11.5.8 目标代码区
11.5.9 方法的动态绑定
11.5.10 快速动态绑定目标代码
主要参考文献
