Header Ads Widget

Array references in arithmetic expressions

Array references in arithmetic expressions

Elements of arrays can be accessed quickly if the elements are stored in a block of consecutive location. Array can be one dimensional or two dimensional.

For one dimensional array:

  1. A: array[low..high] of the ith elements is at:  
  2. base + (i-low)*width → i*width + (base - low*width)  

Multi-dimensional arrays:

Row major or column major forms

  • 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]
  • In raw major form, the address of a[i1, i2] is
  • Base+((i1-low1)*(high2-low2+1)+i2-low2)*width

Translation scheme for array elements

Limit(array, j) returns nj=highj-lowj+1

place: the temporaryor variables

offset: offset from the base, null if not an array reference

The production:

  1. S  →  L := E  
  2.    E  →  E+E  
  3.    E  →  (E)  
  4.    E  →  L  
  5.    L  →  Elist ]  
  6.    L  →  id  
  7.    Elist →   Elist, E  
  8.    Elist  →   id[E  

A suitable transition scheme for array elements would be:

Production RuleSemantic Action
S → L := E{if L.offset = null then emit(L.place ':=' E.place)
 else EMIT (L.place'['L.offset ']' ':=' E.place);
}
E → E+E{E.place := newtemp;
 EMIT (E.place ':=' E1.place '+' E2.place);
}
E → (E){E.place := E1.place;}
E → L{if L.offset = null then E.place = L.place
  else {E.place = newtemp;
  EMIT (E.place ':=' L.place '[' L.offset ']');
   }
}
L → Elist ]{L.place = newtemp; L.offset = newtemp;
  EMIT (L.place ':=' c(Elist.array));
  EMIT (L.offset ':=' Elist.place '*' width(Elist.array);
}
L → id{L.place = lookup(id.name);
  L.offset = null;
}
Elist → Elist, E{t := newtemp;
  m := Elist1.ndim + 1;
  EMIT (t ':=' Elist1.place '*' limit(Elist1.array, m));
  EMIT (t, ':=' t '+' E.place);
  Elist.array = Elist1.array;
  Elist.place := t;
  Elist.ndim := m;
}
Elist → id[E{Elist.array := lookup(id.name);
  Elist.place := E.place
  Elist.ndim := 1;
}

Where:

ndim denotes the number of dimensions.

limit(array, i) function returns the upper limit along with the dimension of array

width(array) returns the number of byte for one element of array.


Post a Comment

0 Comments