第六章 中间代码生成

图6.24：表达式c+a[i][j]的的三地址代码 练习6.4.3：使用图6.22所示的翻译方案来翻译下列赋值语句： a) x=a[i]+b[j] b) x=a[i][j]+b[i][j] !c) x=a[b[i][j]][c[k]]

!练习6.4.4：修正图6.22中的翻译方案，使之适合Fortran风格的数组引用，也就是说，n维数组的引用为id[E1,E2,…,En]。

练习6.4.5：将公式（6.7）推广到多维数组上，并指出哪些值可以被存放到符号表中并用来计算偏移量。考虑下列的情况：

a) 一个二维数组A，按行存放。第一维的下标从l1到h1，第二维的下标从l2到h2。单个数

组元素的宽度为w。

b) 和(a)相同，但是采用按列存放方式。

！c) 一个k维的数组A，按行存放，元素宽度为w，第j维的下标从lj到hj。 ！d) 和(c)相同，但是采用按列存放方式。

符号化表示的类型宽度 中间代码应该相对独立于目标机器，这样当代码生成器被替换为另一台机器的生成器时，优化程序不需要很大的改变。然而，正如我们刚刚描述的类型宽度计算方法中显示的，关于基本类型的信息被融合到了这个翻译方案中。例如，例子6.12中假定每个整数数组的元素占4个字节。一些中间代码，如Pascal的p-code，让代码生成器来填写数组元素的大小，因此这个中间代码独立于机器的字长。只要用一个符号常量来代替翻译方案中的（作为整数类型宽度的）4，我们就可以在我们的翻译方案中同样做到这一点。 练习6.4.6：一个整数数组A[i,j]的下标i的范围从1到10，下标j的范围从1到20。每个整数占4个字节。假设数组A从0字节开始存放，请给出下列元素的位置： a) A[4,5] b) A[10,8] c) A[3,17]

练习6.4.7：假定A是按列存放的，重复练习6.4.6。

练习6.4.8：一个实数型数组A[i,j,k]的下标i的范围从1到4，j的范围从0到4，且k的范围从5到10。每个实数占8个字节。假设数组A从0字节开始存放。计算下列元素的位置。 a) A[3,4,5] b) A[1,2,7] c) A[4,3,9]

练习6.4.9：假定A是按列存放的，重复练习6.4.8。

6.5 类型检查

为了进行类型检查，编译器需要给源程序的每一个组成成分赋予一个类型表达式。然后，编译器需要确定这些类型表达式是否满足一组逻辑规则。这些规则被称为源语言的类型系统。

类型检查具有发现程序中的错误的功能。原则上，如果目标代码在保存元素值的同时保存了元素类型的信息，任何检查都可以动态地进行。一个健全的类型系统可以消除对动态类型检查的需要，因为它可以帮助我们静态地确定这些错误不会在程序运行的时候发生。如果编译器可以保证它接受的程序在运行时刻不会发生类型错误，那么该语言的这个实现就被称为强类型的。

除了用于编译，类型检查的思想还被用来提高系统的安全性，使得人们安全地导入和执行软件模块。Java程序被编译成为机器无关的字节码。在字节码中包含了有关字节码中的操作的详细类型信息。导入的代码在被允许执行之前首先要进行类型检查，以防止因疏忽造成的错误和恶意攻击。

6.5.1 类型检查规则

类型检查有两种形式：综合和推导。类型综合根据子表达式的类型构造出表达式的类型。它要求名字先声明再使用。表达式E1+E2的类型是根据E1和E2的类型定义的。一个典型的类型综合规则具有如下形式：

if f的类型为s→t 且 x的类型为s,

then 表达式f(x)的类型为t. (6.8)

这里，f和x表示表达式，而s→t表示从s到t的函数。这个针对单参数函数的规则可以推广到带有多个参数的函数。稍作修改，规则（6.8）就可以被用于E1+E2，我们只需要把它看作一个函数应用add(E1,E2)就可以了7。

类型推导根据一个语言结构的使用方式来推导该结构类型。预先看一下6.5.4节中的例子，令null是一个测试列表是否为空的函数。那么根据这个函数的使用null(x)，我们可以指出x必须是一个列表类型。列表x中的元素类型是未知的，我们所知道的全部信息是：x是一个列表类型，其元素类型当前未知。

代表类型表达式的变量使得我们可以考虑未知类型。我们可以用希腊字母α、β等等作为类型表达式中的变量。

一个典型的类型推导具有下面的形式： if f(x)是一个表达式,

then 对某些α和β, f的类型为α→β且x的类型为α (6.9)

在类似ML这样的语言中需要进行类型推导。ML语言会检查类型，但是不需要对名字进行声明。

在本节中，我们考虑表达式的类型检查。检查语句的规则和检查表达式类型的规则类似。例如，我们可以把条件语句“if (E) S;”看作是对E和S应用if函数。令特殊类型void表示没有值的类型。那么if函数将被应用在一个布尔型和一个void型的对象上；此函数的结果类型是void类型。

7

即使我们在确定类型时需要某些上下文信息，我们仍将使用“综合”这个术语。使用重载函数时，多个函数可能被赋予同一个名字。在某些语言中，我们还需要考虑E1+E2的上下文才能确定其类型规则。

