第1章 引论 1
1.1编译器概述 1
词法分析 1
语法分析 3
语义分析 3
中间代码生成 4
代码优化 4
代码生成 5
符号表管理 5
阶段的分组 6
解释器 7
1.2编译器技术的应用 7
高级语言的实现 7
针对计算机体系结构的优化 8
新计算机体系结构的设计 9
程序翻译 10
提高软件开发效率的工具 11
习题1 12
第2章 词法分析 13
2.1词法记号及属性 13
词法记号、模式、词法单元 14
词法记号的属性 15
词法错误 16
2.2词法记号的描述与识别 16
串和语言 16
正规式 17
正规定义 19
状态转换图 20
2.3有限自动机 23
不确定的有限自动机 23
确定的有限自动机 24
NFA到DFA的变换 25
DFA的化简 28
2.4从正规式到有限自动机 30
2.5词法分析器的生成器 32
习题2 35
第3章 语法分析 38
3.1上下文无关文法 38
上下文无关文法的定义 39
推导 40
分析树 41
二义性 42
3.2语言和文法 43
正规式和上下文无关文法的比较 43
分离词法分析器的理由 44
验证文法产生的语言 44
适当的表达式文法 45
消除二义性 46
消除左递归 47
提左因子 48
非上下文无关的语言构造 49
形式语言鸟瞰 51
3.3自上而下分析 52
自上而下分析的一般方法 52
LL(1)文法 53
递归下降的预测分析 54
非递归的预测分析 56
构造预测分析表 58
预测分析的错误恢复 59
3.4自下而上分析 62
归约 62
句柄 63
用栈实现移进-归约分析 64
移进-归约分析的冲突 65
3.5 LR分析器 67
LR分析算法 67
LR文法和LR分析方法的特点 71
构造SLR分析表 72
构造规范的LR分析表 79
构造LALR分析表 83
非二义且非LR的上下文无关文法 86
3.6二义文法的应用 87
使用算符的优先级和结合性来解决冲突 88
使用其他约定来解决冲突 90
LR分析的错误恢复 91
3.7语法分析器的生成器 93
分析器的生成器Yacc 93
用Yacc处理二义文法 96
Yacc的错误恢复 99
习题3 100
第4章 语法制导的翻译 106
4.1语法制导的定义 106
语法制导定义的形式 107
综合属性 108
继承属性 108
属性依赖图 109
属性计算次序 110
4.2 S属性定义的自下而上计算 111
语法树 111
构造语法树的语法制导定义 112
S属性的自下而上计算 113
4.3 L属性定义的自上而下计算 115
L属性定义 116
翻译方案 116
预测翻译器的设计 120
用综合属性代替继承属性 121
4.4 L属性的自下而上计算 122
删除翻译方案中嵌入的动作 122
分析栈上的继承属性 123
模拟继承属性的计算 125
习题4 127
第5章 类型检查 130
5.1类型在编程语言中的作用 130
执行错误和安全语言 131
类型化语言和类型系统 131
类型化语言的优点 133
5.2描述类型系统的语言 134
定型断言 135
定型规则 136
类型检查和类型推断 137
5.3一个简单类型检查器的规范 137
一个简单的语言 137
类型系统 138
类型检查 140
类型转换 141
5.4多态函数 142
为什么要使用多态函数 143
类型变量 144
一个含多态函数的语言 145
代换、实例和合一 146
多态函数的类型检查 147
5.5类型表达式的等价 151
类型表达式的结构等价 151
类型表达式的名字等价 152
记录类型 153
类型表示中的环 154
5.6函数和算符的重载 154
子表达式的可能类型集合 155
缩小可能类型的集合 156
习题5 157
第6章 运行时存储空间的组织和管理 163
6.1局部存储分配 164
过程 164
名字的作用域和绑定 165
活动记录 165
局部数据的安排 166
程序块 167
6.2全局栈式存储分配 168
运行时内存的划分 168
活动树和运行栈 169
调用序列 171
栈上可变长度数据 173
悬空引用 174
6.3非局部名字的访问 175
无过程嵌套的静态作用域 175
有过程嵌套的静态作用域 176
动态作用域 179
6.4参数传递 180
值调用 180
引用调用 181
换名调用 181
6.5堆管理 182
内存管理器 183
计算机内存分层 184
程序局部性 185
手工回收请求 186
习题6 186
第7章 中间代码生成 199
7.1中间语言 200
后缀表示 200
图形表示 200
三地址代码 201
静态单赋值形式 203
7.2声明语句 204
过程中的声明 204
作用域信息的保存 205
记录的域名 207
7.3赋值语句 207
符号表中的名字 208
数组元素的地址计算 208
数组元素地址计算的翻译方案 209
类型转换 212
7.4布尔表达式和控制流语句 213
布尔表达式 214
控制流语句的翻译 214
布尔表达式的控制流翻译 216
开关语句的翻译 218
过程调用的翻译 220
习题7 221
第8章 代码生成 227
8.1代码生成器设计中的问题 227
目标程序 227
指令选择 228
寄存器分配 229
计算次序选择 229
8.2目标语言 230
目标机器的指令集 230
指令的代价 231
8.3基本块和流图 233
基本块 233
基本块的优化 234
流图 235
下次引用信息 236
8.4一个简单的代码生成器 237
寄存器描述和地址描述 238
代码生成算法 238
寄存器选择函数 239
为变址和指针语句产生代码 241
条件语句 241
习题8 242
第9章 独立于机器的优化 250
9.1优化的主要种类 250
优化的主要源头 250
一个实例 251
公共子表达式删除 252
复写传播 255
死代码删除 256
代码外提 256
强度削弱和归纳变量删除 257
9.2数据流分析介绍 258
数据流抽象 259
数据流分析模式 260
到达-定值 261
活跃变量 265
可用表达式 267
小结 269
9.3数据流分析的基础 270
半格 270
迁移函数 273
一般框架的迭代算法 274
数据流解的含义 276
9.4常量传播 278
常量传播框架的数据流值 278
常量传播框架的迁移函数 279
常量传播框架的单调性 280
常量传播框架的非分配性 280
结果的解释 281
9.5部分冗余删除 282
冗余的根源 282
能否删除所有的冗余 284
惰性代码移动问题 285
预期表达式 286
惰性代码移动算法 286
9.6流图中的循环 291
支配结点 291
回边和可归约性 293
流图的深度 294
自然循环 294
迭代流图算法的收敛速度 296
习题9 297
第10章 依赖于机器的优化 306
10.1处理器体系结构 307
指令流水线和分支延迟 307
流水化的执行 308
多指令发射 308
10.2代码调度的约束 309
数据相关 309
发现内存访问中的相关性 310
寄存器使用和并行执行之间的折中 311
寄存器分配和代码调度的次序安排 312
控制相关 313
投机执行的支持 313
一个基本的机器模型 314
10.3基本块调度 315
数据依赖图 315
基本块的表调度 316
区分优先级的拓扑次序 317
10.4全局代码调度 318
简单的代码移动 318
向上的代码移动 319
向下的代码移动 320
更新数据相关 321
全局调度的其他问题 321
静态调度器和动态调度器的交互 322
10.5软件流水 323
引言 323
循环的软件流水 324
寄存器分配和代码生成 326
do-across循环 327
软件流水的目标和约束 328
软件流水算法 329
无环数据依赖图的调度 330
10.6并行性和数据局部性优化概述 331
多处理器 331
应用中的并行性 333
循环级并行 334
数据局部性 335
矩阵乘法算法 336
矩阵乘法算法的优化 338
习题10 340
第11章 编译系统和运行系统 343
11.1 C语言的编译系统 343
预处理器 344
汇编器 345
连接器 346
目标文件的格式 347
符号解析 349
静态库 350
可执行目标文件及装入 352
动态连接 353
处理目标文件的一些工具 354
11.2 Java语言的运行系统 355
Java虚拟机语言简介 355
Java虚拟机 356
即时编译器 357
11.3无用单元收集 359
标记和清扫 359
引用计数 360
拷贝收集 361
分代收集 363
渐增式收集 364
编译器与收集器之间的相互影响 364
习题11 367
第12章 面向对象语言的编译 371
12.1面向对象语言的概念 371
对象和对象类 371
继承 372
信息封装 374
12.2方法的编译 374
12.3继承的编译方案 377
单一继承的编译方案 378
重复继承的编译方案 380
习题12 384
第13章 函数式语言的编译 387
13.1函数式编程语言简介 387
语言构造 387
参数传递机制 389
变量的自由出现和约束出现 390
13.2函数式语言的编译简介 392
几个受启发的例子 392
编译函数 394
环境与约束 394
13.3抽象机的体系结构 396
抽象机的栈 396
抽象机的堆 397
名字的寻址 398
约束的建立 399
13.4指令集和编译 400
表达式 400
变量的引用性出现 401
函数定义 402
函数应用 404
构造和计算闭包 407
letrec表达式和局部变量 409
习题13 410
参考文献 412