第1章 概论 1
1.1 为什么学习编译 1
1.2 什么叫编译程序 2
1.3 编译过程概述 3
1.3.1 词法分析 3
1.3.2 语法分析 4
1.3.3 语义分析和中间代码生成 4
1.3.4 代码优化 5
1.3.5 目标代码生成 5
1.4 编译程序的构成 6
1.4.1 基本功能模块 7
1.4.2 符号表的组织与管理 7
1.5.1 遍的概念 8
1.5 其他与编译有关的概念和技术 8
1.4.3 错误诊断和报告 8
1.5.2 编译的前端和后端 9
1.5.3 编译程序的分类 9
1.5.4 编译技术和软件工具 10
1.6 如何开发编译程序 11
1.6.1 编译程序的自展技术 11
1.6.2 编译程序的移植技术 11
1.6.3 编译程序的自动生成技术 12
1.7 编译系统以及其他相关程序 12
练习1 14
第2章 词法分析 15
2.1 词法分析器的设计 15
2.1.1 词法分析器的功能与输出 15
2.1.4 词法错误的处理 17
2.1.3 词法分析器的两种实现模式 17
2.1.2 词法扫描器与符号表 17
2.2 词法分析器的一种手工实现 18
2.2.1 输入的预处理 18
2.2.2 超前搜索和最长匹配 19
2.2.3 状态转换图 19
2.2.4 基于状态转换图的词法分析器的实现 22
2.3 规表达式 25
2.3.1 符号、符号串与符号集合 26
2.3.2 正规式与正规集 27
2.3.3 扩展的正规式 28
2.4 有限自动机 29
2.4.1 确定的有限自动机 30
2.4.2 不确定的有限自动机NFA 32
2.4.3 从NFA到DFA的等价变换 33
2.4.4 DFA的最小化 36
2.4.5 从正规式到有限自动机 38
2.4.6 有限自动机在计算机中的表示 41
2.5 词法分析的自动生成器Lex 42
2.5.1 Lex概述 42
2.5.2 Lex的语言与实现 43
练习2 45
第3章 程序语言的语法描述 49
3.1 文法和语言 49
3.1.1 文法的形式定义 50
3.1.2 推导与归约 51
3.1.3 分析树与语法树 52
3.1.4 文法产生的语言 54
3.1.5 语言的验证 55
3.1.6 语言的文法表达 56
3.1.7 文法的二义性 58
3.1.8 BNF与EBNF 61
3.2文法的分类 63
3.2.1 0型文法 63
3.2.2 1型文法 63
3.2.3 2型文法——上下文无关文法 64
3.2.4 3型文法 65
3.3 文法的等价变换 67
3.3.1 文法等价的概念 67
3.3.2 增广文法 67
3.3.3 提取左因子 68
3.3.4 消除左递归 68
3.4 语法分析概述 70
3.4.1 自顶向下的语法分析 70
3.3.5 对文法的使用限制 70
3.4.2 自底向上的语法分析 71
3.4.3 语法分析的基本问题 72
练习3 73
第4章 自顶向下的语法分析 77
4.1 自顶向下语法分析的一般方法 77
4.2 LL(1)文法 78
4.2.1 首符集FIRST 79
4.2.2 后继符集FOLLOW 80
4.2.3 选择集SELECT 81
4.2.4 LL(1)文法 82
4.3 递归下降分析技术 84
4.3.1 递归下降分析器的设计 84
4.3.2 从EBNF构造递归下降分析器 88
4.4 预测分析技术 89
4.4.1 预测分析程序的工作过程 89
4.3.3 递归下降分析的特点 89
4.4.2 预测分析表的构造 91
4.5 LL(1)分析中的错误处理 96
练习4 98
第5章 自底向上的语法分析 100
5.1 自底向上语法分析概述 100
5.1.1 自底向上语法分析器的体系结构 100
5.1.2 规范归约和算符优先归约 101
5.1.3 短语、句柄和最左素短语 103
5.2 算符优先分析方法 104
5.2.1 算符优先文法 105
5.2.2 算符优先关系的构造 107
5.2.3 算符优先分析算法 108
5.2.4 算符优先函数及其构造 110
5.3.1 LR分析概述 112
5.3 LR分析方法 112
5.3.2 LR(0)分析表的构造 116
5.3.3 SLR分析表的构造 122
5.3.4 规范LR分析表的构造 127
5.3.5 LALR分析表的构造 132
5.3.6 LR分析方法小结 134
5.4 LALR分析器的生成工具YACC 139
5.4.1 YACC概述 139
5.4.2 YACC源程序 140
5.4.3 YACC解决二义性和冲突的方法 142
5.4.4 YACC对语法分析中的错误处理 143
练习5 144
第6章 符号表的组织和管理 148
6.1 符号表的作用 148
6.2 符号表的主要属性及其作用 149
6.3 符号表的组织结构 152
6.3.1 符号表的整体组织结构 153
6.3.2 关键码域的组织 154
6.3.3 不等长域的组织 155
6.3.4 符号表的操作与符号表项的组织 156
6.4 名字的作用范围 159
6.4.1 名字的声明 159
6.4.2 块结构与符号表的分层次管理 160
6.4.3 静态作用域和动态作用域 162
练习6 163
第7章 运行时环境 165
7.1 程序运行的基本概念 165
7.1.1 过程及其活动 165
7.1.3 调用序列和返回序列 167
7.1.2 活动记录 167
7.1.4 活动树 168
7.1.5 环境和名字的绑定 168
7.2 参数传递机制 169
7.2.1 按值调用 169
7.2.2 引用调用 170
7.2.3 值—结果调用 170
7.2.4 换名调用 171
7.3 运行时存储空间的组织和管理 172
7.3.1 局部数据的存放 172
7.3.2 运行时存储空间的划分 173
7.3.3 存储分配策略 174
7.4 静态运行时环境 174
7.5 栈式运行时环境 176
7.5.1 无过程嵌套的栈式运行时环境 176
7.5.2 有过程嵌套的栈式运行时环境 180
7.6 堆式运行时环境 184
7.6.1 堆式动态存储分配的实现 185
7.6.2 堆的自动管理 186
7.7 面向对象语言的运行时环境 189
7.7.1 面向对象语言的动态存储管理 189
7.7.2 Java运行时环境 191
练习7 192
第8章 属性文法和语义分析 197
8.1 语义分析概况 197
8.2 属性与属性文法 199
8.2.1 属性的引入 199
8.2.2 属性文法的定义 200
8.2.3 属性文法的扩展与简化 204
8.3.1 属性依赖图和计算顺序 206
8.3 属性的计算 206
8.3.2 综合属性和继承属性及其计算 210
8.3.3 语法分析的同时计算属性 214
8.4 数据类型与类型检查 222
8.4.1 类型表达式与类型构造器 223
8.4.2 类型等价 225
8.4.3 类型检查 228
8.4.4 类型转换 229
8.4.5 类型检查的其他问题 231
练习8 232
第9章 语法制导的中间代码翻译 235
9.1 中间语言 235
9.1.1 后缀式 237
9.1.2 图形表示 239
9.1.3 字节代码 240
9.1.4 三地址代码及其四元式实现 241
9.2 声明语句的翻译 244
9.2.1 过程中的声明 244
9.2.2 保留声明的作用域信息 245
9.2.3 记录中的域名 249
9.3 赋值语句的翻译 249
9.3.1 简单算术表达式及赋值语句 250
9.3.2 数组元素的引用 252
9.3.3 记录和指针的引用 257
9.3.4 类型转换 258
9.4 基本控制结构的翻译 259
9.4.1 布尔表达式的翻译 259
9.4.2 控制流语句的多趟翻译模式 262
9.4.3 回填技术基础 264
9.4.4 控制流语句的单趟翻译模式 267
9.5 转向语句的翻译 270
9.5.1 标号语句与goto语句的翻译 270
9.5.2 出口语句的翻译 271
9.5.3 开关语句的翻译 272
9.5.4 过程调用的翻译 274
练习9 275
第10章 目标代码生成 277
10.1 代码生成器设计的基本问题 277
10.1.1 目标程序 278
10.1.2 指令选择 278
10.1.3 寄存器分配 278
10.1.4 计算顺序的选择 279
10.2 虚拟计算机模型 279
10.3 语法制导的目标代码生成 280
10.4.1 基本块及其构造 283
10.4 基本块和待用信息 283
10.4.2 流图 285
10.4.3 待用信息 286
10.5 一个简单代码生成器 288
10.5.1 寄存器和地址的描述 289
10.5.2 寄存器的分配原则与选择算法 289
10.5.3 代码生成算法 290
10.5.4 其他三地址语句的目标代码 292
练习10 293
第11章 代码优化 295
11.1 代码优化的概念 295
11.2 代码优化的基本技术 297
11.2.1 删除公共子表达式 297
11.2.4 代码外提 299
11.2.3 删除无用代码 299
11.2.2 复写传播 299
11.2.5 强度消弱和删除归纳变量 300
11.3 局部优化 301
11.3.1 基本块的变换 301
11.3.2 基本块的DAG实现 302
11.3.3 基于DAG的局部优化 305
11.4 机器代码优化－窥孔技术 307
11.4.1 冗余存取的删除 308
11.4.2 不可达代码的删除 308
11.4.3 控制流优化 308
11.4.4 代数化简与强度消弱 309
11.4.5 特殊指令的使用 310
11.5 代码优化的高级技术简介 310
练习11 311
参考文献 313