编译原理(第2版)(Alfred V. Aho著)(2)

2012-10-20

《编译原理(第2版)》全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术，并在相关章节中给出大量的实例。

商家名称	信用等级	购买信息	订购本书
		编译原理(第2版)(Alfred V. Aho著)
		编译原理(第2版)(Alfred V. Aho著)

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章过程间分析

序言

绝大部分软件是使用高级程序设计语言来编写的。用这些语言编写的软件必须经过编译器的编译，才能转换为可以在计算机上运行的机器代码。编译器所生成代码的正确性和质量会直接影响成千上万个软件。因此，编译器构造原理和技术是计算机科学技术领域中的一个非常重要的组成部分。不仅如此，编译技术在当前已经广泛应用于编译器构造之外的其他领域，比如程序分析／验证、模型转换、语言处理等领域。因此，虽然大部分读者不会参与设计商用编译器，但拥有编译的相关知识仍然会对他们的研究开发生涯产生有益的影响。
A．V．Aho等人撰写的《Compilers：Principles，Techniques，andYools》被誉为编译教科书中的“龙书”。这说明这本书具有很高的权威性。我们有幸受机械工业出版社的委托，翻译龙书的第2版。
本书不仅包含了词法分析、语法分析、语义分析、代码生成等传统、经典的编译知识，还详细介绍了一些最新研究成果，比如过程间指针分析的最新进展。这使得本书不仅适用于编译原理的初学者，还可以作为研究人员的参考书目。本书不仅介绍编译器构造的基本原理和技术，还详细介绍一些有用的编译器构造工具，比如对Lex和Yacc的介绍使得读者可以了解这些工具的工作原理和使用方法。除此之外，读者还可以看到很多其他领域的概念在编译器构造中的应用。比如在第9章，读者可以看到群论中的抽象概念“格”被完美地应用于数据流分析算法的设计。而在第11章，线性规划和整数规划技术被成功地应用于程序并行化技术。这些内容对拓展读者的视野和思路有很大的好处。
由于本书覆盖的范围非常广，不可能在一个学期内讲完本书的全部内容。因此我建议采用本书作为本科生教材的老师只选择讲授其中的基础部分，即第1章到第9章中的大部分内容。第2章是对后面各章内容的介绍，可以在讲授相应内容之前指导学生预习。
最后感谢机械工业出版社的温莉芳女士以及姚蕾和朱劫两位编辑在本书的翻译过程中给予我们的有力帮助，也感谢其他给予我们支持的同事。由于水平有限，翻译中的错漏之处在所难免，欢迎读者批评指正。

文摘

插图：

第二个目标是编译器应该有效提高很多输入程序的性能。性能通常意味着程序执行的速度。我们也希望能够尽可能降低生成代码的大小，在嵌入式系统中更是如此。而对于移动设备的情况，尽量降低代码的能耗也是我们期待的。在通常情况下，提高执行效率的优化也能够节约能耗。除了性能，错误报告和调试等的可用性方面也是很重要的。
第三，我们需要使编译时间保持在较短的范围内，以支持快速的开发和调试周期。当机器变得越来越快，这个要求会越来越容易达到。开始时，一个程序经常在没有进行优化的情况下开发和调试。这么做不仅可以降低编译时间，更重要的是未经优化的程序比较容易调试。这是因为编译器引入的优化经常使得源代码和目标代码之间的关系变得模糊。在编译器中开启优化有时会暴露出源程序中的新问题，因此需要对经过优化的代码再次进行测试。因为可能需要额外的测试工作，有时会阻止人们在应用中使用优化技术，当应用的性能不很重要的时候更是如此。
最后，编译器是一个复杂的系统，我们必须使系统保持简单以保证编译器的设计和维护费用是可管理的。我们可以实现的优化技术有无穷多种，而创建一个正确有效的优化过程需要相当大的工作量。我们必须划分不同优化技术的优先级别，只实现那些可以对实践中遇到的源程序带来最大好处的技术。
因此，我们在研究编译器时不仅要学习如何构造一个编译器，还要学习解决复杂和开放性问题的一般方法学。在编译器开发中用到的方法涉及理论和实验。在开始的时候，我们通常根据直觉确定有哪些重要的问题并把它们明确描述出来。