Activation records and call stack in Compiler Design - Full Explanation

Introduction

Imagine you are following a recipe that calls for other recipes inside it. You need a way to keep track of where you are and what ingredients you need at each step. Activation records and the call stack solve this problem for programs when they call functions inside other functions.

Explanation

Activation Record

An activation record is a special box that holds all the information a function needs when it runs. This includes the function's parameters, local variables, and where to return after finishing. Each time a function is called, a new activation record is created to keep its data separate from others.

Activation records store all the data needed for a single function call.

Call Stack

The call stack is like a stack of plates where each plate is an activation record. When a function calls another, a new activation record is placed on top. When a function finishes, its activation record is removed from the top. This keeps track of the order of function calls and returns.

The call stack manages activation records in the order functions are called and finished.

Function Call Process

When a function is called, the program creates an activation record and pushes it onto the call stack. The function runs using the data in this record. When the function ends, its activation record is popped off the stack, and control returns to the previous function.

Function calls add activation records to the stack; returns remove them.

Why This Matters

This system allows programs to handle many nested function calls without mixing up data. It also helps in managing recursion, where a function calls itself multiple times, by keeping each call's data separate.

Activation records and the call stack keep function calls organized and data isolated.

Real World Analogy

Imagine you are reading a book and come across a reference to another book. You put a bookmark in the current book and open the new one. When done, you close the new book and return to the first bookmark. This way, you never lose your place in any book.

Activation Record → A bookmark holding your place and notes in a book

Call Stack → A stack of bookmarks for all the books you are reading in order

Function Call Process → Putting a new bookmark when opening a new book and removing it when done

Why This Matters → Ensuring you never lose track of where you are in any book, even with many references

Diagram

Diagram

┌───────────────┐
│ Activation    │
│ Record for    │
│ Function C    │
├───────────────┤
│ Activation    │
│ Record for    │
│ Function B    │
├───────────────┤
│ Activation    │
│ Record for    │
│ Function A    │
└───────────────┘

Call Stack (top is current function)

This diagram shows the call stack with activation records stacked for nested function calls.

Key Facts

Activation Record → A data structure that stores information needed for a single function call.

Call Stack → A stack data structure that manages activation records in the order of function calls.

Push Operation → Adding a new activation record to the top of the call stack when a function is called.

Pop Operation → Removing the top activation record from the call stack when a function returns.

Recursion → A function calling itself, relying on the call stack to keep each call's data separate.

Common Confusions

Thinking all function calls share the same data space.

Thinking all function calls share the same data space. Each function call has its own activation record, so local variables and parameters do not interfere with each other.

Believing the call stack grows downward in memory always.

Believing the call stack grows downward in memory always. The call stack's growth direction depends on the system architecture; conceptually, it is a stack structure managing activation records.

Assuming the call stack stores the actual function code.

Assuming the call stack stores the actual function code. The call stack stores data about function calls, not the code itself, which resides elsewhere in memory.

Summary

Activation records hold all the information a function needs during its execution, keeping data separate for each call.

The call stack organizes these activation records in the order functions are called and returned, managing nested and recursive calls.

This system ensures programs run functions correctly without mixing data or losing track of where they are.