论 13 RISC概念的。虽然x86体系结构（最流行的微处理器）具有CSC指令集，但在这个处理器本身的 实现中使用了很多为RSC机器发展得到的思想。不仅如此，使用高性能x86机器的最有效的方 法是仅使用它的简单指令 专用体系结构 在过去的30年中，提出了很多的体系结构概念。其中包括：数据流机器、向量机、VW(非常 长指令字)机器、S1MD(单指令，多数据)处理器阵列、心动阵列(systolie my)、共享内存的多处理 器、分布式内存的多处理器。每种体系结构概念的发展都伴随着相应编译器技术的研究和发展。 这些思想中的一部分已经应用到嵌人式机器的设计中。因为整个系统都可以放到一个芯片 里面，所以处理器不再是预包装的商品。人们可以针对特定应用进行裁剪以获得更好的费效比 由于规模经济效用，通用处理器的体系结构具有趋同性。而专用应用的处理器则与此相反，体现 出了计算机体系结构的多样性。人们不仅需要编译器技术来为这些体系结构编程提供支持，也 需要用它们来评价拟议中的体系结构设计 1.5.4程序翻译 我们通常把编译看作是从 一个高级语言到机器语言的糊译过程。同样的技术也可以应用到 不同种类的语言之间的翻译。下面是程序翻译技术的一些重要应用。 二进制题译 编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使得可以 在一个机器上运行原本为另一个指令集编译的程序。二进制翻译技术已经被不同的计算机公司 用来增加它们的机器上的可用软件。特别地，因为x86在个人计算机市场上的主导地位，很多软 件都是以x86二进制代码的形式提供的。 人们开发了二进制代码翻译器，把86代码转换成 Alpha和Sparc的代码。Transmeta公司也在他们的x&6指令集实现中使用了二进制转换。他们没 有直接在硬件上运行复杂的x86指令集，他们的Tar smeta Crusoe处理器是一个VLW处理器 它依赖于二进制翻泽器来把x86代码转换成为本地的V山W代码。 二进制翻译也可以被用来提供向后兼容性。I994年，当Apple Macintosh中的处理器从 Motorola MC68040变为PowerPC的时候，便使用二进制翻译来支持PowerPC处理器运行遗留下来 的MC68040代码。 硬件合成 不仅仅大部分软件是用高级语言描述的，连大部分硬件设计也是使用高级硬件描述语言描 述的，这些语言有Verilog和VHDL(Very high-speed integrated circuit Hardware Description Lan uage.甚高速集成电路硬件措述语言)。硬件设计通常是在寄存器传输层(Register Transfer Level RTL)上描述的 在这个层中，变量代表寄存器，而表达式代表组合逻辑。硬件合成工具把T 描述自动翻译成为门电路，而门电路再被翻译成为晶体管，最后生成一个物理布局。和程序设计 语言的编译器不同.这些工具经常会花费几个小时来优化门电路。还存在一些用来翻译更高层 次（比如行为和函数层次）的设计描述的技术 数据查询解释器 除了描述软件和硬件，语言在很多应用中都是有用的。比如，查询语言（特别是SQL语言 (Structured Query Language,结构化查询语言)被用来搜紫数据库。数据库查询由包含了关系和布 尔运算符的断言组成。它们可以被解释，也可以编译为代码，以便在一个数据库中搜索满足这个 断言的记录。 编译然后模拟 模拟是在很多科学和工程领城内使用的通用技术。它用来理解一个现象或者验证一个设计
14 第1章 模拟器的输人通常包括设计描述和某次特定模拟运行的具体输入参数。模拟可能会非常昂费。 我们通常需要在不同的输人集合中模拟很多可能的设计选择。而每个实验可能需要在高性能计 算机上花费儿天时间才能完成。另一个方法不需要写 个模拟器来解释这些设计。它对设计进 行编译并生成能够在机器上直接模拟特定设计的机器代码。后者的运行更加快。经过编译的模 拟运行可以比基于解释器的方法快几个数量级。在那些可以模拟用Verilog或VHDL描述的设计 的最新工具中，人们都使用了编择后模以的技术。 1.5.5软件生产率工具 程序可以说是人类迄今为止生出的最复袋的工程制品，它们包含了很多很多的细节。要 使得程序能够完会正确云行，每个细节都必须是正确的。结果是程序中的错误很是得领。错误 可以使一个系统崩溃，产生错误的输出 ,使得系统容易受到安全性攻击，在关键系统中甚至会引 起灾难性的运行错误。测试是对系统中的借误进行定位的主要技术。 个很有意思且很有前景的辅助性方法是通过数据流分析技术静态地（即在程序运行之前） 定位错误。数据流分析可以在所有可能的执行路径上找到错误，而不是像程序测试的时候所做 的那样，仅仅是在那些由输入数据组合执行的路径上找错误。很多原本为编译器优化所开发的 数据流分析技术可以用来创建相应的工具，帮助程序员完成他们的软件工程任务。 找到程序的所有错误是不可判定问题。可以设计 个数据流分析方法来找出所有可能带有 某种错误的语句，对程序员发出警告。但是如果这些警告中的大部分都是误报，用户将不会使用 这个工具。因此，实用的错误检测器经常既不是健全的也不是完全的。也就是说，它们不可能找 出程序中的所有错误，也不能保证报告的所有错误都真正是错误。虽然如此，人们仍然开发了很 多种静态分析工具，这些工具能够在实际程序中有效地找到错误，比如释放空指针或已释放过的 指针。错误探测器可以是不健全的。这个事实使得它们和编译器的优化有着显著不同。优化器 必须是保守的，在任何情况下都不能改变程序的语义。 在本节中，我们将提到使用程序分析技术来提高软件生产数率的几个已有途径。这些分析 是在原本为编译器代码优化而开发的技术的基础上建立的。其中静态探测一个程序是否具有安 全漏洞的技术是极为重要的。 类型检查 类型检查是一种有效的，且被充分研究的技术，它可以被用于捕捉程序中的不一致性。它可以 用来检测一些错误，比如，运算被作用于错误类型的对象上，或者传递给一个过程的参数和该过程 的范型(signatur©)不匹配。通过分析程序中的数据流，程序分析还可以做出比检查类型错误更多的 工作。比如 个指针被赋予了NLL值，然后又立刻被释放了，这个程序显然是错误的， 这个技术也可以用来捕捉某种安全漏洞。其中，攻击者可以向程序提供一个字符串或者其 他数据，而这些数据没有被程序谨慎使用。一个用户提供的字符串可以被加上一个“危险”的标 号。如果没有检查这个字符串是否满足特定的格式，那么它仍然是“危险”的。如果这种类型的 字符串能够在某个程序点上影响代码的控制流，那么就存在一个潜在的安全漏洞。 边界检查 相对于较高级的程序设计语言而言，用较低级语言编程更加容易犯错。比如，很多系统中的 安全漏洞都是因为用C语言编写的程序中的缓冲区溢出造成的。因为C语言没有数组边界检查， 所以必须由用户来保证对数组的访问没有超出边界。因为不能检验用户提供的数据是否可能溢 出一个缓冲区，程序可能被欺骗，把一个数据存放到缓冲区之外。攻击者可以巧妙处理这些数 据，使得程序做出错误的行为，从而危及系统的安全。人们已经开发了一些技术来寻找程序中的 缓冲区溢出，但收效并不显著
孙 论 如果程序是用一种包含了自动区间检查的安全的语言编写的，这个问题就不会发生。用来 消除程序中的冗余区间检查的数据流分析技术也可以用来定位缓冲区溢出错误。而最大区别在 于，没能消除某个区间检查仅仅会导致很小的额外运行时刻开销，而没有指出一个潜在的缓冲区 溢出错误却可能危及系统的安全性。因此，虽然使用简单的技术去进行区间检查优化就已经足 够了，但在错误探测工具中获得高质量的结果则需要复杂的分析技术，比如在过程之间跟踪指针 值的技术。 内存管理工具 垃圾收集机制是在效率和易编程及软件可靠性之间进行折衷处理的另一个极好的例子。自 动的内存管理消除了所有的内存管理错误（比如内存泄漏）。这些错误是C或C++程序中问题 的主要来源之 。人们开发了很多工具来帮助程序员寻找内存管理错误。比如，Pu是一个能 够动态地捕提内存管理错误的被广泛使用的工具。还有一些能够帮助静态识别部分此类错误的 工具也已经被开发出来。 1.6程序设计语言基础 这一节我们将讨论在程序设计语言的研究中出现的最重要的术语和它们的区别。我们的目 标并不是涵盖所有的概念或所有常见的程序设计语言。我们假设读者已经至少熟悉C、C++、 C#或Java中的一种语言，并且也可能已经遇到过其他语言。 1.6.1静态和动态的区别 在为一个语言设计一个编译器时，我们所面对的最重要的问题之一是编译器能够对一个程 序做出些判定。如果一个语言使用的策路支特编译器静态决定某个问题，那么我们说这个语 言使用了一个静态(static)策略，或者说这个问题可以在编译时刻(compile time)决定。另一方面 个只允许在运行程序的时候做出决定的策略被称为动态略(dynamie policy),或者被认为需 要在运行时刻(run time)做出决定。 我们需要注意的另一个问题是声明的作用域。x的一个声明的作用域(sop心)是指程序的 个区域，在其中对x的使用都指向这个声明。如果仅通过阅读程序就可以确定一个声明的作用 域，那么这个语言使用的是静态作用线(static scope),或者说词法作用域(lexical scope)。否则 这个语言使用的是动态作用城(dynamic scop)。如果使用动态作用域，当程序运行时，同一个对 x的使用会指向x的几个声明中的某一个。 大部分语言（比如C和Java)使用静态作用域。我们将在1.6.3节中讨论静态作用域 例1.3作为静态/动态区别的另一个例子，我们考虑一下Java类声明中术语static的使用。这 个术语作用于数据。在Jaa中，一个变量是用于存放数据值的某个内存位置的名字。这里， “static“指的并不是变量的作用域，而是编译器确定用于存放被声明变量的内存位置的能力。比 如声 public static int xi 使得x成为一个类变量(class variable),也就是说不管创建了多少个这个类的对象，只存在一个x 的拷贝。此外，编译器可以确定内存中的被用于存放整数x的位置。反过来，如果这个声明中省 略了“static”,那么这个类的每个对象都会有它自己的用于存故x的位置，编译器没有办法在运行 程序之前预先确定所有这些位置。 1.6.2环撞与状态 我们在讨论程序设计语言时必须了解的另一个重要区别是在程序运行时发生的改变是否会
6 第！掌 影响数据元素的值，还是影响了对那个数据的名字的解释。比如，执行像×=y+1这样的赋值 语句会改变名字x所指的值。更加明确地说，这个赋值改变了x所指向的内存位置上的值。 可能下面这一点就不是那么明显了。即x所指的位置也可能在运行时刻改变。比如，我们在例 1.3中讨论过，如果x不是一个静态（或者说“类”）变量，那么这个类的每一个对象都有它自己的分 配给变量x的实例的位置。这种情况下，对x的赋值可能会改变那些“实例”变量中的某一个变量的 值，这取决于包含这个赋值的方法作用于哪个对象 环境 状态 名字和内存（存储）位置的关联，及之后和值的关联可以用两 个映时来描述。这两个映射随若着程序的运行而改变（见图18）。 名 1)环境(en nment)是一个从名字到存储位置的映射。 因为变量就是指内存位置（即C语言中的术语“左值”），我们 图18从名字到值的两步映射 还可以换一种方法，把环境定义为从名字到变量的映射。 2)状态(sate)是 个从内存位置到它们的值的映射。以C语言的术语来说，即状态把左值 映射为它们的相应右值。 环境的改变需要遵守语言的作用域规侧， 例1④考虑图19中的C程序片断。整数i被声明为一个全局变量，同时也被声明为局部于 函数∫的变量。执行∫时，环境相应地调整，使得名字i指向那个为局部于∫的那个所保留的存 储位置，日的所有使用（如图中明确显示的赋值语句1=3）都指向这个位局部的通营站 赋予一个运行时刻栈中的位置 只要当一个不同于∫的函数g运行时，i的使用就不能指向那个局部于∫的i。在函数g中对 名字的使用必须位于其他某个对i的声明的作用域内。 一个例子是图中明确显示的赋值语句 ×=1+1,它位于某个其定义没有在图中显示的过程中。可以假定i+1中的i指向全局的i。和 大多数语言一样，C语言中的声明必须先于其使用， 因此在全局：的声明之前的函数不能指向它。 int: :金局 图18中的环境和状态映射是动态的，但是也 有一些例外。 /:局部 1)名字到位置的静态绑定与动态绑定。大部分 /。对局部的使用， 从名字到位置的绑定是动态的。我们在这一节中讨 论了这种绑定的几种方法。某些声明（比如图19中 的全局变量)可以在编译器生成目标代码时一劳永 x=1+1 对会局的使用+/ 逸地分配一个存储位置。日 2)从位置到值的静态绑定与动态绑定 一般来 图19名字i的两个声明 说，位置到值的绑定（图18的第二阶段）也是动态的，因为我们无法在运行一个程序之前指出一 个位置上的值。被声明的常量是一个例外。比如，C语言的定义 sdetine ARrAYsIzE 1000 把名字ARRAYSIZE静态地绑定为值1000。我们看到这个语句就可以知道这个绑定关系，并且知 道在程序运行时刻这个绑定不可能改变。 合生大米林.G西含分根一五 物地址中的什么地方 过程没有影响。我们法 如下的方式处现地址空问题
引论 17 1.6.3静态作用域和块结构 包括C语言和它的同类语言在内的大多数语言使用静态作用域。C语言的作用域规则是基 于程序结构的，一个声明的作用城由该声明在程序中出现的位置隐含地决定。稍后出现的语言， 比如C++、Java和C#,也通过诸如public、private和protected等关键字的使用，提供了对作用 城的明确控制。 在本节中，我们将考虑块结构语言的静态作用城规则，其中块(k)是声明和语句的一个组 合。C使用括号和来界定一个块。另一种为同一目的使用begin和end的方法可以追湖到Alg@l。 名字、标识符和变量 虽然术语“名字”和“变量”通常指的是同一个事物，我们还是要很小心地使用它们，以便 区别编译时刻的名字和名字在运行时刻所指的内存位置 标识符(identifier)是一个学符串，通常由字母和数字组成。它用来指向（标记）一个实体 比如一个数据对象、过程、类，或者类型。所有的标识符都是名字，但并不是所有的名字都是 标识符。名字也可以是 一个表达式。比如名字xy可以表示x所指的一个结构中的字段y。 这里，x和y是标识符，而xy是一个名字。像xy这样的复合名字称为受限名字(qualifi©d name） 变量指向存储中的某个特定的位置。同一个标识符被多次声明是很常见的事情，每一个 这样的声明引入一个新的变量。即使每个标识符只被声明一次，一个递归过程中的局部标识 符将在不同的时刻指向不同的存储位置。 例15C语言的静态作用城策略可以概述如下： 1)一个C程序由一个顶层的变量和函数声明的序列组成。 2)函数内部可以声明变量，变量包括局部变量和参数。每个这样的声明的作用域被限制在 它们所出现的那个函数内。 3)名字x的一个顶层声明的作用域包括其后的所有程序。但是如果一个函数中也有一个x 的声明，那么函数中的那些语句就不在这个顶层声明的作用域内。 还有一些关于C语言的静态作用域策略的细节用来处理语句中的变量声明。我们将在接下 来的内容中，以及在例1.6中查看这样的声明。 回 过程、函数和方法 为了避免总是说“过程、函数或方法”，每次我们要讨论一个可以被调用的子程序时，我 们通常把它们统称为“过程”。但是当明确地讨论某个语言（比如C)的程序时有一个例外。因 为C语言只有函数，所以我们把它们称为“函数”。或者，如果我们讨论像Java这样的只有 “方法”的语言时，我们就使用这个术语。 个函数通常返回某个类型（即“返回类型”）的值，而一个过程不返回任何值。C和类似 的语言只有函数，因此它们把过程当作是具有特殊返回类型“void”的函数来处理。“void"表 示没有返回值。像av和C+这样的面向对象语言使用术语“方法”。这些方法可以像函数 或者过程一样运行，但是总是和某个特定的类相关联。 在C语言中。有关块的语法加下 1)块是一种语句。块可以出现在其他类型的语句（比如赋值语句）所能够出现的任何地方