Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is nonlocal data on the stack?
3.
Nested Procedures
4.
Accessing Non-Local Data
5.
Access Link
6.
Example
7.
Displays
8.
Frequently Asked Questions
8.1.
How does a compiler handle access to non-local data on the stack?
8.2.
What is the role of access links in accessing non-local data on the stack?
8.3.
How does the depth of nesting affect access to non-local data on the stack? 
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Access to Non-local data on the Stack in Compiler Design

Author Avni Gupta
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Compiler design is a crucial aspect of programming that involves the creation of software that can translate high-level programming languages into machine-readable code. The compilation process involves various stages, including lexical analysis, syntax analysis, semantic analysis, code generation, and optimization access to non-local data on the stack in compiler design.

Access to non-local data on the Stack in Compiler Design

In this blog, we will discuss one of the crucial aspects of compiler design: the management of data on the stack. In particular, compilers must ensure that access to non-local data on the stack is handled correctly.

What is nonlocal data on the stack?

In programming, variables are stored in memory locations that are referred to as the stack. A stack is a data structure that stores information in a last-in-first-out manner. When a function is called, a new frame gets created on the stack to store the function's local variables. However, a function may sometimes need to access data outside its scope. Such data is referred to as non-local data on the stack. Consequent access is called access to non-local data on the stack in compiler design.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Nested Procedures

In a programming language that allows for nested procedures (i.e., functions or subroutines defined within other functions), a new activation record gets created for that procedure's variables. It returns an address each time we call a nested procedure.

The activation records for nested procedures are organized in a stack-like data structure, where each stack frame is linked to the activation record of the calling function, forming a chain of activation records.

Accessing Non-Local Data

When a language allows nested procedures, access becomes difficult. For example, in the figure below, p is inside q, so at compile time, it is impossible to determine the position of each activation record. If either of p and q or both are recursive, then there will be a series of activation records.

nested functions

For p to access a variable or any kind of data declared in q, it requires the activation’s run-time information. Two strategies for accessing non-local data on the stack in Compiler Design are - Access Links and Displays. Let us look at each one of them.

Access Link

Access Links in one activation record are links that are used to refer to the non-local data in other activation records and provide access to it. A chain of access links is formed on the top of the stack and represents the program's scope or static structure.

The chain is a sequence of function activations with progressively lowering depths. The function currently being executed is at the end of the chain and has access to data and procedures of all the activations present in the chain.

Access link example representation

The above picture depicts how the stack looks with the activation records of 4 functions and how the access links are connected for various functions depending on their depths and positions.

f1()
{
	f2()
	f3()
	{
		f4()
	}
}

 

In this, f1() is the function calling all other functions that's why all other function’s access links point to its access link. Then f4() is called in f3().

The cost of lookup and maintenance is variable for access links.

Example

Code in C

int global_var = 5;

void foo()
{
    int x = 1;
    int y = global_var;
    bar();
}

void bar()
{
    int z = 3;
    z=y+z;// How can I access the global variable from here?
}

 

global_var: A global variable that is defined outside the functions foo() and bar().

x,y: local variables of the function foo()

z: local variable of the function bar()

When we call bar(), a new activation record is created for it which has variables x and y which were declared in it.

When foo() calls bar(), it wants to use y, a non-local bar variable. y is stored in the activation record of foo(). So, we use the chain of activation records to follow the chain until we reach the value of y.

Displays

One of the issues of the access links is that if there are many nested calls of functions, there will be a very long chain of access links that we must follow to reach the non-local data we need. To solve this, we make the use of displays.

Displays are auxiliary arrays that contain a pointer for every nesting depth. At any point, d[i] is the pointer to the activation record which is the highest in the stack for a procedure which is at depth i.

Display representation

In the above figure, we assume that each function f1(),f2(), f3(), and f4() lies at different depths. d[1] holds the pointer to the activation record for f1(), the only one for that depth. Similarly, there are pointers for each depth.

Now if a procedure requires access to data from another procedure, let's say f2() wants to access some data from f1(), then runtime only searches in activations from d[i] where i is the nesting depth of f1() and follow the pointer.

The cost of lookup and maintenance is constant for displays.

Also see, Cross Compiler

Frequently Asked Questions

How does a compiler handle access to non-local data on the stack?

The compiler generates code to set up an access link in the current stack frame, pointing to the calling function's stack frame or subroutine. This allows nested functions or subroutines to access non-local variables by following the chain of stack frames using access links.

What is the role of access links in accessing non-local data on the stack?

Access links are pointers that follow the chain of stack frames to locate non-local variables. They point to the stack frame of the calling function or subroutine, allowing nested functions or subroutines to access variables in the calling function's stack frame and variables in the stack frames of any other calling functions up the chain.

How does the depth of nesting affect access to non-local data on the stack? 

The depth of nesting refers to the number of levels of nested functions or subroutines. Each level of nesting requires an additional link in the chain of stack frames, which must be followed to access non-local data on the stack. Therefore, deeper levels of nesting can lead to longer chains of stack frames and potentially slower access times.

Conclusion

In summary, access links are used in nested procedures to allow for access to non-local variables. The access link is a special pointer that points to the stack frame of the calling function, and it is used to follow the chain of stack frames to locate the variable's memory location. The depth of nesting refers to the number of levels of nested procedures, and it affects the length of the stack frame chain that must be followed to access non-local variables.

Check out the following blogs:

You can also consider our Mern Stack Course to give your career an edge over others.
Happy Learning!!

Previous article
Characteristics of Compiler
Next article
What is a Compiler?
Live masterclass