本书是一本优秀的编译器构造方面的教材,适合高等院校计算机专业的学生及专业程序员使用,已经被国际上多所大学或学院选作教材。本书提供了创新的编译器构造方法,通过大量的示例和练习,描述如何从头至尾设计一个可用的编译器。书中均衡覆盖了编译器设计中的理论与实现两大部分,详细讨论了标准编译器设计的相关主题 (如自顶向下和自底向上的语法分析、语义分析、中间表示和代码生成)。本书中所有的程序均采用易读的基于C语言的代码来表示。
本书特色: ●均衡讨论了编译器设计的理论与实现两大部分,既很好地介绍了编译器理论,又提供了大量的编译器设计示例和练习。 ●强调使用可以生成语法分析器和词法分析器的编译器工具。 ●彻底讨论LR语法分析和归约技术。 ●介绍了FLex和ScanGen。 ●在每章末尾包含可选的高级主题。
目录
- 第1章 绪论 1
- 1.1 概述和历史 1
- 1.2 编译器可以做什么 2
- 1.3 编译器结构 5
- 1.4 程序设计语言的语法和语义 8
- 1.5 编译器设计与程序设计语言设计 10
- 1.6 编译器分类 11
- 1.7 影响编译器设计的因素 12
- 练习 13
- 第2章 一个简单编译器 15
- 2.1 Micro编译器结构 15
- 2.2 Micro词法分析器 15
- 2.3 Micro 语法 19
- 2.4 递归下降语法分析 21
- 2.5 翻译 Micro 25
- 2.5.1 目标语言 25
- 2.5.2 临时变量 25
- 2.5.3 动作符号 25
- 2.5.4 语义信息 25
- 2.5.5 Micro动作符号 26
- 练习 31
- 第3章 词法分析—理论和实践 33
- 3.1 概述 33
- 3.2 正则表达式 34
- 3.3 有限自动机和词法分析器 35
- 3.4 使用词法分析器生成器 38
- 3.4.1 ScanGen 38
- 3.4.2 Lex 43
- 3.5 实现时考虑的问题 45
- 3.5.1 保留字 45
- 3.5.2 编译器指示与源程序行列表 47
- 3.5.3 符号表中的标识符条目 47
- 3.5.4 词法分析器的终止 48
- 3.5.5 多字符的超前搜索 48
- 3.5.6 词法错误恢复 49
- 3.6 将正则表达式转换为有限自动机 51
- 3.6.1 构造确定的有限自动机 52
- 3.6.2 优化有限自动机 54
- 练习 55
- 第4章 文法和语法分析 59
- 4.1 上下文无关文法:概念与记号 59
- 4.2 上下文无关文法中的错误 61
- 4.3 转换扩展 BNF文法 62
- 4.4 语法分析器与识别器 63
- 4.5 文法分析算法 64
- 练习 69
- 第5章 LL(1)文法及分析器 71
- 5.1 LL(1) Predict函数 71
- 5.2 LL(1)分析表 73
- 5.3 从LL(1)分析表构造递归下降分析器 74
- 5.4 LL(1)分析器驱动程序 77
- 5.5 LL(1)动作符号 77
- 5.6 文法的LL(1)化 78
- 5.7 LL(1)分析中的If-Then-Else问题 81
- 5.8 LLGen—LL(1)语法分析器生成器 82
- 5.9 LL(1)分析器的性质 85
- 5.10 LL(k)分析 85
- 练习 87
- 第6章 LR分析 89
- 6.1 移进-归约分析器 89
- 6.2 LR分析器 91
- 6.2.1 LR(0)分析 92
- 6.2.2 如何判定LR(0)分析程序工作的正确性 96
- 6.3 LR(1)分析 98
- 6.3.1 LR(1)分析的正确性 101
- 6.4 SLR(1)分析 102
- 6.4.1 SLR(1)分析的正确性 103
- 6.4.2 SLR(1)技术的局限性 104
- 6.5 LALR(1)分析 105
- 6.5.1 构造LALR(1)分析器 108
- 6.5.2 LALR(1)分析的正确性 112
- 6.6 在移进-归约分析器中调用语义例程 113
- 6.7 使用语法分析器生成器 114
- 6.7.1 LALRGen语法分析器生成器 114
- 6.7.2 Yacc 116
- 6.7.3 可控二义性的使用和误用 117
- 6.8 优化分析表 120
- 6.9 实用的LR(1)分析器 123
- 6.10 LR分析的性质 125
- 6.11 LL(1)和LALR(1)分析方法的比较 125
- 6.12 其他的移进-归约技术 128
- 6.12.1 扩展的超前搜索技术 128
- 6.12.2 优先级技术 128
- 6.12.3 一般的上下文无关分析器 130
- 练习 132
- 第7章 语义处理 137
- 7.1 语法制导翻译 137
- 7.1.1 使用分析的语法树表示 137
- 7.1.2 编译器组织的候选形式 138
- 7.1.3 一遍编译中的分析、检查和翻译 142
- 7.2 语义处理技术 143
- 7.2.1 LL分析器和动作符号 143
- 7.2.2 LR分析器和动作符号 143
- 7.2.3 语义记录表示 144
- 7.2.4 实现动作控制的语义栈 146
- 7.2.5 分析器控制的语义栈 149
- 7.3 中间表示和代码生成 155
- 7.3.1 比较中间表示和直接代码生成 155
- 7.3.2 中间表示的形式 155
- 7.3.3 一个元组语言 157
- 练习 157
- 第8章 符号表 161
- 8.1 符号表接口 161
- 8.2 基本实现技术 162
- 8.2.1 二叉搜索树 162
- 8.2.2 哈希表 163
- 8.2.3 串空间数组 164
- 8.3 块结构符号表 165
- 8.4 块结构符号表的扩展 169
- 8.4.1 域和记录 169
- 8.4.2 导出规则 170
- 8.4.3 导入规则 174
- 8.4.4 可更改的搜索规则 175
- 8.5 隐式声明 177
- 8.6 重载 177
- 8.7 前向引用 178
- 8.8 小结 180
- 练习 180
- 第9章 运行时存储组织 183
- 9.1 静态分配 183
- 9.2 栈分配 183
- 9.2.1 显示表 185
- 9.2.2 块级与过程级活动记录 187
- 9.3 堆分配 188
- 9.3.1 无空间释放 188
- 9.3.2 显式释放 188
- 9.3.3 隐式释放 189
- 9.3.4 管理堆空间 190
- 9.4 内存中的程序布局 191
- 9.5 静态链簇和动态链簇 193
- 9.6 形式过程 195
- 9.6.1 静态链簇 196
- 9.6.2 显示表 197
- 9.6.3 一些看法 198
- 练习 199
- 第10章 处理声明 203
- 10.1 声明处理的基本原则 203
- 10.1.1 符号表中的属性 203
- 10.1.2 类型描述符结构 204
- 10.1.3 语义栈中的列表结构 205
- 10.2 简单声明的动作例程 207
- 10.2.1 变量声明 207
- 10.2.2 类型定义、声明和引用 209
- 10.2.3 记录类型 212
- 10.2.4 静态数组 214
- 10.3 高级特性的动作例程 216
- 10.3.1 变量和常量声明 216
- 10.3.2 枚举类型 218
- 10.3.3 子类型 220
- 10.3.4 数组类型 221
- 10.3.5 变体记录 227
- 10.3.6 访问类型 232
- 10.3.7 包 233
- 10.3.8 attributes和semantics_record结构 236
- 练习 239
- 第11章 处理表达式和数据结构引用 241
- 11.1 概述 241
- 11.2 简单名字、表达式和数据结构的动作例程 242
- 11.2.1 处理简单标识符和文字常量 242
- 11.2.2 处理表达式 243
- 11.2.3 简单的记录和数组引用 246
- 11.2.4 记录和数组示例 249
- 11.2.5 串 250
- 11.3 高级特性的动作例程 250
- 11.3.1 多维数组的组织和引用 250
- 11.3.2 含动态对象的记录 258
- 11.3.3 变体记录 261
- 11.3.4 访问类型的引用 262
- 11.3.5 Ada中其他名字的使用 263
- 11.3.6 记录和数组聚合 265
- 11.3.7 重载解析 266
- 练习 269
- 第12章 翻译控制结构 271
- 12.1 if语句 271
- 12.2 循环 274
- 12.2.1 while循环 274
- 12.2.2 for循环 275
- 12.3 编译exit语句 280
- 12.4 case语句 282
- 12.5 编译goto语句 287
- 12.6 异常处理 290
- 12.7 短路计算布尔表达式 294
- 12.7.1 单地址短路计算 299
- 练习 305
- 第13章 翻译过程和函数 309
- 13.1 简单子程序 309
- 13.1.1 声明无参子程序 309
- 13.1.2 调用无参过程 311
- 13.2 向子程序传递参数 312
- 13.2.1 值、结果和值-结果参数 313
- 13.2.2 引用和只读参数 314
- 13.2.3 处理参数声明的语义例程 314
- 13.3 处理子程序调用和参数表 316
- 13.4 子程序调用 317
- 13.4.1 保存和恢复寄存器 317
- 13.4.2 子程序的入口和出口 318
- 13.5 标号参数 321
- 13.6 名字参数 323
- 练习 324
- 第14章 属性文法和多遍翻译 327
- 14.1 属性文法 327
- 14.1.1 简单赋值形式和动作符号 329
- 14.1.2 树遍历的属性计算程序 331
- 14.1.3 直接属性计算程序 335
- 14.1.4 属性文法示例 340
- 14.2 树结构的中间表示 342
- 14.2.1 抽象语法树接口 343
- 14.2.2 语法树抽象接口 344
- 14.2.3 实现树 348
- 练习 349
- 第15章 代码生成和局部代码优化 351
- 15.1 概述 351
- 15.2 寄存器和临时变量管理 352
- 15.2.1 临时变量的分类 353
- 15.2.2 分配和释放临时变量 353
- 15.3 简单的代码生成器 354
- 15.4 解释性代码生成 356
- 15.4.1 优化地址计算 357
- 15.4.2 避免冗余计算 359
- 15.4.3 寄存器追踪 361
- 15.5 窥孔优化 367
- 15.6 从树结构生成代码 368
- 15.7 从dag生成代码 371
- 15.7.1 别名 376
- 15.8 代码生成器的生成器 377
- 15.8.1 基于文法的代码生成器 380
- 15.8.2 在代码生成器中使用语义属性 382
- 15.8.3 生成窥孔优化器 385
- 15.8.4 基于树重写的代码生成器的生成器 387
- 练习 387
- 第16章 全局优化 393
- 16.1 概述—目标与限制 393
- 16.1.1 理想的优化编译器结构 394
- 16.1.2 优化展望 397
- 16.2 优化子程序调用 397
- 16.2.1 子程序调用的内联展开 397
- 16.2.2 优化对封闭子例程的调用 399
- 16.2.3 过程间数据流分析 402
- 16.3 循环优化 406
- 16.3.1 外提循环不变式 406
- 16.3.2 循环中强度削弱 409
- 16.4 全局数据流分析 411
- 16.4.1 单路径流分析 411
- 16.4.2 全路径流分析 415
- 16.4.3 数据流问题的分类 416
- 16.4.4 其他重要的数据流问题 416
- 16.4.5 使用数据流信息的全局优化 418
- 16.4.6 求解数据流方程 422
- 16.5 集成优化技术 430
- 练习 431
- 第17章 现实世界中的语法分析 437
- 17.1 压缩表 437
- 17.1.1 压缩LL(1)分析表 439
- 17.2 语法错误的恢复与修复 440
- 17.2.1 即时错误检测 442
- 17.2.2 递归下降分析器中的错误恢复 443
- 17.2.3 LL(1)分析器中的错误恢复 445
- 17.2.4 FMQ LL(1)错误修复算法 446
- 17.2.5 在FMQ修复算法中添加删除操作 449
- 17.2.6 FMQ算法的扩展 450
- 17.2.7 利用LLGen进行错误修复 454
- 17.2.8 LR错误恢复 455
- 17.2.9 Yacc中的错误恢复 455
- 17.2.10 自动生成的LR修复技术 456
- 17.2.11 利用LALRGen进行错误修复 462
- 17.2.12 其他LR错误修复技术 462
- 练习 463
- 附录A Ada/CS语言定义 467
- 附录B ScanGen 487
- 附录C LLGen用户手册 493
- 附录D LALRGen用户手册 499
- 附录E LLGen和LALRGen错误修复特性 507
- 附录F 编译器开发实用工具 511
- 参考文献 517
-
索引 523