Copyright © 2006 Gradiance Corporation.

 

 

     

Intermediate-Code Generation --- Arrays

 

 

 

3-address code for array accesses.

 

1.  

A real array A[i,j,k] has indexes i ranging from 1 to 4, j ranging from 0 to 4, and k ranging from 5 to 10. Suppose A is allocated space starting at byte 0, elements are stored in COLUMN-MAJOR order, and each real value requires 8 bytes. Give the formula that tells, in terms of i, j, and k, the byte at which element A[i,j,k] begins. Then, identify from the list below the byte where element A[2][3][7] begins.

 

 

 

 a) 

1232

 

 b) 

400

 

 c) 

53

 

 d) 

424

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.  

An integer array A[i,j] has indexes i ranging from 1 to 10 and j ranging from 1 to 20. Suppose A is allocated space starting at byte 0, elements are stored in ROW-MAJOR order, and each integer element requires 4 bytes. Give the formula that tells, in terms of i and j, the byte at which element A[i,j] begins. Then, identify from the list below the element that is located correctly.

 

 

 

 a) 

A[6,2] is in byte 404.

 

 b) 

A[3,4] is in byte 128.

 

 c) 

A[5,17] is in byte 300.

 

 d) 

A[3,4] is in byte 256.

 

 

 

 

 

3.  

A real array A[i,j,k] has indexes i ranging from 1 to 4, j ranging from 0 to 4, and k ranging from 5 to 10. Suppose A is allocated space starting at byte 0, elements are stored in ROW-MAJOR order, and each real value requires 8 bytes. Give the formula that tells, in terms of i, j, and k, the byte at which element A[i,j,k] begins. Then, identify from the list below the byte where element A[2][3][7] begins.

 

 

 

 a) 

50

 

 b) 

400

 

 c) 

680

 

 d) 

192

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.  

Suppose we use the following simplified translation scheme for expressions involving arrays. Arrays are assumed to be one-dimensional and to have integer values. Expressions involve only addition, but the operands may be either integers, integer-valued variables, or expressions involving array accesses. Integers are assumed to ooccupy 4 bytes. No error checking is performed, so, for example, an array access could be out of bounds, or a variable could be undefined.

E → id[ E1 ]

{E.place = newTemp();

 

offset = newTemp();

 

gen(offset "=" E1.place "*" 4);

 

gen(E.place "=" id.name() "[" offset "]"};

 

 

E → E1 + E2

{E.place = newTemp();

 

gen(E.place "=" E1.place "+" E1.place)}

 

 

E → id

{E.place = id.name()}

 

 

E → int

{E.place = newTemp();

 

gen(E.place "=" int.value())}

Here:

  • name() is a method that returns the name of an id token from the symbol table.
  • value() is a method at applies to an integer token (int) and returns the value of that integer.
  • Function newTemp() returns a new temporary. Assume that newTemp() returns T1, T2,... in order, when in it is called.
  • Function gen(...) emits a line with a three-address statement, using the constituents inside parentheses, in order.

Notice that we handle integers in the last rule by creating a temporary for their value, which is a "bug" that would be removed in code optimization. Also notice that we generate the temporary for the result of an array access (the first production) before we generate the temporary to hold the offset into the array.

Apply this translation scheme to the expression: 

     a[x+2] + b[c[y]+3]

To be specific, assume that the parse is left-to-right and bottom-up, and a rule is applied during reduction by the associated production. Then, identify the three-address statement that appears in your result.

 

 

 

 a) 

T10 = b[T9]

 

 b) 

T6 = b[T7]

 

 c) 

T6 = y * 4

 

 d) 

T7 = T4 * 4