【编译原理笔记12】中间代码生成：简单赋值语句的翻译，数组引用的翻译

本次笔记内容：
6-3 简单赋值语句的翻译
6-4 数组引用的翻译

本节课幻灯片，见于我的 GitHub 仓库：第12讲 中间代码生成_2.pdf

简单赋值语句的翻译

赋值语句翻译的任务

赋值语句翻译的主要任务：

• 生成对表达式求值的三地址码

赋值语句的SDT

动作中有三个函数：

• lookup(name)：查询符号表，返回 name 对应的记录；
• gen(code)：生成三地址指令 code ；
• newtemp()：生成一个新的临时变量 t ，返回t的地址

可以看出，表达式的 code 属性要复制子表达式的 code 属性，以此递推…这样，code 属性就可能是一个比较长的字符串。这样在复制和移动的过程中就需要较长的时间。因此使用增量的方式进行翻译。

增量翻译 Incremental Translation

在增量翻译中，不需要设置 code 属性，而是在已经生成的三地址码后面追加三地址指令。下图中，就可以把 code 属性对应的行删掉。

在增量方法中，gen( )不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后。

例

上图中，根据③的语义动作，生成一个临时变量用于记录表达式的地址，假设变量名为$t_2$t2​；之后调用了栈函数，生成一条三地址指令：
$t_2 = t_1 * c$t2​=t1​∗c

注意这里我们用名字表示地址。

数组引用的翻译

赋值语句的基本文法：

• $S \to id=E;|L=E;$S→id=E;∣L=E;
• $E \to E_1 + E_2 | -E_1 | (E_1)|\text{id}|L$E→E1​+E2​∣−E1​∣(E1​)∣id∣L
• $L\to \text{id}[E]|L_1 [E]$L→id[E]∣L1​[E]

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址。

数组元素寻址 Addressing Array Elements

一维数组

假设每个数组元素的宽度是$w$w，则数组元素$a[i]$a[i]的相对地址是：
$base+i\times w$base+i×w
其中，$base$base是数组的基地址，$i\times w$i×w是偏移地址。

二维数组

假设一行的宽度是$w_1$w1​，同一行中每个数组元素的宽度是$w_2$w2​，则数组元素$a[i_1] [i_2]$a[i1​][i2​]的相对地址是：
$base+i_1 \times w_1+i_2\times w_2$base+i1​×w1​+i2​×w2​

k维数组

数组元素$a[i_1] [i_2] …[i_k]$a[i1​][i2​]…[ik​]的相对地址是：
$base+i_1\times w_1+i_2\times w_2+…+i_k\times w_k$base+i1​×w1​+i2​×w2​+…+ik​×wk​
其中：

• $w_1 \to a[i_1]$w1​→a[i1​] 的宽度
• $w_2 \to a[i_1] [i_2]$w2​→a[i1​][i2​] 的宽度
• …
• $w_k \to a[i_1] [i_2] …[i_k]$wk​→a[i1​][i2​]…[ik​] 的宽度

例

带有数组引用的赋值语句的翻译

例1

这里，用数组的名字 a 表示其基地址。

例2

数组引用的SDT

在数组引用的翻译方案的设计过程中，关键的问题在于如何将地址计算公式同数组引用的文法关联起来。

还通过这个例子来理解 SDT 。