名 九语言 B代 L语 B代 代码上语言L语者 B代B代码 L语百L语言 A代码A代两 A代 图1.5编译程序“移植” 个编译程序。这种通过一系列自展途径而形成编译程序的过程叫做自编译过程。 现在人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于 自动产生扫描器（如EX),有些可用于自动产生语法分析器（如YACC),有些甚至可用来 自动产生整个的编译程序。这些构造编译程序的工具称为编译程序一编译程序、编译程 序产生醫或译程序书写系统，它们是按对源程序和目标语言（或机器）的形式描述（作为 输入数据)而自动产生编译程序的。 最后，我们来谈一谈如何学习构造编译程序。要在某一台机器上为某种语言构造一 个编译程序，必须掌握下述三方面的内容： (I)源语言，对被编译的源语言（如FORTRAN、Pascal或C),要深刻理解其结构（语法） 和含义（语义）： (2)目标语言，假定目标语言是机器语言，那么，就必须搞清楚硬件的系统结构和操 作系统的功能； ,(3)编译方法，把一种语言程序翻译为另一种语言程序方法很多，但必须准确地掌握 本课程是讲编译方法的，并且主要是讨论FORTRAN、Pascal、C之类强制式语言的编 译技术，同时也将介绍一些有关面向对象语言编译和并行化编译的内容。尽管假设读者 对这些语言已有一定的基本知识，但为了衔接，第二章，我们仍将复习一下高级语言的基 本概念。 在本门课中，我们并不假定以某种特定机器作为目标机器。当需要涉及目标指令时 将采用-一些人所共知的假想指令。因此，在学习这门课之前，读者必须具有计算机基础程 序设计的知识。 由于编译程序是一个极其复杂的系统，放在讨论中，只好把它肢解开来，一部分一部 分地进行研究。因此，在学习过程中应注意前后联系，切忌用静止的、弧立的观点看待问 题。作为一门技术课程，学习时务必注意理论联系实际，多做练习，多多实践。要加强实 践教学环节，学完这门课后，学生们应能实现一个小编译程序（如Pc语言子集的编译 程序)。有关实践方面的讨论，可参阅参考文献46。 本书中所使用的具体算法有些是用文字描述的，有些是用类似Pcl的语言表示的 所有这些算法都是原理性和解释性的，而且大多是不完备的（忽略某些次要因素或尚未学 到的成分)。因此，并不意味著着这些算法可以直接照抄使用
11 在着手构造一个编译程序时，需要预先考虑种种具体因素[诸如，系统功能要求（这种 要求常常是多方面的)、硬件设备、软件工具等等]，特别是必须估量所有这些因素对编译 程序构造的影响。虽然这些都是工程实现时应予考惑的细节，但因篇幅所限，不可能涉及 太多。 后面，在复习高级语言的基本概念之后，我们将按照1.2节所说的编译过程的各基本 阶段，逐步介绍编译程序的构造方法和技术
第二章高级语言及其语法描述 本章概述高级程序语言的结构和主要的共同特征，并介绍程序语言的语法描述方法。 要学习和构造编译程序，理解和定义高级程序语言是必不可少的。 高级程序语言是用来描球算法和计算机实现这双重日的的。日前，世跟上口右的启 级语言至少上千种，在较大的范围内得到使用的语言也有几十种甚至上百种。从应用角 度看，它们各有不同的侧重面。例如，FORTRAN宜于数值计算，COBOL宜于事务处理， PROLOG适合于人工智能，Ada适合于大型嵌人式实时处理，SNOBOL则更利于符号处理。 从语言范型来分，高级程序语言可分为强制式语言、作用式语言、基于规则的语言和面向 对象语言等。 2.1程序语言的定义 任何语言实现的基础是语言定义。语言用户把语言定义理解为用户手册，例如语言 初等成分的实际含义是什么？如何有意义地使用它们？怎样以有意义的方式组合它们？ 另一方面，编译程序研制者则对哪些构造允许出现更感兴趣。他们即使一时不能看出某 种构造的实际应用，或者判断实现该结构会导致严重的困雅，但仍必须严格根据语言的定 义实现它。程序设计教科书中的语言描述侧重于语言成分的意义，它常常只讲到语言的 部分，因此，不能把这种描述作为构造编译程序的基础。 个程序语言是一个记号系统。如同自然语言一样，程序语言主要由语法和语义两 个方面定义。有时，语言定义也包含语用信息，语用主要是有关程序设计技术和语言成分 的使用方法，它使语言的基本概念与语言的外界（如数学概念或计算机的对象和操作）联 系起来。我们在这里重点讨论语法和语义。 2.1.1语法 任何语言程序都可看成是一定字符集（称为字母表）上的一字符串（有限序列）。但 是，什么样的字符串才算是一个合式的程序呢？所谓一个语言的语法是指这样的一组规 则，用它可以形成和产生一个合式的程序。这些规则的一部分称为词法规则，另一部分称 为语法规则（或产生规则）。 例如，字符申0.5*X1+C,通常被看成是常数0.5、标识符X1和C,以及算符和+ 所组成的一个表达式。其中常数0.5'，标识符X1'和‘C',算符·￥’和‘+称为语言的 单词符号，而表达式0.5*X1+C'称为语言的一个语法范，或语法单位。 语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符申是 一个单词符号
13 一个程序语言只使用一个有限字符集作为字母表。 例如Paacal的字母表中含有26 个英文字母A,B,C,.,X,Y,Z10个数字0,1，.，9：以及20个其它字符：空白，+，-， ,/.=，<。>《)「1}}.。：。4 单词符号是语亩中具有独立意义的最基本结构。例如，0.5'是一个“实型常数”， ‘:='在Pascal中是“赋值号”。 词法规则是指单词符号的形成规则。在现今多数程序语言中，单词符号一般包括：各 类型的常数、标识符、基本字、算符和界符等。由于单词符号本身很简单，因此形成规则也 不复杂。在第三章我们将看到，正规式和有限自动机理论是描述词法结构和进行词法分 析的有效工具。 语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法 规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函数、 过程和程序等等。 如何描述一个程序语言的语法规则呢？描述语法规则一般是很不容易的。但就现今 的多数程序语言来说，上下文无关文法仍是一种可取的有效工具。在本书中，有限自动机 和上下文无关文法是我们讨论词法分析和语法分析的主要理论基础。 语法单位比单词符号具有更丰富的意义。例如单词符号串0.5+7.4*14.2'代表 个算术式，具有通常的算术意义。如何定义各种语法单位的含义属于语言的语义问题。 语言的词法规则和语法规则定义了程序的形式结构，是判断输人字符串是否构成 个形式上正确（即合式）程序的依据 一般而言，程序语言的词法、语法规则并不限定程序的书写格式。但是，某些程序语 言要求程序的书写服从一定的格式，如FORTRAN,所有语句都必须写在每行8O列的一定 位受上。这种要求增加了词法分析的复杂性。现在多数语言倾向于使用自由格式书 法，容许程序员随自已的意愿编排程序格式。这既便于阅读，又可以回避因书写格式不正 确而造成的错误。 空白字符是另 一个值得注意的问题。有些语言规定，空白字符除了在文字常数中的 出现之外，在别的任何地方的出现都是没有意义的。在这种情况下，空白字符可用于编排 程序格式，但增加了词法分析的麻须。在某些语言中，空白字符用作间隔符。它们的出现 决定了单词符号的划分。 2.1.2语义 个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语 法单位的意义。这就是语义问题。离开语义，语言只不过是一堆符号的集合。在许多语 言中有着形式上完全相同的语法单位，但含义却不尽相同。例如在AGOL和FORTRAN 中，符号串 X+F(X)+Y 都代表一个“算术表达式”但含义有区别。ALGOL规定按左结合的规则计算这个表达式 的值，FORTRAN容许使用交换律和结合律来计算其值；ALGOL容许函数F(X)的计值有副 作用，但ORTRAN禁止对所在的表达式环境产生副作用。又例如，许多语言都具有如下 形式的话句：
多 for i:=E step Ea until E do S 但其含义各有不同。对于编译来说，只有了解程序的语义，我们才知道应把它翻译成什么 样的目标指令代码。 所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些 规则称为语义规则。阐明语义要比阚明语法难得多。现在还没有一种公认的形式系统， 借助于它可以自动地构造出实用的编译程序。本书将介绍的是目前大多数编译程序普遍 采用的一种方法，即基于性文法的语法制导翻译方法，虽然这还不是一种形式系统，但 它还是比较接近形式化的。 一个程序语言的基本功能是描述数据和对数据的运算。所谓一个程序，从本质上来 说是描述一定数据的处理过程。在现今的程序语言中，一个程序大体上可视为下面所示 的层次结构： 程序 子程序或分程序 函句 表达式 数据引用算符函数调用 自上而下看上述层次结构：顶端是程序本身，它是一个完整的执行单位。一个程序通 常是由若干个子程序或分程序组成的，它们常常含有自己的数据（局部名） ,于程序或分 程序是由语句组成的。而组成语句的成分则是各种类型的表达式。表达式是描述数据运 算的基本结构，它通常含有数据引用、算符和函数调用。 自下而上看上述层次结构：我们希望通过对下层成分的理解来掌握上层成分，从而掌 握整个程序。在下节中我们将综述程序语言各层次的结构和意义。 程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。当从数学 上考虑每个组成成分时，我们注重它的逻辑意义。当从计算机这个角度来看时，我们注重 它在机内的表示和实现的可能性与效率。例如，一个表示实数的名字，从逻辑上说，可以 看成是一一个变量或一个可用于保存实数的场所；从计算机实现上说，可看成是一个或若干 个相继的存储单元，这些单元的每位都有特殊的解释（如符号位，阶码和尾数），它们能表 示一个一定大小和精度的数值。 2.2高级语言的一般特性 本节将讨论高级程序设计语言最基本的、共有的技术特性