第一章 引论 1
1.1 编译程序是一种特定的翻译程序 1
1.2 编译程序的结构 2
一、词法分析阶段 3
二、语法分析阶段 3
三、语义分析、中间代码生成阶段 3
四、优化阶段 3
五、目标代码生成阶段 3
六、符号表管理 4
七、出错管理程序 4
八、编译阶段的前端和后端 4
1.3 编译程序的生成 5
九、遍 5
一、自展 6
二、移植 6
三、对编译程序的评价 7
1.4 编译程序的学习 7
第二章 文法和语言 9
2.1 基本概念 9
一、语言 9
二、文法 11
三、归约与句柄 13
2.2 分析树与二义性 15
一、分析树 15
二、子树 15
三、二义性 16
2.3 形式语言分类 17
习题 18
第三章 词法分析 20
3.1 构造一个简单的词法分析器 20
一、词法分析器的功能 20
二、扫描援冲区 23
三、超前搜索 25
四、状态转换图 25
五、状态转换图的实现 26
3.2 正规表达式与正规集 29
一、正规式与正规集的定义 29
二、正规式的性质 30
一、有限自动机的定义 31
三、正规式与正规文法 31
3.3 有限自动机 31
二、FA的表示 32
三、FAM识别的语言 33
四、NFAM的确定化 34
五、DFAM的简化 36
3.4 正规式与有限自动机 37
一、正规式与有限自动机的等价性 37
二、自正规式构造等价的NFAM 39
3.5 词法分析器的自动生成 40
习题 40
4.2 梯归下降分析方法 43
一、试探分析法 43
4.1 语法分析概述 43
第四章 语法分析 43
二、提取左因子 44
三、清除左递归 45
四、预测分析器 47
4.3 非递归的预测分析方法 48
一、表驱动的预测分析器 48
二、FIRST集和FOLLOW集 50
三、LL(1)文法 51
四、预测分析表的构造 52
五、错误处理 52
4.4 算符优先分析法 53
一、算符优先关系表 53
二、算符优先分析方法 54
三、优先关系表的构造 56
四、优先函数 57
五、错误处理 58
4.5 LR分析器 58
一、LR分析法 58
二、识别活前缀的DFA 61
三、SLR分析表的构造 65
四、LR(1)分析表的构造 66
五、LALR分析表的构造 69
4.6 二义文法的应用 75
4.7 分析表的自动生成 77
习题 78
一、语法制导定义形式 81
5.1 语法制导定义 81
第五章 语法制导翻译 81
二、属性分类 82
三、综合属性 83
四、继承属性 84
五、依赖图 84
六、计算次序 85
5.2 L--属性定义 86
一、深度为主属性求值 86
二、L--属性定义 86
三、翻译方案 87
5.3 属性的自下而上计算 88
一、S属性的自下而上计算 88
二、继承属性的自下而上计算 90
一、删除翻译方案的左递归 94
5.4 属性的自上而下计算 94
二、构造语法树的翻译方案 96
三、预测翻译器的设计 99
四、递归计算 99
习题 104
第六章 运行时的环境 106
6.1 若干问题的讨论 106
一、关于过程 106
二、活动树及控制栈 107
三、名字的作用域 109
四、名字的关联 110
五、要回答的问题 110
6.2 存贮管理 111
一、存贮空间的组织 111
二、活动记录 112
四、栈式存贮分配 113
三、静态存贮分配 113
五、堆式存贮分配 117
6.3 动态存贮分配对作用域的考虑 118
一、静态作用域规则与动态作用域规则 118
二、程序块(Block) 119
三、不含嵌套过程的词法作用域 120
四、含嵌套过程的词法作用域 120
五、动态作用域 124
6.4 参数传递 124
一、传值调用(call-by-valuc) 125
二、引用调用(call-by-reference) 125
四、传名调用(call-by-name) 126
三、复写恢复(copy-restore) 126
6.5 符号表 127
一、符号表的组织 127
二、常用的符号表结构 128
三、作用域在符号表组织中的反映 129
习题 130
第七章 中间代码生成 133
7.1 中间语言 133
一、后缀表示 133
二、图表示 133
三、三地址代码 135
四、三地址语句的种类 135
五、语法制导翻译生成三地址代码 136
六、三地址代码的具体实现 137
7.2 说明语句 138
一、一类说明语句的翻译方案 138
二、嵌套过程中的说明语句 139
三、记录中的域名 141
7.3 赋值语句 142
一、只含简单变量的情况 142
二、数组元素的地址计算公式 143
三、含数组元素的变量的访问 144
四、含数组元素的赋值语句的翻译方案 144
五、赋值语句中类型转换问题 146
六、访问记录结构中的域 147
二、布尔表达式的两种翻译方法 148
三、数值表示法 148
7.4 布尔表达式 148
一、布尔表达式的两种基本作用 148
四、控制流语句 150
五、控制流语句中布尔表达式的翻译 151
7.5 CASE语句 153
7.6 控制转移中的回填方法 154
一、使用回填翻译布尔表达式 155
二、使用回填翻译控制流语句 157
三、标号和转向语句 160
7.7 过程调用 161
习题 162
二、不同阶段的优化 165
一、优化定义 165
8.1 优化概述 165
第八章 代码优化 165
三、程序流图的构造 166
8.2 局部优化 168
一、基本块内的优化 168
二、基本块的dag表示 169
三、dag的构造 169
四、dag实现的优化 172
五、对dag构造算法的修正 173
8.3 控制流分析及循环的查找 174
一、循环的定义 175
二、必经结点集 176
三、自然循环 177
四、可归约流图 179
五、深度优先搜索 180
6.4 数据流分析 182
一、到达一定值数据流方程和ud链 182
二、活跃变量数据流方程和du链 183
三、可用表达式数据流方程与复写传播 184
四、非常忙表达式与代码提升 186
五、数据流方程的求解 186
8.5 循环优化 187
一、循环优化的例子 188
二、代码外提 188
三、归纳变量 192
四、强度削弱 193
五、删除归纳变量 193
习题 195
9.1 目标代码 199
一、代码生成器的输入与输出 199
二、目标机器 199
第九章 代码生成 199
9.2 一个简单代码生成器 200
一、待用信息 200
二、寄存器描述和地址描述 201
三、如何生成目标代码 201
四、函数getreg(P:x:=y op z) 202
五、代码生成算法 202
9.3 寄存器分配 203
一、执行代价的节省 203
二、固定分配寄存器的代码生成 205
四、用图的点着色法作寄存器分配 206
三、多重循环的寄存器分配 206
9.4 窥孔优化 207
一、删除多余存取指令 207
二、删除死代码 207
三、控制流优化 207
四、代数化简 208
五、强度削弱 208
六、利用机器特点 209
9.5 由dag生成代码 209
一、重新安排计算次序 209
二、dag为树时最优化码生成 211
习题 214
参考书目 216