Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
How is an activation tree created?
Symbol table in activation tree with example
1.
Example
2.
The sequence of calls 
3.
Understanding the Activation Tree 
4.
Activation record and its components.
5.
Uses of Activation Tree
6.
Frequently Asked Questions
6.1.
What is an activation tree in compiler design?
6.2.
Why do we use an activation tree in compiler design?
6.3.
What are activation records?
7.
Conclusion
Last Updated: Jun 11, 2024
Medium

Activation Tree in Compiler Design

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

An activation tree tells the flow of execution of a program and represents it in a graphical manner where each node depicts a particular procedure.

A compiler uses stack-based memory management to manage, allocate, and deallocate memory for executing a program. It uses some units of user-defined action, such as procedures, methods, or functions for managing their runtime memory or a part of memory on the stack. 

Activation Tree in Compiler Design

How is an activation tree created?

Whenever a compiler calls a procedure, it allocates a space for it by pushing it into the stack. After the termination of the procedure, it is popped off the stack. This enables sharing of space by procedure calls. Thus the use of stack makes code compilation efficient. The compiler allocates space to the activation record on the stack’s top.

The execution of a procedure is known as activation. An activation record comprises all the crucial information required to call a procedure. It stores immediate values and temporary values of expression.
Each procedure’s activation record is pushed in a stack in a predictable order. A procedure performs a specific task, and whenever it is called an instance of the procedure, an activation is created. 

The local variables can be accessed relatively at the code’s beginning and the non-local variable’s address.  A program has a sequential flow of control. Control is passed to the part of the procedure called for execution. After the procedure is completed, the control returns to the caller. 

Procedure activates a tree where the main program is the root and a new node is created whenever a procedure is called. The children of the tree represent the procedures from the particular node.A procedure is considered recursive if a new activation starts before the completion of the previous procedure. Therefore an activation tree tells the flow of execution of a program and represents the control flow of a program in a graphical manner where each node depicts a particular procedure.

Symbol table in activation tree with example

A symbol table is a data structure that the compiler uses for storing information regarding functions, a variables symbols in a program. It stores the name of all the entities in a structured manner and determines the scope of a variable or a procedure. A runtime behavior can be depicted using the activation tree.

Each node is a procedure in the activation tree with its symbol table consisting of information about its variables and procures used in that particular node.

Code

#include <iostream>
using  namespace std;

int NinjaVar1=5;
void NinjaFunc(){
    int NinjaVar=20;
    cout<<"NinjaFunc() called in main():"<<NinjaVar1+NinjaVar;
}

int main() {
   
    NinjaFunc();
    
    return 0;
}


Output

output

The symbol table for the above program is represented in the following activation tree.

symbol table

In the main function, the ‘NinjaFunc()’ takes a parameter of data type ‘int’  and consists of the local variable ‘NinjaVar’ of data type ‘int.’ When the ‘‘NinjaFunc()’ is called from the main function, a node in the activation tree is created. Similarly, other nodes are created when the program continues further.

Example

Let's understand the activation tree using merge sort.

Consider the following pseudo-code of merge sort.

int a[4];

void NinjaReadArray(){
    
    //function that reads the input
    //from the code for performing computations   
}

void Ninjamerge(arr,s,e){
    
    //merging
}

void NinjamergeSort(array[],s,e){
     if(s>=e) return;
     int mid=(s+e)/2;     
     mergeSort(arr,s, mid);     
     mergeSort(arr,mid+1,e);     
     merge(arr,mid+1,e);    
}

int main() {
   NinjaReadArray();
   NinjamergeSort(0,4);
    
   return 0;
}


In the above pseudo-code, we have called the NinjaReadArray() function that reads the input from the code for performing computation. It is used for separating the code that reads the input and is considered a better practice rather than keeping hard-coded values in a program.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The sequence of calls 

Let's see the sequence of calls involved in the execution of a program.

enter main(){
    enter NinjaReadArray()
    leave NinjaReadArray()
    enter NinjaMergeSort(arr,0,3){

        enter NinjaMergeSort(0,1){

            enter NinjaMergeSort(0,0)
            leave NinjaMergeSort(0,0)

            enter NinjaMergeSort(1,1)
            leave NinjaMergeSort(1,1)

            enter NinjaMerge(0,1)
            leave NinjaMerge(0,1)
        }
        
        leave NinjaMergeSort(0,1)
        
        enter NinjaMergeSort(2,3){
            enter NinjaMergeSort(2,2)
            leave NinjaMergeSort(2,2)

            enter NinjaMergeSort(3,3)
            leave NinjaMergeSort(3,3)

            enter NinjaMerge(2,3)
            leave NinjaMerge(2,3)
        }
        
        leave NinjaMergeSort(2,3)
        
        enter NinjaMerge(0,1,2,3)
        leave NinjaMerge(0,1,2,3)
    }
    leave NinjaMergeSort(0,3)  
}
leave main()


