相比记录类型而言，数组可能更深入人心。笔者相信可能存在不支持记录类型的语言，却不可能存在不支持数组的语言。关于数组的基本概念，似乎已经没有阐述的必要了。这里，笔者将从编译器实现的角度来深入剖析数组的特性，让读者从一个崭新的视角来重新审视这种最通用的构造类型。

1．数组的存储布局

数组是一种连续存储的数据结构，用户通常以下标形式存取数组的元素。那么，下标与数组元素逻辑地址的映射关系就是编译器所关心的。然而，众所周知，物理存储区都是线性编址的。数组的存储布局主要就是讨论各种形态的数组在线性物理存储区中的组织形式，这是将下标引用转换为逻辑地址的基础。由于一维数组的形态本身就是线性结构，其存储布局与本身的形态基本一致，故不再详述。这里，先以二维数组为例，引入数组存储布局的相关问题。然后，再将其结论推广到更一般的多维数组中。

二维数组的映射方案主要有如下三个：行优先映射、列优先映射、间接向量映射。对于读者来说，前两种方案应该并不陌生。几乎任何一个程序设计课程都会对此作相关说明，因此，笔者就不再赘述了。较之前两者，在过去很长一段时期内，间接向量映射的概念却并没有得到普及，直至Java的出现。

所谓“间接向量映射”就是使用间接向量把所有多维数组压缩在一个向量集合中。以一个普通的二维数组为例，采用间接向量映射的存储布局如图6-10所示。

图6-10 间接向量映射的存储布局

仔细观察图6-10，不难发现这种存储布局的特点就是每一行元素是连续存储的，行之间是完全离散的。编译器借助一个行向量完成行寻址操作，而行内元素的寻址与一维数组完全一样。同样，间接向量映射也存在行优先或列优先之分。

从存储布局来看，这带来了两个新问题。

(1)增加了间接向量的空间开销。传统行（列）优先映射并不需要借助间接向量引用元素，而这种方案却不得不借助间接向量来完成元素寻址。事实上，随着数组维数的增大，间接向量的开销是非常可观的。以一个3×3×4的数组为例，将多消耗9个存储空间用于存储间接向量。

(2)建立间接向量需要大量的初始化代码，用于处理所有间接向量内部的指针。

当然，间接向量映射方式也有其自身的魅力，是传统映射方案无法比拟的。它降低了目标程序对连续存储区的需求是毋庸置疑的。其次，间接向量映射对于处理那些异形数组的优势比较明显。传统映射方案也可以处理异形数组，但代价较大。

在目前流行的程序设计语言中，行优先映射方案是应用最广的，例如，C、Pascal、C++等采用这种映射方案，只有一个经典的例外就是Fortran，它使用了列优先映射方案。而一些较新的语言都支持间接向量的映射方案，最典型例子的就是Java。

最后，将二维数组的映射方案推广到多维数组中。与二维数组类似，多维数组也有三种映射方案，即左下标优先映射、右下标优先映射、间接向量映射。由于多维数组并没有行、列之分，所以也就不存在行（列）优先之说。实际上，左（右）下标优先是一种更通用的观点。所谓“左下标优先”就是指将数组元素逐一映射到存储区时，左侧下标的变化速度比右侧下标的变化速度快。例如，A[l，1，1]、A[2，1，1]、A[3，1，1]、A[l，2，11……。实际上，二维数组的列优先映射就是一种左下标优先方案。同样，所谓“右下标优先”就是指将数组元素逐一映射到存储区时，右侧下标的变化速度比左侧下标的变化速度快。二维数组的行优先映射就是一种右下标优先方案。而多维数组的间接向量映射方案与二维数组的类似，只是其间接向量将比二维数组多得多。

2．数组元素的引用

下面继续讨论如何将源程序中下标引用形式翻译成该元素的逻辑地址，或者说相对于该数组首地址的偏移量。这个计算过程依赖语言所选择的数组映射方案，不同映射方案的翻译方式是完全不同的。本书以最常见的行优先映射方式为例，深入剖析下标引用转换成逻辑地址的过程。

首先讨论最简单的一维数组的情形。假设A是一个长度为n的数组，而其每个元素占用的存储空间为w。那么，A[i]的地址为：

BaseA+(i-lowi)xw

其中，Base_A表示数组A的首地址，low₁表示数组A第1维的下限。在C语言中，规定数组维度的下限都是O，所以不必考虑low₁的取值。而Pascal的下限是由用户定义的，所以low₁的取值是不可以忽略的。读者只需通过简单的手工演算，不难发现这个地址公式是完全可行的。

下面再来看看二维数组的情形。假设A是一个2行5列的二维数组，各维的下限都是1，其形式即为A[l．．2，1．．5]。那么，A[2，3]元素的地址是多少呢？根据行优先映射的特点，不难得到如下的计算过程：

A[2,3]的地址=Base_A+(2-low_l)×(high₂-low₂+1)×w+(3-low₂)×w

=Base_A+(2-1)×(5-1+1)×w+(3-1)×w

=Base_A+5xw+2xw=Base_A+7xw

其中，high2为第2维的上限。可以将整个计算过程分为三步：

1)求元素所在行的首地址。换句话说，就是求所在行第1列元素之前的所有元素的个数N。假设当前行之前的行数为L，而该二维数组的列数为C。显然，不难得到如下等式：

