X 12.2.4语句的执行顺序 343 12.3依赖关系. 12.3.1依赖关系定义. ,345 12.3.3 依赖距离、，依赖方向与依赖层次 348 12.4依赖关系问题. 12.5依越关系测试. 4+4*35S6 12.6 循环的向量化与并行化 ·364 12.7循环变换技术. ”369 练 习0 m.381 参考文献 .38%
第一章引 论 1.1什么叫编译程序 使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算 的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配 置了儿个不同性能的编译程序，供用户按不同需要进行选择。高级语言编译程序是计算 机系统软件最重要的组成部分之一，也是用户最直接关心的工具之一。 在计算机上执行一个高级语言程序一般要分为两步：第一步，用一个编译程序把高级 语言翻译成机器语育程序；第二步，运行所得的机器语言程序求得计算结果。 通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为源语言程 序)转换成另一种语言程序（称为目标语言程序），而后者与前者在逻辑上是等价的。如果 源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这样的“高级语言”，而目标语 言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程 序。 高级语言程序除了像上面所说的先编译后执行外，有时也可“解释”执行。一个源语 言的解释程序是这样的程序，它以该语言写的源程序作为输人，但不产生目标程序，而是 边解释边执行源程序本身。本书将不对解释程序作专门的讨论。实际上，许多编译程序 的构造与实现技术同样适用于解释程序。 根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试 的编译程序称为诊断编译程序(Compiler),着重于提高目标代码效率的编译程序 叫优化编译程序(Optimizing Compiler）。现在很多编译程序同时提供了调试、优化等多种 功能，用户可以通过“开关”进行选择。运行编译程序的计算机称宿主机，运行编译程序所 产生目标代码的计算机称目标机。如果 个编译程序产生不同于其宿主机的机器代码 则称它为交叉编译程序(Cro Compiler)。如果不需重写编译程序中与机器无关的部分就 能改变目标机，则称该编译程序为可变目标编译程序(Returgetable Compiler）。 世界上第一 个编译程序 -FORTRAN编译程序是20世纪50年代中期研制成功的 当时，人们普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情。经过40年 的努力，编译理论与技术得到迅速发展，现在已形成了一套比较成熟的、系统化的理论与 方法，并且开发出了一些好的编译程序的实现语言、环境与工具。在此基础上设计并实现 一个编译程序不再是高不可攀的事情。 本书主要介绍设计和构造编译程序的基本原理和方法。我们不想罗列太多细节性的 材料，着重讲-一些原理性的东西，但将反映一些最新的进展
1.2编译过程概述 编译程序的工作，从输人源程序开始到输出目标程序为止的整个过程，是非常复杂 的。但就其过程而言，它与人们进行自然语言之间的翻译有许多相近之处。当我们把 种文字翻译为另一种文字，例如把一段英文翻译为中文时，通常需经下列步骤： (1)识别出句子中的 个个单词 (2)分析句子的语法结构： (3)根据句子的含义进行初步翻译 (4)对译文进行修饰 (5)写出最后的译文。 类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义 分析与中间代码产生、优化、目标代码生成。 第一阶段，词法分析。词法分析的任务是：输人源程序，对构成湖程序的字符串进行 扫描和分解，识别出-一个个的单词（亦称单词符号或简称符号），如基本字(begn、end、if、 for、while等)，标识符、#数、算符和界符（标点符号、左右括号等等）。例如，对于Pascal的 循环语句 for I:=1 to 100 do 词法分析的结果是识别出如下的单词符号： 基本字 for 标识符 赋值号 1三 整常数 基本字 整常数 100 基本字 a 这些单词是组成上述Pc语句的基本符号。单词符号是语言的基本组成成分，是人们 理解和编写程序的基本要素。识别和理解这些要素无疑也是翻译的基础。如同将英文面 译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。在词法分 析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效工具 是正规式和有限自动机。 第二阶段，语法分析。语法分析的任务是：在词法分析的基础上，根据语言的语法规 则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子“(“语句”)、 “程序段”和“程序”等。通过语法分析，确定整个输人串是否构成语法上正确的“程序 语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析 是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串 Z:=X+0.618￥Y 代表一个“赋值语句”，而其中的X+0.618￥Y代表一个“算术表达式”。因而，语法分析 的任务就是识别X+0.618*Y为算术表达式，同时，识别上述整个符号串属于赋值语句
3 这个范畴 第三阶段，语义分析与中间代码产生。这一阶段的任务是：对语法分析所识别出的各 类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。这一阶段通常包括两个方面 的工作。首先，对每种语法范畴进行静态语义检查，例如，变量是否定义类型是否正确等 等。如果语义正确，则进行另一方面工作，即进行中间代码的翻译。这一阶段所依循的是 语言的语义规则。通常使用属性文法描述语义规则。 “翻译”仅仅在这里才开始涉及到。所谓“中间代码”是一种含义明确、便于处理的记 号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种 程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。例如，许多编译程 序采用了一种与“三地址指令”非常近似的“四元式”作为中间代码。这种四元式的形式 是： 算符 左操作数 右操作数 结果 它的意义是：对“左，右操作数”进行某种运算（由“算符”指明），把运算所得的值作为“结 果”保留下来。在采用四元式作为中间代码的情形下，中间代码产生的任务就是按语言的 语义规则把各类语法范睛翻译成四元式序列。例如，下面的赋值句 Z:三(X+0.418)*Y/W 可被翻译为如下的四元式序列： 序号 算符 左操作数 右操作数 结果 (1) + 0.418 T Y T (3) W 其中，T和T2是编译期间引进的临时工作变量：第一个四元式意味着把X的值加 0.418存放于①，中：第二个四元式指将T,的值和Y的值相乘存于T2中：第三个四元式指 将飞2的值除以Y的值留结果于Z中。 一般而言，中间代码是一种独立于具体硬件的记号系统。常用的中间代码，除了四元 式之外，还有三元式间接三元式逆波兰记号和树形表示等等。 第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工变换，以期在最后 阶段能产生出更为高效（省时间和空间）的目标代码。优化的主要方面有：公共子表达式 的提取、循环优化、除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并 行化处理。优化所依循的原则是程序的等价变换规则。例如，如果我们把程序片断 for K:=1 to 100 do begin M.=】+100K: N:=J+10*K end
的中间代码 序号 OP ARGI ARG2 RESULT 解 (1) K:1 (2) j< 100 K (9) 若100<K转至第(9)个四元式 (3) K T:=0*K;T为临时变量 M M:=I+T (5) K T2:=10“k:2为临时变量 (6) N:cJ+T (7) + K K:=K+1 (8) 转至第(2)个四元式 (9) 转换成如下的等价代码： 序号 OP ARGI ARG2 RESULT 翻 1) := M:=I N N:=J (3) 小 K:=1 (4 K i100<k)oto(9) M 10 M:=M+10 (6) 0 N:=N+10 (7) + 1 卡 K:=K+1 go(4) (9) 那么，最终所得的目标程序的执行效率就肯定会提高很多。因为，对于前者，在循环中需 做300次加法和200次乘法；对于后者，在循环中只需做300次加法。尤其是，在多数硬件 中，乘法的时间比加法的时间要长得多。 第五阶段，目标代码生成。这一阶段的任务是：把中间代码（或经优化处理之后）变换 成特定机器上的低级语言代码。这阶段实现了最后的翻译，它的工作有赖于硬件系统结 构和机器指令含义。这阶段工作非复杂，涉及到硬件系统功能部件的运用，机器指令的 选择，各种数据类型变量的存储空间分配，以及寄存器和后援寄存器的调度，等等。如何 产生出足以充分发挥硬件效率的目标代码是一件非常不容易的事情。 目标代码的形式可以是绝对指令代码或可重定位的指令代码或汇编指令代码。如目 标代码是绝对指令代码，则这种目标代码可立即执行。如果目标代码是汇编指令代码，则 需汇编器汇编之后才能运行。必须指出，现代多数实用编译程序所产生的目标代码都是 一种可重定位的指令代码。这种目标代码在运行前必须借助于一个连接装配程序把各个