Draw a DAG for the expression
a-a-a-(a-a)-(a-a-a-a)
.
Translate the following assignment statement into three address code:
a[i] = b[a[i], j] + c[i+j];
Assume that all array indexes start at zero, that the starting
addresses of the three arrays are available as
basea, baseb, and
basec, that array b
is 10 by 20 and
stored in row-major order, and that all array elements are 8 bytes in
size.
(This problem is a modified version of one from the forthcoming edition of the dragon book.) Consider the following C/C++/Java procedure for computing Fibonacci numbers using tree recusion:
int f(int n){ int t, s; if (n<2) return 1; s = f(n-1); t = f(n-2); return s+t; }
Suppose the initial call is f(5)
.
Draw the complete activation tree.
Draw the stack of activation records the first time
f(1)
is about to return. For each activation record,
show the following values in this order: n
,
s
, t
. Ignore other items that would
realistically need to be in the activation records and assume that all
variables are in the activation records, not registers. For any
variable that has not yet been assigned a value, show a blank slot
within the activation record.
Draw the stack of activation records again, following the same
conventions, but as it exists at the time when f(1)
is
about to return the fifth time.