第1章 引论 1
1.1 编译程序是一种特定的翻译程序 1
1.2 编译程序的结构 2
1.2.1 词法分析阶段 2
1.2.2 语法分析阶段 2
1.2.3 语义分析、中间代码生成阶段 3
1.2.4 优化阶段 3
1.2.5 目标代码生成阶段 3
1.2.6 符号表管理 3
1.2.7 出错管理程序 3
1.2.9 遍 4
1.2.8 编译阶段的前端和后端 4
1.3 编译程序的生成 5
1.3.1 自展 5
1.3.2 移植 6
1.3.3 对编译程序的评价 7
1.4 编译程序的学习 7
第2章 文法和语言 8
2.1 基本概念 8
2.1.1 语言 8
2.1.2 文法 10
2.1.3 归约与句柄 12
2.2.1 分析树 14
2.2.2 子树 14
2.2 分析树与二义性 14
2.2.3 二义性 15
2.3 形式语言分类 15
习题2 17
第3章 词法分析 19
3.1 构造一个简单的词法分析器 19
3.1.1 词法分析器的功能 19
3.1.2 扫描缓冲区 22
3.1.3 超前搜索 23
3.1.4 状态转换图 23
3.1.5 状态转换图的实现 25
3.2.1 正规式与正规集的定义 27
3.2 正规表达式与正规集 27
3.2.2 正规式的性质 29
3.2.3 正规式与正规文法 30
3.3 有限自动机 30
3.3.1 有限自动机的定义 30
3.3.2 FA的表示 31
3.3.3 FAM识别的语言 32
3.3.4 NFA M的确定化 33
3.3.5 DFA M的简化 34
3.4 正规式与有限自动机 35
3.4.1 正规式与有限自动机的等价性 35
3.4.2 由正规式构造等价的NFA M 37
3.5 词法分析器的自动生成 38
习题3 39
第4章 语法分析 41
4.1 语法分析概述 41
4.2 递归下降分析方法 41
4.2.1 试探分析法 41
4.2.2 提取左因子 42
4.2.3 消除左递归 43
4.2.4 预测分析器 45
4.3 非递归的预测分析方法 46
4.3.1 表驱动的预测分析器 46
4.3.2 FIRST集和FOLLW集 47
4.3.4 预测分析表的构造 50
4.3.3 LL(1)文法 50
4.3.5 错误处理 51
4.4 算符优先分析法 52
4.4.1 算符优先关系表 52
4.4.2 算符优先分析方法 53
4.4.3 优先关系表的构造 55
4.4.4 优先函数 56
4.4.5 错误处理 57
4.5 LR分析器 58
4.5.1 LR分析法 58
4.5.2 识别活前缀的DFA 60
4.5.3 SLR分析表的构造 65
4.5.4 LR(1)分析表的构造 66
4.5.5 LALR分析表的构造 69
4.6 二义文法的应用 74
4.7 分析表的自动生成 76
习题4 77
第5章 语法制导翻译和中间代码生成 81
5.1 翻译概述 81
5.1.1 静态语义检查 81
5.1.2 语义制导翻译的例子 81
5.1.3 翻译要解决的问题 82
5.2 中间语言 82
5.2.1 后缀式表示 82
5.2.2 图表示 83
5.2.4 三地址语句的种类 84
5.2.3 三地址代码 84
5.2.5 三地址代码的具体实现 85
5.3 说明语句 86
5.3.1 一类说明语句的翻译方案 86
5.3.2 嵌套过程中的说明语句 87
5.3.3 记录中的域名 90
5.4 赋值语句 90
5.4.1 只含简单变量的赋值语句的翻译 90
5.4.2 类型转换 91
5.4.3 含数组元素的赋值语句的翻译 92
5.4.4 访问记录结构中的域 97
5.5.1 布尔表达式的两种基本作用 98
5.5.2 布尔表达式的两种翻译方法 98
5.5 控制流语句 98
5.5.3 数值表示法翻译方案 99
5.5.4 控制流语句中布尔表达式的翻译 100
5.5.5 控制流语句的翻译 104
5.5.6 转向语句和语句标号 108
5.6 循环语句、过程调用语句及CASE语句 108
5.6.1 循环语句的翻译 108
5.6.2 过程调用、函数调用语句的翻译 109
5.6.3 CASE语句或switch语句的翻译 110
5.7 属性文法 111
5.7.1 语法制导定义 112
5.7.2 属性的分类 112
5.7.3 依赖图 113
5.7.4 语义规则的计算次序 114
5.7.5 属性文法的两个子类 114
习题5 115
第6章 运行时存储空间管理 118
6.1 变量及存储分配 118
6.1.1 程序的存储空间 118
6.1.2 活动记录 119
6.1.3 变量的存储分配 119
6.1.4 存储分配模式 120
6.2 静态分配 122
6.2.1 FORTRAN程序运行时的结构 122
6.2.2 运行环境的转换 122
6.3 栈式分配 124
6.3.1 只含半静态变量的栈式分配 125
6.3.2 半动态变量的栈式分配 127
6.3.3 动态变量的存储分配 127
6.3.4 非局部环境 128
6.3.5 对非局部环境的引用 129
6.4 堆分配 130
6.5 参数传递 131
6.5.1 数据参数传递 131
6.5.2 过程参数的传递 132
6.6 符号表 133
6.6.1 符号表的组织 133
6.6.2 常用的符号表结构 134
习题6 136
第7章 代码优化 139
7.1 优化概述 139
7.1.1 优化定义 139
7.1.2 不同阶段的优化 139
7.1.3 程序流图的构造 140
7.2 局部优化 142
7.2.1 基本块内的优化 142
7.2.2 基本块的dag表示 143
7.2.3 dag的构造 143
7.2.4 dag实现的优化 146
7.2.5 对dag构造算法的修正 146
7.3.1 循环的定义 148
7.3 控制流分析及循环的查找 148
7.3.2 必经结点集 149
7.3.3 自然循环 151
7.3.4 可归约流图 152
7.3.5 深度优先搜索 153
7.4 数据流分析 155
7.4.1 到达一定值数据流方程和ud链 156
7.4.2 活跃变量数据流方程和du链 157
7.4.3 可用表达式数据流方程与复写传播 158
7.4.4 非常忙表达式与代码提升 160
7.4.5 数据流方程的求解 160
7.5.1 循环优化的例子 161
7.5 循环优化 161
7.5.2 代码外提 162
7.5.3 归纳变量 165
7.5.4 强度削弱 165
7.5.5 删除归纳变量 165
习题7 167
第8章 代码生成 171
8.1 目标代码 171
8.1.1 代码生成器的输入与输出 171
8.1.2 目标机 171
8.2 一个简单代码生成器 172
8.2.1 待用信息 172
8.2.3 如何生成目标代码 173
8.2.2 寄存器描述和地址描述 173
8.2.4 函数getreg(P:x:=y op z) 174
8.2.5 代码生成算法 174
8.2.6 其他语句的代码生成 175
8.3 寄存器分配 176
8.3.1 执行代价的节省 176
8.3.2 固定分配寄存器的代码生成 178
8.3.3 多重循环的寄存器分配 178
8.3.4 用图的点着色法做寄存器分配 178
8.4 窥孔优化 179
8.5 由dag生成代码 181
8.5.1 重新安排计算次序 181
8.5.2 dag为树时最优代码生成 183
习题8 186
第9章 并行编译概述 188
9.1 并行计算机及其编译系统 188
9.1.1 向量计算机 188
9.1.2 共享存储器多处理机 189
9.1.3 分布存储器大规模并行计算机 190
9.1.4 并行编译系统的结构 191
9.2 并行编译技术 193
9.2.1 依赖关系 193
9.2.2 依赖测试 194
9.2.3 循环向量化与并行化 194
参考文献 196