6.4 节的练习

6.4.1

向图 6-19 的翻译方案中加入对应于下列产生式的规则：

1. E -> E1 * E2
2. E -> +E1

解答

产生式           语义规则

E -> E1 * E2    { E.addr = new Temp();
                  E.code = E1.code || E2.code ||
                           gen(E.addr '=' E1.addr '*' E2.addr); }

   | +E1        { E.addr = E1.addr;
                  E.code = E1.code; }

6.4.2

使用图 6-20 的增量式翻译方案重复练习 6.4.1

解答

产生式           语义规则

E -> E1 * E2    { E.addr =  new Temp();
                  gen(E.addr '=' E1.addr '*' E2.addr; }

   | +E1        { E.addr = E1.addr; }

6.4.3

使用图 6-22 的翻译方案来翻译下列赋值语句：

1. x = a[i] + b[j]
2. x = a[i][j] + b[i][j]
3. ! x = a[b[i][j]][c[k]]

解答

1. x = a[i] + b[j]

   语法分析树:

   

   三地址代码

    t_1 = i * awidth
    t_2 = a[t_1]
    t_3 = j * bwidth
    t_4 = b[t_3]
    t_5 = t_2 + t_4
    x = t_5
   

2. x = a[i][j] + b[i][j]

   语法分析树：

   

   三地址代码：

    t_1 = i * ai_width
    t_2 = j * aj_width
    t_3 = t_1 + t_2
    t_4 = a[t_3]
    t_5 = i * bi_width
    t_6 = j * bj_width
    t_7 = t_5 + t_6
    t_8 = b[t_7]
    t_9 = t_4 + t_8
    x = t_9
   

3. ! x = a[b[i][j]][c[k]]

6.4.4 !

修改图 6-22 的翻译方案，使之适合 Fortran 风格的数据引用，也就是说 n 维数组的引用为 id[E1, E2, …, En]

解答

仅需修改 L 产生式（同图 6-22 一样，未考虑消除左递归）

L -> id[A]  { L.addr = A.addr; 
              global.array = top.get(id.lexeme); }

A -> E      { A.array = global.array;
              A.type = A.array.type.elem;
              A.addr = new Temp();
              gen(A.addr '=' E.addr '*' A.type.width; }

A -> A1,E   { A.array = A1.array;
              A.type = A1.type.elem;
              t = new Temp();
              A.addr = new Temp();
              gen(t '=' E.addr '*' A.type.length);
              gen(A.addr '=' A1.addr '+' t); }

注意

令 a 表示一个 i*j 的数组，单个元素宽度为 w

a.type = array(i, array(j, w))
a.type.length = i
a.type.elem = array(j, w)

6.4.5

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

1. 一个二维数组 A，按行存放。第一维的下标从 l_1 到 h_1，第二维的下标从 l_2 到 h_2。单个数组元素的宽度为 w。
2. 其他条件和 1 相同，但是采用按列存放方式。
3. ！一个 k 维数组 A，按行存放，元素宽度为 w，第 j 维的下标从 l_j 到 h_j。
4. ！其他条件和 3 相同，但是采用按列存放方式。

解答

令 n_i 为第 i 维数组的元素个数，计算公式：n_i = h_i - l_i + 1

3. A[i_1]]…[i_k] = base + 
                   (
                       (i_1 - l_1) * n_2 * … * n_k +
                       … + 
                       (i_k-1 - l_k-1) * n_k +
                       (i_k - l_k)
                   ) * w

4. A[i_1]]…[i_k] = base + 
                   (
                       (i_1 - l_1) +
                       (i_2 - l_2) * n_1 + 
                       … +
                       (i_k - l_k) * n_k-1 * n_k-2 * … * n_1
                   ) * w

6.4.6

一个按行存放的整数数组 A[i, j] 的下标 i 的范围为 1~10，下标 j 的范围为 1~20。每个整数占 4 个字节。假设数组 A 从 0 字节开始存放，请给出下列元素的位置：

1. A[4, 5]
2. A[10, 8]
3. A[3, 17]

解答

计算公式：((i-1) 20 + (j-1)) 4

1. (3 20 + 4) 4 = 256
2. (9 20 + 7) 4 = 748
3. (2 20 + 16) 4 = 224

6.4.7

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

解答

计算公式：((j-1) * 10 + (j-1)) * 4

1. (4 10 + 3) 4 = 172
2. (7 10 + 9) 4 = 316
3. (16 10 + 2) 4 = 648

6.4.8

一个按行存放的实数型数组 A[i, j, k] 的下标 i 的范围为 1~4，下标 j 的范围为 0~4，且下标 k 的范围为 5~10。每个实数占 8 个字节。假设数组 A 从 0 字节开始存放，计算下列元素的位置：

1. A[3, 4, 5]
2. A[1, 2, 7]
3. A[4, 3, 9]

解答

计算公式：((i-1) 5 6 + j 6 + (k-5)) 8

1. ((3-1) 5 6 + 4 6 + (5-5)) 8 = 672
2. ((1-1) 5 6 + 2 6 + (7-5)) 8 = 112
3. ((4-1) 5 6 + 3 6 + (9-5)) 8 = 896

6.4.9

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

解答

计算公式：((i-1) + j 4 + (k-5) 5 4) 8

1. ((3-1) + 4 4 + (5-5) 5 4) 8 = 144
2. ((1-1) + 2 4 + (7-5) 5 4) 8 = 384
3. ((4-1) + 3 4 + (9-5) 5 4) 8 = 760