Stack Allocation of Space

 Run-time memory for procedures, functions, and methods is often

managed as a stack.

 When a procedure is called, an activation record (or frame)

is pushed onto the stack.

 When it returns, the record is popped off.

 Benefits: Efficiently shares space between non-overlapping calls and

enables consistent addressing of non-local variables.

Activation Trees

 Procedure calls nest in time, forming a tree-like structure called

an activation tree.

 Each node represents one procedure activation.

 The root is the main procedure.

 Children of a node are the procedures it calls, ordered from left to right.

 Key Relationships:

 Procedure calls correspond to a preorder traversal of the tree.

 Procedure returns correspond to a postorder traversal.

 The currently active procedures are the path from the root to the
current node.

Example

int factorial(int n) {

if (n == 0) return 1;

return n * factorial(n-1);

int main() {

int result = factorial(3);

}
 Activation Tree

main

└── factorial(3)

└── factorial(2)

└── factorial(1)

└── factorial(0)

 Each call creates a new activation.

 Calls nest, meaning factorial(0) must finish before factorial(1) can finish.

Activation Records (Frames)

 This is the block of memory on the stack for a single procedure activation.

 A general activation record typically contains the following fields (from top
to bottom):

o Actual Parameters: Values passed by the caller.

o Returned Value: Space for the function's return value.

o Control Link: A pointer to the activation record of the caller.

o Access Link: To access non-local data .

o Saved Machine Status: Registers and the return address (where to
resume in the caller).

o Local Data: The procedure's local variables.

o Temporaries: Space for intermediate expression values

Stack Evalution

Example

int factorial(int n) {

if (n == 0) return 1;

return n * factorial(n-1);

int main() {

int result = factorial(3);

Stack:

[ main activation record ]

Call factorial(3):

Stack:

[ factorial(3) activation record ]

[ main activation record ]

Call factorial(2):

Stack:

[ factorial(2) activation record ]

[ factorial(3) activation record ]

[ main activation record ]

Call factorial(1):

Stack:
 [ factorial(1) activation record ]

[ factorial(2) activation record ]

[ factorial(3) activation record ]

[ main activation record ]

Call factorial(0):

Stack:

[ factorial(0) activation record ]

[ factorial(1) activation record ]

[ factorial(2) activation record ]

[ factorial(3) activation record ]

[ main activation record ]

 Each call pushes a new frame.

 Local variables, parameters, and return address are stored in each frame.

Calling Sequences

 This is the code that manages the stack during a call and return, divided
between the caller and the callee.

Caller's Responsibilities:

o Evaluate actual parameters.

o Store the return address and old stack pointer ( top-sp) into the callee's
new activation record.

o Adjust top-sp to point to the end of the fixed-length fields in the new
record that is callees activation record

Callee's Responsibilities:

o Save register values and other machine status.

o Initialize its local data and begin execution.

Return Sequence:

 Callee places return value next to parameters (top-sp reference).

 Callee restores registers and top-sp using saved machine-status field.

 This moves top-sp back to caller’s frame.

 Callee jumps to return address stored by caller.

 Caller can now access the return value, knowing its location relative to current top-sp.

Variable-Length Data on the Stack

 Some local objects/arrays have size unknown at compile time.

 Strategy:
o Only pointers to arrays appear in activation record.
o Actual arrays are allocated on the stack beyond the activation record.
 Access:
o Through top (actual top of stack) and top-sp (points to end of fixed-length
fields).
o Stack pointer values updated at runtime for dynamic-sized allocations.
Symbol Table:

A symbol table is a data structure used by a compiler to store information about

identifiers (variables, functions, classes, objects, etc.) used in a program.
It helps the compiler in semantic analysis, code generation, and optimization phases.

Contents of Symbol Table

The symbol table contains entries for each identifier appearing in the source program.
Each entry stores attributes or information related to that identifier.

Identifier Attribute Description

Name / Lexeme Actual name of the identifier (variable, function, etc.)
Type Data type (e.g., int, float, char, array, record, class, etc.)
Scope / Visibility Part of the program where the identifier is valid
Storage Class Indicates storage type – static, automatic, register, etc.
Memory Location / Address Location of the variable in memory
Value (optional) Constant or initial value (if applicable)
Number of Parameters For functions/procedures
Type of Parameters Type list of function arguments
Return Type For function identifiers

Need for Symbol Table

 To verify declarations and uses of identifiers.

 To detect multiple declarations and undeclared variables.
 To support type checking during semantic analysis.
 To assist in storage allocation for variables and procedures.
 To support code generation (mapping variable names to addresses).

Operations on Symbol Table

A symbol table must efficiently support the following operations:

Operation Purpose
Insert(name, attributes) Add a new identifier when declared
Lookup(name) Search and retrieve information about an identifier
Delete(name) Remove an identifier (when it goes out of scope)
Modify(name, new_attributes) Update attributes (e.g., after type inference)
Display() List current entries (useful for debugging or visualization)

Data Structures for Symbol Tables

The choice of data structure affects lookup, insertion, and deletion efficiency.
Commonly used structures:

Linear List (Sequential Search Table)

Implementation: An unsorted or sorted linear list (array or linked list).

 Easiest way to implement Symbol table.

 New names are added to the table in the order that they arrive.

 Whenever a new name is to be added, the table is first searched linearly to check whether
or not the name is already present in the table.

 If the name is not present, then the record for the new name is created & added to the end
of the list

Advantages:

 Simple to implement.

 Good for small numbers of symbols.

Disadvantages:

 lookup becomes prohibitively slow for large symbol tables (e.g., in

large source files).

Hash Table

 A hash table is a table of k pointers from 0 to k−1 that points to the Record in a Symbol
table.

 Before entering a name into Symbol table we find out the hash value of the name by
applying hash function.

 This hash value specifies the position of the name in the symbol table having a value 0 to
k−1.

Position of name = h(Name)=value(0 to k−1)]

 .

 The adv. of using hashing is that it is very quick in searching.

 The disadv. of hashing is that it is complicated to implement.

Binary Search Trees (BSTs)

 It is an efficient approach to implement Symbol table.

 We add two links, left & right in each record.

 These links point to the record in the Symbol table.

 Whenever the name is to be added, first the name is searched in the tree.

 If the name is not available, then the record for the new name is created and added to the
proper position in the search tree.