6.5.2 类型转换

考虑类似于x+i的表达式，其中x类型是浮点数而i是整型。因为整数和浮点数在计算机中有不同的表示形式，而且使用不同的机器指令来操作整数和浮点数。编译器需要把+的某个运算分量进行转换，以保证在进行加法运算时两个运算分量具有相同的类型。

假定在必要的时候可以使用一个单目运算符（float）将整数转换成浮点数。例如，整数2在表示式2*3.14的代码中被转换成浮点数： t1 = (float) 2 t2 =t1*3.14

我们可以扩展这样例子，考虑运算符的整型版本和浮点型版本；比如int*表示作用于整型运算分量的运算符，而float*表示作用于浮点型运算分量的运算符。

我们将扩展6.4.2节中的用于表达式翻译的翻译方案，以说明如何进行类型综合。我们引入另一个属性E.type，该属性的取值可以是integer或float。和E→E1+E2关联的规则可用如下的伪代码给出：

if (E1.type=integer and E2.type=integer) E.type=integer; else if (E1.type=float and E2.type=integer) … …

随着需要转换的类型的增多，需要处理的不同情况急剧增多。因此在处理大量的类型时，精心组织用于类型转换的语义动作就变得非常重要。

不同语言具有不同的类型转换规则。图6.25中的Java的转换规则区分了拓宽转换和窄化转换。拓宽转换可以保持原有的信息，而窄化转换则可能丢失信息。拓宽规则通过图6.25（a）中的层次结构给出：在该层次结构中位于较低层的类型可以被拓宽为较上层的类型。因此，char类型可以被拓宽为int型和float型，但是不可以被拓宽为short类型。窄化转换的规则表示为图6.25(b)中的图：如果存在一条从s到t的路径，则可以将s窄化为t。可以看出，char、short、byte之间可以两两相互转换。

如果类型转换由编译器自动完成，那么这样的转换就被称为隐式转换。隐式转换又称为coercion类型转换。在很多语言中coercion转换仅仅限于拓宽转换。如果程序员必须写出某些代码来引发类型转换操作，这个转换就称为显式的。显式转换也被称为cast转换。

（a）拓宽类型转换 （b）窄化类型转换 图6.25：Java中简单类型的转换

检查E→E1+E2的语义动作使用了两个函数:

1. max(t1,t2)接受t1和t2两个类型参数，并返回拓宽层次结构中这两个类型的最大者（或者

最小上界）如果t1或t2之一没有出现在这个层次结构中，比如有个类型是数组类型或指针类型，那么该函数返回一个错误信息。

2. 如果需要将地址a中类型为t的值转换成w类型的值，函数widen(a,t,w)将生成类型转换

的代码。如果t和w是相同的类型，该函数返回a本身。否则，它会生成一条指令来完

成转换工作并将转换结果放置到临时变量t中。这个临时变量作为结果返回。函数widen的伪代码如图6.26所示，这里假设只有integer和float两种类型。

图6.26：widen函数的伪代码 图6.27中E→E1+E2的语义动作演示了如何把类型转换加入到在图6.20所示的表达式翻译的翻译方案中。在这个语义动作中，如果E1的类型不需要被转换成E的类型时，临时变量a1就是E1.addr。如果需要进行这样的转换，a1就是widen函数返回的一个新的临时变量。类似地，a2可能是E2.addr，也可能是一个新临时变量，用于存放转换后的E2的值。如果两个变量都是整型或者都是浮点型，就不需要进行任何转换。然而我们会发现，总的来说将两个不同类型的值相加的唯一方法是把它们都转换成为第三种类型。

图6.27：表达式求值中引入类型转换 6.5.3 函数和运算符的重载

依据它所在的不同上下文，被重载的符号会有不同的含义。如果能够为一个名字的每次出现确定其唯一的含义，该名字的重载就得到了解决。在本节中，我们仅考虑那些只需要查看函数参数就能解决的函数重载。Java中的重载即是如此。

例子6.13：根据其运算分量的类型，Java中的+运算符既可以表示字符的连接运算，也可以表示加法运算。用户自定义的函数同样可以重载，例如 void err() { … }

void err(String s) {…}

请注意，我们可以根据函数err的参数来确定选择这个函数的哪一个版本。□

以下是针对重载函数的类型综合规则： if f可能的类型为si→ti, （1≤i≤n），其中如果i≠j，si≠sj

and x 的类型为sk, 对某个1≤k≤n (6.10) then 表达式f(x)的类型为tk

6.1.2节中的值编码方法同样可以被用于类型表达式，根据参数类型高效地解决重载问题。在表示类型表达式的一个DAG图上，我们给每个结点赋予一个被称为值编码的整数值。使用算法6.3，我们可以构造出每个结点的范型，该范型由该结点的标号及其从左到右的子结点的值编码组成。一个函数的范型由其函数名和它的参数的类型组成。根据函数的参数类型解决重载的问题就等价于基于范型解决重载的问题。

仅仅通过查看一个函数的参数类型并不一定能够解决重载问题。在Ada中，一个子表达式会有一组可能的类型，而不是只有一个确定的类型。它所在的上下文必须提供足够的信息来缩小可选范围，最终得到唯一的可选类型（见练习6.5.2）。