本书详细介绍了编译程序设计中的词法分析（扫描程序）、语法分析（分析程序）、语义分析（约束程序）、中间代码优化以及代码生成等内容。作为颇受好评的编译原理经典教材，本书的最大特色是在全书贯穿了一种基于文法的指导思路，语义分析、代码优化、代码生成等均采用文法定义其规格说明，并且最后给出了变换属性文法（TAG）的一种自编译实现。此外，本书还探讨了面向不同计算机体系结构的代码生成技术，以及非过程式语言的编译问题。
编译程序设计艺术 理论与实践
The Art of Compiler Design
Theory and Practice
(美) Thomas Pittman James Peters 著 李文军 高晓燕 译
本书详细介绍了编译程序设计中的词法分析（扫描程序）、语法分析（分析程序）、语义分析（约束程序）、中间代码优化以及代码生成等内容。作为颇受好评的编译原理优秀入门教材，本书的最大特色是在全书贯穿了一种基于文法的指导思路：在语法分析阶段，该书遵循了一般教材采用的上下文无关文法；在语义分析阶段，采用以上下文无关文法为基础的属性文法；而在代码优化和代码生成阶段，则采用了变换属性文法。书中最后还给出变换属性文法的一种自编译实现。此外，本书还探讨了面向不同计算机体系结构的代码生成技术以及非过程式语言的编译问题。
本书适合作为高等院校计算机科学与技术、软件工程以及相关专业编译原理课程的教学参考书，同时也可供计算机语言及其处理技术爱好者参考。
本书特点
坚定不移地扎根于文法，一开始就介绍文法和语言识别器之间的理论关系，然后贯穿全书将文法技术应用到编译程序设计的每一方面。
统一将实用的属性文法作为编译程序语义的载体，坚持这一立场自然会产生一个完全由属性文法定义的、可编译其自身的“编译程序—编译程序”。
具有非常实用的特征，编译程序的“设计”必须以属性文法定义，而编译程序的“构造”则需要可执行的代码，并且每一个重要的理论原则均需通过一种真实程序设计语言的大量代码清单加以阐明，不断展示文法与机器代码之间极其自然的关系。
选择Modula-2作为演示代码的程序设计语言，旨在概念抽象与具体效率之间取得平衡。
实用且复杂的现代信息系统并不是从累积的偶然事件中发展起来的。编译程序作为一个实用的信息系统，只有经过精心设计，才能以简单的措辞理解其复杂性。不仅未经设计的编译程序会有功能缺陷，编译程序理论本身还依赖于它与两种理论之间的一种微妙关系，其中一种理论是源自人类自然语言的语言学原理，另一种理论是将计算机看作有穷状态自动机。理解并利用这一关系需在文法理论的基本原理方面有扎实的根基，并熟练掌握其机械化实现过程。因而编译程序设计的教学亦涉及一个复杂的信息系统，需精心设计才能以连贯、合理的次序展示相关概念，从而让学生体会到编译程序设计的内容既是相关的，也是可管理的。
本书并非一本试图以所有可能的方法去构造所有可能的编译程序的百科全书，而是依次介绍编译程序设计中的最基本问题；其内容的深度足以让勤奋的学生有能力通过手工方式或使用编译程序生成工具（亦或两种方式之结合），构造实用且高效的编译程序。更重要的是，学生将明白这些工具是如何工作的，以及为什么必须以某种方式书写文法方可取得预期的结果。这正是设计的原则。因此，尽管大多数现代分析程序生成工具采用自底向上分析技术，但本书深入研究有更多限制的自顶向下分析理论，然后才利用相对简短（但完整）的一章内容学习自底向上分析程序。本书每一章的目标都是先灌输对基本概念的理解，然后再将这些概念应用到实践中。
与同类教材相比，本书在四个重要方面有显著特色。第一个特色是，它坚定不移地扎根于文法，一开始就介绍文法和语言识别器之间的理论关系，然后贯穿全书将文法技术应用到编译程序设计的每一方面。第二个特色是，统一将实用的属性文法作为编译程序语义的载体，坚持这一立场自然会产生一个完全由属性文法定义的、可编译其自身的“编译程序－编译程序”，这正是本书最后一章的重点。第三个特色是，具有非常实用的特征，编译程序的设计必须以属性文法定义，而编译程序的构造则需要可执行的代码，并且每一个重要的理论原则均需通过一种真实程序设计语言的大量代码清单加以阐明，不断展示文法与机器代码之间极其自然的关系。第四个特色是，选择Modula-2作为演示代码的程序设计语言，旨在概念抽象与具体效率之间取得平衡；与C语言等更低级的语言相比，应用本书后几章所介绍的优化技术能以更低的开销更显著地提高Modula-2程序的效率。
本书可用于一学期的编译原理入门课程，重点介绍前6章或前7章。本书亦可用于整学年的学习，更好地涉猎更多的高级课题。一学期的课程学习可安排在半年或一个季度的时间内完成；经过不断优化和实际教学检验，本书循序渐进地布置学生实验项目，并在期末完成一个可工作的Itty Bitty Modula编译程序，该编译程序可在最终的实验项目中用于编译另一个分析程序，例如第6章最后概述的美化打印工具或Tiny BASIC语言解释程序。
书中的某些章节和练习被设计为任选的。虽然我们坚信编译程序设计需要扎实的理论基础，但根据时间安排或学生能力等，某些章节中的一些趣味数学内容可略过，这些内容在其页边空白处用一个“教师授课”图标
注明。另一些章节虽与编译程序设计的主要问题密切相关，但由于本书的定位是初学编译原理的学生，他们的水平难以理解这些内容，因而在这些章节的页边空白处标注了一个“石中剑”图标 。类似地，有些问题富有挑战性，读者解决这些问题有助于更好地理解编译程序设计的错综复杂，但不在这些问题上花费额外的时间和精力，也不影响对课程内容的良好理解，因而在这些问题的页边空白处也标注了“石中剑”图标。
尽管无法逐一向所有对本教材作出贡献的人致谢，我们仍要首先感谢Brad Blaker，没有他的鼓励和早期协助，本书将不会面世；感谢Bill Hankley、Austin Melton和堪萨斯州立大学耐心的同学们，他们坚持使用了早期的书稿；感谢Frank DeRemer孕育了书中的许多思想。Thom Boyer、Dick Karpinski、Brian Kernighan、Marvin Zelkowitz、Wayne Citrin、Norman C. Hutchinson、Johnson M. Hart、Bernhard Weinberg、Will Gillett，特别是Dean Pittman、Chota和Dave Schmidt等人提出的意见和建议对本书的最终定稿有莫大帮助。
Thomas Pittman
James Peters
计算机\编译
本书详细介绍了编译程序设计中的词法分析（扫描程序）、语法分析（分析程序）、语义分析（约束程序）、中间代码优化以及代码生成等内容。作为颇受好评的编译原理经典教材，本书的最大特色是在全书贯穿了一种基于文法的指导思路：在语法分析阶段，该书遵循了一般教材采用的上下文无关文法；在语义分析阶段，则采用以上下文无关文法为基础的属性文法；而在代码优化和代码生成阶段，则采用了变换属性文法。书中最后还给出变换属性文法的一种自编译实现。此外，本书还探讨了面向不同计算机体系结构的代码生成技术，以及非过程式语言的编译问题。
本书适合作为高等院校计算机科学与技术、软件工程以及相关专业编译原理课程的教学参考书，同时也可供计算机语言及其处理技术爱好者参考。
本书特色
? 坚定不移地扎根于文法，一开始就介绍文法和语言识别器之间的理论关系，然后贯穿全书将文法技术应用到编译程序设计的每一方面。
? 统一将实用的属性文法作为编译程序语义的载体，坚持这一立场自然会产生一个完全由属性文法定义的、可编译其自身的“编译程序―编译程序”
? 具有非常实用的特征，编译程序的“设计”必须以属性文法定义，而编译程序的“构造”则需要可执行的代码，并且每一个重要的理论原则均需通过一种真实程序设计语言的大量代码清单加以阐明，不断展示文法与机器代码之间极其自然的关系。
? 选择Modula-2作为演示代码的程序设计语言，旨在概念抽象与具体效率之间取得平衡。
李文军 高晓燕 译：暂无简介
长期以来，编译原理一直是计算机相关专业本科生的专业主干课程。提起编译原理的英文原版教材，许多人自然想到龙书（A. Aho等人所著《Compilers: Principles, Techniques, and Tools》，俗称Dragon Book）、虎书（A. Appel所著《Modern Compiler Implementation in C/Java/ML》，俗称Tiger Book）、鲸书（S. Muchnick所著《Advanced Compiler Design and Implementation》，俗称Whale Book）等经典著作，其中鲸书侧重于编译程序的后端，并不适合第一门编译原理课程使用。此外，较有影响力的教材还有K. Louden所著《Compiler Construction: Principles and Practice》、C. Fischer等人所著《Crafting a Compiler with C》、K. Cooper等人所著《Engineering a Compiler》以及A. Holub所著《Compiler Design in C》等。
与上述流行教材相比，由美国阿肯色大学T. Pittman和J. Peters合著的本书的最大特色，是在全书贯穿了一种基于文法的指导思路：在语法分析阶段，该书遵循了一般教材采用的上下文无关文法；在语义分析阶段，采用以上下文无关文法为基础的属性文法；而在代码优化和代码生成阶段，则采用了变换属性文法。书中最后还给出变换属性文法的一种自编译实现。由于将文法技术贯穿于编译程序设计的每一方面，设计人员可以在规格说明层次定义一种语言的语法和语义，这将有益于编译程序的实现（无论采用手工方式，还是基于生成工具的自动方式）。例如，书中“Tiny BASIC解释程序”和“Micro-Modula美化打印工具”这两个例子很好地展示了这一方法的强大能力，以及独立于具体实现语言的特性。
本书虽然扎根于文法，但又不至于赘述文法。例如，与很多教材不同的是，本书基于下推自动机模型讲解LL(k)分析技术，有助于读者更好地理解编译程序设计与其理论基础之间的关联。又如，定义正则语言的形式化工具包括正则表达式、正则文法（左线性和右线性）、有穷状态自动机（确定的和不确定的）等多种等价方式，它们之间的等价转换是编译原理的重要理论基础；本书在词法分析部分重点介绍了从定义词法规则的正则表达式（或正则文法）到约简的确定有穷状态自动机这一变换路径上的各个环节，而不像一些教材那样将形式语言和自动机理论的许多内容未加以精心筛选就照搬到编译原理课程中。
尽管本书在编译程序设计的应用技术与理论基础之间的折中可圈可点，但也有未尽人意之处，例如第7章关于LR(k)分析技术的介绍可能 会令许多初学者“知其然而不知其所以然”。在介绍编译程序后端的许多内容时，本书也因为过于简略并且缺少具体例子的解说，给读者理解相关技术造成困难。
鉴于本书编写年代较早，书中未涉及近十多年来编译程序的原理、方法、技术、工具等方面的最新进展，譬如面向对象程序设计语言的编译、垃圾收集机制的实现、许多代码优化技术等，这是读者使用本教材时应注意的地方。但这并不妨碍本书作为第一门编译原理课程的优秀入门教材或参考书，这些不足可通过其他较新的教材弥补。
中山大学计算机科学系软件工程实验室（selab@sysu）的周晓聪、乔海燕、罗达、李曦、朱建伟、梁焯佳、吴梓彦仔细阅读了译稿，并提出了宝贵的意见和建议，译者对此表示衷心感谢。由于译者水平所限，书中谬误之处在所难免，恳请广大读者不吝批评指正。
李文军 高晓燕
2009年9月于广州康乐园
出版者的话
译者序
前言
第1章 编译程序理论概述............................1
1.1 简介..........................................................1
1.2 语言与翻译程序.......................................1
1.3 文法的作用...............................................2
1.4 若干例子..................................................4
1.5 编译程序的结构.......................................6
1.5.1 词法分析.......................................7
1.5.2 字符串表.......................................8
1.5.3 语法分析.......................................9
1.5.4 约束..............................................9
1.5.5 符号表...........................................9
1.5.6 代码生成.......................................9
1.5.7 优化............................................10
符号.................................................................11
缩略词.............................................................11
关键术语.........................................................11
练习.................................................................12
复习小测验.....................................................12
编译程序实验项目..........................................13
进一步阅读.....................................................13
第2章 文法：乔姆斯基层次......................14
2.1 简介........................................................14
2.2 文法........................................................14
2.2.1 字母表与串.................................14
2.2.2 非终结符与产生式.....................15
2.2.3 若干文法例子.............................15
2.3 乔姆斯基层次.........................................18
2.4 文法及其机器.........................................19
2.4.1 图灵机.........................................19
2.4.2 线性有界自动机.........................20
2.4.3 下推自动机.................................20
2.4.4 删除空产生式.............................21
2.4.5 比较上下文无关文法和上下文 敏感文法....................................22
2.4.6 有穷状态自动机.........................22
2.5 空串与空语言........................................23
2.6 规范推导................................................23
2.7 二义性....................................................24
2.8 文法思维的艺术.....................................25
2.8.1 有穷状态自动机的局限性..........26
2.8.2 上下文无关文法的计数..............27
2.8.3 对上下文敏感.............................29
小结................................................................30
符号................................................................31
缩略词.............................................................31
关键术语.........................................................31
练习................................................................32
复习小测验.....................................................34
编译程序实验项目.........................................35
进一步阅读.....................................................35
第3章 扫描程序和正则语言......................37
3.1 词法分析简介........................................37
3.2 正则表达式............................................37
3.2.1 正则表达式代数.........................39
3.2.2 正则表达式的形式化特性..........40
3.3 文法与正则表达式的转换.....................41
3.4 有穷状态自动机.....................................44
3.5 不确定的有穷状态自动机.....................45
3.6 将文法转换为自动机.............................46
3.7 自动机的转换........................................48
3.7.1 删除空环路.................................49
3.7.2 删除空变迁.................................50
3.7.3 自动机的确定化.........................51
3.7.4 自动机的约简.............................52
3.8 将自动机转换为文法.............................53
3.9 左线性文法.............................................54
3.10 在计算机上实现有穷状态自动机........54
3.11 扫描程序的特殊实现问题....................59
3.11.1 输入字母表的大小....................59
3.11.2 扫描程序自动机中的停机 状态...........................................60
3.11.3 过滤空格与注释........................60
3.11.4 单词的输出...............................61
3.12 字符串表的实现...................................62
3.12.1 基于线性查找的实现................63
3.12.2 基于散列表的实现....................64
3.12.3 基于查找树的实现....................66
3.12.4 不同实现的性能比较................69
3.13 保留字..................................................69
3.14 使用扫描程序生成工具.......................70
小结.................................................................70
符号.................................................................71
缩略词.............................................................71
关键术语.........................................................71
练习.................................................................72
复习小测验.....................................................74
编译程序实验项目..........................................74
进一步阅读.....................................................75
第4章 分析程序和上下文无关语言.........76
4.1 简介........................................................76
4.2 下推自动机.............................................76
4.2.1 停机条件的等价性.....................78
4.2.2 根据上下文无关文法构造下推 自动机.........................................79
4.3 LL(k)条件...............................................81
4.3.1 First和Follow集.......................82
4.3.2 选择集.........................................83
4.4 左递归....................................................85
4.5 公共左因子.............................................86
4.6 为上下文无关文法扩展正则表达式 运算符....................................................88
4.7 使用分析程序生成工具.........................89
4.7.1 使用TAG编译程序...................90
4.7.2 使用YACC.................................92
4.8 递归下降分析程序.................................92
4.9 递归下降分析程序作为下推自动机......95
小结................................................................95
缩略词.............................................................96
关键术语.........................................................96
练习................................................................97
复习小测验...................................................101
编译程序实验项目.......................................101
进一步阅读...................................................102
第5章 语义分析与属性文法....................103
5.1 简介......................................................103
5.2 属性文法..............................................103
5.2.1 继承属性和综合属性...............104
5.2.2 属性值流...................................107
5.3 非终结符作为属性求值函数...............108
5.4 符号表作为属性...................................109
5.5 Micro-Modula的属性文法....................110
5.6 在TAG编译程序中使用属性...............113
5.7 作用域与标识符类别............................114
5.7.1 标识符作用域的文法................114
5.7.2 标识符作用域例子分析.............116
5.7.3 符号表的其他问题...................120
5.8 在递归下降中实现属性.......................121
5.9 实现符号表..........................................122
小结..............................................................123
符号..............................................................123
关键术语.......................................................123
练习..............................................................124
复习小测验...................................................126
编译程序实验项目.......................................126
进一步阅读...................................................126
第6章 语法制导代码生成........................128
6.1 简介......................................................128
6.2 计算机硬件体系结构...........................128
6.3 栈机器的表达式求值...........................130
6.4 Itty Bitty栈机器...................................131
6.5 带属性的代码生成...............................134
6.5.1 运算符优先级与结合性质........137
6.5.2 程序结构的语义.......................138
6.5.3 向前分支问题...........................139
6.6 过程和函数的代码生成.......................143
6.7 块结构的栈帧管理...............................144
6.7.1 帧与帧指针...............................144
6.7.2 静态链与动态链.......................145
6.7.3 帧指针的Display向量.............146
6.8 其他数据类型.......................................148
6.9 结构化数据类型...................................149
6.9.1 指针类型...................................150
6.9.2 记录结构...................................151
6.9.3 数组的语义...............................151
6.10 其他数据结构.....................................153
6.11 Itty Bitty栈机器的输入和输出..........154
6.12 语法制导语义的局限.........................154
6.13 手工编写编译程序的代码生成..........155
6.14 语法制导语义的应用.........................155
6.14.1 Tiny BASIC解释程序.............155
6.14.2 Micro-Modula美化打印工具...156
小结...............................................................158
关键术语.......................................................158
练习...............................................................159
复习小测验...................................................160
编译程序实验项目........................................160
进一步阅读...................................................160
第7章 自底向上分析程序的自动化
第7章 设计...................................................162
7.1 简介......................................................162
7.2 LR(k)分析程序.....................................165
7.2.1 构造LR(k)状态机.....................166
7.2.2 一个LR(2)分析程序.................168
7.2.3 归约与移进操作.......................168
7.3 冲突......................................................169
7.4 例子：文法G2的冲突解析...................169
7.5 在栈中保存状态...................................171
7.6 其他LR(k)分析程序：SLR..................172
7.7 LALR(k)分析程序................................174
7.8 自底向上分析程序的实现...................175
7.9 出错恢复..............................................177
7.10 LR分析程序中的属性求值...............177
小结..............................................................178
关键术语.......................................................179
练习..............................................................180
复习小测验...................................................180
编译程序实验项目.......................................181
进一步阅读...................................................181
第8章 变换属性文法.................................182
8.1 简介......................................................182
8.2 程序的树表示......................................182
8.3 树变换文法..........................................183
8.3.1 非生成的文法...........................186
8.3.2 一个TAG例子.........................187
8.3.3 求值次序...................................188
8.3.4 信息流与存储...........................188
8.3.5 带树值的属性...........................189
8.3.6 不确定的分析...........................191
8.4 组合串文法与树文法...........................191
8.5 TAG中的类型检查..............................192
8.6 基于变换的代码优化...........................193
8.6.1 数据流分析...............................193
8.6.2 数据流分析中使用属性文法....197
8.7 中间代码树表示的替代方案...............198
8.7.1 四元式的数据流.......................199
8.7.2 循环的数据流分析...................200
8.8 实用优化变换综述...............................203
8.8.1 模拟执行优化的类别...............204
8.8.2 常量折叠分析...........................204
8.8.3 使用值编号检测公共
8.8.3 子表达式...................................208
8.8.4 左移动提升................................211
8.8.5 右移动提升...............................212
8.8.6 无用代码以及其他从右到左 的数据流分析...........................216
8.8.7 数学等式与代码选择...............216
8.8.8 循环结构分析...........................217
8.9 实现抽象语法树...................................220
8.10 实现TAG驱动的树变换....................228
小结...............................................................231
符号...............................................................232
缩略词...........................................................232
关键术语.......................................................232
练习...............................................................233
复习小测验...................................................234
编译程序实验项目........................................234
进一步阅读...................................................234
第9章 代码生成与优化.............................237
9.1 简介......................................................237
9.2 循环优化..............................................237
9.2.1 循环的范围分析.......................238
9.2.2 归纳变量...................................239
9.2.3 循环展开...................................240
9.3 寄存器与内存分配...............................241
9.3.1 寄存器分配算法.......................242
9.3.2 表达式中的寄存器分配............243
9.3.3 更好的寄存器分配数据流 分析..........................................257
9.3.4 循环的寄存器分配...................257
9.3.5 寻址模式...................................258
9.3.6 分支寻址选择...........................259
9.3.7 分支链.......................................264
9.4 代码生成的复杂性...............................265
9.4.1 指令选择...................................266
9.4.2 强度削弱...................................268
9.5 专用指令..............................................269
9.5.1 RISC和流水线处理器调度......269
9.5.2 向量处理器...............................272
9.6 代码优化的变形...................................276
9.6.1 代码优化的分类.......................276
9.6.2 窥孔优化...................................277
小结..............................................................277
缩略词...........................................................277
关键术语.......................................................278
练习..............................................................278
复习小测验...................................................279
编译程序实验项目.......................................279
进一步阅读...................................................279
第10章 非过程式语言...............................281
10.1 简介....................................................281
10.2 应用式语言的编译.............................282
10.2.1 Lisp语言的一些概念.............283
10.2.2 尾递归....................................284
10.2.3 实现一个应用式语言的编译 程序........................................285
10.3 变换属性文法的编译程序.................293
10.3.1 TAG编译程序的组成部分.....293
10.3.2 文法中的迭代运算符.............294
10.3.3 向用户报告语法错误.............295
10.3.4 自动构造扫描程序.................296
10.3.5 TAG编译程序的语法分析.....300
10.3.6 树变换....................................305
10.3.7 语法错误停机.........................307
小结..............................................................307
关键术语.......................................................308
练习..............................................................308
复习小测验...................................................309
进一步阅读...................................................309
附录A Itty Bitty Modula语法图..............311
附录B TAG编译程序的TAG.................313
附录C Itty Bitty栈机器的指令集...........335
附录D 四种计算机的代码生成表...........339
