计算机科学丛书 第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
2.6词法分析 47 3.5词法分析器生成工具…89 2.6.1别除空白和注释 3.5.1Lcx的体用： 26.2预读………… 48 3.5.2Lex程序的结构 89 26.3 常量 35.3 Lx中的冲突解决 2.6.4识别关排字知标识符 40 3.5,4向前署云 2.6.5词法分析器 50 3.5.53.5节的练习 92 2.6.62,6节的练习 3.6有穷自动机 2.7符县表. 53 3.6.1 不确定的有穷自动机… 93 27,1为每个作用域设置一个符号表 3.6.2 转换表 2.7,2符号表的使用 56 3.6.3 自动机中输入字符串的接受… 28生成中间代码 57 36.4确定的有穷自动机… .95 2.8.1两种中间表示形式 365 3.6节的练习 96 2.8.2语法树的构港 3.7从正则表达式到自动机…… 96 2.8.3静态检杏· 61 3.7.1 从NFA到DFA的转换 96 2.8.4 三地址码 62 3.1.2 NFA的模拟 9 2.8.52.8节的练习 66 3.7.3 NFA模拟的效率 99 2.9第2章总结 66 3.7,4从正则表达式构造NFA 100 第3章 词法分析… 3.7.5 字符串处理算法的效率 105 3.1词法分析器的作用 68 3.7.63.7节的练习 105 3.1.1词法分析及语法分 3.8词法分析器生成工具的设计 3.1.2词法单元、模式和词素 3.81生成的词法分析器的结构… 109 3.1.3词法单元的属性 70 3.82 基于NFA的模式匹配： 106 3.1.4词法错误 383 词法分析器使用的DFA 107 3.1.53.1节的练习… 71 3.8.4 实现向前看运算符 108 3.2输人缓冲… 71 3.8.53.8节的练习 100 3.2.1缓冲区对 72 3.9 基于DFA的模式匹配器的优化 109 3.2.2哨兵标记… 72 3.9.1 NFA的重要状态+…+… 109 3.3词法单元的规约 72 3.9.2 根据抽象语法树计算得到的 33.1 申和语言 74 函数 110 3.3.2语言上的运算 75 3.9.3 i计算nullable、6 rstpos及 3.3.3正则表达式 75 11 3.3. 正则定义 77 394 计算f6 lowpos 112 3.3.5正则表达式的扩展 78 3.9.5 根据正则表达式构建DFA 113 3.3.63.3节的练习 78 3.9.6 最小化一个DFA的状态数 114 3.4词法单元的识别 80 3.9.7 词法分析器的状态最小化 3.4.】状态转换图 3.9.8DFA模拟中的时间和空间权·116 3.4.2 保留字和标识符的识别 3.9.93.9节的练习 117 3.4.3完成我们的例子 3.10第3章总结 118 3.4.4 基于状态转换图的词法分析器的 3.11第3章参考文献 体系结构 84 第4章 语法分析 12 3.4.53.4节的练习 486 4.1引论… …121
X 4.1.1语法分析架的作用+…2】 4.6.5可行前级…163 4.1.2代表性的文法…122 4.6.64.6节的练习…… ...。164 4.1.3语法错误的处理 4.7 更强大的R语法分析器 165 4,1,4错误恢复策略 123 4.7.1规范R(1）项： 165 4,2上下文无关文法 124 4.7.2构造LR(1)项集… 166 4.2.1上下文无关文法的正式定义 125 4.7.3规范1R(1)语法分析表 4.2.2符号表示的约定…… 125 4.7.4构造LALR语法分析表… 170 423 推导 126 4.7.5 高效构造LALR语法分析表 4.2.4 语法分析树和推导… 127 的方法* 4.2.5 二义性 128 4.7.6LR语法分析表的压缩… 176 4.2.6脸证文法生成的语言 129 4.7.74.7节的练 4.2.7上下文无美文法和正则 4,8使用二义性文法…… 178 表达式… .130 4.8.】用优先级和结合性解决冲突· 178 4.2.84.2节的练习 130 4.8.2“悬空eds”的二义性 4.3设计文法 32 4.8.3LR语法分析中的错误恢复 18 4.3.1词法分析和语法分析 132 8.44.8节的练习… 182 4.3.2 消除二义性+ 13 49 语法分析器生成工具 183 4.3.3左洋归的消除 134 4.9.】语法分折墨生成工具Yace 183 4.3.4 提取左公因子 4.9.2使用带有二义性文法的Yac 4.3.5非上下文无关语言的构造 136 规约 185 4.3.64.3节的练习 4.9.3用Ix创建Yace的词法 4.4自顶向下的语法分析 137 分析器 187 4,4,】递归下降的语法分析 139 4,9.4Yace中的错误恢复 4.42 RST和FOL10W 4.9.54.9节的练习…… 189 44.3 (1)文法 141 4.10 第4章总结 44.4非祥日的而测分折· 144 4.11第4意参考文献 4.4.5预测分析中的错误恢复 第5章 语法制导的翻译 194 4.4.64.4节的练习 14 5.1语法制导定义· 194 4.5自底向上的语法分析 148 5.1.】推承鼠性和综合属性 195 4.5.1 归约 5.1.2在语法分析树的结点上对 4.5.2 句柄剪枝 149 SDD求值： 196 4.5.3移入-自约语法分析技术 150 5.1.35.1节的套习 198 4.5.4移入-归约语法分析中的 5.2SDD的求值顺序 /9g 5.2.】依赖图* 198 4.5.54.5节的练习… 152 5.2.2属性求值的顺序 199 4.6 LR语法分析技术介绍：简单LR 5.2.3S属性的定义 20 技术· 153 5.2.4L属性的定义+++… 200 4.6.1为什么使用LR语法分析器 153 5.25具有受控副作用的语义规则…201 4.6.2项和1R(0)自动机 5.2.65.2节的练习 202 4.6.3LR语法分折算法… 158 53语法制导翻译的应用… 203 4.6.4构造SR语法分析表 16 5.3.1抽象语法树的构造 203
5.3.2类型的结构 ...206 6.4.1 表达式中的运算 243 5.3.35.3节的练习 20 6.4.2增量回择… 244 5.4语法制导的翻译方案 207 6.43数组元套的寻址 245 5.4.1后银翻译方案 207 6.4.4 数组引用的翻译 246 5.4.2后缀SDT的语法分析栈实现 .208 6.4.56.4节的练习 247 5.4.3产生式内部措有语义动作 6.5举则待 248 的SDT 209 6.5.1类型检查规则 246 5.4.4从SDT中消除左递归 210 6.5.2 卷别转输 249 5.4.5L属性宗义的SDT 212 6.53 函数和运算符的重载 250 5.4.65.4节的练习 216 65.4 类型推导和多态函覺 251 5.5实现L屋性的SDD 216 6.5.5一个合一算法· 254 5.5.1在递归下降语法分析过程中 6.5.66.5节的练习 250 进行翻译 21 6.6控制流 256 5.52边扫描边华成代码 219 6.6.】布尔表达式 257 5,5,3L属性的SDD和山语法 66.2短路代码 257 分析 220 6.6.3控制流语句…… 257 5.5.4L属性的SDD的自底向上语法 66.4布尔表达式的控制流翻译 .259 分析 22 665 避免生成冗余的o指令 26 5.5.55.5节的练习 226 6.6.6布织有和转代码 262 5.6第5意总结… 227 6.6.76.6节的练习 26 5.7第5章套考文献 228 6. 回填 26E 第6章中问代码生成 229 6.7.1使用回填技术的一销式目标 6.1语法树的变体， 230 代码生虚 263 6.1.1 表达式的有向无环图 230 67.2 布尔表达式的回填 26 6.1.2构造DAG的值编码方法 231 6.7.3控制转移语句 266 6136】节的练习 232 67.4 break语句、continue语句和 62 三地址代码 233 00语句· 26 6.21地址知指今 23 6.7.56.7节的练习 ,268 622四元式表示 235 6.8 switch语句 269 6.2.3 三元式表示· 233 6.8.1 switch语句的翻译 …269 6.2.4静态单赋值形式 237 6.8.2 switch语句的语法制导等译·270 6.256.2节的练习 237 6.8.36.8节的练习 27 6.3类型和声明… 237 6.9过程的中问代码……… ·271 63.1类彩表法式 238 6.10第6章总结 272 632 类型等价 239 6.11第6章参考文 273 63.3声明 239 第7章 运行时肉环持 275 6.3.4局部变量名的存储布局 239 71 存储组织… 273 63.5 声明的序列· …24 7.2 空间的栈式分配· …276 6.3.6记录和类中的字段 242 7.2.1活动树 ,277 6.3.76.3节的练习 241 7.2.2活动记录 279 64表达式的翻泽… 243 7.23调用代码序列 280
XⅫ 7.2.4栈中的变长数据…282 781并行知并发垃极同收，39 7.2.57.2节的练习…283 7.8.2部分对象重新定位 …321 ?,3栈中非局部数据的访问 2 7.8.3类型不安全的语言的保守垃圾 7.3.1没有嵌套过程时的数据访问 .321 7.3.2和嵌套过程相关的问题 28 7.8.4 弱引用 322 7.3.3 一个支持嵌套过程声明的 7.8.57.8节的练习…. 322 285 7.9第7资总结… 322 7.3.4 嵌套深度 285 7.10 第7章参考文制 324 7.3.5访间链*… 286 篇8章 代码生成 326 7.3.6处理访链 287 8.1代码生成器设计中的问题 27 7.3.7 过程型参数的访问链 8.1,1 代码生成器的输人 327 7.3.8见示大…4… 289 8.1.2目标程序… 327 7.3.97.3节的练习 290 81.3 指令选择 328 7.4堆管理 29 8.1.4寄存得分配+…………… 329 741存储答理到 291 8.1.5求值题序 330 14.2 一台计算机的存储层次结构 292 8.2目标语言 330 7,4.3程序中的局部性… 293 8.21 个简单的日标机模型 330 7.4.4碎片整理… 205 8.2.2 程序和指令的代价 332 7.4.5 人工回收请球 297 &2.3 8.2节的练习 33 7.4.67.4节的练习 299 8.3目标代码中的地址… 334 7.5垃圾回收概述… 200 8.3.1 静态分配… 334 7.5. 垃圾回收器的设计目标 299 83.2 分配 335 7,5.2可达性 30 8.3.3名字的运行时刻地址 337 7.5.3引用计数垃圾回收器 302 83.483节的练习 7.5.47.5节的练习 8.4基本块和流图… 338 7.6基于跟踪的回收的介绍 304 8.4.】基本块 39 7.6】基本的标记-清扫式回收器 &42 后续使用信息 340 7.6.2 基本轴象4 30 8.4.3 340 7.6.3标记-清扫式算法的优化 306 8.4.4流图的表示方式…。 341 7.6.4标记并压缩的垃圾回收器 307 84.5 循环 341 7.6.5拷贝回收器… 309 8.4.68.4节的练习… 342 7.6.6开销的比较… 8.5基本块的优化 342 7.6.77.6节的练习 31 8.51 基本块的DAG表示· 7.7灯停顿垃圾回收……。 31 8.5.2 寻找局部公共子表达式+ 343 7.7.1增量式垃圾回收… 312 85.3 消除死代码 344 1.1.2 增量式可达性分析 8.5.4 代数恒等式的使用 344 7.7.3部问的求 314 855 数组引用的表示 3d5 72.7.4世代垃圾回收 8.5.6 指针赋值和过程调用 346 7.7.5列车算法* 316 8.5.7从DAG到基本块的南组 347 7.7.67.7节的练习· 21R 8.5.88.5节的练习… 4.348 7.8 垃圾回收中的高级论题 319 8.6 个单的代码生成器 348
8.6,】寄存器和地址描述符 .340 9.1.1元余的原因 …374 8.6.2代码生成算法+ 9.1.2 …个贯穿本章的例子：快速 86.3函数gctReg的设H 352 非家，， .....75 8.6.48.6节的练习 9.1.3 保持语义不变的转 37 8.7宽孔优化… 35 9.1.4全局公共子表达式 377 87.】消除元余的加2和保存指今353 9.15复制传播… 8.7.2消除不可达代 354 9.1.6 死代码消除 379 8.7.3控制流优化… 354 9.1.7代码移动… 379 8.7.4代数化简和强度消减 9.1.8归纳变量和强度消减… 20 8.7.5 使用机器特有的指 355 9.1.9 9.1节的练习 38 8.7.68.7节的练习… 355 9.2数据流分析简介 382 8,8寄存器分配和指派… 44355 9.2.】数据流抽象 382 8.81全局寄存器分配… 35d 92.2 数据流分析模式· 38 8.8.2使用计数+ 356 9.2.3基本块上的数据流模式 384 8.8.3外层循环的寄存器指派 ..358 924 到达定值… 385 8.8.4 通过图着色方法进行寄存器 9.2.5 话跃变量分析 390 358 9.2.6可用表达式… 391 8.8.588节的练习 4,350 027 小结 303 8.9通过树重写来选择指令 359 9.2.89.2节的练习 394 8.9.1树翻译方案… 359 9.3数据流分析基础…… 395 8.9.2 通过覆盖一个输人树来生成 93.1 半格 396 代码 …36 9.3.2 传递函数 399 8.9,3通过扫描进行模式匹配 :362 93.3通用框架的选代算法 400 894 用于语义检查的例程 …363 9.3.4 数据流解的含义 402 8.9.5通用的树匹配方法 363 9.3.59.3节的练习4***+ 404 8.9.68.9节的练习 36d 9.4堂量传播… 404 8.10表达式的优化代码的生成 365 941 常量传播框架的数据流值 404 8.10.1Ehow数 365 9.4.2 常量传播框里的交汇摆算 405 8.10.2从带标号的表达式树生成 9.4.3 常量传播框架的传递函数 405 代码 365 9.4.4 常量传递框架的单调性 40c 8.10.3寄存器数量不足时的表达式 9.4.5 常量传播框架的不可分配性· 406 求值 66 9.4.6 对算法结果的解释 407 8.10.48.10节的练习 368 9.4.79.4节的练习… 408 8.11使用动态规划的代码生成…… .368 9.5部分余消除· 408 811.连续求值 368 9.5.】冗余的来源 408 8.11.2动态规划的算法 369 9.5.2 可能消除所有元余吗 410 8.1138.11节的统习 371 9.5.3 懒情代码移动问题 411 8.12第8章总结… 371 9.5.4 表达式的预期执行 412 813第8章参考文献 372 9.5.5 微情代码移动算法 413 第9章机器无关优化 9.5.69.5节的练习 ,A》R 9.】优化的主要来源… 374 9.6流图中的循环 419