引论 23 客们发现的多种入侵方式之一的伤害 ·作用城规则：一个x的声明的作用域是一段上下文，在此上下文中对x的使用指向这个声 明。如果仅仅通过阅读某个语言的程序就可以确定其作用域，那么这个语言就使用了静 态作用城，或者说词法作用城。否则这个语言就使用了动态作用域。 ·环境：名字和内存位置关联，然后再和值相关联。这个情况可以使用环境和状态来描述。 其中环境把名字映射成为存储位置，而状态则把位置映射到它的值 。块结构：允许语句块相互按套的语言称为块结构的语言。假设一个块中有一个x的声明 D,而怅套于这个块中的块B中有一个对名字x的使用。如果在这两个块之间没有其他声 明了x的块，那么这个x的使用位于D的作用域内。 。参数传递：参数可以通过值或引用的方式从调用过程传递给被调用过程。当通过值传递 方式传递大型对象时，实际被传递的值是指向这些对象本身的引用。这样就变成了一个 高效的引用调用。 ·别名：当参数被以引用传递方式（高效地）传递时，两个形式参数可能会指向同一个对象。 这会造成一个变量的修改改变了另一个变量的值。 1.8第1章参考文献 对于在1967年之前被开发并使用的程序设计语言（包括Fortran、Alg@l、Lip和Simula)的发 展历程见[7]。对于1982年前被创建的语言（包括C、C++、Pascal和Smalltalk)见[1]。 GNU编译器集合gcc(GNU Compiler Collection)是C、C++、Fortran、Java和其他语言的开源 编译器的流行源头[2]。Phoenix是一个编译器构造工具包，它提供 一个集成的框架，用于建立 本书中提到的编译器的程序分析、代码生成和代码优化步骤[3]。 要获取更多的关于程序设计语言概念的信息，我们推荐[5,6]。要知道更多的关于计算机体 系结构信息，以及体系结构是如何影响编译的，我们建议阅读[4]。 1.Bergin,T.J.and R.G.Gibson,History of Programming Languages,ACM Press.New York.1996. 2.http://gcc.gnu.org/ 3.http://research.microsoft.com/phoenix/default.aspx 5 Scott M I Pr ge Pragmatics,second edition,Morgan- Kaufmann.San Francisco.CA.2006. 6.Sethi,R.,Programming Languages:Concepts and Constructs,Addison- Wesley,1996. 7.Wexelblat,R.L.History of Programming Languages,Academic Press, New York,1981
第2章 一个简单的语法制导翻译器 本章的内容是对本书第3章至第6章中介绍的编译技术的总体介绍。通过开发一个可运行 的Java程序来演示这些编译技术。这个程序可以将具有代表性的程序设计语言语句翻译为三地 址代码（一种中间表示形式）。本章的重点是编译器的前端，特别是词法分析、语法分析和中间 代码生成。在第7章和第8章将介绍如何根据三地址代码生成机器指令。 我们从小事做起，首先建立一个能够将中缀算术表达式转换为后缀表达式的语法制导翻译 器。然后我们将扩展这个翻译器，使它能将某些程序片段（如图21所示）转换为如图22所示的 三地址代码。 x-a):ai]=a(l:a[j)x 图2.1一个将被翻译的代码片段 这个可运行的Java程序见附录A。使用Java比较方便，但并非必须用Java。实际上，本章中 描述的思想在Java和C语言出现之前就存在了。 1:1m1+1 2.1引言 编译器在分析阶段把一个源程序划分成各个组成部分 并生成源程序的内部表示形式。这种内部表示称为中间代 码。然后，编译器在合成阶段将这个中间代码翻译成目标 程序。 分析阶段的工作是围绕着待编译语言的“语法”展开的 9012 一个程序设计语言的语法(syntax)描述了该语言的程序的正 at33-x 确形式，而该语言的语义(semantics)则定义了程序的含义，即 每个程序在运行时做什么事情。我们将在2.2节中给出一个 图22与图21中程序片段对应的 广范使用的表示方法来描述语法，这个方法就是上下文无关 经过简化的中间代码表示 文法或BNF(Backus-Naur范式)。使用现有的语义表示方法来 描述一个语言的语义的难度远远大于描述语言的语法的难度。因此，我们将结合非形式化描述 和启发性的示例来描述语言的语义 上下文无关文法不仅可以描述一个语言的语法，还可以指导程序的翻译过程。在23节中。 我们将介绍一种面向文法的编译技术，即语法制导朝译(syntax-.directed translation)技术。语法扫 描，或者说语法分析，将在2.4节中介绍
一个简单的语法制导翻译器 25 本竟的其金部分将快谏测览一下图23所示的编译器前物模型。我们将首先介绍语法分折 器。为简单起见，我们首先考虑从中缀表达式到后缀表达式的语法制导翻译过程。后缀表达式 是一种将运算符置于运算分量之后的表示方法。例如，表达式9-5+2的后缀形式是95-2+ 将表达式翻译为后缀形式的过程可以充分演示语法分析技术，同时这个翻译过程又很简单，我们 将在2.5节中给出这个翻译器的全部程序。这个简单的翻译器处理的表达式是由加、减号分隔的 数位序列，如9一5+2。我们之所以先考虑这样的简单表达式，主要目的是简化这个语法分析器 使得它在处理运算分量和运算符时只需要考虑单个字符。 源程序 调法分析器 同法单元 语法分析器 语法分析树中代码三地址代码】 生成指 符号表 图23一个编译器前端的模型 词法分析器使得翻译器可以处理由多个字符组成的构造，比如标识符。标识符由多个字符 组成，但是在语法分析阶段被当作一个单元进行处理。这样的单元称作词法单元(tokm)。例如， 在表达式cout+1中，标识符cou被当作一个单元。2.6节中介绍的词法分析器允许表达式中 出现数值、标识符和“空白字符”（空格、 do-while 制表符和换行符)。 接下来我们考虑中间代码的生成。 body 在图24中显示了两种中间代码形式。 1:1■1+1 种称为抽象语法树(abstract syntax tree) 或简称为语法树(syntax tree)。它表示了 源程序的层次化语法构。在图23的镯 b) 型中，语法分析器生成一棵语法树，它又 被进一步翻译为三地址代码。有些编译图2.4“a011+1:i1e(af1)<v):的中间代码 器会将语法分析和中间代码生成合并为一个组件 图24a中的抽象语法树的根表示整个do-hile循环。根的左子树表示循环的循环体，它仅 包含赋值语句i=i+1:,根的右子树表示循环控制条件a[i】<。在2.8节中将介绍一个构造语 法树的方法 图24h中给出了另一种常见的中间表示形式，它是一组“三地址”指令序列，图22中显示 了一个更加完整的示例。这个中间代码形式的名字源于它的指令形式：x=y即：，其中即是一 个二目运算符，y和：是运算分量的地址，x是运算结果的存放地址。三地址指令最多只执行 个运算，通常是计算、比较或者分支跳转运算。 在附录A中，我们将把本章中的技术集成在一起，构造出一个用Jav语言编写的编译器前 端。这个前端将语句翻译成汇编级的指令序列。 2.2语法定义 在这一节，我们将介绍一种用于描述程序设计语言语法的表示方法一“上下文无关文法” 或简称“文法”。在本书中，文法将被用于组织编译器前端
26 第2章 文法自然地描述了大多数程序设计语言构造的层次化语法结构。例如，Jaa中的lse语句 通常具有如下形式 if (exp ession statement else statemen 即一个if-else语句由关键字ir、左括号、表达式、右括号、一个语句、关键字ese和另一个语句连 接面成。如果我们用变量epr来表示表达式，用变量mt表示语句，那么这个构造规则可以表 示为 stmt一→if(expr）stmt else stmt 其中的箭头（一）可以读作“可以具有如下形式”。这样的规则称为产生式(production)。在一个产 生式中，像关键字if和括号这样的词法元素称为终结符号(erminal)。像cxpr和sm这样的变量 表示终结符号的序列，它们称为非终结符号(nonterminal)。 22.1文法定义 一个上下文无关文法(context-free grammar)由四个元素组成： 1)一个终结符号集合，它们有时也称为“词法单元”。终结符号是该文法所定义的语言的基 本符号的集合。 2)一个非终结精号集合，它们有时也称为“语法变量”。每个非终结符号表示一个终结符写 串的集合。我们将在后面介绍这种表示方法。 3)一个产生式集合，其中每个产生式包括一个称为产生式头或左部的非终结符号，一个箭 头，和一个称为产生式体或右都的由终结符号及非终结符号组成的序列。产生式主要用来表示 某个构造的某种书写形式。如果产生式头非终结符号代表一个构造，那么该产生式体就代表了 该构造的一种书写方式。 4)指定一个非终结符号为开始符号 词法单元和终结符号 在编译器中，词法分析器读入源程序中的字符序列，将它们组织为具有词法含义的词素 生成并输出代表这些词素的词法单元序列。词法单元由两个部分组成：名字和属性值。词法 单元的名字是语法分析器进行语法分析时使用的抽象符号。我们常常把这些词法单元名字称 为终站符号，因为它们在描述程序设计语言的文法中是以终结符号的形式出现的。如果词法 单元具有属性值，那么这个值就是一个指向符号表的指针，符号表中包含了该词法单元的附 加信息。这些附加信息不是文法的组成部分，因此在我们讨论语法分析时，通常将词法单元 和终结符号当做同义词 在描述文法的时候，我们会列出该文法的产生式，并且首先列出开始符号对应的产生式。我 们假设数位、符号（如<、<=）和黑体字符串（如whil)都是终结符号。斜体字符串表示非终结 符号，所有非斜体的名字或符号都可以看作是终结符号。为表示方便，以同一个非终结符号为 头部的多个产生式的体可以放在一起表示，不同体之间用符号（读作“或”）分隔 例2.1在本章中，有多个例子使用由数位和+、-符号组成的表达式，比如9-5+2,3-1或 ?。由于两个数位之间必须出现+或-，我们把这样的表达式称为“由+、~号分隔的数位序 日单个斜体字母在第4章中详细讨论文法时另有它用。例如，我们将使用X,Y和Z来表示终结符号或非终结符号。 但是，包含两个或两个以上字符的任何斜体名字仍然表示一一个非终结符号
一个简单的语法制导翻译器 27 列”。下面的文法描述了这种表达式的语法。此文法的产生式包括： lit-→it+digit (2.1 lit→lit-dig (2.2) list-digit (2.3) dig-+0111213141516171819 (2.4) 以非终结符号为头部的三个产生式可以等价地组合为： li一→liu+digit list-digit digi 根据我们的习惯，该文法的终结符号包括如下符号 -0123456789 该文法的非终结符号是斜体名字s和dig。因为：的产生式首先被列出，所以我们知道 m是此文法的开始符号。 如果某个非终结符号是某个产生式的头部，我们就说该产生式是该非终结符号的产生式。 一个终结符号串是由零个或多个终结符号组成的序列。零个终结符号组成的串称为空串（©mpy tring),记为e白 2.2.2推导 根据文法推导符号串时，我们首先从开始符号出发，不断将某个非终结符号楼换为该非终结 符号的某个产生式的体。可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的 语言(language)。 例2.2由例2.1中的文法定义的语言是由加减号分隔的数位列表的集合。非终结符号dg的 0个产生式使得dig可以表示0、1、·、9中的任意数位。根据产生式(2.3)，单个数位本身就 是一个。产生式(2.1)和(2.2)表达了如下规则：任何列表后跟一个符号+或-以及另一个数 位可以构成一个新的列表。 产生式(2.1)-(2.4)就是我们定义所期望的语言时需要的全部产生式。例如，我们可以按 照如下方法推导出9-5+2是一个i。 1)因为9是dg,根据产生式(2.3)可知9是i缸 2)因为5是dig,且9是，由产生式(2.2)可知9-5也是。 3)因为2是dig,9-5是lit,由产生式(2.1)可知，9-5+2也是li。 例2.3另一种稍有不同的列表是函数调用中的参数列表。在Jaa中，参数是包含在括号中 的，例如max(x,y)表示使用参数×和y调用函数ma×。这种列表的一个微妙之处是终结符 号“(”和“)”之间的参数列表可能是空串。我们可以为这样的序列构造出具有如下产生式的 文法： ams） params,paramparam 注意，在optparam(“可选参数列表")的产生式中，第二个可选规则体是∈，它表示空的符 号串。也就是说，pparams可以被替换为空串，因此一个cal可以是函数名加上两个终结符号 “(”和“)”组成的符号串。请注意，params的产生式和例2.1中i的产生式类似，只是将算术运 算符+或-换成了逗号，并将dig进换成param。函数参数实际上可以是任意表达式，但是在这里 日从技术上讲，《可以是任意字母表（符号的集合）上的零个符号组成的串