引论 3 间表示之上进行转换，以便后端程序能够生成更好的目标程序。如果基于未经过此优化步骤的 中间表示来生成代码。则代码的质量会受到影向 因为优化是可选的，所以图16中所示的两个优化 字符液 词法分析器 北骤之一可以被省略。 1.2.1词法分析 符号 编译器的第一个步警称为词法分折(1 exica ■ 语法分析☐ analysis)或扫描(scanning)。词法分析器读人组成 语法树 源程序的字符流，并且将它们组织成为有意义的词 语义分析 素(lexeme)的序列。对于每个词素，词法分析器产 生如下形式的词法单元(token)作为输出 语法树 token-name,attribute-value) 符号表 中钢代码生成静 这个词法单元被传送给下一个步骤，即语法分 中闻表示形式 析。在这个词法单元中，第 一个分量token-name是 机器无关代码优化器 一个由语法分析步骤使用的抽象符号，而第二个分 中间表示形式 量attribute-vaue指向符号表中关于议个词法单元 的条目。符号表条目的信息会被语义分析和代码生 ■ 代码生成器 成步骤使用。 日标机器语言 比如，假设一个源程序包含如下的赋值语句 机器相关代码优化器 (1.1) 日标机器语言 这个赋值语句中的字符可以组合成如下词素， 并映射成为如下词法单元。这些词法单元将被传递 图1-6一个编译器的各个步骤 给语法分析阶段。 I)position是一个词素，被映射成词法单元(id,),其中id是表示标识符(identifier)的 抽象符号，而1指向符号表中p0 sition对应的条目。一个标识符对应的符号表条目存放该标 识符有关的信息，比如它的名字和类型。 2)赋值符号=是一个词素，被映射成词法单元(=)。因为这个词法单元不需要属性值，所 以我们省略了第二个分量。也可以使用assign这样的抽象符号作为词法单元的名字，但是为了 标记上的方便，我们选择使用词素本身作为抽象符号的名字】 3)initial是一个词素，被映射成词法单元(id,2),其中2指向1 nitia1对应的符号表 条目。 4)+是一个词素，被映射成词法单元(+)。 5)rate是一个词素，被映射成词法单元(id,3》,其中3指向rate对应的符号表条目。 6)*是一个词素，被映射成词法单元(*。 7)60是一个词素，被映射成词法单元(60)9 分隔词素的空格会被词法分析器忽略掉。 图17给出经过词法分析之后，赋值语句1.1被表示成如下的词法单元序列： (id.1)(=》(id.2)(+)(d,3)(*)(60》 (1.2) 在这个表示中，词法单元名=、+和◆分别是表示赋值、加法运算符、乘法运算符的抽象符号。 日从技术上讲，我们应该为语法单元60建立一个形如(umb,4)的词法单元，其中4指向符号表中对应于整数60 的条目。但是我们要到第2章中才讨论数字的词法单元。第3章将讨论建立词法分析器的技术
4 第1章 pomition·4 nitial+rate·60 法分析器 td,1)(=)d,2)(+)id.3)()60 语法分析器■ d,1 position 0d,2r itial d.3 ·-60 7 符号表 (id,1 d,2 (id,3 60 ■ 中代生成荐 代码生成器 ￥60.0 图17一个赋值语句的翻译 1.2.2语法分析 编译器的第2个步骤称为语法分析(syntax analysis)或解析(parsing)。语法分析器使用由词 法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。该中间表示给出了词法分 析产生的词法单元流的语法结构。 ,个常用的表示方法是语法树(syntax tree),树中的每个内部 结点表示一个运算，而该结点的子结点表示该运算的分量。在图17中，词法单元流(1.2)对应 的语法树被显示为语法分析器的输出 这棵树显示了赋值语句 position initial+rate.60 中各个运算的执行顺序。这棵树有一个标号为*的内部结点，<，3>是它的左子结点，整数60 是它的右子结点。结点<id,3>表示标识符xate。标号为*的结点指明了我们必须首先把xate 的值与60相乘。标号为+的结点表明我们必须把相乘的结果和initial的值相加。这棵树的根 结点的标号为=，它表明我们必须把相加的结果存储到标识符positior对应的位置上去。这个运 算顺序和通常的算术规则相同，即乘法的优先级高于加法，因此乘法应该在加法之前计算。 绵译器的后续步骤使用这个语法结构来帮助分析题程序，并生成目标程序。在第4章，我门 将使用上下文无关文法来描述程序设计语言的语法结构，并讨论为某些类型的语法自动构造高
引 论 5 效语法分析器的算法。在第2章和第5章，我们将看到，语法制导的定义将有助于描述对程序设 计语言结构的翻译 1.2.3语义分析 语义分析器(semantie analyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义 的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中 间代码生成过程中使用。 语义分析的一个重要部分是类型检查(type checking)。编译器检查每个运算符是否具有匹配 的运算分量。比如，很多程序设计语言的定义中要求一个数组的下标必须是整数。如果用一个 浮点数作为数组下标，编译器就必须报告错误。 程序设计语言可能允许某些类型转换，这被称为自动类型转换(cocr©iom)。比如，一个二元 算术运算符可以应用于一对整数或者一对浮点数。如果这个运算符应用于一个浮点数和一个整 数，那么编译器可以把该整数转换（或者说自动类型转换）成为一个浮点数 图l7中显示了一个这样的自动类型转换。假设position、initial和rate已被声明为浮 点数类型，而词素60本身形成一个整数。图1-7中的语义分析器的类型检查程序发现运算符*被用 于一个浮点数rate和一个整数60。在这种情况下，这个整数可以被转换成为一个浮点数。请注 意，在图1-7中，语义分析器输出中有一个关于运算符into0oat的额外结点。into门oat明确地把它 的整数参数转换为…个浮点数。类型检查和语义分析将在第6章中讨论。 1.2.4中间代码生成 在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示。 这些中间表示可以有多种形式。语法树是一种中间表示形式，它们通常在语法分析和语义分析 中使用。 在源程宰的语法分析和语义分析完成之后，很多编译器生成一个明确的低级的或类机器语 言的中间表示。我们可以把这个表示看作是某个抽象机器的程序。该中间表示应该具有两个重 要的性质：它应该易于生成，且能够被轻松地翻译为目标机器上的语言。 在第6章，我们将考虑一种称为三地址代码(three~address code)的中间表示形式。这种中间 表示由一组类似于汇编语言的指令组成，每个指令具有三个运算分量。每个运算分量都像一个 寄存器。图17中的中间代码生成器的输出是如下的三地址代码序列： t1·inttof1oat(60) (1.3) 关于三地址指令，有几点是值得专门指出的。首先，每个三地址赋值指令的右部最多只有 个运算符。因此这些指令确定了运算完成的顺序。在源程序1.1中，乘法应该在加法之前完成。 第二，编译器应该生成一个临时名字以存放一个三地址指令计算得到的值。第三，有些三地址指 令的运算分量的少于三个（比如上面的序列1.3中的第一个和最后一个指令）。 在第6章，我们将讨论在不同编译器中用到的主要中间表示形式。第5章将介绍语法制导翻 译技术。这些技术在第6章中被用于处理典型程序设计语言构造进行类型检查和中间代码生成。 这些程序设计语言构造包括：表达式、控制流构造和过程调用： 1.2.5代码优化 机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码。“更好”通常意味着 更快，但是也可能会有其他目标，如更短的或能耗更低的目标代码。比如，一个简单直接的算法会 生成中间代码(1.3)。它为由语义分析器得到的树形中间表示中的每个运算符都使用一个指令
6 第1章 使用一个简单的中间代码生成算法，然后再进行代码优化步骤是生成优质目标代码的一个 合理方法。优化器可以得出结论：把60从整数转换为浮点数的运算可以在编译时刻一劳水逸地 完成。因此，用浮点数60.0来替代整数60就可以消除相应的intofloat运算。而且，t3仅被使 用一次，用来把它的值传递给i1。因此，优化器可以把序列(1.3)转换为更短的指令序列 1=1d360.0 (1.4) 不同的编译器所做的代码优化工作量相差很大。那些优化工作做得最多的编译器，即所谓的 “优化编译器”，会在优化阶段花相当多的时间。有些简单的优化方法可以极大地提高目标程序的运 行效率而不会过多降低编译的速度。从第8章开始，将详细讨论机器无关和机器相关的优化。 1.2.6代码生成 代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言。如果目标语言是 机器代码，那么就必须为程序使用的每个变量选择寄存器或内存位置。然后，中间指令被翻译成 为能够完成相同任务的机器指令序列。代码生成的一个至关重要的方面是合理分配寄存器以存 放变量的值。 比如，使用寄存器1和R2,(1.4)中的中间代码可以被翻译成为如下的机器代码： 86o0 (1.5) 每个指令的第一个运算分量指定了一个目标地址。各个指令中的卫告诉我们它处理的是浮 点数。代码(1.5)把地址13中的内容加载到寄存器2中，然后将其与浮点常数60.0相乘。井 号“#"表示60.0应该作为一个立即数处理。第三个指今把12移动到寄存器1中，而第四个指 令把前面计算得到并存放在R2中的值加到R1上。最后，在寄存器R1中的值被存放到id1的地 址中去。这样，这些代码正确地实现了赋值语句(1.1)。第8章将讨论代码生成 上面对代码生成的讨论忽略了对源程序中的标识符进行存储分配的重要问题。我们将在第7 章中看到，运行时刻的存储组织方法依赖于被编译的语言。编译器在中间代码生成或代码生成 阶段做出有关存储分配的决定。 1.2.7符号表管理 编译器的重要功能之一是记录源程序中使用的变量的名字，并收集和每个名字的各种属性 有关的信息。这些属性可以提供一个名字的存储分配、它的类型、作用域（即在程序的哪些地方 可以使用这个名字的值)等信息。对于过程名字，这些信息还包括：它的参数数量和类型、每个 参数的传递方法（比如传值或传引用）以及返回类型。 符号表数据结构为每个变量名字创建了一个记录条目。记录的字段就是名字的各个属性。 这个数据结构应该允许编译器迅速查找到每个名字的记录，并向记录中快速存放和获取记录中 的数据。符号表在第2章中讨论 1.2.8将多个步骤组合成趟 前面关于步骤的讨论讲的是 一个编译器的逻辑组织方式。在 一个特定的实现中，多个步 的活动可以被组合成一趋(ss)。每趟读人一个输人文件并产生一个输出文件。比如，前端步骤 中的词法分析、语法分析、语义分析，以及中间代码生成可以被组合在一起成为一趟。代码优化 可以作为一个可选的趟。然后可以有一个为特定目标机生成代码的后端。 有些编译器集合是围绕一组精心设计的中间表示形式而创建的，这些中间表示形式使得我 们可以把特定语言的前端和特定目标机的后端相结合。使用这些集合，我们可以把不同的前端
引论 7 和某个目标机的后端结合起来，为不同的源语言建立该目标机上的编译器。类似地，我们可以把 一个前端和不同的目标机后端结合，建立针对不同目标机的编译器。 1.29编译器构造工具 和任何软件开发者一样，写编译器的人可以充分利用现代的软件开发环境。这些环境中包 含了诸如语言编辑器、调试器、版本管理、程序描述器、测试管理等工具。除了这些通用的软件 开发工具，人们还创建了一些更加专业的工具来实现编译器的不同阶段。 这些工具使用专用的语言来描述和实现特定的组件，其中的很多工具使用了相当复杂的算 法。其中最成功的工具都能够隐藏生成算法的细节，并且它们生成的组件易于和编译器的其他 部分相集成。一些常用的编译器构造工具包括： 1)语法分析器的生成器：可以根据一个程序设计语言的语法描述自动生成语法分析器 2)扫描器的生成器：可以根据一个语言的语法单元的正则表达式描述生成问法分析器。 3)语法制果的翻译引整，可以生成一组用于璃历分析树并生成中间代码的例程。 4)代码生成器的生成器：依据一组关于如何把中间语言的每个运算翻译成为目标机上的机 器语言的规则，生成一个代码生成器。 5)数据流分析引擎：可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递 到另一部分。数据流分析是代码优化的一个重要部分。 6)编译器构造工具集·提供了可用于物造编泽器的不同阶段的例程的完整集合」 在本书中，我们将讨论多个这类工具的例子。 1.3程序设计语言的发展历程 第一台电子计算机出现在20世纪40年代。它使用由0、1序列组成的机器语言编程，这个 序列明确地告诉计算机以什么样的顺序执行哪些运算。运算本身也是很低层的：把数据从一个 位置移动到另一个位置，把两个寄存器中的值相加 比较两个值，等等。不用说，这种编程速度 慢且枯燥，而且容易出错。写出的程序也是难以理解和修改的。 1.3.1走向高级程序设计语言 走向更加人类友好的程序设计语言的第一步是20世纪50年代早期人们对助记汇编语言的 开发。一开始， 一个汇编语言中的指令仅仅是机器指令的助记表示。后来，宏指令被加人到汇编 语言中。这样，程序员就可以通过宏指令为额繁使用的机器指令序列定义带有参数的缩写。 走向高级程序设计语言的重大一步发生在20世纪50年代的后五年。其间，用于科学计算的 Fortran语言，用于商业数据处理的Cobol语言和用于符号计算的Lisp语言被开发出来。在这些语 言的基本原理是设计高层次表示方法，使得程序员可以更加容易地写出数值计算、商业应用和构 号处理程序。这些语言取得了很大的成功，至今仍然有人使用它们。 在接下来的几十年里，很多带有新特性的程序设计语言被陆续开发出来。它们使得编程更 加容易、自然，功能也更强大。我们将在本章的后面部分讨论很多现代程序设计语言所共有的 些关键特征。 当前有几千种程序设计语言。可以通过不同的方式对这些语言进行分类。方式之一是通过 语言的代来分类。第一代语言是机器语言，第二代语言是汇编语言，而第三代语言是Fortran Cobol、Lisp、C、C++、C#及Java这样的高级程序设计语言。第四代语言是为特定应用设计的语 言，比如用于生成报告的NOMAD,用于数据库查询的SQL和用于文本排版的Postscript。术语第 五代语言指的是基于逻辑和约束的语言，比如Pr0log和OPS5