第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.4.3错误诊断和报告 8
1.5其他与编译有关的概念和技术 8
1.5.1遍的概念 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.2词法扫描器与符号表 17
2.1.3词法分析器的两种实现模式 17
2.1.4词法错误的处理 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章 程序语言的语法描述 48
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.3.5对文法的使用限制 70
3.4语法分析概述 70
3.4.1自顶向下的语法分析 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 80
4.2.2后继符集FOLLOW 82
4.2.3选择集SELECT 84
4.2.4 LL（1）文法 85
4.2.5 LL（1）文法的分析 87
4.3递归下降分析技术 88
4.3.1递归下降分析器的设计 88
4.3.2从EBNF构造递归下降分析器 92
4.3.3递归下降分析的特点 93
4.4预测分析技术 93
4.4.1预测分析程序的工作过程 93
4.4.2预测分析表的构造 95
4.5 LL（1）分析中的错误处理 98
练习4 100
第5章 自底向上的语法分析 102
5.1自底向上语法分析概述 102
5.1.1自底向上语法分析器的体系结构 102
5.1.2规范归约和算符优先归约 103
5.1.3短语、句柄和最左素短语 105
5.2算符优先分析方法 106
5.2.1算符优先文法 107
5.2.2算符优先关系的构造 109
5.2.3算符优先分析算法 110
5.2.4算符优先函数及其构造 112
5.3 LR分析方法 114
5.3.1 LR分析概述 114
5.3.2 LR（0）分析表的构造 118
5.3.3 SLR分析表的构造 124
5.3.4规范LR分析表的构造 129
5.3.5 LALR分析表的构造 134
5.3.6 LR分析方法小结 136
5.4 LALR分析器的生成工具YACC 141
5.4.1 YACC概述 141
5.4.2 YACC源程序 142
5.4.3 YACC解决二义性和冲突的方法 144
5.4.4 YACC对语法分析中的错误处理 145
练习5 146
第6章 符号表的组织和管理 150
6.1符号表的作用 150
6.2符号表的主要属性及其作用 151
6.3符号表的组织结构 154
6.3.1符号表的整体组织结构 155
6.3.2关键码域的组织 156
6.3.3不等长域的组织 157
6.3.4符号表的操作与符号表项的组织 158
6.4名字的作用范围 161
6.4.1名字的声明 161
6.4.2块结构与符号表的分层次管理 162
6.4.3静态作用域和动态作用域 164
练习6 165
第7章 运行时环境 167
7.1程序运行的基本概念 167
7.1.1过程及其活动 167
7.1.2活动记录 169
7.1.3调用序列和返回序列 169
7.1.4活动树 170
7.1.5环境和名字的绑定 170
7.2参数传递机制 171
7.2.1按值调用 171
7.2.2引用调用 172
7.2.3值-结果调用 172
7.2.4换名调用 173
7.3运行时存储空间的组织和管理 174
7.3.1局部数据的存放 174
7.3.2运行时存储空间的划分 175
7.3.3存储分配策略 176
7.4静态运行时环境 176
7.5栈式运行时环境 178
7.5.1无过程嵌套的栈式运行时环境 178
7.5.2有过程嵌套的栈式运行时环境 182
7.6堆式运行时环境 186
7.6.1堆式动态存储分配的实现 187
7.6.2堆的自动管理 188
7.7面向对象语言的运行时环境 191
7.7.1面向对象语言的动态存储管理 191
7.7.2 Java运行时环境 193
练习7 194
第8章 属性文法和语义分析 199
8.1语义分析概况 199
8.2属性与属性文法 201
8.2.1属性的引入 201
8.2.2属性文法的定义 202
8.2.3属性文法的扩展与简化 206
8.3属性的计算 208
8.3.1属性依赖图和计算顺序 208
8.3.2综合属性和继承属性及其计算 212
8.3.3语法分析的同时计算属性 216
8.4数据类型与类型检查 224
8.4.1类型表达式与类型构造器 225
8.4.2类型等价 227
8.4.3类型检查 230
8.4.4类型转换 231
8.4.5类型检查的其他问题 233
练习8 234
第9章 语法制导的中间代码翻译 237
9.1中间语言 237
9.1.1后缀式 239
9.1.2图形表示 241
9.1.3字节代码 242
9.1.4三地址代码及其四元式实现 243
9.2声明语句的翻译 246
9.2.1过程中的声明 246
9.2.2保留声明的作用域信息 247
9.2.3记录中的域名 251
9.3赋值语句的翻译 251
9.3.1简单算术表达式及赋值语句 252
9.3.2数组元素的引用 254
9.3.3记录和指针的引用 259
9.3.4类型转换 260
9.4基本控制结构的翻译 261
9.4.1布尔表达式的翻译 261
9.4.2控制流语句的多趟翻译模式 264
9.4.3回填技术基础 266
9.4.4控制流语句的单趟翻译模式 269
9.5转向语句的翻译 272
9.5.1标号语句与goto语句的翻译 272
9.5.2出口语句的翻译 273
9.5.3开关语句的翻译 274
9.5.4过程调用的翻译 276
练习9 277
第10章 目标代码生成 279
10.1代码生成器设计的基本问题 279
10.1.1目标程序 280
10.1.2指令选择 280
10.1.3寄存器分配 280
10.1.4计算顺序的选择 281
10.2虚拟计算机模型 281
10.3语法制导的目标代码生成 282
10.4基本块和待用信息 285
10.4.1基本块及其构造 285
10.4.2流图 287
10.4.3待用信息 288
10.5一个简单代码生成器 290
10.5.1寄存器和地址的描述 291
10.5.2寄存器的分配原则与选择算法 291
10.5.3代码生成算法 292
10.5.4其他三地址语句的目标代码 294
练习10 295
第11章 代码优化 297
11.1代码优化的概念 297
11.2代码优化的基本技术 299
11.2.1删除公共子表达式 299
11.2.2复写传播 301
11.2.3删除无用代码 301
11.2.4代码外提 301
11.2.5强度消弱和删除归纳变量 302
11.3局部优化 303
11.3.1基本块的变换 303
11.3.2基本块的DAG实现 304
11.3.3基于DAG的局部优化 307
11.4机器代码优化——窥孔技术 309
11.4.1冗余存取的删除 310
11.4.2不可达代码的删除 310
11.4.3控制流优化 310
11.4.4代数化简与强度消弱 311
11.4.5特殊指令的使用 312
11.5代码优化的高级技术简介 312
练习11 313
参考文献 315