数组元素的引用-编译原理与实践

为了可以快速访问数组中的元素，一般将它们放在连续的存储空间中。不过，要想访问某个具体的数组元素，还需要计算出该数组元素的地址。数组在存储器中的存放方式决定了数组元素的地址计算方法，从而也决定了应该产生什么样的中间代码。

若数组A的元素存放在一片连续单元里，则可以较容易地访问数组的每个元素。假设数组A每个元素宽度为w，则A[i]这个元素的起始地址为

其中，low为数组下标的下界，base是分配给数组的相对地址，即A[low]的相对地址。

若将式（6.1）改写为i×w+（base-low×w），则其子表达式base-low×w的值可以在处理数组说明时提前计算出来，记为C。假定C值存放在符号表中数组A的对应项中，则A[i]的相对地址可由i×w+C计算出来。

对于二维数组也可作类似处理。一个二维数组可以按行或按列存放，如对于2×3的数组A，图6-14给出了两种不同的存放方式，其中，图6-14（a）采用的是按行存放方式，图6-14（b）采用的是按列存放方式。

图6-14　二维数组的存放方式

对于按行存放的二维数组A来说，可用如下公式计算A[i1，i2]的相对地址：

其中，low1、low2分别为i1、i2的下界；n2是i2可取值的个数，若i2的上界为high2，则n2=high2-low2+1。式（6.2）可以改写为

其中，子表达式（base-（（low1×n2）+low2）×w）的值可以在编译时确定。

按行或按列存放方式可以推广到多维数组的情形。若多维数组A按行存放，则可将式（6.3）推广成如下的形式以计算元素A[i1，i2，…，ik]的相对地址：

假设对于任何j，nj=highj-lowj+1都是确定的，则式（6.4）中的子表达式

可以在编译时计算出来并存放到符号表中数组A对应的项里。对于按列存放的多维数组A来说，元素A[i1，i2，…，ik]的相对地址计算方法与按行存放类似，这里不再赘述。

在分析了数组元素的寻址方法的基础上，下面将对数组元素的翻译问题进行探讨，关键在于如何将式（6.4）的计算与数组文法结合起来。在表6-10中id出现的地方引入下面的产生式，则可把对数组元素的引用加入赋值语句之中。

L→id[Elist]|id

Elist→Elist,E|E

为了便于语义处理，可将上述产生式改写为

L→Elist]|id

Elist→Elist,E|id[E

这样做，可把数组名字id与最左下标表达式E相联系，而不是在形成L时与Elist相联系，从而使得在整个下标表达式Elist的翻译过程中，随时都能知道符号表中相对于数组名字id的全部信息。

可以为非终结符号Elist引进综合属性array，用来记录指向符号表中相应数组名字表项的指针；利用Elist.ndim来记录Elist中的下标表达式的个数，即维数；调用函数limit（array，j）来返回nj，即由array所指示的数组的第j维长度；最后，使用Elist.place表示临时变量，用来存放由Elist中的下标表达式计算出来的值。

一个Elist可以产生一个k-维数组A[i1，i2，…，ik]的前m维下标，并将生成计算下式的三地址代码：

式（6.6）可以利用如下的递归公式进行计算：

当m=k时，将ek乘以元素域宽w便可计算出式（6.4）的第一个子项。

L的左值（地址）可以用两个属性L.place和L.offset来描述，其中，L.place表示指向符号表中相应名字表项的指针，L.offset表示数组元素相对于起始地址的偏移量。因此，当L为一个简单名字时，L.offset为null。(www.xing528.com)

当一个赋值语句中含有对数组元素的引用时，需要判断L究竟是一个简单的名字，还是一个数组元素。如果L是一个简单的名字，则将生成一般的赋值；如果L为数组元素引用，则将生成对L所指示地址的索引赋值。具体翻译模式如下：

(1)S→L:=E

(2)E→E1+E2

(3)E→(E1)

(4)E→L

(5)L→Elist]

(6)L→id

(7)Elist→Elist,E

(8)Elist→id[E

例如，假设A为一个10*20的数组，w=4，low1=low2=1，则有n1=10，n2=20。关于赋值语句x：=A[y，z]的带注释的语法分析树如图6-15所示。

图6-15　x：=A[y，z]的带注释的语法分析树

该赋值语句将被翻译成如下的三地址代码序列，对于其中的每个变量，用它的名字来代替id.place：

T1:=y*20

T1:=T1+z

T2:=A-84

T3:=4*T1

T4:=T2[T3]

x:=T4

目前为止，算术表达式和赋值语句中所有的id都是同一类型，实际上，在一个表达式中可以出现各种不同类型的变量或常数。因此，编译程序必须做到要么拒绝接受某种混合运算，要么产生有关类型转换的指令。