计算机科学丛书 第2版 编译原理 (美) Alfred V.Aho Monica s.Lam Ravi Sethi Jeffrey D.Ullman 赵建华郑滔戴新宇 哥伦比亚大学 斯坦福大学 Avaya实验室 斯坦福大学 著 南京大学 译 Compilers Principles,Techniques,tools Second Edition Alfred V.Aho Monica S. Lam Ravi Sethi Jeffrey D.ullman Compilers Principles, Techniques and Tools Second Edition 机械工业出版社 111 China Machine Press
前言 从本书的1986版出版到现在，编译器设计领域已经发生了很大的改变。随着程序设计语言 的发展，提出了新的编译问题。计算机体系结构提供了多种多样的资源，而编译器设计者必须能 够充分利用这些资源。最有意思的事情可能是，古老的代码优化技术已经在编译器之外找到了 新的应用。现在，有些工具利用这些技术来寻找软件中的缺陷，以及（最重要的是）寻找现有代 码中的安全漏洞。而且，很多“前端”技术一文法、正则表达式、语法分析器以及语法制导翻泽 器等 一仍然被广泛应用。 因此，本书先前的版本所体现的我们的价值观一直没有改变。我们知道，只有很少的读者将 会去构建甚至维护一个主流程序设计语言的编译器。但是，和编译器相关的模型、理论和算法可 以被应用到软件设计和开发中出现的各种各样的问题上。因此，我们会关注那些在设计一个语 言处理器时常常会碰到的问题，而不考虑具体的源语言和目标机器究竟是什么。 使用本书 要学完本书的全部或大部分内容至少需要两个学季(quarter),甚至两个学期(semester) 通常会在一门本科课程中讲授本书的前半部分内容；而本书的后半部分（强调代码优化）会在研 究生层面或另一门小范围的课程中讲授。下面是各章的概要介绍： 。第1章给出一些关于学习动机的资料，同时也将给出一些关于计算机体系结构和程序设 计语言原则的背景知识。 ·第2章会开发一个小型的编译器，并介绍很多重要概念。这些概念将在后面的各章中深 人介绍。这个编译器本身将在附录中给出。 ·第3章将讨论词法分析、正则表达式、有穷状态自动机和词法分析器的生成器工具。这 些内容是各种文本处理的基础。 。第4章将讨论主流的语法分析方法，包括自顶向下方法（递归下降法、山技术）和自底向 上方法(LR技术和它的变体)。 ·第5章将介绍语法制导定义和语法制导翻译的基本思想 ·第6章将使用第5章中的理论，并说明如何使用这些理论为一个典型的程序设计语言生 成中间代码。 ·第7章将讨论运行时刻环境，特别是运行时刻栈的管理和垃圾回收机制 。第8章将主要讨论目标代码生成技术。该章会讨论基本块的构造，从表达式和基本块生 成代码的方法，以及寄存架分配技术 。第9章将介绍代码优化技术，包括流图、数据流分析框架以及求解这些框架的选代算法。 美国大学的学制大致可以分为两种：9aer(学季)和c er(学期)。前者是把一年分为4个qu山世，每个gu证 :3个月，原则上是上3个quarter修一个9ua:的限：面后者则类似我国国内的寒特般制的大学学制，大极4个 月一个semester。 编辑注
。第0章将讨论指令级优化。该章的重点是从小段指令代码中抽取并行性，并在那些可以 同时做多件事情的单处理器上调度这些指令。 。第11章将介绍大规模并行性的检测和利用。这里的重点是数值计算代码。这些代码具有 对多维数组进行遍历的紧致循环。 ·第12章将介绍过程间分析技术。它将讨论指针分析、别名和数据流分析。这些分析都考 虑了到达代码中某个给定点时的过程调用序列。 哥伦比亚大学、哈佛大学、斯坦福大学已经开设了讲授本书内容的课程。哥伦比亚大学定期 开设一门关于程序设计语言和醒译器的课程，使用了本书前8章的内容。该课程常年面向高年级 本科生/一年级研究生讲授，这门课程的亮点是 一个长达一个学期的课程实践项目。在该项目 中，学生分成小组，创建并实现一个他们自己设计的小型语言。学生创建的语言涉及多个应用领 域，包括量子计算、音乐合成、计算机图形学、游戏、矩阵运算和很多其他领域。在构建他们自 己的编译器时，学生们使用了很多种可以生成编译器组件的工具，比如ANTLR、Lx和Ya©；他 们还使用了第2章和第5章中讨论的语法制导翻译技术。后续的研究生课程的重点是本书第9 章到第12章的内容，着重强调适用于当代计算机（包括网络处理器和多处理器体系结构）的代码 生成和优化技术。 断相福大学开设了一门历时一个学季的人门梁程，大致涵盖了本书第】章到第8章的内容 同时还会简介本书第9章中全局代码优化的相关内容。第二门编译器课程包括本书第9章到第 12章的内容，另外还包括第7章中更为深人的有关垃圾收集的内容。学生使用一个该校开发的 基于Java的系统Joeg来实现数据流分析算法。 预备知识 学习本书的读者应该拥有一些“计算机科学的综合知识”，至少学过两门程序设计课程，以 及数据结构和离数学的课程。具备多种程序设计语言的知识对学习本书会有所帮助 练习 本书包含内容广泛的练习，几乎每一节都有一些练习。我们用感叹号来表示较难的练习或 练习中的一部分。难度最大的练习有两个感叹号。 万维网上的支持 在本书的主页(htp:/dragonbook.stanford.edu)e上可以找到本书已知错误的勘误表以及一 些支持性资料。我们希望将我们讲授的每一门与编译器相关的课程的可用讲义（包括家庭作 业、答案和练习等)都提供出来。我们也计划公布由一些重要编译器的作者撰写的关于这些编 译器的描述。 致谢 本书封面由Strange Tonic Productions的S.D.Ullman设计。 Jon Bentley针对本书的初稿中的多章内容与我们进行了广泛深人的讨论。我们收到了来 自下列人员的有帮助的评价和勘误：Domenico Bianculli,Peter Bosch、Marcio Buss、Marc Eaddy、 读者可以从hp:/idb.sand.ed~namn/ema.hm找到本书的粉误表，并可以从p:/n d.edu/~ullman/dragon.iml处找到本书的一些支持资料
Stephen Edwards、Vibhav Garg、Kim Hazelwood、Gaurav Ke、Wcii、Mike Smith、Art Stamness、Krys ta Svore、Olivier Tardieu和Jia Zeng。我们衷心感谢这些人的帮助。当然，书中还可能有错漏之 处，希望得到指正和反馈。 另外，Monica希望能够向她在SUF编译器团队的同事表示感谢，感谢他们在18年的时间里 给予她的支持和帮助，他们是：Gerald Aigner、Dzintars Avots、Saman Amarasinghe、Jennifer Ander- son、Michael Carbin、Gerald Cheong、Amer Diwan、.Robert French、Anwar Chuloum、Mary Hall、John Hennessy、David Heine、Shih-Wei Liao、Amy Lim、Benjamin Livshits、Michael Martin、Dror Maydan、 Todd Mowry、Brian Murphy、Jeffrey Oplinger、Karen Pieper、Martin Rinard、Olatunji Ruwase、Constan- tine Sapuntzakis、Patrick Sathyanathan、Michael Smith、Steven Tjiang、Chau-Wen Tseng、Christopher Unkel、John Whaley、Robert Wilson、Christopher Wilson和Michael Wolf。 A.V.A.Chatham NI M.S.L,Menlo Park CA R.S.,Far Hills NJ J.D.U.,Stanford CA 2006年6月
目录 出版者的话 1.6.6参数传递机制……20 译者序 16.7别名…21 前言 1.6.81.6节的练习…22 第1章 1.7第1章总结…22 引论 1.8第1章参考文献 1.1语言处理器……1 第2章一个简单的语法制导翻译器…24 1.2一个编译摆的结地。2 2.1引宫…24 1.21词法分析… ，3 2.2语法定义…25 1.22语法分析 2.2.1文法定义…26 1.2.3语义分析…5 22.2推导27 1.2.4中间代码生成*5 2.2.3语法分析树 …28 1.2.5代码优化…5 2.2.4二义性*…29 12.6代码生成 6 22.5运算符的结合性 ,.429 1.2.7符号表管理…6 22.6 运算符的优先级 30 1.2.8将多个步骤组合成…6 2.2.722节的练习…31 1.2.9编译器构造工具 …7 23语法制导翻译… …32 1,3程序设计语言的发展历程…7 23.1后搬表示 …33 1.3.】走向高级程序设计语言 7 23.2综合配性………33 1.3.2对编译器的影响+…8 2.3.3简单语法导定义…35 1.3.31.3节的练月 2.3.4树的遍历 …35 1.4构建一个编译器的相关科学 …8 2.3.5翻译方案** 35 1.4.1编译器设计和实现中的建模 9 2.3.62.3节的练习… 1.4.2代码优化的科学…9 24语法分析… 1.5编译技术的应用… 2.4.1自顶向下分析方法 38 1.5.1高级程序设计语言的实现……·0 24.2预测分析法 1.5.2针对计算机体系结构的优化 …11 2.4.3何时使用e产生式…4 1.5.3新计算机体系结构的设计…12 2.4.4设计一个预测分析器…·4 1.5.4程序翻译…13 2.4.5左递归 1.5.5软件生产率工具 14 2462.4节的练习…2 1.6程序设计语言基础…15 2.5简单表达式的翻译器… 1.6.静态和动态的区别 15 2.5.1抽象语法和具体语法 43 1.6.2环境与状态：/5 2.52调整翻译方案… 3 1.6.3静态作用城和块结构…7 25.3非终结符号的过程 1.6.4显式访问控制+**： 2.5.4翻译器的简化· …45 16.5动态作用域*…19 2.5.5完整的程序……4…46