320 翁译原理及实践 China-pub.com 下载 这些新地址模式的实现要求三地址码的数据结构包含一个或多个新域。例如，图84的四 元式数据结构增加了一个枚举型的AddrMode域，枚举值为None、Address和Indiredct 2)用于地址计算的P代码在P代码中，通常引入新的指令表示新的地址模式（由于很少有 外在的地址需要指定地址模式)。为了这个日的将引入如下两条指令： ·id(间接装入)用一个整型偏移量作为参数，假设栈顶上有一个地址，就将这个地址 与偏移量相加得到新地址，再将新地址中的值压入栈以代替原来栈顶的地址。 aid手+a+i)☐ 执行前的钱 执行后的栈 ·1xa(索引地址)用整型比例因子作为参数，假设一个偏移量已在栈顶并且在其下边有 一个基地址，则用比例因子与偏移量相乘，再加上基地址以得到新地址，再将偏移量和基地址 从栈中弹出，压入新地址。 top a+4☐ 执行前的栈 执行后的栈 这两个P代码指令，和以前介绍过的1a(装入地址)指令，将允许我们执行和三地址码中地址模 式一样的地址计算和引用 ⊙。例如，前面的例子（把常量2存入变量x加10字节处的地址）现在用 P代码实现如下： lda x 1dc10 ixa 1 1de 2 sto 我们现在开始讨论数组，记录和指针，随后是目标代码生成和一个扩展的例子。 8.3.2数组引用 数组引用通过表达式涉及了数组变量下标，得到数组元素的引用或值。正如下面的C代码 所示： inta【sIzE】:inti,j: a【1+1】=a[j2】+3: 在这个赋值语句中，a的下标表达式1+1产生了一个地址（赋值的目标地址），而通过下标表达式 *2在已计算的地址中得到ā元素类型的一个值。由于数值按顺序存放于存储器中，每个地址 必须根据a的基地址(base address)(即数组a在存储器中的起始地址)和线性地依赖于下标的偏移 量计算。 当需要的是一个值而不是地址时，就必须生成一个额外的间接步骤从已计算的地址中 取出值。 日实际上，1xa指令能用算术运算符来模拟，除了在P代码中，这些操作被类型化(a1=整数相乘)，因此不 能应用于地址。我们不强调P.代码的类型限制，因为这涉及额外的参数，为了简化，设有使用
这些新地址模式的实现要求三地址码的数据结构包含一个或多个新域。例如，图 8 - 4的四 元式数据结构增加了一个枚举型的A d d r M o d e域，枚举值为N o n e、A d d r e s s和I n d i r e d c t。 2) 用于地址计算的P -代码 在P -代码中，通常引入新的指令表示新的地址模式(由于很少有 外在的地址需要指定地址模式)。为了这个目的将引入如下两条指令： • i n d (间接装入) 用一个整型偏移量作为参数，假设栈顶上有一个地址，就将这个地址 与偏移量相加得到新地址，再将新地址中的值压入栈以代替原来栈顶的地址。 • i x a (索引地址) 用整型比例因子作为参数，假设一个偏移量已在栈顶并且在其下边有 一个基地址，则用比例因子与偏移量相乘，再加上基地址以得到新地址，再将偏移量和基地址 从栈中弹出，压入新地址。 这两个P -代码指令，和以前介绍过的l d a (装入地址)指令,将允许我们执行和三地址码中地址模 式一样的地址计算和引用 。例如，前面的例子(把常量2存入变量x加1 0字节处的地址)现在用 P -代码实现如下： lda x ldc 10 ixa 1 ldc 2 s t o 我们现在开始讨论数组，记录和指针，随后是目标代码生成和一个扩展的例子。 8.3.2 数组引用 数组引用通过表达式涉及了数组变量下标，得到数组元素的引用或值。正如下面的 C代码 所示： int a[SIZE]; int i,j; . . . a[i+1] = a[j*2] + 3; 在这个赋值语句中，a的下标表达式i + 1产生了一个地址(赋值的目标地址)，而通过下标表达式 j * 2在已计算的地址中得到 a元素类型的一个值。由于数值按顺序存放于存储器中，每个地址 必须根据a的基地址(base address) (即数组a在存储器中的起始地址)和线性地依赖于下标的偏移 量计算。当需要的是一个值而不是地址时，就必须生成一个额外的间接步骤从已计算的地址中 取出值。 3 2 0 编译原理及实践 下载 执行前的栈 执行后的栈 执行前的栈 执行后的栈 实际上，i x a指令能用算术运算符来模拟，除了在 P -代码中，这些操作被类型化 (a d i = 整数相乘)，因此不 能应用于地址。我们不强调P -代码的类型限制，因为这涉及额外的参数，为了简化，没有使用
China-pub.com 第8章代码生成 321 下载 从下标值中计算偏移量如下：首先，假如下标范围不从0开始（这在Pascal和Ada中是可能 的)，就必须对下标值作一调整。其次，调整后的下标值必须与比例因子(scale factor)相乘，比 例因子等于存储器中数组元素类型的尺寸。最后比例作用过的下标值加上基地址，从而得到数 组元素的最终地址 例如，C数组引用a【i+1]的地址是：⊙ a+(任+1)*sizoof(int) 更一般地，任何语言中数组元素a【】的地址是 base_address(a)+(t-lower bound(a))*element_size(a) 我们现在转向用三地址码和P代码表示这个地址计算的方法。为了不依赖目标机器，假设 数组变量的地址就是它的基地址。因此，如果a是数组变量，在三地址码和P-代码中，sā就是 数组a的基地址。P-代码 将a的基地址压入P机器栈。由于数组引用计算依赖于目标机器元素类型的尺寸，所以用 elem-size(a)代表目标机器上数组a的元素尺寸e。由于这是一个静态量（假设是静态类型）， 这个表达式在编译时将用常量代替。 1)数组引用的三地址码在三地址码中表示数组引用的一个可能的方法是引入两个新的操 作。一个是获取数组元素的值 七2=a【七1j 还有一个是给数组元素地址中赋值。 a【t2】=t1 (这些就用符号=[]和[]=表示)，用这个术语表示实际地址的计算不是必要的（机器依赖性如元 素尺寸将从这个概念中消失)。例如，源代码语句 a【i+1】。【5*21+3 将翻译成下面的三地址指令： t1=1青2 t2=a【t1] t3=t2+3 t4=1+1 a【t5】=t3 然而，引入前面所述的地址模式仍是必需的，在处理记录域和指针引用时，用统一方式处理 所有地址运算是有意义的，因此在三地址码中也直接写出数组元素地址的计算。例如，赋值 语句： 飞2■a【飞1】 能写成：（用更多的临时变量：t3和t4) t3 =t1 t elem_size (a) a+3 t2=*t4
从下标值中计算偏移量如下：首先，假如下标范围不从 0开始(这在P a s c a l和A d a中是可能 的)，就必须对下标值作一调整。其次，调整后的下标值必须与比例因子 (scale factor)相乘，比 例因子等于存储器中数组元素类型的尺寸。最后比例作用过的下标值加上基地址，从而得到数 组元素的最终地址。 例如，C数组引用a [ i + 1 ]的地址是： a + (i + 1) * sizeof (int) 更一般地，任何语言中数组元素a [t]的地址是： b a s e _ a d d ress (a) + (t - lower_bound (a)) * element_size (a) 我们现在转向用三地址码和P -代码表示这个地址计算的方法。为了不依赖目标机器，假设 数组变量的地址就是它的基地址。因此，如果 a是数组变量，在三地址码和 P -代码中，& a就是 数组a的基地址。P -代码 lda a 将a的基地址压入 P -机器栈。由于数组引用计算依赖于目标机器元素类型的尺寸，所以用 e l e m - s i z e ( a )代表目标机器上数组a的元素尺寸 。由于这是一个静态量(假设是静态类型)， 这个表达式在编译时将用常量代替。 1) 数组引用的三地址码 在三地址码中表示数组引用的一个可能的方法是引入两个新的操 作。一个是获取数组元素的值 t2 = a[t1] 还有一个是给数组元素地址中赋值。 a[t2] = t1 (这些就用符号= [ ]和[ ] =表示)，用这个术语表示实际地址的计算不是必要的 (机器依赖性如元 素尺寸将从这个概念中消失)。例如，源代码语句 a[i+1] = a [j*2] + 3 将翻译成下面的三地址指令: t1 = j * 2 t2 = a [t1] t3 = t2 + 3 t4 = i + 1 a [t5] = t3 然而，引入前面所述的地址模式仍是必需的，在处理记录域和指针引用时，用统一方式处理 所有地址运算是有意义的，因此在三地址码中也直接写出数组元素地址的计算。例如，赋值 语句： t2 = a [t1] 能写成：(用更多的临时变量：t 3和t 4) t3 = t1 * elem_size (a) t4 = &a + t3 t2 = *t4 第 8章 代 码 生 成 3 2 1 下载 在C中，一个数组(如此例中的a)的名字代表了它的基地址。 这实际上是一个由符号表提供的函数
322希译原理及实我 China-pub.com 下载 赋值语句 a【t2】=t1 写成 t3 t2 elem_size(a) t4=6a+t3 +t4=t1 最后，一个更复杂的例子，源代码语句 a【1+1】=a【5*21+3: 翻译成三地址指令如下： t1=方*2 t2 t1 t elom_size(a) t3=6a+t2 t4”+t3 t5=t4+3 t6=1+1 t7 .t6 t elem_size (a) 2)数组引用的P代码正如前面所描述的，我们用新的地址指令ind和ixa。指令ixa实 际上由数组地址计算精确地构成。in指令用来装入前面已计算地址的值（例如实现一个间接 装入)，数组引用 t2=a【t1] 的P代码表示如下： 1da t2 1。dt1 4xa910m_s1z0(a) indo sto 数组赋值 a【t21=t1 的P代码如下： lda a lod t2 ixa elem_size(a) lod t1 sto 最后，前面那个较复杂的例子 a【1+1】▣a【5*2】+3: 翻译成P代码如下：
赋值语句 a[t2] = t1 写成 t3 = t2 * elem_size(a) t4 = &a + t3 *t4 = t1 最后，一个更复杂的例子，源代码语句 a[i+1] = a [j*2] + 3; 翻译成三地址指令如下： t1 = j * 2 t2 = t1 * elem_size(a) t3 = &a + t2 t4 = *t3 t5 = t4 + 3 t6 = i + 1 t7 = t6 * elem_size (a) t8 = &a + t7 *t8 = t5 2) 数组引用的P -代码 正如前面所描述的，我们用新的地址指令 i n d和i x a。指令i x a实 际上由数组地址计算精确地构成。 i n d指令用来装入前面已计算地址的值 (例如实现一个间接 装入)，数组引用 t2 = a [t1] 的P -代码表示如下： lda t2 lda a lod t1 ixa elem_size(a) ind 0 sto 数组赋值 a[t2] = t1 的P -代码如下： lda a lod t2 ixa elem_size(a) lod t1 sto 最后，前面那个较复杂的例子 a [i+1] = a [j*2] + 3 ; 翻译成P -代码如下： lda a lod i 3 2 2 编译原理及实践 下载
China-pub.com 第8章代码生成 323 下载 1de 1 adi ixa olom_size(a) Ida a lodj 1de 2 mpi ixa elem_size(a) ind 0 3)数组引用的代码生成过程这里将显示数组引用是怎样由一个代码生成过程产生的，我 们用前一节中的C表达式子集的例子，但扩充了下标操作。要用的新文法如下： exp→subs=expaexp aexp-aexp +factor factor factor一（exp)I num subs subs→id|id【ep】 注意，赋值的目标可能是一个简单变量，也可能是一个有下标的变量（都包括在非终结符sbs 中)。我们使用和前面的语法树一样的数据结构，另外为下标增加Sub3操作 typedef enum Plus,Assign,Subs optype: /:像前面一样的其他说明·1 由于下标表达式可以在一个赋值号的左边，那么是不可能将目标变量名存入赋值节点中（因为 可能没有这样的名字)。赋值节点现在有2个子树，这同加法节点一样。左子树必须是标识符 或下标表达式。下标本身只能被用作标识符，因此，存储数组变量名于下标节点。所以，表 达式， （a[1+11=2)+a【】 的语法树如下： 程序清单8-9是一个为这样的语法树产生P代码的代码生成过程（同程序清单8-7比照）。这个代 码同程序清单&-7代码的主要不同在于它需要继承属性isAddr,用于识别下标表达式标识符在 赋值号的左边还是在右边。如果isAddr被设置成rUE,那么就必须返回表达式的地址：否则 返回值。请读者检验下面的表达式(a[i+1】=2)+a【5】的P-代码生成过程：
ldc 1 a d i ixa elem_size(a) lda a lod j ldc 2 m p i ixa elem_size(a) ind 0 ldc 3 a d i sto 3) 数组引用的代码生成过程 这里将显示数组引用是怎样由一个代码生成过程产生的，我 们用前一节中的C表达式子集的例子，但扩充了下标操作。要用的新文法如下： exp → subs = exp | a e x p aexp → aexp + factor | f a c t o r factor → ( e x p ) | n u m | s u b s s u b s → i d | i d [ exp ] 注意，赋值的目标可能是一个简单变量，也可能是一个有下标的变量 (都包括在非终结符 s u b s 中)。我们使用和前面的语法树一样的数据结构，另外为下标增加 S u b s操作 typedef enum { Plus, Assign, Subs } Optype; /* 像前面一样的其他说明 * / 由于下标表达式可以在一个赋值号的左边，那么是不可能将目标变量名存入赋值节点中 (因为 可能没有这样的名字 )。赋值节点现在有 2个子树，这同加法节点一样。左子树必须是标识符 或下标表达式。下标本身只能被用作标识符，因此，存储数组变量名于下标节点。所以，表 达式： ( a [ i + 1 ] = 2 ) + a [ j ] 的语法树如下： 程序清单8 - 9是一个为这样的语法树产生 P -代码的代码生成过程 (同程序清单8 - 7比照)。这个代 码同程序清单8 - 7代码的主要不同在于它需要继承属性 i s A d d r，用于识别下标表达式标识符在 赋值号的左边还是在右边。如果i s A d d r被设置成T R U E，那么就必须返回表达式的地址；否则 返回值。请读者检验下面的表达式( a [ i + 1 ] = 2 ) + a [ j ]的P -代码生成过程： 第 8章 代 码 生 成 3 2 3 下载
324 翁译原理及实践 China-pub.com 下载 lda a ad olom_sizo(a) ixa elem size(a) ind 0 adi 在练习中也请读者检验这个文法的三地址码的代码生成器的构造。 程序清单8-9上面的表达式文法对应的P码的生成过程的实现 /CODESIZE max length of 1 line of P-code kind) switch(t->op】 【ca o1ae【gencode(化->1ohi1d,FLsz), case Subs: ,da",) gencode(t->lchild,FALSE): ",t->8tva1,)) ig (isAddr)emitcode("ind 0) break; broak de("Error") break; ig (isAddr)omitcode("Error") else sprintf(codestr,"%s %s","ldc",t->atrval);
lda a lod i ldc 1 a d i ixa elem_size(a) ldc 2 s t n lda a lod j ixa elem_size(a) ind 0 adi 在练习中也请读者检验这个文法的三地址码的代码生成器的构造。 程序清单8-9 上面的表达式文法对应的P -码的生成过程的实现 3 2 4 编译原理及实践 下载