In the above activation tree for the merge sort, we first enter the main() program, and the NinjaReadArray() function reads the input values for 4 elements. Next, the NinjaMergeSort() function is called with starting index (s=0) and ending index (e=3) as arguments. We know that merge sort is a recursive function. Therefore the array is divided into two halves, i.e., NinjaMergeSort(0,1) and NinjaMergeSort(2,3), and the NinjaMerge() function merges the sorted arrays.

From the above example, we can see that if procedure A is activated first, and it calls for a specific procedure, say, B, then the activation of B ends before the activation of A.

When the B procedure terminates, the control resumes after the point where the call for B was made in procedure A.

Also, if B faces any error in the execution that that error propagates to A, it will also abort, i.e., stop its execution if A cannot handle the exceptions; thus, they will end their computations simultaneously.

Therefore the procedure’s activation can be represented in a tree structure, where each node represents a specific procedure, and the root is the main() procedure.

Understanding the Activation Tree 

Procedure calls are managed by the control stack, a runtime stack(also known as the execution stack). The function calls made during the program execution are tracked by a runtime stack. The root of the tree is present at the bottom of the stack.

We have the following activation tree to represent merge sort execution. 

activation tree

The sequence of procedure calls can be known using the pre-order traversal of the activation tree, and the sequence of returns can be known using the post-order traversal of the activation tree.

The activation tree can be considered as a map. Like many paths to reach a destination, each stop can be considered a procedure. As we call a procedure, a new branch is created in the activation tree, and branches are created below it if this further calls more procedures, as shown in the image. 

The ‘live’ activations are those where we are currently present/visiting and the ones before using which we arrived at that particular node/destination. The activations are returned in reverse, meaning the most recent node is returned first as we move back up the path. At last, we are back at the tree's root when the execution is finished.

Activation record and its components.

An activation record is stored in a stack during runtime. The activation record stores temporary values, local data, saved machine status, and access links. The contents of an activation cord can vary according to a programming language. Some languages may have only minimum requirements, but languages such as Python, java may consist of additional information. They are created dynamically when a program is executed. Therefore the activation records can be visualized using an activation tree.

The components of activation records are mentioned below.

  • Temporary values: Temporary values are those entities that arise whenever we evaluate an expression and are stored in fields.
     
  • Local data: This field consists of local data for a particular procedure’s execution.
     
  • Saved Machine Link: This field contains information regarding the machine’s state before a procedure is called.It have program counter and machine register’s value. These values are restored whenever the control is returned from the procedure.
     
  • Access Link: This field refers to the non-local information stored in other activation 
    records. This is a static link through which we can access the data not present in the activation record’s local scope.

Uses of Activation Tree

Some of the uses of an activation tree are mentioned below.

  • An activation tree tells the flow of execution of a program. It represents the control flow of a program in a graphical manner, which makes it easier to understand the flow of execution.
     
  • An activation tree is used in managing a stack of activation records.
     
  • The scope of variables can also be determined using an activation tree.
     
  • The current activation record is tracked using an activation tree and helps generate code for nested procedure calls.
     
  • In languages like C/C++, activation trees are used to manage function and block scopes. When each function is called, a new symbol table is created that stores the function, parameters, local variables, etc. After the execution, the symbol tables are removed from the activation tree.
     
  • Activation trees are used for managing classes, methods, and block scopes; in languages like Python, they also manage module scopes, and in JavaScript, for managing function and block scopes.


Also see, Cross Compiler

Frequently Asked Questions

What is an activation tree in compiler design?

An activation tree tells the flow of execution of a program and represents the control flow of a program in a graphical manner where each node depicts a particular procedure. The execution of a procedure is known as activation.

Why do we use an activation tree in compiler design?

An activation tree tells the flow of execution of a program. It represents the control flow of a program in a graphical manner, which makes it easier to understand the flow of execution.

What are activation records?

An activation record is stored in a stack during runtime. The activation record stores temporary values, local data, saved machine status, access link, returned values, and actual parameters. The contents of an activation cord can vary according to a programming language.

Conclusion

In this article, we have discussed activation trees in compiler design, uses of activation trees, and activation records. We have also discussed an example to understand the concept properly. You can read more such articles on our platform, Coding Ninjas Studio.

Also, Read-


You will find straightforward explanations of almost every topic on this platform. So take your coding journey to the next level using Coding Ninjas.

Happy coding!

Previous article
Handle in Compiler Design
Next article
First and Follow in Compiler Design
Live masterclass