第1部分 基 础篇 3
第1章 编译概述 3
1.1 什么是程序设计语言 3
1.1.1 程序设计语言的定义方法 4
1.1.2 程序设计语言的处理系统 5
1.1.3 编译程序和解释程序 5
1.2 与编译程序相关的处理系统 8
1.3 编译程序和程序设计环境 10
1.4 编译程序的构造 12
1.5 编译技术在软件工程中的应用 19
练习1 21
第2章 文法和语言的概念和表示 22
2.1 文法的非形式讨论 22
2.1.1 语法树 22
2.1.2 规则 23
2.1.3 由规则推导句子 24
练习2-1 26
2.2 符号、符号串及其集合的运算 27
2.2.1 字母表和符号串 27
2.2.2 符号串及其集合的运算 27
练习2-2 29
2.3 文法和语言的形式定义 29
2.3.1 文法的形式定义 29
2.3.2 推导的形式定义 31
2.3.3 语言的形式定义 32
2.3.4 递归规则与递归文法 35
2.3.5 短语、简单短语和句柄 36
练习2-3 38
2.4 语法树和二义性 39
2.4.1 推导与语法树 39
2.4.2 文法的二义性 43
练习2-4 46
2.5 符号串的分析 48
2.5.1 自顶向下分析 49
2.5.2 自底向上分析 50
2.6 有关文法的实用限制 51
练习2-5 53
2.7 扩充的BNF表示和语法图 53
2.7.1 扩充的BNF表示 53
2.7.2 语法图 56
2.8 文法和语言分类 57
第3章 词法分析程序的设计 60
3.1 词法分析程序的功能及实现方案 60
3.2 单词的种类及词法分析程序的输出形式 61
3.3 正则文法及其状态图 63
3.3.1 状态图 63
3.3.2 状态图的使用 64
3.4 词法分析程序的设计与实现 65
3.4.1 文法及其状态图 65
3.4.2 词法分析程序的构造 67
3.4.3 词法分析程序的实现 70
练习3 73
第4章 语法分析（一） 74
4.1 自顶向下分析方法 74
4.1.1 带回溯的自顶向下分析方法 74
4.1.2 存在的问题及解决办法 76
练习4-1 84
4.2 递归下降分析法 84
4.3 基于递归下降分析法的语法分析程序构造 85
练习4-2 91
第5章 符号表管理技术 93
5.1 概述 93
5.1.1 符号表的概念及建立和访问时间 93
5.1.2 符号表的重要性和作用 95
5.1.3 在符号表上的操作 95
5.2 符号表的组织和内容 97
5.2.1 符号表的结构与内容 97
5.2.2 符号表的组织方式 99
5.3 非分程序结构语言的符号表组织 101
5.3.1 标识符的作用域及基本处理方法 101
5.3.2 符号表的组织方式 102
5.4 分程序结构语言的符号表组织 109
5.4.1 标识符的作用域及基本处理方法 109
5.4.2 定位和重定位操作 110
5.4.3 符号表的组织方式 112
练习5 115
第6章 运行时的存储组织及管理 117
6.1 静态存储分配 117
练习6-1 119
6.2 动态存储分配 120
6.2.1 活动记录 121
6.2.2 参数区 121
6.2.3 display区 122
6.2.4 运行时的地址计算 125
6.2.5 递归过程的处理 125
6.3 内存垃圾回收器 128
6.3.1 引用计数 128
6.3.2 标记和清除垃圾回收器 129
6.3.3 标记紧缩算法 129
6.3.4 拷贝回收算法 130
6.3.5 分代垃圾回收器 130
练习6-2 133
第7章 源程序的中间形式 135
7.1 波兰表示 135
7.2 N-元表示 137
7.3 抽象语法树 139
7.4 抽象机代码 140
7.4.1 可移植性和抽象机 141
7.4.2 Pascal的P-code抽象机 142
7.4.3 P-code指令 143
练习7 144
第8章 错误处理 145
8.1 概述 145
8.2 错误的分类 146
8.3 错误的检查与报告 146
8.4 错误处理技术 148
8.4.1 错误改正 149
8.4.2 错误局部化处理 149
8.4.3 目标程序运行时错误检测与处理 152
8.4.4 遏止重复的错误信息 152
第9章 语法制导翻译技术 153
9.1 翻译文法 154
9.2 语法制导翻译 156
9.3 属性翻译文法 158
9.3.1 综合属性 158
9.3.2 继承属性 160
9.3.3 属性翻译文法 162
9.3.4 属性翻译文法举例：算术表达式的翻译 164
练习9-1 166
9.4 自顶向下语法制导翻译 168
9.4.1 翻译文法的自顶向下翻译 168
练习9-2 172
9.4.2 属性翻译文法的自顶向下翻译 173
练习9-3 180
第10章 语义分析和代码生成 182
10.1 语义分析的概念 182
10.2 栈式抽象机及其汇编指令 184
10.3 声明语句的处理 186
10.3.1 常量类型 188
10.3.2 简单变量 188
10.3.3 数组变量 190
10.3.4 记录变量 192
10.3.5 过程声明 193
10.4 表达式语句 194
10.5 赋值语句 201
10.6 控制语句 203
10.6.1 if语句 203
10.6.2 分情形语句 205
10.6.3 repeat-while语句 208
10.6.4 for循环语句 209
10.7 过程调用和返回语句 211
10.7.1 参数的基本传递形式 211
10.7.2 过程调用 213
10.7.3 返回语句和过程终止 217
10.8 输入/输出语句 218
10.8.1 输入语句 218
10.8.2 输出语句 221
10.9 编译程序的辅助功能 222
练习10 223
第2部分 提 高篇 227
第11章 词法分析程序的自动生成技术 227
11.1 正则文法与正则表达式 227
11.1.1 正则表达式 227
11.1.2 正则文法转换为正则表达式 230
11.1.3 正则表达式转换为正则文法 231
11.2 有穷自动机 231
11.2.1 确定的有穷自动机 232
11.2.2 不确定的有穷自动机 233
11.2.3 NFA的确定化 235
11.2.4 确定有穷自动机的化简（最小化） 238
11.2.5 正则表达式与有穷自动机的等价性 242
11.2.6 正则文法与有穷自动机的等价性 246
11.3 词法分析程序的自动生 248
成器 248
11.3.1 Lex源程序（Lex的输入文件） 248
11.3.2 Lex的实现 250
练习11 254
第12章 语法分析（二） 256
12.1 LL（1）分析方法 256
12.1.1 LL（1）分析器的逻辑结构及工作过程 256
12.1.2 LL（1）分析表的构造方法 259
练习12-1 264
12.2 自底向上分析方法 265
12.3 算法优先分析法 268
12.3.1 方法概述 268
12.3.2 直观算符优先分析法 270
12.3.3 算符优先分析法的进一步讨论 273
练习12-2 279
12.4 LR语法分析方法 280
12.4.1 概念和术语 281
练习12-3 282
12.4.2 LR分析算法 282
练习12-4 288
12.4.3 LR文法 288
12.4.4 构造SLR语法分析表 289
练习12-5 297
12.4.5 构造规范LR语法分析表 299
练习12-6 304
12.4.6 构造LALR语法分析表 305
练习12-7 309
第13章 语法制导翻译技术（二） 311
13.1 LL（1）文法的语法制导翻译 311
13.1.1 翻译文法的自顶向下翻译——LL（1）翻译器 311
练习13-1 313
13.1.2 属性文法自顶向下翻译的实现——下推机法 314
练习13-2 320
13.2 自底向上语法制导翻译 321
13.2.1 波兰翻译 322
13.2.2 S-属性文法 323
练习13-3 325
第14章 代码优化 327
14.1 基本块和流图 328
14.2 基本块内优化 330
14.2.1 基本块的DAG图表示 331
14.2.2 消除局部公共子表达式 331
14.2.3 数组、指针及函数调用 332
14.2.4 从DAG图重新导出中间代码 334
14.2.5 窥孔优化 336
14.2.6 常数合并和传播 337
14.3 全局优化 338
14.3.1 数据流分析 338
14.3.2 活跃变量分析 344
14.3.3 定义-使用链、网和冲突图 346
14.3.4 消除全局公共子表达式 351
14.3.5 复制传播 352
14.3.6 死代码删除 353
14.4 循环优化 353
14.4.1 循环交换 354
14.4.2 循环展开 354
14.4.3 代码外提和循环强度削弱 355
练习14 356
第15章 目标代码生成及优化 357
15.1 微处理器体系结构简介 358
15.1.1 指令集架构 359
15.1.2 存储层次架构 362
15.1.3 流水线 364
15.2 地址空间 367
15.2.1 程序地址空间的实例分析 369
15.2.2 程序运行栈的设计 371
15.3 寄存器的分配和指派 374
15.3.1 全局寄存器分配 374
15.3.2 临时寄存器分配 377
15.4 指令选择 379
练习15 381
第16章 编译程序生成方法和工具 383
16.1 编译程序的书写语言 383
16.2 自展 384
16.3 移植 385
16.4 编译程序的生成工具 386
16.4.1 语法分析器的生成器YACC 387
16.4.2 用YACC处理二义文法 390
16.4.3 用Lex建立YACC的词法分析器 393
16.4.4 YACC的错误恢复 394
练习16 396
第3部分 实 例篇 399
第17章 PL/O简单编译系统 399
17.1 PL/O语言 399
17.2 PL/O编译系统结构 404
17.3 PL/O的词法分析 406
17.4 PL/O的语法分析 407
17.5 出错处理 409
17.6 目标代码的生成和解释执行 411
17.7 PL/O程序编译和运行举例 414
第18章 Pascal-S编译系统 427
18.1 Pascal-S语言 427
18.2 Pascal-S编译程序的结构 434
18.3 Pascal-S编译程序 439
18.3.1 表格 439
18.3.2 编译初启 446
18.3.3 实用程序 447
18.3.4 词法分析及处理 448
18.3.5 语法分析处理 449
18.3.6 出错处理 455
18.4 Pascal-S解释执行程序 458
18.4.1 P代码指令系统 458
18.4.2 运行栈 461
18.4.3 运行时的display 462
18.4.4 运行出错处理和现场剖析打印 464
18.5 编译及运行的例子 465
参考文献 479