N=LxC

其中，L可以用（当前行号-lowi）表示，而C则可以用（high2-low2+l）表示。这样，在考虑元素占用存储空间w的情况下，就不难得到计算式中的第2项。

2)求元素相对于所在行首地址的偏移。这个过程与一维数组元素的计算相同，并不难求得。同样，就可以轻松得到计算式中的第3项。

3)将两者相加就是元素相对于数组首地址的偏移。

至此，就可以得到如下的计算公式（其中，len2=high2-low2+l）：(www.daowen.com)

A[c₁,C₂]的地址=Base_A+(c₁﹣low_l)×len₂×w+(c₂-low₂)×W

假设各维下限都为0时，可以将该公式简化为：

A[c₁，C₂]的地址=Base_A+(c_l×len₂+c₂)×w

这两个公式应该并不难理解，但是编译器设计者却不满足于此。这里，考虑更一般的情况，那就是c₁、C₂都是未知的变量，而不是常量。不难发现，由于存在变量，整个公式的计算过程都将依赖于目标代码完成，甚至len₂的计算也可能由目标程序完成，这并不是预期的结果。事实上，由于数组的上、下限都是已知的，所以len₂的计算是完全可以在编译阶段完成的。换句话说，若希望得到更精简的目标代码，就需要在计算的过程中尽可能将已知的常量折叠。确实，表面上看，公式本身并没有提供太多常量折叠的机会。不过，可以做如下公式变换：

读者可能会对公式变换的意义有所疑惑。事实上，公式变换的目的就是为常量折叠创造机会。不难发现，将变量c₁、C₂集中到了公式的第3项中，而将可能的常量集中提取到了第2项中。如果数组上、下限己知，那么，第2项的值是可以在编译过程中计算得到的。虽然这样的变换可能会使公式的含义并不那么明晰，但是，它对生成精简的目标代码是有现实意义的。公式变换的思想并不是由笔者提出的，在经典编译技术中，对此早有详细记载。许多书中将第1项、第2项合称为公式的“不变部分”，而将第3项称为公式的“可变部分”。借助公式变换来实现常量折叠的思想印证了笔者先前提到的一个观点，即在最有利于解决某一问题的时刻处理该问题是最优的选择，不要拘泥于功能模块的划分。从理论上来说，完全可以按照原始的公式生成复杂的IR序列，而将精简优化的问题交由IR优化模块来处理。不过，届时所需付出的努力将是巨大的，而优化却未必能达到预期的效果。

最后，将二维数组的地址计算公式推广到多维数组中。根据多维数组的特性，可以得到如下的计算公式（其中，p_i=c_i-low_i）：

这里，笔者就不再详细解释此公式的推导过程，有兴趣的读者可以借助实例验证其正确性。这个具有一般意义的数组元素地址计算公式是基于如下两个基本条件讨论的：

(1)数组的映射方式是右下标优先。

(2)在编译过程中，数组各维度的上、下限是己知的。注意，如果上、下限是未知的，那么，试图通过公式变换来实现常量折叠是没有任何意义的。关于上、下限未知数组的相关问题，将稍后讨论。

3．越界访问的检测

所谓“越界访问”就是指引用了数组预定义界外的元素，这种异常的访问会给程序带来不可预知的后果，甚至会导致整个程序崩溃。不过，不同语言对越界访问的检测力度是不同的。有些语言进行静态检测，即在编译过程中，判定访问是否越界。有些语言则进行动态检测，即在目标程序执行过程中，判定访问是否越界。然而，也有些语言不进行越界检测。其中，C语言对数组访问既不做静态越界检测，也不做动态越界检测。

静态越界检测的实现比较容易，只需根据符号表的相关信息，判断下标是否越界即可。不过，在实际编译器设计中，静态越界检测的功效并不显著。这是因为数组访问的下标通常是一个变量，而不是常量。下标的值是依赖实际运行环境的。在这种情况下，静态越界检测就完全失效了。

动态越界检测的实现稍复杂，大致的思想就是在目标代码的适当位置插入越界检测的程序段，并且在每次数组访问的代码之前，调用越界检测子程序。如果检测发现异常访问，则中断程序执行，并给出相应的出错提示。通常，动态越界检测程序段必须依赖数组的内情向量（就是用于描述数组信息的数据结构）完成检测，因此，编译器需要将内情向量以适当的形式置入目标程序中。

