第1幸 另一种语言分类方式把程序中指明如何完成一个计算任务的语言的称为强制式(imperative)语 言，而把程序中指明要讲行明哪此计缆的语言称为声明式(declarative)语言。者如C,C++,C#和Jav 等语言都是强制式语言。所有强制式语言中都有用于表示程序状态和语句的表示方法，这些语句可 以改变程序状态。像ML、Haskell这样的函数式语言和Prolog这样的约束逻辑语言通常被认为是声 明式语言。 术语冯·诺伊曼语言(von Neumann language)是指以冯·诺伊曼计算机体系结构为计算模型 的程序设计语言。今天的很多语言（比如Fortran和C)都是冯·诺伊曼语言。 面向对象语言(object-oriented)指的是支持面向对象编程的语言，面向对象编程是指 用一组相互作用的对象组成程序的编程风格。Simula67和Smalltalk是早期的主流面向对象语言。 C++、C#、Java和Ruby是现在常用的面向对象语言。 脚本语言((scripting language))是具有高层次运算符的解释型语言，它通常被用于把多个计算过 程“粘合”在一起。这些计算过程被称为脚本。Awk、JavaScrip、Perl、PHP、Python、Ruby和Td是常 见的脚本语言。使用脚本语言编写的程序通常要比用其他语言（比如C)写的等价的程序短很多。 1.3.2对编译器的影响 因为程序设计语言的设计和编译器是紧密相关的，程序设计语言的发展向编译器的设计者 提出了新的要求。他们必须设计相应的算法和表示方式来翻译和支持新的语言特征。从20世纪 40年代以来，计算机体系结构也有了很大的发展。编译器的设计者不仅需要银踪新的语言特征 还需要设计出新的翻泽算法，以便尽可能地利用新硬件的能力。 通过降低用高级语言程序的执行开销，编译器还可以推动这些高级语言的使用。要使得高性能计 算机体系结构能够高效运行用户应用，编译器也是至关重要的。实际上，计算机系统的性能是非常依 横于编译技术的。以至于在构建个计算机之前，编译器会被用作评价一个体系结构概念的工具。 编写编译器是很有战性的。编译器本身就是一个大程序。而且，很多现代语言处理系统在同 个框架内处理多种源语言和目标机。也就是说，这些系统可以被当做一组编译器来使用，可能包 含几百万行代码。因此，好的软件工程技术对于创建和发展现代的语言处理器是非常重要的 编译器必须能够正确翻译用源语言书写的所有程序。这样的程序的集合通常是无穷的。为 个源程序生成最佳目际代码的问题一最来说是不可判定的。因此，编译器的设计者必须作出 折衷处理，确定解决那些间题，使用哪些启发式信息，以便解决高效代码牛成的问题 我们将在1.4节看到，有关编译器的研究也是有关如何使用理论来解决实践问题的研究 本书的目的是教授编译器设计中使用的根本思想和方法论。本书并不想让读者学习建立 个最新的语言处理系统时可能用到的所有镇法和技术。但是，本书的读者将获得必要的基础知 识和理解，学会建立 个相对简单的编译器 1.3.31.3节的练习 练习1.3.1：指出下面的术语 1)漏制式的 2)声明式的 3)冯·诺伊号式的 4)面向对象的 5)雨数式的 6)第三代 7)第四代 8)脚本语言 可以被用于描述下面的哪些语言： 1）C 2）C++ 3)Cobol 4)Fortran 5)Java 6)Lisp 7)ML 8)Perl 9)Python 10)VB 1.4构建一个编译器的相关科学 编译器的设计中有很多通过数学方法抽象出题本质从而解决现实世界中复杂问题的完美
论 例子。这些例子可以被用来说明如何使用抽象方法来解决向题：接受一个问题，写出抓住了问题 的关键特性的数学拍象表示，并用数学技术来解决它。向题的表达必须根植于对计算机程序特 性的深人理解，而解决方法必须使用经验来验证和精化。 编译器必须接受所有遵循语言规范的源程序。源程序的集合是无穷的，而程序可能大到包 含几百万行代码。在翻译一个源程序的过程中，编译器所做的任何翻译工作都不能改变被编译 源程序的含义。因此，编译器设计者的工作不仅会影响到他们创建的编译器，还会影响到他们所 创建的编译器所编译的全部程序。这种杠杆作用使得编译器设计的回报丰厚，但也使得编译器 的开发工作具有桃战性 1.4.1编译器设计和实现中的建模 对编译器的研究主要是有关如何设计正确的数学模型和选择正确算法的研究。设计和选择 时，还需要考虑到对通用性及功能的要求与简单性及有效性之间的平衡。 最基本的数学模型是我们将在第3章介绍的有穷状态自动机和正则表达式。这些模型可以 用于措述程序的词法单位（关键字、标识符等）以及描述被编译器用来识别这些单位的算法。最 基本的模型中还包括上下文无关文法，它用于描述程序设计语言的语法结构，比如嵌套的括号和 控制结构。我们将在第4章研究文法。类似地，树形结构是表示程序结构以及程序到目标代码的 翻译方法的重要模型。我们将在第5章介绍这一概念 1.4.2代码优化的科学 在编译器设计中，术语“优化”是指编译器为了生成比浅显直观的代码更加高效的代码而做 的工作。“优化”"这个词并不恰当，因为没有办法保证一个编译器生成的代码比完成相同任务的 任何其他代码更快，或至少一样快 现在，编译器所作的代码优化变得更加重要，而且更加复杂。之所以变得更加复杂，是因为 处理器体系结构变得更加复杂，也有了更多改进代码执行方式的机会。之所以变得更加重要，是 因为巨型并发计算机要求实质性的优化，否则它们的性能将会呈数量级地下降。随着多核计算 机（这些计算机上的芯片拥有多个处理器）日益流行，所有的编译器都将面临充分利用多处理器 计算机的优势的问题 即使有可能通过随意的方法来建造一个健壮的编译器，实现起来也是非常困难的。因此，人们 已经围绕代码优化建立了一套广泛且有用的理论。应用严格的数学基础，使得我们可以证明一个优 化是正确的，并且它对所有可能的输入都产生预期的效果。从第9章开始，我们将会看到，如果想 使得编译器产生经过良好优化的代码，图、矩阵和线性规划之类的模型是必不可少的。 从另一方面来说，只有理论是不够的。很多现实世界中的问题都没有完美的答案。实际上 我们在编译器优化中提出的很多问题都是不可判定的。在编译器设计中，最重要的技能之一是 明确描述出真正要解决的问题的能力。我们在一开始需要对程序的行为有充分的了解，并且需 要通过充分的试验和评价来验证我们的直觉。 编译器优化必须满足下面的设计目标】 。优化必须是正确的，也就是说，不能改变被编译程序的含义。 。优化必须能够改善很多程序的性能。 。优化所需的时间必须保持在合理的范围内 。所需要的工程方面的工作必须是可管理的 对正确性的强调是无论如何不会过分的。不管设计得到的院译翠能够生成运行谏度多么快的代 码，只要生成的代码不正确，这个设计就是毫无意义的。正确设计优化编译器是如此困难，我们敢说没
10 第1章 有一个优化编译器是完全无错的！因此，设计一个编译器时最重要的目标是使它正确。 第二个目标是编译器应该有效提高很多输人程序的性能。性能通常意味著程序执行的速度。 我们也希望能够尽可能降低生成代码的大小，在嵌人式系统中更是如此。而对于移动设备的情 况，尽量降低代码的能耗也是我们期待的。在通常情况下，提高执行效率的优化也能够节约能 耗。除了性能，错误报告和调试等的可用性方面也是很重要的。 第三，我们需要使编译时间保持在较短的范围内，以支持快速的开发和调试周期。当机器变 得越来越快，这个要求会越来越容易达到。开始时，一个程序经常在没有进行优化的情况下开发 和调试。这么做不仅可以降低编译时间，更重要的是未经优化的程序比较容易调试。这是因为 编译器号引人的优化经常使得原代码和目标代码之间的关系变得模糊。在编译器中开启优化有时 会暴露出源程序中的新问题，因此需要对经过优化的代码再次进行测试。因为可能需要额外的 测试工作，有时会阻止人们在应用中使用优化技术，当应用的性能不很重要的时候更是如此。 最后，编译器是一个复杂的系统，我们必须使系统保持简单以保证编译器的设计和维护费用 是可管理的。我们可以实现的优化技术有无穷多种，而创建一个正确有效的优化过程需要相当 大的工作量。我们必须划分不同优化技术的优先级别，只实现那些可以对实践中遇到的源程序 带来最大好处的技术。 因此，我们在研究编译器时不仅要学习如何构造一个编译器，还要学习解决复杂和开放性问 题的一般方法学。在编译器开发中用到的方法涉及理论和实验。在开始的时候，我们通常根据 直党确定有哪些重要的问题并把它们明确描述出来。 1.5编译技术的应用 编译器设计并不只是关于编译器的。很多人用到了在学校里研究编译器时学到的技术，但 是严格地说，它们从没有为一个主流的程序设计语言编写过一个编译器（甚至其中的一部分）。 编译器技术还有其他重要用途。另外，编译器设计影响了计算机科学中的其他领域。在本节，我 们将回顾和编译技术有关的最重要的互动和应用。 1.5.1高级程序设计语言的实现 个高级程序设计语言定义了一个编程抽象：程序员使用这个语言表达算法，而编译器必须 把这个程序翻译成目标语言。总的来说，用高级程序设计语言编程比较容易，但是比较低效，也 就是说，目标程序运行较慢。使用低级程序设计语言的程序员能够更多地控制一个计算过程，因 比从原则上讲，可以产生更加高数的代码。遗感的是，低级程序比较难绝写，而目更糟糕的是可可 稳植性较差，西容易出错，而日更加谁以维护。优化编择器句括了据高所生成代码性能的技术 因此弥补了因高层次抽象而引人的低效率 例1.2C语言中的关键字register是编译器技术和语言发展互动的一个较早的例子。当C语 言在20世纪70年代中期被创立时，人们认为有必要让程序员来控制哪个程序变量应该存放在寄 存器中。当有效的寄存器分配技术出现后，这个控制变得没有必要了，大多数现代的程序不再使 用这个语言特征 实际上，使用关键字r gister的程序还可能损失效率，因为寄存器分配是一类很低层次的问 题，程序员常常不是最好的判断这类问题的人选。寄存器分配的最优选择很大程度上取决于 个机器的体系结构的特点。把低层次资源管理的决策，比如寄存器分配，写死在程序中反而有可 能损害性能。当运行程序的计算机有别于当初所设定的目标机时更是如此。 对于程序设计语言的选择的变化与不断提高抽象层次的方向是一致的。C语言是在20世纪
引 论 80年代主流的系统程序设计语言：20世纪90年代开始的很多项目则选择C++:在1995年推出 的Jav很快在20世纪90年代后期流行起来。在每一轮中引人的新的程序设计语言特征都会推 动对于编译器优化的新研究。接下来，我们将给出一个关于主要语言待征的概览 这些特征曾经 推动了编译器技术的重要发展。 在实践中，所有的通用程序设计语言，句括C、Foan和Cobol,都支持用户定义的骤合类型 (如数组和结枸)和高级控制流（比如循环和过程调用）。如果我们仅仅把每个高级结构和数据存 取运算直接翻译成为机器代码，得到的代码将会非常低效。编译器优化的一个组成部分称为数 据流优化，它可以对程序的数据流进行分析，并消除这些构造之间的冗余。它们很有效，生成的 代码和 个熟练的低级语言程序员所写的代码类似。 面向对象概念首先于1967年在Simula中弓引人，并被集成到Smalltalk、C++、C#和Java这样 的语言中。面向对象的主要思想是 1)数据抽象 2)特性的继承 人们发现这两者都可以使想程序更加模块化和易干雄护。面向对鱼程序和用很多其他语言编 写的程序之间的不同在于它们由多得多的（但是较小）过程（在面向对象术语中称为方法(method) 组成。因此，编译器优化技术必须能够很好地跨越源程序中的过程边界进行优化。过程内联技 术（即把一个过程调用替换为相应过程体）在这里是非常有用的。人们还开发了可以加速虚拟方 法分发的优化技术。 Java有很多特征可以使编程变得更容易，其中的很多特征之前已经在别的语言中引入。Java 语言是类型安全的：也就是说 一个对象不能被当作另一个无关类型的对象来使用。所有的数组 访问运算都会被检查以保证它们在数组的界限之内。Jv没有指针，也不允许指针运算。它具有 一个内建的垃圾收集机制来自动释放那些不再使用的变量所占用的内存。虽然所有这些特征使 得编程变得更加容易，但它们也会引起运行时刻的开销。人们开发了相应的编译优化技术来降 低这个开销。比如，消除不必要的下标范周检查，以及把那些在过程之外不可访问的对象分配在 栈里而不是堆里。此外，人们还开发了高效的算法来尽量降低垃圾收集的开销。 除此之外，Java用来支持可移植和可移动的代码。程序以Jav阳字节码的方式分发。这些字 节码要么被解释执行，要么被动态地（即在运行时刻）编译为本地代码。动态编译也曾经在其他 上下文环境中被研究过。在那里，信息在运行时刻被动态地抽取出来，并用来生成更加优化的代 码。在动态编译中，尽可能降低编译时间是很重要的，因为编译时间也是运行开销的一部分 个常用的技术是只编择和优化那些经常运行的程序片断 1.5.2针对计算机体系结构的优化 计算机体系结构的快速发展也对新编译器技术提出了越来越多的需求。几乎所有的高性能 系统都利用了两种技术：并行(parallelism)和内存层次结构(me ory hierarchy)。并行可以出现在 多个层次上：在指令层次上，多个运算可以被同时执行：在处理器层次上，同一个应用的多个不 同线程在不同的处理器上运行。内存层次结构是应对下述局限性的方法：我们可以制造非常快 的内存，或者非常大的内存，但是无法制造非常大又非常快的内存。 并行性 所有的现代微处理器都采用了指令级并行性。但是，这种并行性可以对程序员隐藏起来。 程序员写程序的时候就好像所有指令都是顺序执行的。硬件动态地检测顺序指令流之间的依赖 关系，并且在可能的时候并行地发出指令。在有些情况下，机器包含一个硬件调度器。该调度器 可以改李指今的顺序以提高程序的并行性。不管硬件是否对指今进行重新排序，集泽器都可以
12 第1章 重新安排指令，以使得指令级并行更加有效 指今级的并行也显式地出现在指今集中。VLIW(Very long Instruction Word.非常长指今字】 机器拥有可并行执行多个运算的指令。tIA64是这种体系结构的一个有名的例子。所有的高 性能通用微处理器还包含了可以同时为 个向量中的所有数据进行运算的指令。人们已经开发 出了相应的编译器技术，从顺序程序出发为这样的机器自动生成代码。 多处理器也已经日益流行，即使个人计算机也拥有多个处理器。程序员可以为多处理器编 写多线程的代码，也可以通过编译器从传统的顺序程序自动生成并行代码。这样的编译器对程 序员隐藏了一些细节，包括如何在程序中找到并行性，如何在机器中分发计算任务，以及如何最 小化处理器之间的同步和通信。很多科学计算和工程性应用需要进行高强度的计算，因此可以 从并行处理中得到很大的好处。人们已经开发了并行技术以使自动地把顺序的科学计算程序 译成为多处理器代码。 内存层次结构 个内存层次结构由几层具有不同速度和大小的存储器组成。离处理器最近的层速度最快 但是容量最小。如果一个程序的大部分内存访问都能够由层次结热中最快的层满是，那么程 的平构内存访问时间就会降低。并行性和内存层次结构的存在都会提高 个机器的潜在性能 但是。它们必须被编译器有效利用才能够直正为一个应用提供高性能计算 内存层次结物可以在所有的机器中找到 一个处理器通常右少量的几百个字节的蛊存摆 几层包含了几K到几兆字节的高速缓存，包含了几兆到几G字节的物理寄存器，最后还包括多 个几G字节的外部存储器。相应地，层次结构中相邻层次间的存取速度会有两到三个数量级上 的差异。系统性能经常受到内存子系统的性能（而不是处理器的性能）的限制。虽然一般来说编 译器注重优化处理器的执行，现在人们更多地强调如何使得内存层次结构更加高效 高效使用寄存器可能是优化一个程序时要处理的最重要的问题。和寄存器必须由软件明确 管理不同，高速缓存和物理内存是对指令集合隐藏的，并由硬件管理。人们发现，由硬件实现的 高速缓存管理策略有时并不高效。当处理具有大型数据结构（通常是数组）的科学计算代码时更 是如此。我们可以改变数据的布局或数据访问代码的顺序来提高内存层次结构的效率。我们也 可以通过改变代码的布局来提高指令高速缓存的效率。 1.5.3新计算机体系结构的设计 在计算机体系结构设计的早期，编译器是在机器建造好之后再开发的。现在，这种情况已经 有所改变。因为使用高级程序设计语言是一种规范，决定一个计算机系统性能的不是它的原始 速度，还包括编译器能够以何种程度利用其特征。因此，在现代计镇机体系结构的开发中。编图 器在处理器设计阶段就进行开发，然后编译得到代码并运行于模拟器上。这些代码被用来评价 提议的体系结构特征。 RISC 有关编译器如何影响计算机体系结构设计的最有名的例子之一是RISC(Reduced Instruction Set Computer,,精简指令集计算机)的发明。在发明RISC之前，趋势是开发的指令集越来越复杂 以使得汇编编程变得更容易。这些体系结构称为CISC(Complex Instruct n-Set Computer,复杂指 令集计算机)。比如，CSC指令集包含了复杂的内存寻址模式来支持对数据结构的访问，还包含 了过程调用指令来保存寄存器和向栈中传递参数。 编译器优化经常能够消除复杂指令之间的冗余，把这些指令削减为少量较简单的运算。因 此，人们期望设计出简单指令集。编译器可以有效地使用它们，而硬件也更容易进行优化。 大部分通用处理器体系结构，包括PowerPC、SPARC、MIPS、Anha和PA-RISC.都是基于