Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

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]

    语法分析树:

    6 4 3-1

    三地址代码

     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]

    语法分析树:

    6 4 3-2

    三地址代码:

     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