Translation of Array References in Compiler Design

Translation of Array References

We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of an array is one less than the number of the element stored in an array. We can categorize an array mainly in two types:

• One Dimensional Array
• Multi-Dimensional Array

The location of the i^th element of an array ‘A’ having width ‘w’ of each array element is:

base + i * w

Here, the base is the relative address of the storage allocated for the array.

One Dimensional Array

The element of a one-dimensional array is numbered in the form of low, low + 1, and so on. We can rewrite the above formula for the i^th element of an array as follows:

A[low] = base + (i – low) * w

The above expression can also be written as:

i * w + (base – low * w)

Multi-Dimensional Array

We can store the multi-dimensional array in two types:

1. Row-Major
2. Column-Major

Row-major: A[1, 1], A[1, 2], A[1,3], A[2, 1], A[2, 2], A[2, 3]

Column-major: A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3]

Translation Scheme for Array Elements

The translation scheme for an array element for the three-address statement is given below. This scheme consists of production and semantic action.

L.addr: Temporary variable

L.type: Pointer to symbol table entry for the array name

L.array: Array name

Production Rule	Semantic Action
S => id = E;     |    L = E;	{ gen ( top.get (id.lexeme) ‘=’  E.addr ); } {gen(L.array.base‘[‘ L.addr ‘]’ ‘=’ 0 E.addr ); }
E => E1 + E2          | id        | L	{E.addr = new Temp (); gen(E.addr ‘=’ E1.addr ‘+’ E2.addr ); }   {E.addr = top.get(id.lexeme ); }    {E.addr = new Temp (); gen(E.addr ‘=’ L.array.base‘[‘ L.addr ‘]’);}
L => id [ E ]	{L.array = top.get(id.lexeme ); L.type = L.array.type.elem ; L.addr = new Temp (); gen (L.addr ‘=’ E.addr ‘*’ L.type.width ); }
L => L1 [ E ]	{L.array = L1.array ; L.type = L1.type .elem ; t = new Temp (); L.addr = new Temp (); gen( t ‘=’ E.addr ‘*’ L.type.width ); gen(L.addr ‘=’ L1.addr ‘+’ t ); }