前言 1
第1章 编译程序概论 1
本章学习目标 1
1.1 程序设计语言 1
序 1
1.2 编译程序的编译过程和结构 2
1.3 编译程序的设计技术 5
1.4 形式语言理论和编译实现技术 7
小结 7
习题一 8
2.1 字母表和符号串 10
2.1.2 符号串 10
2.1.1 字母表 10
本章学习目标 10
第2章 形式语言概述 10
2.1.3 符号串集合 12
2.2 文法的定义及其分类 12
2.2.1 文法的直观概念 12
2.2.2 文法的形式定义 13
2.2.3 文法的分类 14
2.2.4 文法举例 15
2.2.5 各类文法与自动机的关系 16
2.2.6 文法分类的意义 17
2.3 文法产生的语言和句型的语法树 18
2.3.1 推导和规范推导 18
2.3.2 句型、句子和语言 19
2.3.3 语法树 20
2.3.4 二义性文法及其他 21
2.3.5 文法产生的语言和产生语言的文法 23
2.4 句型分析与句柄 24
2.4.1 自顶向下的分析方法 25
2.4.2 确定的自顶向下的分析方法 26
2.4.3 自底向上的分析方法 27
2.4.4 文法的存储 30
2.5 例题分析与解答 33
小结 35
习题二 36
第3章 词法分析 37
本章学习目标 37
3.1 词法分析程序与单词符号 37
3.1.1 词法分析 37
3.1.2 单词符号 38
3.1.3 一个简单的词法分析程序的设计 39
3.2 单词的描述工具 42
3.2.1 正规文法 42
3.2.2 正规式 42
3.2.3 正规文法和正规式的相互转换 43
3.3 有穷自动机 45
3.3.1 确定的有穷自动机 45
3.3.2 不确定的有穷自动机 46
3.3.3 不确定的有穷自动机到确定的有穷自动机之间的转换 47
3.4 正规式与有穷自动机的等价性 54
3.4.1 正规式到NFA的转换 54
3.4.2 NFA到正规式的转换 56
3.4.3 NFA和正规式表示的相互转换示例 57
3.5.1 从正规文法到自动机的转换 61
3.5 正规文法和自动机的转换 61
3.5.2 根据自动机写出正规文法 62
3.6 词法分析程序的自动生成 63
3.6.1 用LEX语言表达正规式 63
3.6.2 LEX程序的结构 64
3.7 词法分析程序的C语言实现 66
3.7.1 单词的内部定义 66
3.7.2 词法分析程序流程图 67
3.7.3 数据结构的设计 68
小结 68
习题三 68
4.1 确定的自顶向下分析方法 71
4.1.1 确定的自顶向下分析思想 71
本章学习目标 71
第4章 自顶向下的语法分析技术 71
4.1.2 LL（1）文法的定义 73
4.2 LL（1）文法 75
4.2.1 LL（1）文法的判别 75
4.2.2 将非LL（1）文法转变成LL（1）文法 78
4.3 确定的自顶向下分析技术 84
4.3.1 递归子程序法 84
4.3.2 预测分析法 88
小结 93
习题四 94
第5章 自底向上优先分析技术 97
本章学习目标 97
5.1 自底向上分析方法 97
5.1.1 自底向上分析的基本思想 97
5.1.2 移进—归约方法 98
5.2.1 优先关系 100
5.2 简单优先分析技术 100
5.2.2 简单优先分析法的定义及操作步骤 102
5.2.3 简单优先分析法的局限性 104
5.3 算符优先分析方法 105
5.3.1 算符优先文法 105
5.3.2 算符优先文法（OPG）优先关系表的构造 107
5.3.3 算符优先分析法的算法 112
5.3.4 实际应用中的算符优先函数及其构造 117
5.3.5 采用算符优先分析法的语法分析程序的实现 120
5.4 两种优先分析法的比较 123
小结 124
习题五 124
6.1 LR分析器的工作原理 127
第6章 LR分析技术 127
本章学习目标 127
6.2 LR（0）分析表的构造 130
6.2.1 采用活前缀的方法构造有限自动机 131
6.2.2 采用项目的方法构造有限自动机 133
6.2.3 采用文法的项目集规范族构造有限自动机 135
6.3 SLR（1）分析表的构造 143
6.3.1 问题的提出 144
6.3.2 解决LR（0）分析方法中冲突问题的方法 145
6.4 LR（1）分析 149
6.4.1 问题的提出 149
6.4.2 LR（1）分析的基本思想 151
6.5.1 同心集的合并 154
6.5 LALR分析 154
6.5.2 LALR分析表的构造步骤 155
6.6 二义性文法的应用 157
6.7 SLR（1）分析器的设计实现 161
6.7.1 LR语法分析程序的C语言实现 161
6.7.2 自动生成语法分析器 162
小结 166
习题六 167
第7章 语法制导翻译和中间代码生成 169
本章学习目标 169
7.1 概述 169
7.1.1 语义分析的概念 169
7.1.2 语法制导翻译 170
7.2.2 属性文法 172
7.2.1 文法的属性 172
7.2 属性文法 172
7.3 几种常见的中间代码形式 173
7.3.1 逆波兰式表示方法 173
7.3.2 逆波兰式表示方法的推广 174
7.3.3 四元式 175
7.3.4 三元式和树形表示 176
7.4 表达式及赋值语句的翻译 177
7.4.1 简单表达式及赋值语句的翻译 177
7.4.2 布尔表达式的翻译 179
7.4.3 在控制语句中布尔表达式的翻译 180
7.5 控制语句的翻译 184
7.5.1 控制语句的翻译 185
7.5.2 多分支控制语句case的翻译 190
7.5.3 for循环语句 192
7.6 数组元素的翻译 194
7.6.1 数组元素的地址计算及中间代码的生成 194
7.6.2 赋值语句中数组元素的翻译 195
7.6.3 数组元素翻译示例 196
7.7 高级语言中其他语句的翻译 198
7.7.1 结构体说明和引用的翻译 198
7.7.2 说明语句的翻译 199
7.7.3 转向语句的翻译 200
7.7.4 过程调用语句的翻译 201
小结 202
习题七 203
8.1.1 优化概述 204
8.1 优化的概念 204
本章学习目标 204
第8章 代码优化 204
8.1.2 优化技术简介 205
8.2 局部优化 208
8.2.1 基本块的划分方法 208
8.2.2 基本块的DAG表示 209
8.2.3 用DAG图进行优化得到优化后的四元式 212
8.3 循环优化 213
8.3.1 程序流图 213
8.3.2 循环的查找 215
8.3.3 循环优化 216
8.3.4 窥孔优化 219
小结 219
习题八 219
9.2 静态存储分配 222
9.1 存储分配策略 222
第9章 运行时存储空间的组织与管理 222
本章学习目标 222
9.3 栈式存储分配 223
9.3.1 简单的栈式存储分配 223
9.3.2 嵌套过程语言的栈式实现 226
9.3.3 分程序结构的存储管理 229
9.4 堆式动态存储分配 233
9.5 参数传递方式及其实现 233
9.5.1 参数传递的方法 233
9.5.2 参数传递的示例 234
小结 235
习题九 235
10.1.1 符号表的建立和访问 237
10.1 符号表的组织和内容 237
本章学习目标 237
第10章 符号表和错误处理 237
10.1.2 符号表的组织 238
10.1.3 符号表的内容 245
10.2 符号表的操作和错误处理 246
10.2.1 符号表的初始化 246
10.2.2 符号表的登录 247
10.2.3 符号的查找 247
10.2.4 符号表中关于分层结构的管理 247
10.3 错误处理 250
10.3.1 语法错误的校正 250
10.3.2 语义错误的校正 252
10.4 一个符号表的设计实例 252
习题十 256
小结 256
本章学习目标 257
11.1 中间代码生成目标代码 257
11.1.1 假想的计算机模型 257
第11章 目标代码的生成 257
11.1.2 从四元式生成代码 258
11.1.3 从三元式生成代码 259
11.1.4 从树形表示到生成代码 262
11.1.5 从逆波兰表示生成代码 264
11.1.6 寄存器的分配 264
11.2 常用的代码生成程序的开发方法 265
11.2.1 解释性的代码生成法 265
11.3 代码生成程序的自动化构造 266
11.3.1 基于语法制导翻译的代码生成程序自动构造技术 266
11.2.3 表驱动代码生成法 266
11.2.2 模式匹配代码生成法 266
11.3.2 基于语义制导的代码生成程序自动构造技术 269
11.3.3 模式匹配和动态规划 269
11.4 目标代码生成器设计实例 270
11.4.1 待用信息与活跃信息 271
11.4.2 代码生成算法 272
11.4.3 目标代码生成的具体实例 274
小结 279
习题十一 279
附录A 编译原理实践部分 280
参考文献 315