虽然动态越界检测可以很大程度上保证数组访问的安全性，但它的实现却是需要付出代价的。动态越界检测机制不但会使目标程序的体积增大，而且还会延长目标程序执行的时间。其中的利弊是值得语言设计者斟酌的。在Pascal语言中，关于数组越界的检测并没有非常明确的规定，因此，不同的编译器实现存在着一定的差别。例如，Turbo Pascal动态越界检测机制是可选的，但默认情况下只进行静态越界检测，并不做动态越界检测。

4．动态数组的实现

所谓“动态数组”就是指数组的上、下限在编译阶段是不能确定的，换句话说，就是数组的上、下限在运行过程中是可变的，有时，亦称为“可变数组”。动态数组的历史远没有静态数组久远，早期的经典程序设计语言（如C、Pascal等）都不支持这一机制。随着软、硬件技术飞速发展，动态数组机制受到了越来越多语言的青睐，例如，C++、Java、C#等。

从应用的角度来说，除了可变上、下限之外，动态数组与静态数组的差异并不大。不过，从实现机制来说，两者的差异是非常巨大的。动态数组与指针却有几分相似之处。这里就来分析一下动态数组的内核实现。

数组都是在编译过程中由编译器静态分配存储空间的，在执行过程中，操作系统只需将逻辑存储区映射到实际的物理空间中即可。当然，实现静态分配的前提就是所需分配的空间大小在编译过程中是预知的。然而，动态数组所需空间大小在编译过程中是未知的，完全是由目标程序在运行过程中动态分配存储空间的。

编译器在处理动态数组类型的变量时，通常会为该变量分配一个数据结构，用于管理与维护动态数组。该数据结构主要包含如下两个部分：

(1)内情向量。实际上，就是一套用于描述数组信息的数据结构，其中包含了数组的维度及上、下限信息。在静态数组中，如果不考虑动态越界检测，编译器不一定会将数组的内情向量写入目标代码，而只需要保留在符号表中即可。而动态数组则不然。假设A是一个行优先映射的动态数组，当试图计算A[2，3]的首地址时，编译器则必须按照先前的计算公式生成IR，原公式中的不变部分也需要依靠指令来计算。原因很简单，公式中存在不变部分的前提就是数组各维度的上、下限是己知的。因此，目标程序必须使用一个数据结构（即内情向量）来保存此类信息，以便运行过程中动态计算元素的地址。一般来说，内情向量的元素个数是视数组的维数而定的。然而，在编译阶段，动态数组的维数通常是可以确定的。因此，不必担心内情向量长度无法确定的问题。

(2)首地址。这里所讨论的“首地址”指的就是数组元素实际存储区域的首地址。通常，数组元素实际存储区域是由目标程序根据实际的需要调用操作系统接口申请获得的动态存储区，该区域中存储的才是数组的实际数据。这个过程是由目标程序与操作系统之间协调完成的，编译器是不可能获得任何有关该存储区的线索的。因此，编译器只能静态分配一个存储空间用于存放该区域的首地址，以便通过间接寻址方式访问数组元素。实际上，首地址的作用与C、Pascal语言中的指针是非常类似的。

当然，除了内情向量及首地址信息之外，为了便于编译器生成更为精简的目标代码，这个数据结构中还可能包含一些辅助信息，不再赘述。

最后，简单谈谈动态数组存储区管理。其存储布局如图6-11所示。笔者主要想讨论以下两个问题：

(1)存储区的空间大小。一般来说，它是根据用户设置的数组上、下限而定的。理论上讲，只有显式设置了动态数组的上、下限后，用户才可以访问数组的元素。不过，并非所有语言都明确规定用户必须显式设置动态数组的各维上、下限，很多语言都提供了默认的上、下限值。例如，STL的vector就允许用户不显式设置上限，而使用默认值。那么，这个默认值的大小是多少较为适合呢？这是需要设计者斟酌的。

图6-11 动态数组的存储布局

(2)存储空间的扩展与回收。设置动态数组的目的就是便于用户动态改变数组的上、下限，因此，存储空间的扩展与回收是非常重要的。当然，重设存储空间的大小是必要的，却并不仅限于此。一般来说，用户改变数组上、下限时，并不希望现存的数据丢失。由于数组形态发生了变化，现存的数据元素的映射位置也必须随即改变。用户不可能也没必要了解数组的物理存储布局，因此，这项工作对于用户来说是完全透明的。尤其对于支持异形数组的语言，这方面的设计显得极其重要。另外，为了便于用户使用，有些语言将动态数组扩展、回收等交由编译器处理或者封装成库的形式。例如，当用户向vector对象添加元素时，是否关注过vector对象的容量呢？实际上，STL为此做了许多幕后工作，当用户调用push_back方法向一个vector对象添加元素时，许多辅助的程序片段将被执行，以便在数据溢出时自动扩展vector对象的动态存储区。至于一次扩展空间的大小是非常有讲究的，不同的编译器对此的理解不同。这个数字过大可能会导致存储空间的浪费，过小可能会使扩展操作频繁执行导致效率降低。