Activation records and call stack in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of activation records

What is the main purpose of an activation record in the context of function calls?

A To manage the input/output operations of a program

B To hold the compiled machine code of a function

C To store information about a function call such as parameters, local variables, and return address

D To keep track of global variables across the entire program

💡 Hint

Think about what information a program needs to remember when it calls a function and later returns.

An activation record stores all the necessary information for a single function call, including parameters, local variables, and where to return after the function finishes.

📋 Factual

intermediate

Call stack behavior during nested function calls

Consider three functions: main calls funcA, which calls funcB. How does the call stack change during these calls?

A The call stack replaces the activation record of <strong>main</strong> with <strong>funcA</strong>, then replaces <strong>funcA</strong> with <strong>funcB</strong>

B The call stack remains empty until <strong>funcB</strong> is called

C The call stack grows by adding activation records for <strong>funcB</strong>, then <strong>funcA</strong>, then <strong>main</strong>

D The call stack grows by adding activation records for <strong>main</strong>, then <strong>funcA</strong>, then <strong>funcB</strong> in that order

💡 Hint

Remember that each function call adds a new activation record on top of the stack.

When functions call other functions, each call adds a new activation record on top of the call stack, preserving the order of calls.

🔍 Analysis

advanced

Identifying the return address in an activation record

Which part of an activation record is responsible for telling the program where to continue execution after a function returns?

A Return address field

B Local variables section

C Parameter list

D Saved frame pointer

💡 Hint

Think about what the program needs to know to resume after finishing a function.

The return address field stores the location in the code where execution should continue after the function call completes.

❓ Comparison

advanced

Difference between static and dynamic links in activation records

What is the key difference between static links and dynamic links stored in activation records?

A Static links are used only in recursive calls, dynamic links are used in iterative calls

B Static links point to the activation record of the lexically enclosing function, dynamic links point to the caller's activation record

C Static links store local variables, dynamic links store parameters

D Static links point to the caller's activation record, dynamic links point to the lexically enclosing function

💡 Hint

Consider the difference between lexical scope and call history.

Static links help access variables in the surrounding code blocks (lexical scope), while dynamic links help return control to the caller function.

❓ Reasoning

expert

Effect of missing dynamic link on program execution

What would most likely happen if an activation record did not store a dynamic link during a function call?

A The program would fail to return correctly to the caller, causing incorrect execution flow or crash

B The function would not be able to access its local variables

C The program would run normally without any issues

D The function parameters would be lost during the call

💡 Hint

Think about how the program knows where to go after a function finishes.

Without the dynamic link, the program cannot find the caller's activation record to return control, leading to incorrect execution or crash.

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