第1章编译器概述 1
目 录 1
1.1词法分析 2
1.2语法分析 2
1.3语义分析 4
1.4中间代码生成 5
1.5代码优化 6
1.6代码生成 6
1.8错误诊断和报告 7
1.7符号表管理 7
1.9阶段的分组 9
习题1 9
第2章词法分析 10
2.1词法记号及属性 10
2.1.1词法记号、模式、词法单元 11
2.1.2词法记号的属性 12
2.2.1 串和语言 13
2.1.3词法错误 13
2.2词法记号的描述与识别 13
2.2.2正规式 15
2.2.3正规定义 16
2.2.4状态转换图 17
2.3有限自动机 20
2.3.1不确定的有限自动机 21
2.3.2确定的有限自动机 22
2.3.3 NFA到DFA的变换 23
2.3.4 DFA的化简 27
2.4从正规式到有限自动机 29
2.5词法分析器的生成器 32
习题2 36
第3章语法分析 39
3.1上下文无关文法 39
3.1.1上下文无关文法的定义 39
3.1.2推导 41
3.1.3分析树 43
3.1.4二义性 43
3.2语言和文法 44
3.2.1正规式和上下文无关 45
文法的比较 45
3.2.2分离词法分析器的理由 45
3.2.3验证文法产生的语言 46
3.2.4适当的表达式文法 46
3.2.5消除二义性 47
3.2.6消除左递归 49
3.2.7提左因子 50
3.2.8非上下文无关的语言结构 51
3.2.9形式语言鸟瞰 52
3.3自上而下分析 53
3.3.1 自上而下分析的一般方法 54
3.3.2 LL（1）文法 55
3.3.3递归下降的预测分析 56
3.3.4非递归的预测分析 58
3.3.5构造预测分析表 60
3.3.6预测分析的错误恢复 62
3.4自下而上分析 65
3.4.1 归约 65
3.4.2句柄 66
3.4.3用栈实现移进—归约分析 67
3.4.4移进—归约分析的冲突 69
3.5 LR分析器 70
3.5.1 LR分析算法 71
3.5.2 LR文法和LR分析 74
方法的特点 74
3.5.3构造SLR分析表 75
3.5.4构造规范的LR分析表 83
3.5.5构造LALR分析表 87
3.5.6非LR的上下文无关结构 90
3.6.1使用文法以外的信息来解决 92
分析动作的冲突 92
3.6二义文法的应用 92
3.6.2特殊情况产生式引起的 94
二义性 94
3.6.3 LR分析的错误恢复 95
3.7分析器的生成器 97
3.7.1分析器的生成器Yacc 97
3.7.2用Yacc处理二义文法 100
3.7.3 Yacc的错误恢复 103
习题3 105
第4章语法制导的翻译 111
4.1语法制导的定义 111
4.1.1语法制导定义的形式 111
4.1.2综合属性 113
4.1.3继承属性 113
4.1.4属性依赖图 114
4.1.5属性计算次序 115
4.2 S属性定义的自下而上计算 116
4.2.2构造语法树的语法制导定义 117
4.2.1语法树 117
4.2.3 S属性的自下而上计算 119
4.3L属性定义的自上而下计算 121
4.3.1 L属性定义 122
4.3.2翻译方案 122
4.3.3预测翻译器的设计 126
4.3.4用综合属性代替继承属性 128
4.4L属性的自下而上计算 129
4.4.1删除翻译方案中嵌入的动作 129
4.4.2分析栈上的继承属性 130
4.4.3模拟继承属性的计算 132
4.5递归计算 135
4.5.1 自左向右遍历 136
4.5.2其他遍历方法 137
4.5.3多次遍历 138
习题4 140
第5章类型检查 143
5.1.1引言 144
5.1类型在程序设计语言中的作用 144
5.1.2执行错误和安全语言 145
5.1.3类型化语言的优点 147
5.2描述类型系统的语言 148
5.2.1定型断言 149
5.2.2定型规则 150
5.2.3类型检查和类型推断 151
5.3简单类型检查器的说明 151
5.3.1一个简单的语言 152
5.3.2类型系统 152
5.3.3类型检查 154
5.3.4类型转换 156
*5.4多态函数 157
5.4.1为什么要使用多态函数 157
5.4.2类型变量 158
5.4.3一个含多态函数的语言 160
5.4.4代换、实例和合一 161
5.4.5多态函数的类型检查 162
5.5类型表达式的等价 167
5.5.1类型表达式的结构等价 168
5.5.2类型表达式的名字等价 169
5.5.3记录类型 170
5.5.4类型表示中的环 171
5.6函数和算符的重载 172
5.6.1子表达式的可能类型集合 172
5.6.2缩小可能类型的集合 174
习题5 175
第6章运行时存储空间的组织 181
和管理 181
6.1局部存储分配策略 181
6.1.1过程 182
6.1.2名字的作用域和绑定 182
6.1.3活动记录 183
6.1.4局部数据的安排 184
6.1.5程序块 185
6.2.1运行时内存的划分 187
6.2全局存储分配策略 187
6.2.2静态分配 188
6.2.3栈式分配 190
6.2.4堆式分配 196
6.3非局部名字的访问 197
6.3.1无过程嵌套的静态作用域 198
6.3.2有过程嵌套的静态作用域 198
6.3.3动态作用域 202
6.4.1值调用 203
6.4参数传递 203
6.4.2引用调用 204
6.4.3复写－恢复调用 204
6.4.4换名调用 205
习题6 206
第7章中间代码生成 215
7.1 中间语言 215
7.1.1后缀表示 215
7.1.2图形表示 216
7.1.3三地址代码 217
7.2声明语句 219
7.2.1过程中的声明 219
7.2.2作用域信息的保存 219
7.2.3记录的域名 222
7.3赋值语句 223
7.3.1符号表中的名字 223
7.3.2临时名字的重新使用 224
7.3.3数组元素的地址计算 225
7.3.4数组元素地址计算的 226
翻译方案 226
7.3.5类型转换 230
7.4布尔表达式和控制流语句 231
7.4.1布尔表达式的翻译 232
7.4.2控制流语句的翻译 233
7.4.3布尔表达式的控制流翻译 235
7.4.4开关语句的翻译 237
7.4.5过程调用的翻译 240
习题7 241
第8章代秒生成 245
8.1代码生成器设计中的问题 245
8.1.1 目标程序 245
8.1.2指令选择 246
8.1.3寄存器分配 247
8.1.4计算次序选择 247
8.2.1 目标机器的指令系统 248
8.2 目标机器 248
8.2.2指令的代价 249
8.3基本块和流图 251
8.3.1基本块 251
8.3.2基本块的变换 253
8.3.3流图 254
8.3.4下次引用信息 255
8.4一个简单的代码生成器 256
8.4.1 寄存器描述和地址描述 256
8.4.2代码生成算法 257
8.4.3寄存器选择函数 258
8.4.4为变址和指针语句产生代码 259
8.4.5条件语句 260
习题8 261
*第9章代码优化 269
9.1优化的主要种类 269
9.1.1代码改进变换的标准 269
9.1.2公共子表达式删除 272
9.1.3复写传播 273
9.1.4死代码删除 274
9.1.5代码外提 275
9.1.6强度削弱和归纳变量删除 275
9.1.7优化编译器的组织 276
9.2流图中的循环 278
9.2.1必经结点 278
9.2.2 自然循环 279
9.2.4可归约流图 280
9.2.3前置结点 280
9.3全局数据流分析介绍 281
9.3.1点和路径 282
9.3.2到达－定值 283
9.3.3可用表达式 286
9.3.4活跃变量分析 289
9.4代码改进变换 290
9.4.1公共子表达式删除 291
9.4.2复写传播 292
9.4.3寻找循环不变计算 294
9.4.4代码外提 294
9.4.5归纳变量删除 297
习题9 300
第10章编译系统和运行系统 306
10.1 C语言的编译系统 306
10.1.1预处理器 307
10.1.2汇编器 308
10.1.3连接器 310
10.1.4目标文件的格式 311
10.1.5符号解析 313
10.1.6静态库 314
10.1.7可执行目标文件及装入 316
10.1.8动态连接 317
10.1.9处理目标文件的一些工具 319
10.2 Java语言的运行系统 319
10.2.1 Java虚拟机语言简介 320
10.2.2 Java虚拟机 321
10.2.3即时编译器 322
*10.3无用单元收集 324
10.3.1标记和清扫 325
10.3.2引用计数 326
10.3.3拷贝收集 327
10.3.4分代收集 328
10.3.6编译器与收集器之间 330
的相互影响 330
10.3.5渐增式收集 330
习题10 334
*第11章 面向对象语言的编译 337
11.1面向对象语言的概念 337
11.1.1对象和对象类 337
11.1.2继承 338
11.1.3信息封装 341
11.2方法的编译 341
11.3继承的编译方案 344
11.3.1单一继承的编译方案 345
11.3.2重复继承的编译方案 347
习题11 352
*第12章 函数式语言的编译 355
12.1 函数式程序设计语言简介 355
12.1.1语言构造 355
12.1.2参数传递机制 357
出现 358
12.1.3变量的自由出现和约束 358
12.2函数式语言的编译简介 360
12.2.1几个受启发的例子 360
12.2.2编译函数 362
12.2.3环境与约束 363
12.3抽象机的系统结构 364
12.3.1抽象机的栈 365
12.3.2抽象机的堆 366
12.3.3名字的寻址 366
12.3.4约束的建立 368
12.4指令集和编译 369
12.4.1表达式 369
12.4.2变量的引用性出现 371
12.4.3函数定义 372
12.4.4函数应用 373
12.4.5构造和计算闭包 376
12.4.6 letrec表达式和局部变量 378
习题12 380
参考文献 382