Compilers: Principles, Techniques, and Tools

第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 从正则表达式到nfa

3.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.7 lr分析算法

4.8 使用二义性文法

4.9 分析生成器

小结：

每一个编程语言都有一些描述已经形成的程序的语法结构的规则。pascal中，举例来说，一个应用程序由块组成的，块由若干语句组成，语句由表达式组成，一个表达式由若干符号组成，等等。编程语言结构的语法可以通过上下文无关文法或者bnf标识来描述，文法为语言设计者和编译器书写者都提供了一些好处。

l 文法给了一个精确的，而且很容易理解的程序语言的文法规则。

l 从一个特定文法的一些类中我们可以自动构造一个高效的分析器来判断一个源程序在语法上结构是否是完整的。有一个额外的优点就是分析器构造过程可以显示出语法的二义性以及一些其它较难分析的结构，而那些结构很可能在一个语言和编译器的最初设计阶段是很难检查出来的。

l 恰当设计的文法将一个结构传给应用程序语言。这个程序语言对于将源程序翻译成正确的目标代码以及进行错误的检测都是非常有用的。工具有利于将基于文法的翻译描述转换成能用的应用程序。

l 随着时间的推移，语言增加了一些新的结构，同时又实现了一些别的工作。这些新的结构可以更容易地添加到语言中，特别是当存在一个基于语言文法描述的实现时。


这一章描述了编译器中使用的分析方法。我们提出的首先是基本概念；接着是适合手工实现的技术；最后是自动化工具中使用的算法。由于程序可能包含语法错误，我们扩展了这个分析方法以使它们能够从产生的普通错误中恢复。


第5章 语法制导翻译

5.1 语法制导定义

5.2 语法树的构造

5.3 s－属性定义的自下而上的求值

5.4 l－属性的定义

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.9 fortran中的动态存储分配

小结：

在考虑代码生成之前，我们需要将一个应用程序的静态源文本同运行时的行为联系起来来实现应用程序。随着执行代码的继续，源文本中的同一个名字在目标机器中可能意味着不同的数据对象。这儿就讨论名字和数据对象之间的关系。

数据对象的分配和回收由run-time support package进行管理，包括随生成的目标代码一起装载的例行程序。run-time support package的设计受到过程的语义影响。像fortran，pascal和lisp语言的支持包也可以使用本章中的技术来构建。

每一个程序的执行都可看作是这个过程的activation。如果一个程序是递归的，那么它的几个动作应该是同时被激活的。每一个过程的调用都有可能导致分配给它使用的数据对象的操作激活。

运行时数据对象的表示由它的类型决定。经常的，像字符，整数和实数这样的元素数据类型，就是由目标机器中等价的数据对象表示的。可是，像数组，字符串和结构等聚集，通常由原始对象的集合来表示。


第8章 中间代码的生成

8.1 中间语言

8.2 声明

8.3 分配语句

8.4 布尔表达式

8.5 case语句

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.9 peephole 优化

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 排版数学的预处理器，即eqn

12.2 pascal编译器

12.3 c编译器

12.4 fortran h编译器

12.5 bliss／11编译器

12.6 modula－2优化编译器

小结：

讨论了pascal、c、fortran、bliss和modula 2的编译器。我们的意图并不是支持某项设计而排除其它的，而是企图描述编译器实现过程中可能出现的各种情况。


chapter 1 introduction to compiling


chapter 2 a simple one-pass compiler


chapter 3 lexical analysis


chapter 4 syntax analysis


chapter 5 syntax-directed translation


chapter 6 type checking


chapter 7 run-time environments


chapter 8 intermediate code generation


chapter 9 code generation


chapter 10 code optimization


chapter 11 want to write a compiler?


chapter 12 a look at some compilers


appendix a compiler project


bibliography


index