编译原理与技术参考书介绍.doc

编译原理与技术的参考书介绍1.1 编译原理 技术与工具（英文版）1.1.1 书本信息书 名编译原理 技术与工具（英文版）页数796作 者Alfred V.Aho Ravi Se开本16责任编辑李际字数1009千字出 版 社人民邮电出版社印张50.75出版时间2002年2月第1版页数796再版时间2004年8月第5次书号09916装 帧平装定价 63元 带盘否 1.1.2 内容提要作为编译器设计的教程，本书重点主要放在解决在设计语言翻译器过程中所普遍面对的一些问题上而并不考虑源语言或者目标机器。本书共12章：第一章介绍了编译器的基本结构；第二章给出了一个将前缀表达式转换成后缀表达式的编译器，主要使用本书的一些基本技巧来构建；第三章阐述了词法分析、正则表达式、有限自动机和扫描生成器工具，这章中的技术广泛应用于文本处理；第四章详细阐述了主要的分析技术，从适合手工实现的递归下降算法到在分析生成器中使用的LR算法；第五章介绍了语法制导翻译中的主要思想，本书的其它部分都用本章来说明和实现翻译；第六章提出了完成静态语义检查的主要思想，并对类型检查和类型的统一进行了详细的讨论；第七章讨论了支持应用程序运行时环境的存储组织；第八章从中间语言的讨论开始，说明了编程语言结构翻译成中间代码；第九章阐述了目标代码的生成，包含基本的on_the_fly代码生成方法、为表达式生成代码的优化方法、Peephole优化和代码生成器；第十章是代码优化的总述。除了关于数据流分析方法的详细说明，还有关于如何进行全局优化的基本方法；第十一章讨论了在编译器实现过程中可能会产生的一些实际问题；第十二章提出一些使用本书中的技术构建的一些编译器的学习用例。本书可作为高校计算机专业本科和研究生编译原理的教科书，也可供从事计算机软件开发的人员参考。 1.1.3 目录第1章编译器概述1.1编译器1.2源程序代码的分析1.3编译器的各个阶段1.4编译器的预处理器1.5阶段组合1.6编译器构造工具小结：编写编译器的规则和技术如此普遍，以至于书中的思想可以被计算机科学家在他们的工作生涯中多次使用。书写编译器覆盖了程序语言、机器系统结构、语言理论、算法和软件工程的内容。幸运的是，一些基本编译器技术可以用来为许多种类的语言和机器来构建翻译器。这一章中，我们通过描述编译器的各组成部分分别介绍了编译器的主题，编译器工作的环境，以及使得它较容易构造编译器的软件工具。第2章一个简单的一遍扫描编译器2.1概述2.2语法定义2.3语法制导翻译2.4分析2.5简单表达式的翻译机2.6词法分析2.7符号表2.8抽象的栈机器2.9将这些技术组合在一起小结：这一章是这本书3到8章内容的概述。它提出了一系列基本的编译技术，这些编译技术是通过能够将前缀表达式翻译成后缀表达式的C工作程序开发来实现的。重点放在编译器的前端上，也就是说放在词法分析、语法分析和中间代码的生成上。9、10章描述代码生成和优化。第3章词法分析3.1词法分析器的功能3.2输入缓冲（扫描处理）3.3标号说明3.4符号识别3.5识别词法分析器的语言3.6有穷自动机3.7从正则表达式到NFA3.8词法分析生成器的设计3.9基于DFA模式匹配的优化器小结：这一章处理识别和实现词法分析器的技术。构建词法分析器的最简单的一个方法是构建一个描述原语言标号结构的表。然后将这个图表手工翻译成搜索标号的程序。高效的词法分析器可以通过这种方式产生。用来实现词法分析器的这种技术可以被应用到其它地方像查询语言和信息获取系统中。每一个应用程序中，最根本的问题就是执行由字符串中的模式引发的行为的程序说明和设计。由于模式导引的编程是非常有用的，我们引入一个叫做Lex的模式行为语言来说明词法分析器。在这种语言中，模式由正则表达式标志，Lex的编译器可以为正则表达式生成一个高效的有穷自动机识别器。一些语言使用正则表达式来描述模式。举例来说，模式扫描语言AWK使用正则表达式来选择输入行进行处理，UNIX系统外壳允许用户通过书写正则表达式来引用一系列文件名字。举例来说，UNIX命令rm*.o，就是移走所有名字结尾为.o的文件。词法分析器自动构造的软件工具允许不同背景的人们在他们自己的应用程序领域中使用模式匹配。举例来说，Jarvis使用词法分析生成器创建了一个在印刷电路板上识别缺陷的程序。这个电路可以进行数字化扫描并能被转化成不同角度线段的字符串。词法分析器寻找那些同线段字符串中的缺陷相对应的模式。词法分析器生成器的主要优点是它使用的是最著名的模式匹配算法，因此为那些在模式匹配技术中并不是专家的人们创造了高效的词法分析。第4章文法分析4.1分析器的角色4.2上下文无关文法4.3编写一个文法4.4自顶向下的分析4.5自下而上的分析4.6算符优先算法的分析4.7LR分析算法4.8使用二义性文法4.9分析生成器小结：每一个编程语言都有一些描述已经形成的程序的语法结构的规则。Pascal中，举例来说，一个应用程序由块组成的，块由若干语句组成，语句由表达式组成，一个表达式由若干符号组成，等等。编程语言结构的语法可以通过上下文无关文法或者BNF标识来描述，文法为语言设计者和编译器书写者都提供了一些好处。l文法给了一个精确的，而且很容易理解的程序语言的文法规则。l从一个特定文法的一些类中我们可以自动构造一个高效的分析器来判断一个源程序在语法上结构是否是完整的。有一个额外的优点就是分析器构造过程可以显示出语法的二义性以及一些其它较难分析的结构，而那些结构很可能在一个语言和编译器的最初设计阶段是很难检查出来的。l恰当设计的文法将一个结构传给应用程序语言。这个程序语言对于将源程序翻译成正确的目标代码以及进行错误的检测都是非常有用的。工具有利于将基于文法的翻译描述转换成能用的应用程序。l随着时间的推移，语言增加了一些新的结构，同时又实现了一些别的工作。这些新的结构可以更容易地添加到语言中，特别是当存在一个基于语言文法描述的实现时。这一章描述了编译器中使用的分析方法。我们提出的首先是基本概念；接着是适合手工实现的技术；最后是自动化工具中使用的算法。由于程序可能包含语法错误，我们扩展了这个分析方法以使它们能够从产生的普通错误中恢复。第5章语法制导翻译5.1语法制导定义5.2语法树的构造5.3S属性定义的自下而上的求值5.4L属性的定义5.5自顶向下的翻译5.6继承性属性自下而上的求值5.7递归求值5.8编译时属性值的空间5.9编译器构造时分配空间5.10语法制导定义的分析小结：这一章发展了2.3节的主题：上下文无关文法制导的语言翻译。我们将信息同程序语言构造联系起来，主要是通过将属性挂接到代表结构的文法象征上实现的。属性的值由同文法产生式相关联的语义规则来计算。将语义规则同产生式联系要注意两点：语法制导的定义和翻译模式。语法制导定义是翻译的高层次的说明。它们隐藏了许多实现细节从而将用户从不得不明确说明翻译发生的序列中解脱出来。翻译模式表明语义规则求值的顺序，从而允许一些实现细节暴露出来。我们在第六章使用这两点来说明语义检查，特别是类型判断，而在第八章使用它们产生中间代码。概念上，使用语法制导定义和翻译模式，我们将分析输入标号流，建立分析树，接着根据需要遍历树从而对分析树节点上的语义规则求值，将信息保存在符号表中，发布错误信息，或者完成其它一些动作。标号流的翻译是通过求值语义规则获得的结果。语法制导翻译的概念视图一个实现并不一定需要完全符合上图。语法制导定义的特例也可以通过一遍来实现。主要是通过对遍中的语义规则进行求值而不是明显的定义一个分析树或者一个图表来显示属性之间的依赖关系。由于一遍的实现对于编译的高效性有重要影响，这一章主要研究这些特例。一个重要的子类叫做L属性的算法包含了实际上所有的翻译，而这些翻译无需明确构造分析树就能实现的。第6章类型检查6.1类型系统6.2一个简单的类型检查器的说明6.3类型表达式的等价性6.4类型转换6.5函数和操作符的重载6.6多态函数6.7统一性的一个算法小结：编译器应该检查源程序是否遵循源语言的语法和语义。这种检查，叫做静态检查（将它同目标程序执行时的动态检查区分开来），保证了特定类型的程序错误将被检测和报告出来。静态检查的例子包括：1 类型检查。比如如果一个操作符应用到一个不兼容的操作数中时，编译器应该报告出错；举例来说，如果一个数组变量和一个函数变量相加的话。2控制流检查。存在导致一个控制流离开构造器的语句。举例来说，C语言中的break语句将导致控制流离开最小的循环while，for和switch语句；如果这样一个包含语句不存在的话将导致错误。3唯一性检查。有些情况下一个对象只能被定义一次。举例来说，Pascal语言中，标识符应该被声明是唯一的，case语句中的标签也应该是唯一的。4相关名称检查。有时候，同样的名字会多次出现。举例来说，Ada中，循环或块中都将有一个名字同时出现在构造器的开始和结束。编译器将检查同样的名字可以在两端被使用。这一章中，我们着重于类型检查。像上面的例子表示的，大多数静态检查都是惯例程序并且可以运用上一章的技术实现。其中的一些可以被集成到其它一些行为中。举例来说，当我们将名字的信息存到符号表中时。我们可以确定名字的声明是唯一的。许多Pascal编译器通过分析将静态检查和中间代码生成集成为一部分。对于更多的复杂的结构，就象Ada的，很可能是在分析和中间代码生成之间有一个独立的类型检查的遍比较方便。类型检查核实结构的类型同它期待的环境相匹配。举例来说，Pascal中算术运算符mod需要整型操作数，因此一个类型检查器应该保证mod的操作数都是整数类型，同样的，类型检查器核实引用必须用到一个指针，索引只在数组上操作，而一个用户定义的函数应用时参数个数和类型必须正确等等。一个简单的类型检测器的规则出现在6.2。类型表示和什么时候两种类型匹配的问题将在6.3节讨论。由类型检查器收集的类型信息可能是需要的，特别是当生成代码的时候。举例来说，算术操作符像通常应用到每一个整数和实数上。也有其它类型的可能，而且我们不得不观察一下的上下文来决定它导向的意思。在不同的上下文中代表不同操作的符号叫做重载。重载伴随着强制类型转换，编译器提供了一个操作符将操作数转换成上下文期待的类型。重载的明确概念就是多态。多态函数的主体是可以通过多种类型的参数来执行的。这一章还包括推断多态函数的类型的统一算法。第7章运行时环境7.1源语言问题7.2存储组织7.3存储分配策略7.4非局部名称的访问7.5参数传递7.6符号表7.7动态存储分配的语言工具7.8动态存储分配技术7.9Fortran中的动态存储分配小结：在考虑代码生成之前，我们需要将一个应用程序的静态源文本同运行时的行为联系起来来实现应用程序。随着执行代码的继续，源文本中的同一个名字在目标机器中可能意味着不同的数据对象。这儿就讨论名字和数据对象之间的关系。数据对象的分配和回收由run-time support package进行管理，包括随生成的目标代码一起装载的例行程序。Run-time support package的设计受到过程的语义影响。像Fortran，Pascal和Lisp语言的支持包也可以使用本章中的技术来构建。每一个程序的执行都可看作是这个过程的activation。如果一个程序是递归的，那么它的几个动作应该是同时被激活的。每一个过程的调用都有可能导致分配给它使用的数据对象的操作激活。运行时数据对象的表示由它的类型决定。经常的，像字符，整数和实数这样的元素数据类型，就是由目标机器中等价的数据对象表示的。可是，像数组，字符串和结构等聚集，通常由原始对象的集合来表示。第8章中间代码的生成8.1中间语言8.2声明8.3分配语句8.4布尔表达式8.5Case语句8.6回填8.7过程调用小结：编译器分析合成的模型中，前端将源程序翻译成中间表示，然后后端生成目标代码。目标语言的细节尽可能地限制在后台。尽管一个源程序能被直接翻译成目标语言。但使用独立于机器的中间形式也是有好处的：1.有利于重定位；不同机器的编译器可以通过将新机器的后端挂接到现存的前端来创建。2.独立于机器的代码优化器可以被应用到中间代码的表示上。这一章展示了第2章和第5章的语法制导方法如何将声明、赋值以及流控制语句等翻译成它们的中间形式的编程语言结构。而为简单起见，我们假定源程序已经通过编译和静态检查，大多数语法制导定义都能通过自下向上或者自上而下的分析来实现，因此中间代码生成可根据具体需要合成到分析里。第9章代码生成9.1代码生成器设计中的一些问题9.2目标机器9.3运行时存储管理9.4基本块和流程图9.5下一步要使用的信息9.6一个简单的代码生成器9.7寄存器分配9.8基本块的dag代表9.9Peephole 优化9.10从dags产生代码9.11动态编程代码生成算法9.12代码生成生成器小结：编译器模型的最后阶段是代码生成器。它将源程序的中间表示作为输入，从而产生等价的目标程序作为输出。这章中使用的代码生成技术可以广泛应用，尽管在代码生成之前优化器阶段未必就会发生像在一些所谓的优化编译器中那样。这样的阶段企图将中间代码翻译成表单因此会产生更加有效的目标代码。代码优化将在下一章中详细讨论。传统上对代码生成器的要求是很严格的。输出代码应该是正确的并具有较高的质量，这意味着能更好的利用目标机器的资源。还有，代码生成器本身是非常高效的。可是数学上来说，生成优化代码的问题是不确定的。实际上，我们应该满足于启发式技术来产生较好的，并一定是最高效的代码。启发式的选择是重要的，特别是精心设计的代码生成算法能够很容易产生一些代码，它运行起来能比匆忙设计的算法产生的代码快好几倍。第10章代码优化10.1简介10.2优化的主要资源10.3基本块的优化10.4流程图的循环10.5介绍全局数据流分析10.6数据流方程的交互策略10.7代码优化的改造10.8处理别名10.9结构流图的数据流分析10.10高效的数据流算法10.11数据流分析的工具10.12类型的评估10.13优化代码的符号性调试小结：理想中，编译器应该产生像手写的一样好的目标代码。事实是这种目标只会在有限的用例中实现，而且难度还比较高。可是，直接编译算法产生的代码通常运行的比较快或者使用较少的空间，或者两个特征同时具备。这个改善是通过传统上叫做优化的程序改造来实现的，尽管优化这个术语是一个误导，因为实际上它很少能保证结果代码是尽可能优化的。应用代码优化改造的编译器叫做优化编译器。本章重点是独立于机器的优化，程序改造无须考虑目标机器的任何属性就可以改善目标代码。而像寄存器分配和特殊的机器指令序列等这些依赖于机器的优化已经在9章中讨论了。最少的努力获得最好的效果就是我们找出那些常用程序的执行部分，并使这些部分产生尽可能高的效果。有一个比较流行的说法：大多数的应用程序在10的代码上花费了90的执行时间。尽管实际的百分比会发生变化，通常情况下，小部分程序确会占据大多数的运行时间。从输入代表性数据看应用程序运行时的执行时间可准确地找出了问题的吃重运行区域。不幸的是，一个编译器通常没有输入数据的例子，因此它应该尽可能猜测问题热点所在。实际上，应用程序的内在循环是改善应用程序的一个极好的侯选。在一个强调像while和for控制结构的语言中，循环从程序的语法角度看可能是非常明显的；通常情况下，一个叫作控制流分析的过程在程序的流程图中找出循环。这章是一个有用的优化改造和实现它们的技术的丰富集合。编译器中进行什么样的改造是值得的决定这一点的最好的技术就是收集关于源程序的统计数据并且评估源程序典型例子上给定优化集合的好处。第12章描述了在对不同语言的编译器优化中证明是有用的改造。这章的主题是数据流分析，一个收集应用程序中使用变量方法的信息的过程。一个应用程序中不同点收集的信息可以通过简单的集等价方程联合起来。我们展示了几个使用数据流分析收集信息的算法并在优化中高效使用这些信息。我们仍然考虑过程和指针等语言结构对优化的影响。第11章如何写编译器11.1规划一个编译器11.2编译器开发的方法11.3编译器开发环境11.4测试和维护小结：看了这些编译设计的原则，技术和工具，假定我们需要编写一个编译器：如果提前进行规划的话，我们可以进行的更快更好。这章提出了一些编译器构建中出现的实现问题。大多数讨论注意力集中在使用UNIX操作系统和它的工具来编写编译器上。第12章看一下一些编译器12.1 排版数学的预处理器，即EQN12.2 Pascal编译器12.3 C编译器12.4 Fortran H编译器12.5 Bliss11编译器12.6 Modula2优化编译器小结：讨论了Pascal、C、Fortran、Bliss和Modula 2的编译器。我们的意图并不是支持某项设计而排除其它的，而是企图描述编译器实现过程中可能出现的各种情况。 1.2 编译原理（英文版）1.2.1 书本信息书 名编译原理页数524作 者美Alfred V.Aho等开本16责任编辑杨海玲字数千字出 版 社机械工业出版社印张34出版时间2003年8月第1版页数524再版时间2004年8月第4次书号111-12349-2装 帧平装定价 55元 带盘否 1.2.2 内容提要本书深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，每章都提供了大量的练习和参考文献。本书从介绍编译的原理性概念开始，然后通过构建一个简单的一遍编译器来逐一解释这些概念。本书是编译原理课程的经典教材，作者曾多次使用本书的内容在贝尔实验室、哥伦比亚大学、普林斯顿大学和斯坦福大学向本科生和研究生讲授初等及高等编译课程。本书作者AlfredVAho、RaviSethi和JeffreyDUllman是世界著名的计算机科学家，他们在计算机科学理论、数据库等很多领域都做出了杰出贡献。本书是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。本书一直被世界各地的著名高等院校和科研机构(如贝尔实验室、哥伦比亚大学、普林斯顿大学和斯坦福大学等)广泛用作本科生和研究生编译原理与技术课程的教材，本书对我国计算机教育界也具有重大影响。书中深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，而且每章都提供了大量的练习和参考文献。本书可以作为高等院校计算机专业本科生和研究生编译原理与技术课程的教材，也可以作为计算机技术人员必读的专业参考书之一。1.2.3 目录出版者的话专家指导委员会译者序前言第1章 编译简介11.1 编译器11.1.1 编译的分析-综合模型11.1.2 编译器的前驱与后继31.2 源程序分析31.2.1 词法分析31.2.2 语法分析31.2.3 语义分析51.2.4 文本格式器中的分析51.3 编译器的各阶段61.3.1 符号表管理71.3.2 错误检测与报告71.3.3 各分析阶段71.3.4 中间代码生成91.3.5 代码优化91.3.6 代码生成101.4 编译器的伙伴101.4.1 预处理器101.4.2 汇编器111.4.3 两遍汇编121.4.4 装配器和连接编辑器121.5 编译器各阶段的分组131.5.1 前端与后端131.5.2 编译器的遍131.5.3 减少编译的遍数141.6 编译器的构造工具14参考文献注释15第2章 简单的一遍编译器172.1 概述172.2 语法定义172.2.1 分析树192.2.2 二义性202.2.3 操作符的结合规则202.2.4 操作符的优先级212.3 语法制导翻译222.3.1 后缀表示222.3.2 语法制导定义222.3.3 综合属性232.3.4 深度优先遍历242.3.5 翻译模式252.3.6 翻译的输出252.4 语法分析262.4.1 自顶向下语法分析272.4.2 预测分析法292.4.3 何时使用产生式302.4.4 设计一个预测语法分析器302.4.5 左递归312.5 简单表达式的翻译器322.5.1 抽象语法和具体语法322.5.2 调整翻译模式332.5.3 非终结符expr、term 和rest 的过程332.5.4 翻译器的优化352.5.5 完整程序352.6 词法分析372.6.1 剔除空白符和注释372.6.2 常数372.6.3 识别标识符和关键字372.6.4 词法分析器的接口382.6.5 词法分析器382.7 符号表402.7.1 符号表接口402.7.2 处理保留的关键字412.7.3 符号表的实现方法412.8 抽象堆栈机422.8.1 算术指令422.8.2 左值和右值432.8.3 堆栈操作432.8.4 表达式的翻译432.8.5 控制流442.8.6 语句的翻译442.8.7 输出一个翻译452.9 技术的综合462.9.1 翻译器的描述462.9.2 词法分析器模块lexer.c472.9.3 语法分析器模块parser.c482.9.4 输出模块emitter.c482.9.5 符号表模块symbol.c和init.c482.9.6 错误处理模块error.c482.9.7 编译器的建立482.9.8 程序清单49练习53编程练习54参考文献注释55第3章 词法分析573.1 词法分析器的作用573.1.1 词法分析中的问题583.1.2 记号、模式、词素583.1.3 记号的属性593.1.4 词法错误603.2 输入缓冲603.2.1 双缓冲区613.2.2 标志623.3 记号的描述623.3.1 串和语言623.3.2 语言上的运算633.3.3 正规表达式643.3.4 正规定义653.3.5 缩写表示法663.3.6 非正规集663.4 记号的识别673.4.1 状态转换图683.4.2 状态转换图的实现703.5 词法分析器描述语言723.5.1 Lex说明723.5.2 超前扫描操作753.6 有穷自动机763.6.1 不确定的有穷自动机773.6.2 确定的有穷自动机783.6.3 从NFA到DFA的变换793.7 从正规表达式到NFA813.7.1 从正规表达式构造NFA813.7.2 NFA的双堆栈模拟843.7.3 时间空间的权衡853.8 设计词法分析器的生成器853.8.1 基于NFA的模式匹配863.8.2 词法分析器的DFA883.8.3 实现超前扫描操作883.9 基于DFA的模式匹配器的优化893.9.1 NFA的重要状态893.9.2 从正规表达式到DFA893.9.3 最小化DFA的状态数933.9.4 词法分析器的状态最小化953.9.5 表压缩方法95练习97编程练习103参考文献注释103第4章 语法分析1054.1 语法分析器的作用1054.1.1 语法错误的处理1064.1.2 错误恢复策略1084.2 上下文无关文法1094.2.1 符号的使用约定1104.2.2 推导1104.2.3 分析树和推导1124.2.4 二义性1134.3 文法的编写1134.3.1 正规表达式和上下文无关文法的比较1144.3.2 验证文法所产生的语言1144.3.3 消除二义性1154.3.4 消除左递归1164.3.5 提取左因子1174.3.6 非上下文无关语言的结构1184.4 自顶向下语法分析1204.4.1 递归下降语法分析法1204.4.2 预测语法分析器1214.4.3 预测语法分析器的状态转换图1214.4.4 非递归的预测分析1234.4.5 FIRST和FOLLOW1244.4.6 预测分析表的构造1254.4.7 LL(1)文法1264.4.8 预测分析的错误恢复1274.5 自底向上语法分析1284.5.1 句柄1294.5.2 句柄裁剪1304.5.3 用栈实现移动归约分析1314.5.4 活前缀1334.5.5 移动归约分析过程中的冲突1334.6 算符优先分析法1344.6.1 使用算符优先关系1354.6.2 从结合律和优先级获得算符优先关系1364.6.3 处理一元操作符1374.6.4 优先函数1374.6.5 算符优先分析中的错误恢复1394.7 LR语法分析器1424.7.1 LR语法分析算法1424.7.2 LR文法1454.7.3 构造SLR语法分析表1464.7.4 构造规范LR语法分析表1514.7.5 构造LALR语法分析表1554.7.6 LALR语法分析表的有效构造方法1584.7.7 LR语法分析表的压缩1614.8 二义文法的应用1634.8.1 使用优先级和结合规则来解决分析动作的冲突1634.8.2 悬空else的二义性1644.8.3 特例产生式引起的二义性1654.8.4 LR语法分析中的错误恢复1674.9 语法分析器的生成器1684.9.1 语法分析器的生成器Yacc1694.9.2 用Yacc处理二义文法1714.9.3 用Lex建立Yacc的词法分析器1734.9.4 Yacc的错误恢复174练习174参考文献注释182第5章 语法制导翻译1855.1 语法制导定义1855.1.1 语法制导定义的形式1865.1.2 综合属性1865.1.3 继承属性1875.1.4 依赖图1875.1.5 计算顺序1895.2 语法树的构造1895.2.1 语法树1905.2.2 构造表达式的语法树1905.2.3 构造语法树的语法制导定义1915.2.4 表达式的无环有向图1925.3 自底向上计算S属性定义1945.4 L属性定义1955.4.1 L属性定义1965.4.2 翻译模式1965.5 自顶向下翻译1985.5.1 从翻译模式中消除左递归1985.5.2 预测翻译器的设计2015.6 自底向上计算继承属性2025.6.1 删除嵌入在翻译模式中的动作2025.6.2 分析栈中的继承属性2035.6.3 模拟继承属性的计算2045.6.4 用综合属性代替继承属性2065.6.5 一个难计算的语法制导定义2075.7 递归计算2075.7.1 从左到右遍历2075.7.2 其他遍历方法2085.8 编译时属性值的空间分配2095.8.1 在编译时为属性分配空间2095.8.2 避免复制2115.9 编译器构造时的空间分配2115.9.1 从文法中预知生存期2125.9.2 不相重叠的生存期2145.10 语法制导定义的分析2155.10.1 属性的递归计算2165.10.2 强无环的语法制导定义2165.10.3 环形检测217练习219参考文献注释221第6章 类型检查2236.1 类型系统2246.1.1 类型表达式2246.1.2 类型系统2256.1.3 静态和动态类型检查2266.1.4 错误恢复2266.2 一个简单的类型检查器的说明2266.2.1 一种简单语言2266.2.2 表达式的类型检查2276.2.3 语句的类型检查2286.2.4 函数的类型检查2286.3 类型表达式的等价2296.3.1 类型表达式的结构等价2296.3.2 类型表达式的名字2316.3.3 类型表示中的环2326.4 类型转换2336.5 函数和运算符的重载2346.5.1 子表达式的可能类型的集合2356.5.2 缩小可能类型的集合2366.6 多态函数2376.6.1 为什么要使用多态函数2376.6.2 类型变量2386.6.3 包含多态函数的语言2396.6.4 代换、实例和合一2406.6.5 多态函数的检查2416.7 合一算法244练习247参考文献注释251第7章 运行时环境2537.1 源语言问题2537.1.1 过程2537.1.2 活动树2537.1.3 控制栈2557.1.4 声明的作用域2567.1.5 名字的绑定2567.1.6 一些问题2577.2 存储组织2577.2.1 运行时内存的划分2577.2.2 活动记录2587.2.3 编译时的局部数据布局2597.3 存储分配策略2607.3.1 静态存储分配2607.3.2 栈式存储分配2627.3.3 悬空引用2657.3.4 堆式存储分配2657.4 对非局部名字的访问2667.4.1 程序块2677.4.2 无嵌套过程的词法作用域2687.4.3 包含嵌套过程的词法作用域2697.4.4 动态作用域2747.5 参数传递2757.5.1 传值调用2757.5.2 引用调用2767.5.3 复制-恢复2777.5.4 传名调用2777.6 符号表2787.6.1 符号表表项2787.6.2 名字中的字符2797.6.3 存储分配信息2807.6.4 符号表的线性表数据结构2807.6.5 散列表2817.6.6 表示作用域的信息2837.7 支持动态存储分配的语言措施2857.7.1 垃圾单元2857.7.2 悬空引用2867.8 动态存储分配技术2877.8.1 固定块的显式分配2877.8.2 变长块的显式分配2877.8.3 隐式存储释放2887.9 Fortran语言的存储分配2887.9.1 COMMON区域中的数据2897.9.2 一个简单的等价算法2907.9.3 Fortran语言的等价算法2927.9.4 映射数据区294练习294参考文献注释298第8章 中间代码生成2998.1 中间语言2998.1.1 图表示2998.1.2 三地址码3008.1.3 三地址语句的类型3018.1.4 语法制导翻译生成三地址码3028.1.5 三地址语句的实现3038.1.6 表示方法比较：间址的使用3058.2 声明语句3058.2.1 过程中的声明语句3058.2.2 跟踪作用域信息3068.2.3 记录中的域名3088.3 赋值语句3098.3.1 符号表中的名字3098.3.2 临时名字的重用3108.3.3 寻址数组元素3118.3.4 数组元素寻址的翻译模式3128.3.5 赋值语句中的类型转换3148.3.6 记录域的访问3158.4 布尔表达式3158.4.1 翻译布尔表达式的方法3168.4.2 数值表示3168.4.3 短路代码3178.4.4 控制流语句3178.4.5 布尔表达式的控制流翻译3198.4.6 混合模式的布尔表达式3218.5 case语句3218.6 回填3238.6.1 布尔表达式3238.6.2 控制流语句3268.6.3 翻译的实现方案3268.6.4 标号和goto3278.7 过程调用3288.7.1 调用序列3288.7.2 一个简单的例子328练习329参考文献注释331第9章 代码生成3339.1 代码生成器设计中的问题3339.1.1 代码生成器的输入3339.1.2 目标程序3349.1.3 存储管理3349.1.4 指令选择3349.1.5 寄存器分配3359.1.6 计算次序的选择3369.1.7 代码生成方法3369.2 目标机器3369.3 运行时存储管理3389.3.1 静态分配3399.3.2 栈式分配3409.3.3 名字的运行地址3429.4 基本块和流图3439.4.1 基本块3439.4.2 基本块的变换3449.4.3 保结构变换3449.4.4 代数变换3459.4.5 流图3459.4.6 基本块的表示3459.4.7 循环3469.5 下次引用信息3469.5.1 计算下次引用信息3469.5.2 临时名字的存储分配3479.6 一个简单的代码生成器3479.6.1 寄存器描述符和