Activation Records and Symbol Tables in Block-Structured Languages

The Runtime Stack and Activation Records

When a program runs, it needs to manage memory for its procedures (or functions). In most modern languages, this is handled using a call stack. The logic is simple: when a function is called, memory for it is allocated on the stack; when the function returns, that memory is deallocated. The block of memory allocated for a single function call is known as an activation record or stack frame.

An activation record contains all the information necessary for the execution of one invocation of a procedure. While the exact layout can vary, a typical activation record contains several key fields.

To get a concrete idea of these fields, we'll watch a short video that introduces the structure of an activation record.

As you just saw, an activation record is a structured block of data. Let's examine its most important components more closely.

1. Local Variables & Temporary Values

This is perhaps the most intuitive part of the stack frame. Any variables declared inside a function (local variables) need a place to live. The compiler reserves space for them within the activation record.

Additionally, when the compiler evaluates complex expressions, it often needs to store intermediate results. For instance, in z = (a*b) + (c*d), the result of a*b must be stored temporarily while c*d is computed. This space is also allocated within the activation record.

2. Machine Status (including Return Address)

When a function F calls another function G, the program's execution jumps to the start of G. But once G finishes, how does the program know where to resume execution within F?

The activation record saves the state of the machine at the point of the call. The most critical piece of this state is the return address—the address of the instruction immediately following the call. This is usually stored in a special register called the Program Counter (PC) before the jump, and this value is saved in the new activation record. When the called function finishes, the CPU uses this saved return address to jump back and continue.

3. Actual Parameters & Return Value

Functions communicate with each other by passing parameters and returning results. The activation record facilitates this.

• Actual Parameters: The values passed by the caller to the callee are placed in the callee's activation record, where the callee can access them.
• Return Value: A designated spot in the activation record (or a machine register) is used to hold the result of the function, which the caller can then access after the function returns.

4. Control Link and Access Link

These two pointers are essential for managing the stack and accessing variables across different scopes, and they are a frequent topic in GATE questions.

• Control Link (or Dynamic Link): This pointer always points to the activation record of the caller. It forms a chain of stack frames based on the sequence of function calls that occurred dynamically at runtime. When a function returns, the control link is used to find the previous frame, reset the stack pointer, and restore the caller's context.

• Access Link (or Static Link): This pointer is used in block-structured languages with nested functions (like Pascal, or lambda functions in modern languages). It points to the activation record of the function that lexically contains the current function's definition in the source code. This allows a nested function to access variables of its parent function, even if the parent is not the direct caller. This mechanism implements static (lexical) scoping.

The distinction is crucial: the control link follows the dynamic call chain, while the access link follows the static nesting structure of the source code.

Symbol Tables for Block-Structured Languages

We've seen the runtime structure of an activation record. But how does the compiler know the size of local variables, their types, and their positions (offsets) within the stack frame? It gathers this information during the semantic analysis phase and stores it in a symbol table.

A symbol table is a compile-time data structure that maps identifiers (names of variables, functions, etc.) to information about them (type, scope, storage location, etc.). In block-structured languages like C, C++, and Java, where new scopes can be created by blocks (e.g., {...}), the symbol table management is particularly important.

The compiler must handle situations where the same name is used in different scopes, for example:

int x = 10; // Global scope

void myFunction() {
    int x = 20; // Local scope of myFunction
    if (true) {
        int x = 30; // Inner block scope
        printf("%d", x); // Prints 30
    }
    printf("%d", x); // Prints 20
}

To manage this, the compiler uses a scoping mechanism for its symbol table. When it enters a new block, it creates a new symbol table for that scope. When an identifier is used, the compiler searches for it starting from the innermost scope's table and moving outwards until a declaration is found.

The process described in the video is key:

• On entering a block ({): A new symbol table for the current scope is created and linked to the parent scope's table. This is the set operation.
• On exiting a block (}): The symbol table for the current scope is discarded. This is the reset operation.

This stack-like behavior for symbol tables perfectly mirrors the block structure of the code and allows the compiler to resolve names according to lexical scoping rules. The information gathered—like the type of a variable and its relative order in a block—is then used to determine the layout of the activation record, specifically the offsets of local variables from the start of the frame.

Conclusion

In this lesson, we explored the bridge between the compiler's analysis and the program's actual execution. You learned how the runtime environment organizes memory and manages control flow.

Here are the key takeaways:

• Runtime Environments use a call stack to manage function calls.
• Each function call gets an activation record (or stack frame), which stores local variables, parameters, return values, and control information.
• The Control Link (dynamic) points to the caller's frame, while the Access Link (static) points to the frame of the lexically enclosing scope, enabling access to non-local variables.
• Symbol Tables are a compile-time data structure used to track identifiers and their attributes (like type and scope).
• In block-structured languages, symbol tables are managed hierarchically to enforce lexical scoping rules, and the information they contain is used to plan the layout of activation records.

In our next lesson, we will move on to Intermediate Code Generation. You will see exactly how the information from the symbol table—specifically the types and calculated offsets of variables—is used to generate machine-independent code like Three-Address Code (TAC), preparing our program for the final stages of compilation.