Activation records and call stack in Compiler Design - Step-by-Step Execution

Concept Flow - Activation records and call stack

Function Call

↓

Create Activation Record

↓

Push Record on Call Stack

↓

Execute Function Body

↓

Function Returns

↓

Pop Activation Record from Stack

↓

Resume Caller Execution

When a function is called, a new activation record is created and pushed onto the call stack. The function runs, then its record is popped off when it returns, resuming the caller.

Execution Sample

Compiler Design

def main():
    print('Start')
    greet('Alice')
    print('End')

def greet(name):
    print('Hello,', name)

This code calls greet from main, showing how activation records are created and removed on the call stack.

Analysis Table

Step	Action	Call Stack State	Current Function	Output
1	main() called	[main]	main
2	print('Start')	[main]	main	Start
3	greet('Alice') called	[main, greet]	greet
4	print('Hello, Alice')	[main, greet]	greet	Hello, Alice
5	greet returns	[main]	main
6	print('End')	[main]	main	End
7	main returns	[]	none

💡 main function finishes, call stack is empty, program ends

State Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	Final
Call Stack	[]	[main]	[main, greet]	[main]	[]
Current Function	none	main	greet	main	none

Key Insights - 3 Insights

Why does the call stack grow when a function is called?

Each function call creates a new activation record pushed onto the stack to keep track of that call's data and return point, as shown in steps 1 and 3 of the execution table.

What happens to the activation record when a function finishes?

The activation record is popped off the call stack to free space and return control to the caller, as seen in steps 5 and 7.

Why is the call stack empty at the end?

Because all functions have returned and their activation records removed, leaving no active calls, shown in the final step 7.

Visual Quiz - 3 Questions

Look at the execution table at step 3. What is the call stack state?

A []

B [main]

C [main, greet]

D [greet]

💡 Hint

Check the 'Call Stack State' column at step 3 in the execution table.

At which step does the function greet return and its activation record get removed?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look for the 'greet returns' action in the execution table.

If main called another function before printing 'End', how would the call stack change at step 6?

A It would have two activation records

B It would be empty

C It would have only main

D It would have three activation records

💡 Hint

Refer to the call stack growth pattern in the variable tracker and execution table.

Concept Snapshot

Activation records store function call info.
Each call pushes a record on the call stack.
Function runs using its record.
Return pops the record off.
Call stack tracks active calls.
Empty stack means program end.

Full Transcript

When a function is called, the program creates an activation record that holds information like parameters, local variables, and return address. This record is pushed onto the call stack, which keeps track of all active function calls. The function executes using its activation record. When the function finishes, its activation record is popped off the stack, and control returns to the caller. This process repeats for every function call. The call stack grows with each call and shrinks as functions return. When the main function returns, the call stack is empty, and the program ends.

Practice

1. What is the main purpose of an activation record in a program's execution?

easy

A. To store information about a function call such as parameters and local variables

B. To manage the computer's memory allocation for the entire program

C. To compile the source code into machine code

D. To display output on the screen

Solution

1. Step 1: Understand what an activation record stores

   An activation record holds details about a specific function call, including parameters, local variables, and return address.

2. Step 2: Identify the main purpose

   This helps the program keep track of function calls and return correctly after execution.

3. Final Answer:

   To store information about a function call such as parameters and local variables -> Option A

4. Quick Check:

   Activation record = function call info [OK]

Hint: Activation record = function call details stored [OK]

Common Mistakes:

• Confusing activation record with overall memory management
• Thinking activation record compiles code
• Assuming activation record handles output display

2. Which of the following correctly describes the call stack's behavior during function calls?

easy

A. It executes functions in parallel without stacking

B. It removes the activation record before the function starts

C. It stores all activation records in a queue structure

D. It adds a new activation record on top when a function is called

Solution

1. Step 1: Recall how the call stack works

   The call stack adds (pushes) a new activation record on top each time a function is called.

2. Step 2: Confirm the correct description

   This stacking ensures the program knows which function is currently running and where to return after completion.

3. Final Answer:

   It adds a new activation record on top when a function is called -> Option D

4. Quick Check:

   Call stack pushes activation records [OK]

Hint: Call stack pushes new records on function call [OK]

Common Mistakes:

• Thinking activation records are removed before function starts
• Confusing stack with queue behavior
• Assuming functions run in parallel without stacking

3. Consider this sequence of function calls: main() calls funcA(), which calls funcB(). What is the order of activation records on the call stack just before funcB() finishes?

medium

A. funcB at bottom, funcA in middle, main on top

B. funcA at bottom, main in middle, funcB on top

C. main at bottom, funcA in middle, funcB on top

D. funcB at bottom, main in middle, funcA on top

Solution

1. Step 1: Understand call stack order

   The call stack adds activation records in order of calls: main first, then funcA, then funcB on top.

2. Step 2: Determine stack order before funcB finishes

   Since funcB is currently running, its record is on top, with funcA below it, and main at the bottom.

3. Final Answer:

   main at bottom, funcA in middle, funcB on top -> Option C

4. Quick Check:

   Call stack order = main, funcA, funcB [OK]

Hint: Last called function's record is on top [OK]

Common Mistakes:

• Reversing the order of activation records
• Confusing bottom and top of the stack
• Assuming parallel execution changes stack order

4. A programmer notices that after a function returns, the call stack still contains its activation record. What is the most likely cause?

medium

A. The function was never called

B. The activation record was not properly removed (popped) from the stack

C. The call stack is implemented as a queue

D. The program has no functions

Solution

1. Step 1: Understand normal call stack behavior on return

   When a function finishes, its activation record should be removed (popped) from the call stack.

2. Step 2: Identify cause of leftover activation record

   If the record remains, it means the stack pop operation did not happen correctly.

3. Final Answer:

   The activation record was not properly removed (popped) from the stack -> Option B

4. Quick Check:

   Activation record must be popped after return [OK]

Hint: Function return must pop activation record [OK]

Common Mistakes:

• Assuming function was never called
• Confusing stack with queue behavior
• Ignoring that program has functions

5. In a recursive function that calls itself 4 times before returning, how many activation records will be on the call stack at the deepest point of recursion?

hard

A. 5

B. 2

C. 1

D. 4

Solution

1. Step 1: Understand recursion and activation records

   Each recursive call adds a new activation record to the call stack.

2. Step 2: Count total activation records

   If the function calls itself 4 times, there are 4 new calls plus the original call, totaling 5 activation records on the stack.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Recursive calls + original = 5 activation records [OK]

Hint: Count original call plus recursive calls [OK]

Common Mistakes:

• Counting only recursive calls, ignoring original
• Assuming recursion does not add activation records
• Confusing number of calls with return points