编译原理
2008年12月
机械工业出版社
Alfred V. Aho,Monica S.Lam,Ravi Sethi,Jeffrey D. Ullman
631
赵建华,郑滔,戴新宇
无
绝大部分软件是使用高级程序设计语言来编写的。用这些语言编写的软件必须经过编译器的编译，才能转换为可以在计算机上运行的机器代码。编译器所生成代码的正确性和质量会直接影响成千上万个软件。因此，编译器构造原理和技术是计算机科学技术领域中的一个非常重要的组成部分。不仅如此，编译技术在当前已经广泛应用于编译器构造之外的其他领域，比如程序分析／验证、模型转换、语言处理等领域。因此，虽然大部分读者不会参与设计商用编译器，但拥有编译的相关知识仍然会对他们的研究开发生涯产生有益的影响。A．V．Aho等人撰写的《Compilers：Principles，Techniques，andYools》被誉为编译教科书中的“龙书”。这说明这本书具有很高的权威性。我们有幸受机械工业出版社的委托，翻译龙书的第2版。本书不仅包含了词法分析、语法分析、语义分析、代码生成等传统、经典的编译知识，还详细介绍了一些最新研究成果，比如过程间指针分析的最新进展。这使得本书不仅适用于编译原理的初学者，还可以作为研究人员的参考书目。本书不仅介绍编译器构造的基本原理和技术，还详细介绍一些有用的编译器构造工具，比如对Lex和Yacc的介绍使得读者可以了解这些工具的工作原理和使用方法。除此之外，读者还可以看到很多其他领域的概念在编译器构造中的应用。比如在第9章，读者可以看到群论中的抽象概念“格”被完美地应用于数据流分析算法的设计。而在第11章，线性规划和整数规划技术被成功地应用于程序并行化技术。这些内容对拓展读者的视野和思路有很大的好处。由于本书覆盖的范围非常广，不可能在一个学期内讲完本书的全部内容。因此我建议采用本书作为本科生教材的老师只选择讲授其中的基础部分，即第1章到第9章中的大部分内容。第2章是对后面各章内容的介绍，可以在讲授相应内容之前指导学生预习。最后感谢机械工业出版社的温莉芳女士以及姚蕾和朱劫两位编辑在本书的翻译过程中给予我们的有力帮助，也感谢其他给予我们支持的同事。由于水平有限，翻译中的错漏之处在所难免，欢迎读者批评指正。
本书全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术，并在相关章节中给出大量的实例。与上一版相比，本书进行了全面修订，涵盖了编译器开发方面最新进展。每章中都提供了大量的实例及参考文献。
本书是编译原理课程方面的经典教材，内容丰富，适合作为高等院校计算机及相关专业本科生及研究生的编译原理课程的教材，也是广大技术人员的极佳参考读物。
Alfred
V．Aho，美国歌伦比亚大学教授，美国国家工程院院士，ACM和IEEE会士，曾获得IEEE的冯·诺伊曼奖。著有多部算法、数据结构、编译器、数据库系统及计算机科学基础方面的著作。
出版者的话
译者序
前言
第1章 引论
1.1 语言处理器
1.2 一个编译器的结构
1.2.1 词法分析
1.2.2 语法分析
1.2.3 语义分析
1.2.4 中间代码生成
1.2.5 代码优化
1.2.6 代码生成
1.2.7 符号表管理
1.2.8 将多个步骤组合成趟
1.2.9 编译器构造工具
1.3 程序设计语言的发展历程
1.3.1 走向高级程序设计语言
1.3.2 对编译器的影响
1.3.3 1.3节的练习
1.4 构建一个编译器的相关科学
1.4.1 编译器设计和实现中的建模
1.4.2 代码优化的科学
1.5 编译技术的应用
1.5.1 高级程序设计语言的实现
1.5.2 针对计算机体系结构的优化
1.5.3 新计算机体系结构的设计
1.5.4 程序翻译
1.5.5 软件生产率工具
1.6 程序设计语言基础
1.6.1 静态和动态的区别
1.6.2 环境与状态
1.6.3 静态作用域和块结构
1.6.4 显式访问控制
1.6.5 动态作用域
1.6.6 参数传递机制
1.6.7 别名
1.6.8 1.6节的练习
1.7 第1章的总结
1.8 第1章的参考书目
第2章 一个简单的语法制导翻译器
2.1 引言
2.2 语法定义
2.2.1 文法定义
2.2.2 推导
2.2.3 语法分析树
2.2.4 二义性
2.2.5 运算符的结合性
2.2.6 运算符的优先级
2.2.7 2.2节的练习
2.3 语法制导翻译
2.3.1 后缀表示
2.3.2 综合属性
2.3.3 简单语法制导定义
2.3.4 树的遍历
2.3.5 翻译方案
2.3.6 2.3节的练习
2.4 语法分析
2.4.1 自顶向下分析方法
2.4.2 预测分析法
2.4.3 何时使用产生式
2.4.4 设计一个预测语法分析器
2.4.5 左递归
2.4.6 2.4节的练习
2.5 简单表达式的翻译器
2.5.1抽象语法和具体语法
2.5.2调整翻译方案
2.5.3非终结符号的过程
2.5.4 翻译器的简化
2.5.5 完整的程序
2.6 词法分析
2.6.1 剔除空白和注释
2.6.2 预读
2.6.3 常量
2.6.4 识别关键字和标识符
2.6.5 词法分析器
2.6.6 2.6节的练习
2.7 符号表
2.7.1 为每个作用域设置一个符号表
2.7.2 符号表的使用
2.8 中间代码生成
2.8.1 两种中间表示形式
2.8.2 语法树的构造
2.8.4 三地址码
2.8.5 2.8节的练习
2.9 第2章的总结
第3章 词法分析
3.1 词法分析器的作用
3.1.1 词法分析及解析
3.1.2 词法单元、模式、词素
3.1.3 词法单元的属性
3.1.4 词法错误
3.1.5 3.1节的练习
3.2 输入缓冲
3.2.1 缓冲区对
3.2.2 哨兵标记
3.3 词法单元的规约
3.3.1 串和语言
3.3.2 语言上的运算
3.3.3 正则表达式
3.3.4 正则定义
3.3.5 正则表达式的扩展
3.3.6 3.3节的练习
3.4 词法单元的识别
3.4.1 状态转换图
3.4.2 保留字和标识符的识别
3.4.3 完成我们的连续性例子
3.4.4 基于状态转换图的词法分析器的体系结构
3.4.5 3.4节的练习
3.5 词法分析器生成工具Lex
3.5.1 Lex的使用
3.5.2 Lex程序的结构
3.5.3 Lex中的冲突解决
3.5.4 向前看运算符
3.5.5 3.5节练习
3.6 有穷自动机
3.6.1 不确定的有穷自动机
3.6.2 转换表
3.6.3 NFA接受输入字符串
3.6.4 确定的有穷自动机
3.6.5 3.6节的练习
3.7 从正则表达式到自动机
3.7.1 从NFA到DFA的转换
3.7.2 NFA的模拟
3.7.3 NFA模拟效率
3.7.4 从正则表达式构造NFA
3.7.5 字符串处理算法的效率
3.7.6 3.7节的练习
3.8 词法分析器生成工具的设计
3.8.1 被生成的词法分析器的结构
3.8.2 基于NFA的模式匹配
3.8.3 词法分析器使用的DFA
3.8.4 实现向前看运算符
3.8.5 3.8的练习
3.9 基于DFA的模式匹配器的优化
3.9.1 NFA的重要状态
3.9.2 根据抽象语法树计算得到的函数
3.9.3 计算nullable、firstpos及lastpos
3.9.4 计算followpos
3.9.5 根据正则表达式构建DFA
3.9.6 最小化一个DFA的状态数
3.9.7 词法分析器的状态最小化
3.9.8 在DFA模拟中用时间换取空间
3.9.9 3.9节的练习
3.9.10 第3章的总结
3.11 第3章参考文献
第4章 语法分析
4.1 引论
4.1.1 语法分析器的角色
4.1.2 代表性的文法
4.1.3 语法错误的处理
4.1.4 错误恢复策略
4.2 上下文无关文法
4.2.1 上下文无关文法的正式定义
4.2.2 符号表示的惯例
4.2.3 推导
4.2.4 语法分析树和推导
4.2.5 二义性
4.2.6 验证文法生成的语言
4.2.7上下文无关文法和正则表达式
4.2.8 4.2节的练习
4.3 设计文法
4.3.1 词法分析和语法分析
4.3.2 消除二义性
4.3.3 左递归的消除
4.3.4 提取左公因子
4.3.5 非上下文无关的语言构造
4.3.6 4.3节的练习
4.4 自顶向下的语法分析
4.4.1 递归下降的语法分析
4.4.2 FIRST和FOLLOW
4.4.3 LL(1)文法
4.4.4 非递归的预测分析
4.4.5 预测分析中的错误恢复
4.4.6 4.4节的练习
4.5 自底向上的语法分析
4.5.1 归约
4.5.2 句柄剪枝
4.5.3 移入-归约语法分析技术
4.5.4 移入-归约语法分析中的冲突
4.5.5 4.5节的练习
4.6 LR语法分析技术介绍：简单LR技术
4.6.1 为什么使用LR语法分析器？
4.6.2 项和LR(0)自动机
4.6.3 LR-语法分析算法
4.6.4 构造SLR-分析表
4.6.5 可行前缀
4.6.6 4.6节的练习
4.7 更强大的LR语法分析器
4.7.1 规范LR(1)项
4.7.2 构造LR(1)项集
4.7.3 规范LR(1)分析表
4.7.4 构造LALR语法分析表
4.7.5 LALR语法分析表的高效构造方法
4.7.6 LR语法分析表的压缩
4.7.7 4.7节的练习
4.8 使用二义性文法
4.8.1 用优先级和结合性解决冲突
4.8.2 “悬空-else”二义性
4.8.3 LR语法分析中的错误恢复
4.8.4 4.8节的练习
4.9 语法分析器的生成工具
4.9.1 语法分析器的生成工具Yacc
4.9.2 使用Yacc处理二义性文法
4.9.3 用Lex创建Yacc的词法分析器
4.9.4 Yacc中的错误恢复
4.9.5 4.9节的练习
4.10：第4章的小结
4.11 第4章的参考文献
第5章 语法制导的翻译
5.1 语法制导定义
5.1.1 继承属性和综合属性
5.1.2 在一棵语法分析树的结点上对一个SDD求值
5.1.3 5.1节的练习
5.2 SDD的求值顺序
5.2.1 依赖图
5.2.2 属性求值的顺序
5.2.3 S-属性定义
5.2.4 L-属性定义
5.2.5 具有受控副作用的语义规则
5.2.6 5.2节的练习
5.3 语法制导翻译的应用
5.3.1 抽象语法树的构造
5.3.2 类型的结构
5.3.3 5.3节的练习
5.4 语法制导的翻译方案
5.4.1 后缀翻译方案
5.4.2 后缀SDT的语法分析栈实现
5.4.3 产生式内部带有语义动作的SDT
5.4.4 从SDT中消除左递归
5.4.5 L-属性定义的SDT
5.4.6 5.4节的练习
5.5 实现L-属性的SDD
5.5.1 在递归下降语法分析过程中进行翻译
5.5.2 边扫描边生成代码
5.5.3 L-属性的SDD和LL语法分析
5.5.4 L-属性的SDD的自底向上语法分析
5.5.5 5.5节的练习
5.6 第5章的总结
5.7 第5章的参考文献
第6章 中间代码生成
第7章 运行时刻环境
第7章 总结
第8章 代码生成
第9章 机器无关优化
第10章 指令级并行
第11章 并行性和局部性的优化
第12章 过程间分析
插图：第二个目标是编译器应该有效提高很多输入程序的性能。性能通常意味着程序执行的速度。我们也希望能够尽可能降低生成代码的大小，在嵌入式系统中更是如此。而对于移动设备的情况，尽量降低代码的能耗也是我们期待的。在通常情况下，提高执行效率的优化也能够节约能耗。除了性能，错误报告和调试等的可用性方面也是很重要的。第三，我们需要使编译时间保持在较短的范围内，以支持快速的开发和调试周期。当机器变得越来越快，这个要求会越来越容易达到。开始时，一个程序经常在没有进行优化的情况下开发和调试。这么做不仅可以降低编译时间，更重要的是未经优化的程序比较容易调试。这是因为编译器引入的优化经常使得源代码和目标代码之间的关系变得模糊。在编译器中开启优化有时会暴露出源程序中的新问题，因此需要对经过优化的代码再次进行测试。因为可能需要额外的测试工作，有时会阻止人们在应用中使用优化技术，当应用的性能不很重要的时候更是如此。最后，编译器是一个复杂的系统，我们必须使系统保持简单以保证编译器的设计和维护费用是可管理的。我们可以实现的优化技术有无穷多种，而创建一个正确有效的优化过程需要相当大的工作量。我们必须划分不同优化技术的优先级别，只实现那些可以对实践中遇到的源程序带来最大好处的技术。因此，我们在研究编译器时不仅要学习如何构造一个编译器，还要学习解决复杂和开放性问题的一般方法学。在编译器开发中用到的方法涉及理论和实验。在开始的时候，我们通常根据直觉确定有哪些重要的问题并把它们明确描述出来。
《编译原理(第2版)》是编译领域无可替代的经典著作，被广大计算机专业人士誉为"龙书"。《编译原理(第2版)》上一版自1986年出版以来，被世界各地的著名高等院校和研究机构（包括美国哥伦比亚大学、斯坦福大学、哈佛大学、普林斯顿大学、贝尔实验室）作为本科生和研究生的编译原理课程的教材。该书对我国高等计算机教育领域也产生了重大影响。编译领域里程碑式的经典著作——龙书，20年后终于出版新版！这是一个延绵30年的故事，这是一部关于龙书的传奇！最新版本，增添两章节内容，使龙书地位更权威！第2版对每一章都进行了全面的修订，以反映自上一版出版20多年来软件工程。程序设计语言和计算机体系结构方面的发展对编译技术的影响。《编译原理(第2版)》全面介绍了编译器的设计，并强调编译技术在软件设计和开发中的广泛应用。每章中都包含大量的习题和丰富的参考文献。1977年，AlfredV.Aho和JeffreyD.Ullman合作出版了《PrincipiesofCompiletDesign》，封面是一位骑士和一只恐龙，那恐龙是绿色的，因此被称为龙书或绿龙书。1986年，原来的两位作者加上RaviSethi，升级了前一《编译原理(第2版)》，书名改为《compiIers：Principles，TechniquesandTools》，封面依然沿用骑士和恐龙，那恐龙是红色的，因此被称为龙书二或者红龙书。又过了一个9年又一个9年，编译领域的巨无霸——龙书始终都没有升级。终于在2006年底，龙书升级了。作者又增加了MonicaS.Lam，名字与龙书二相同，封面依然沿用恐龙和武士的设计，这次的龙是紫色的，因此被称为龙书三或者紫龙书。
无
编译原理龙书，最经典的编译教材，大学计算机必备
这本书对于了解计算机的底层编译机制有很大的帮助，不愧被称为 龙书
编译原理（第2版） 名副其实的龙书，非常好，可惜还是有点贵，但非常值...
编译是计算机技术中最先进功能展现的领域,因为每个硬件和底层原理细节都能体现,即使是一个简单的解释语言也一样,以前看起来模模糊糊,一知半解,现在重新学习,觉得似乎很多东西能通用,不止是计算机技术,可以应用到很多其他方面,尤其是搞软件开发设计的人来说,更有用,觉得其实用价值超过设计模式
看过这书的第一版，出了第二版，还是忍不住买来看看。书后面的附录A，有个完整的编译器前段的Java的源代码，让我想起大学时的编译原理课程作业。如果当时就有这本书看，该多好啊
不愧是龙书，名不虚传。内容写得很详细，不过编译原理不是那么好懂，真的需要好大的勇气去啃下它
编译界的龙书
编译原理（第2版）——计算机科学丛书
不愧为龙书，讲的非常透彻。
最后还附有前端编译器的代码，非常不错的一本书~
如果作为一名计算机专业的人没有读过龙书，让别人听来就会不可思议了，读下龙书吧，他会把你引入一个你从未见过的奇妙的计算机的知识海洋里
恩，这本书是世界编译学科不可动摇的龙头老大啊有木有，所以说嘛，就叫龙叔啊，学编译当然就买这本了！
龙书没得说，值得收藏的计算机书籍
非常适合初学者的理论书，基本上给读者建立一个完善的编译原理架构。看完这本书后，可以看虎书和鲸书，这两本书相当具体和实用
关于这本书的内容，不用我多说，凡是想学好编译原理的，怎可能放过这本书！关于这本书，我收到书时，有一角小小破损（不影响学习），其他都很好。
经典的编译原理的书，收藏了。
编译原理》的组织注重提炼精华、循序渐进、深入浅出，每章开头提炼了该章涉及的主要内容、要点和关键概念，全书精编、精选了近300道各种类型的习题和思考题，还提供了编译程序实现的具体实例，能够辅助读者更好地学习和掌握编译原理。
龙书实在不易看明白，一到词法分析后面又卡壳了。
这本书确实很经典，毕竟是龙书，非常期待读透这本书
龙书，经典教程，不再多解释
经典龙书，值得推荐，回来好好看看那
国内的编译原理书让人越看越糊涂，想学编译原理就看这本，国内的千万别看，包括什么陈火旺的书，浪费很多时间，走很长的弯路。
这本“龙书”真是经典中的经典，不读会后悔。
经典龙书。不错的书。 值得一看。
龙书，或许经典，但要慢慢品味吧。
讲得很深不愧为龙书赞一个
龙书不解释，能力值低看不懂~
编译原理中的老大。研究生必读经典
龙书拜读中。
编译界的佼佼者，计算机学生的必读之物。
这本书的英文原版我读过，这次读了一下中文翻译版，感觉整体上翻译的很不错，原书的面貌基本上表达出来了。书的质量很好，包装得很严实，能读到这样的书我非常高兴
龙书当之无愧
还没细看，但是龙书铺天盖地的好评毋庸置疑，不过其他2本 虎书 鲸书希望也能买来学习下
不愧为龙书，书有点难，读下去需要毅力。
真的不愧是龙书，讲的详细值得反复阅读！
编译原理配合操作系统，再去理解C语言，很不错
内容很充实，很全面，可以很好的了解编译原理，强烈推荐
这本书对编译原理讲得非常全面，也有一定深度，值得反复阅读多次，相信你每读一次，都会有新的收获
编译原理中不可替代的经典之作可惜纸张差了点
编译原理难学，这本书深入浅出还有很多例子，适合学习
与《java编程思想》和《算法导论》还有《数据库系统概念》一起买的，都是非常经典的图书，适合所有喜爱编程同仁们
这学期学编译原理，听同学说这本书不错，买来学习学习，质量很好！
编译原理 这本书相当不错，就是价格太贵啊！
编译原理权威，最棒一本编译
编译原理内容博大精深！只能慢慢看！要仔细研读！
内容不错，值得拜读，对学习编译原理很有帮助
详细介绍了编译的原理，很好，但大部分人都不需要掌握这些知识
编译之中的经典之作，值得一读。我买来做教材用
学编译原理不看这个真没法学了
非常好的讲解编译原理的书籍
可以深研编译原理，也可以作为手册了解编译的一些知识，对程序员来说值得一读
好东西！学学编译方面的内容
正在读，编译方面的必读书籍，感觉还不错。
这本书是编译圣经~
编程那么久了，才知道编译是这么会儿事
强烈推荐有一定的算法基础的人学习！！书中内容过于深刻，不适合初学者！！
退订教材，直接在这买了这本，比较经典的
个人品味吧，书的封面太薄...
这本是Java版本，且在很多方面有新的突破，我们国内各大计算机牛校第一个参考的好书，值得拥有！
经典不衰的好书，多年以后仍不失光彩，计算机软件工作者提升功力必备
计算机经典图书，不解释
不是计算机专业的人，读来了解了解，扩展知识面，对编程中遇到的部分问题会有比较好的理解
精典吧。只能这样说。学计算机的都应该有这本书。
虽然你可能在平时工作中用不到。但真的对编程很有帮助。
能体现一个人的计算机功力。
对于理解计算机系统有一定帮助，是计算机学习者必备的一本书
作为计算机学习不可或缺的经典读物
对于想巩固计算机基础的人来说决对是一本好书，里面的很多知识对于理解计算机语言是十分有帮助。
很值得细读，精读，研读！是精品中的精品，如果对编译器没有深入理解欲望的还是绕行比较好！
书是经典，很好！早想入手，一直没货。这次看到立刻下单
计算机科学丛书
教材参考书，枯燥，理论化。但无愧于经典，有好的语言基础就看原版。
技术书籍翻译过来，翻译者的翻译水平再高，终归不如第一手的资料。
一个字，强！书很好，经典！
对这本书早有耳闻，讲得很好，虽然讲的内容不能派上直接的用场，但是看书的过程中会明白很多东西，有助于提升自己的水平，讲得不是很容易，但是很到位，不错！
书很厚，内容非常丰富，适合学习。
很好的书,看了前面两章已经很有感受.
经典的书，买来不看，收藏也不错。
很经典的书，买了不亏
经典的书，要认真的看哪！
计算机朋友的福音，好好学习
不学计算机的看的话估计没什么意思。。。
之前在学校图书馆看过部分旧版的，里面的知识点和经验总结什么的很受用，这次买回来准备继续读完。
书的内容讲的很详细，适合出初学者
是需要买的教材，书的质量很不错，就是运来的速度有点慢
很专业，虽然是有点深，但是想学的好，必须看这些书的
昨天上午订的，今天中午就到了，书的质量还好！我在当当买过两次书了，都还不错！不知道有出现收获迟的友人是什么问题！感觉当当的包装不错，比较喜欢那个袋子嘿嘿！
很不错的书，翻译的也还行
书不错，就是习题没答案。
至少掌握两门以上的高级编程语言，还要看看数据结构，才能看此书
不错的书，推荐大家都学习学习
送货速度还可以，书的质量非常棒，希望其他图书也能是这种正版的质量
讲原理层的东西，大家写的评论都基本上评到很多方面了，
想速成看这个不大适合，想研究倒是本不错的书籍。
书不错，包装很好，有书香！内容还没看，应该不错
书刚收到，还没来得及仔细看看，翻了翻，内容应该还不错，只是纸张有点薄，价格有点小贵，其他都挺好。
书很不错 有待研究
看了一点点，书是很好，不过我一点基础都没，还是等我把基础学了再来看！
一本很不错的书，就是不太看的懂，悲剧
书挺不错的，只不过到现在还没怎么看，没时间啊。
书很好还没看看过之后再来评论
对于这样的书，已经不需要任何好评来支撑门面了。好评是对书的质量的，挺好的。
书不错我喜欢 就是等了好多天
书质量还行。但是每次填写的是货到付款pos刷卡。到货是都不能刷卡。很是郁闷。
发货的速度挺快的，书质量也不错
不错，书是全新的，快递速度很快，