Run-Time Environment in Compiler Design: Activation Records, Access Links, and Worked Examples

Run-time environment seems dry until GATE asks for access-link hops, peak recursion depth, or output under a parameter-passing rule. All three answers come out of one picture: how code, static data, the heap, and the control stack divide memory while a program runs, and what each procedure call pushes onto that stack. Lexical Analysis in Compiler Design deals with the front end that reads your source, and this is the memory layout the compiled program then executes in.

What a run-time environment actually is

A run-time environment is the memory arrangement and bookkeeping that gives every executing call, variable, and dynamic object a place to live.

The logical address space has four standard regions, from top to bottom:

1. Code or text: Fixed-size machine instructions.

2. Static or global data: Globals and static variables with compile-time addresses.

3. Heap: Dynamically allocated objects, from operations such as new or malloc, which may outlive their creating call. It grows towards higher addresses.

4. Stack or control stack: Activation records for live procedure calls. It grows towards lower addresses.

Code and static data are fixed at compile time. Heap and stack sizes emerge at run time, sharing the free space between them.

Activation records and the control stack

An activation is one procedure execution. Entry pushes its activation record, or stack frame, and return pops it.

A standard record contains these fields, top to bottom:

1. Actual parameters: Values or addresses from the caller.

2. Returned-value slot: Space for the result.

3. Control link: Pointer to the caller's record.

4. Access link: Pointer to the lexically enclosing procedure's record.

5. Saved machine status: Return address and saved registers.

6. Local data: Variables of this activation.

7. Temporaries: Intermediate expression values.

A depth-first walk of the activation tree gives call and return order. Live activations form its root-to-current-node path, exactly the control stack. This last-in-first-out discipline is central to Context-Free Grammars and Pushdown Automata.

Static, stack, and heap allocation

• Static allocation binds fixed addresses for the whole run. It cannot support recursion because simultaneous activations need separate local variables, but static storage supplies one copy.

• Stack allocation pushes and pops records in last-in-first-out order. Every recursive activation gets a fresh record.

• Heap allocation holds data that must survive its creating call. Allocation and release can occur in any order.

For this function, consider fact(4):

int fact(int n) {
  if (n == 0) return 1;
  return n * fact(n - 1);
}

The activation chain is fact(4) -> fact(3) -> fact(2) -> fact(1) -> fact(0). All 5 calls are live at fact(0), so peak depth is 5 records. In general, fact(n) needs n + 1 records because the base-case call also gets one.

Suppose a record holds parameter n (2 bytes), return address (2), control link (2), and returned-value slot (2):

2 + 2 + 2 + 2 = 8 bytes per record

Therefore, peak stack use is:

5 records x 8 bytes = 40 bytes

That is the numerical pattern: count simultaneously live records, then multiply by record size.

Accessing nonlocal data with access links and displays

Under lexical scope, a nested procedure can read variables declared outside it. The correct outer activation is not always its caller, so the control link is insufficient. An access link instead points to the activation of the lexically enclosing procedure.

The counting rule is simple: from running depth D to declaration depth d, follow exactly D - d access links. A local needs D - D = 0 links.

procedure main;            // depth 1
  var a: integer;
  procedure p;             // depth 2
    var x: integer;
    procedure q;           // depth 3
      var y: integer;
    begin                  // body of q
      y := a + x;
    end;
  begin                    // body of p
    q;
  end;
begin                      // body of main
  p;
end.

While q runs, the chain is q.AR -> p.AR -> main.AR.

• For a: 3 - 1 = 2 access links.

• For x: 3 - 2 = 1 access link.

• For local y: 3 - 3 = 0 links.

A display is an array d[] indexed by nesting depth, where d[i] points to the latest activation at depth i. It changes a nonlocal read from walking D - d links to one O(1) array lookup, at the cost of saving and restoring entries on calls and returns.

Parameter passing changes program output

• Call by value: Copy the argument's value. Parameter changes do not reach the caller.

• Call by reference: Make the parameter an alias for the argument. Changes appear immediately.

• Call by value-result: Copy in on entry and copy the final value back on return.

• Call by name: Substitute the argument expression and evaluate it on every parameter use.

Now trace this program from n = 5:

void inc(int x) { x = x + 1; }
int n = 5;
inc(n);
print(n);

Value prints 5 because only the copy changes. Reference prints 6 because x aliases n. Value-result prints 6 after copying back. Name prints 6 here because substitution gives n = n + 1.

Reference and value-result differ when the argument is aliased: reference writes through immediately, while value-result writes back only on return, so a read taken in between sees different values. Call by name goes further and re-evaluates the argument expression at every use, so passing a[i] while the callee changes i can reach a different element on each use.

Common run-time environment traps

• Control versus access: Why: both point upwards. Wrong: the caller may not be the lexical parent. Do: control means caller; access means source enclosure.

• Off-by-one counts: Why: students count a depth. Wrong: the answer shifts by one. Do: calculate D - d.

• Static recursion: Why: fixed storage works without recursion. Wrong: live calls share locals. Do: give every call a fresh stack record.

• Missing the base case: Why: the base call only returns a constant, so it looks free. Wrong: fact(4) becomes 4, not 5. Do: count every entered call.

• Local address: Why: the code may compile. Wrong: popping the record leaves a dangling pointer. Do: put longer-lived data on the heap.

• Value-result versus reference: Why: simple outputs match. Wrong: aliases can diverge. Do: trace immediate updates and final copy-back.

How GATE and interviews test run-time environments

GATE asks for peak stack depth, total stack bytes, access-link counts, or output under parameter passing. Here, fact(4) peaks at 5 records and 40 bytes, while q follows 2 links for a and 1 for x. Interviews ask about stack versus heap, recursion, and stack-frame fields.

Compiler Design for GATE: Syllabus Areas, Weightage Pattern and How to Prepare lists run-time environments among the named GATE syllabus areas and sets the order to study the compiler phases in.

The official GATE Computer Science syllabus, published by the organising IIT for each cycle, lists Compiler Design and run-time environments. The standard concept reference is Aho, Lam, Sethi and Ullman, Chapter 7, "Run-Time Environments". Confirm the current-cycle syllabus on the official GATE portal.

The short version and your next step

A run-time environment organises code, static data, heap, and stack. Each call pushes a record with parameters, links, saved status, locals, and temporaries. Recursion needs a fresh stack record. Nonlocals take D - d access-link hops or one display lookup. Parameter passing can change the result.

Now redo fact(4) as fact(6): 6 + 1 = 7 records, and 7 x 8 = 56 bytes. Then add a fourth nesting level and recount each nonlocal access.

For guided coverage, continue with GATE Guidance by Sanchit Sir. For timed numerical and parameter-passing practice, use the GATE Test Series (Mocks and Topic-wise Tests).