Activation Record

Control stack is a run time stack which is used to keep track of the live procedure activations i.e. it is used
to find out the procedures whose execution have not been completed.

When it is called (activation begins) then the procedure name will push on to the stack and when it
returns (activation ends) then it will popped.

Activation record is used to manage the information needed by a single execution of a procedure.

An activation record is pushed into the stack when a procedure is called and it is popped when the
control returns to the caller function.

The diagram below shows the contents of activation records:

Activation Record

Return Value: It is used by calling procedure to return a value to calling procedure.

Actual Parameter: It is used by calling procedures to supply parameters to the called procedures.

Control Link: It points to activation record of the caller.

Access Link: It is used to refer to non-local data held in other activation records.

Saved Machine Status: It holds the information about status of machine before the procedure is called.

Local Data: It holds the data that is local to the execution of the procedure.

Temporaries: It stores the value that arises in the evaluation of an expression.

Static storage allocation

Stack storage allocation

Heap storage allocation

Static storage allocation

In static allocation, names are bound to storage locations.

If memory is created at compile time then the memory will be created in static area and only once.

Static allocation supports the dynamic data structure that means memory is created only at compile time
and deallocated after program completion.

The drawback with static storage allocation is that the size and position of data objects should be known
at compile time.

Another drawback is restriction of the recursion procedure.

Stack Storage Allocation

In static storage allocation, storage is organized as a stack.

An activation record is pushed into the stack when activation begins and it is popped when the activation
end.

Activation record contains the locals so that they are bound to fresh storage in each activation record.
The value of locals is deleted when the activation ends.

It works on the basis of last-in-first-out (LIFO) and this allocation supports the recursion process.

Heap Storage Allocation

Heap allocation is the most flexible allocation scheme.

Allocation and deallocation of memory can be done at any time and at any place depending upon the
user’s requirement.

Heap allocation is used to allocate memory to the variables dynamically and when the variables are no
more used then claim it back.

Heap storage allocation supports the recursion process.

Optimization of Basic Blocks:

Optimization process can be applied on a basic block. While optimization, we don’t need to change the
set of expressions computed by the block.

There are two type of basic block optimization. These are as follows:

Structure-Preserving Transformations

Algebraic Transformations
 1. Structure preserving transformations:

The primary Structure-Preserving Transformation on basic blocks is as follows:

Common sub-expression elimination

Dead code elimination

Renaming of temporary variables

Interchange of two independent adjacent statements

(a) Common sub-expression elimination:

In the common sub-expression, you don’t need to be computed it over and over again. Instead of this
you can compute it once and kept in store from where it’s referenced when encountered again.

A:=b+c

B:=a–d

C:=b+c

D:=a–d

In the above expression, the second and forth expression computed the same expression. So the block
can be transformed as follows:

A:=b+c

B:=a–d

C:=b+c

D:=b

(b) Dead-code elimination

It is possible that a program contains a large amount of dead code.

This can be caused when once declared and defined once and forget to remove them in this case they
serve no purpose.

Suppose the statement x:= y + z appears in a block and x is dead symbol that means it will never
subsequently used. Then without changing the value of the basic block you can safely remove this
statement.

© Renaming temporary variables

A statement t:= b + c can be changed to u:= b + c where t is a temporary variable and u is a new
temporary variable. All the instance of t can be replaced with the u without changing the basic block
value.

(c) Interchange of statement

Suppose a block has the following two adjacent statements:

T1 : = b + c

T2 : = x + y

These two statements can be interchanged without affecting the value of block when value of t1 does
not affect the value of t2.

2. Algebraic transformations:

In the algebraic transformation, we can change the set of expression into an algebraically equivalent set.
Thus the expression x:= x + 0 or x:= x *1 can be eliminated from a basic block without changing the set of
expression.

Constant folding is a class of related optimization. Here at compile time, we evaluate constant
expressions and replace the constant expression by their values. Thus the expression 5*2.7 would be
replaced by13.5.

Sometimes the unexpected common sub expression is generated by the relational operators like <=, >=,
<, >, +, = etc.

Sometimes associative expression is applied to expose common sub expression without changing the
basic block value. If the source code has the assignments

Recursive Descent Parser:

It is a kind of Top-Down Parser. A top-down parser builds the parse tree from the top to down, starting
with the start non-terminal. A Predictive Parser is a special case of Recursive Descent Parser, where no
Back Tracking is required.

By carefully writing a grammar means eliminating left recursion and left factoring from it, the resulting
grammar will be a grammar that can be parsed by a recursive descent parser.
Example:

Before removing left recursion After removing left recursion

E –> E + T | T

T –> T * F | F

F –> ( E ) | id E –> T E’

E’ –> + T E’ | e

T –> F T’

T’ –> * F T’ | e

F –> ( E ) | id