Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Symbol Table?
2.1.
Objectives of Symbol Table Operations and Data Structures
2.2.
Format of Symbol Table
3.
Symbol Table Operations
3.1.
insert()
3.2.
lookup()
4.
Data Structures in Symbol Table
5.
Frequently Asked Questions
5.1.
What is a symbol table and what is its use?
5.2.
What are the data structures used for the implementation of the symbol table?
5.3.
What is in the symbol table associated with the name of an object?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Symbol Table: Operations and Data Structures

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Symbol table operations include inserting, searching, and deleting symbols. Data structure used for symbol tables include hash tables, binary search trees, and linked lists. The choice of data structure depends on the requirements of the application and the characteristics of the symbols being stored.

The main work of a compiler is to convert a program written in a source language(high-level) to a low-level language(Object or Machine Language). While converting the codes, the compiler does not change the logic of the code. Compiler Design is the set of principles that guide the translation, analysis, and optimization process. Since the compiler does various tasks while accessing variables and dynamically allocating memory, it requires a symbol table for convenience. Let us dive deeper into this!

Also see, Phases of Compiler

Symbol Table Operations

What is Symbol Table?

Symbol Table is a vital data structure created and maintained by the compiler to keep track of the semantics of variables. A symbol table stores information about the scope and necessary details on names and instances of several entities, like names of variables and functions, classes, objects, etc. Devices will have a challenging time determining addresses or understanding anything about the program if the symbol table has been stripped before the translation into an executable.

Also see Scope Information

Objectives of Symbol Table Operations and Data Structures

A symbol table serves the following objectives:

  • It verifies whether a variable has been declared.
  • It stores all entities' names in a structured form in a single place.
  • It determines the scope of a name.
  • It implements type checking by verifying whether the assignments and expressions in the source code are semantically correct or not.
  • It may be included in a process output to be used later during debugging sessions.
  • It serves as a resource for creating a diagnostic report during or after program execution.

Also Read - Symbol Table Operations ,hash function in data structure

Format of Symbol Table

A symbol table is simply a table which can be either linear or a hash table. Each item in the symbol table has properties like name, kind, type, and others, like the image added below.

Format of Symbol Table

 

Also See, Specifications of Tokens 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

Symbol Table Operations

A symbol table provides the following operations.

insert()

The operation insert( ) inserts information in the table about unique names occurring in the code. The format in which the names are stored depends on the compiler. The analysis phase, i.e., the first half, where tokens are identified, and names are stored in the symbol table more frequently uses this operation. The attributes of a symbol are information associated with the symbol like state, scope, type, etc. The symbols and attributes of the symbols are the arguments of the insert() function. Take, for example, the user writes int a; in the code.

Now, the compiler processes this as insert(a, int);

lookup()

The lookup() operation's primary function is to search for a name in the symbol table. The lookup() function format varies from language to language. The basic format is lookup(symbol). The function returns zero if the entered symbol does not exist in the table, and if it does, it returns its attributes stored in the table. The lookup() function also determines-

  • If the symbol is declared before it is being used.
  • If the name is used in the scope.
  • If the symbol is initialized.
  • If the symbol is declared multiple times.

Data Structures in Symbol Table

Data Structures used for the implementation of symbol tables are-
1.Binary Search Tree
2.Hash Tables
3.Linear search

A compiler contains two types of symbol tables: global and scope symbols tables. All the procedures and the scope symbol table can access the global symbol table while the scope symbol tables are created for each scope in the program. The scope of a name can be determined by arranging the table in the hierarchy structure as shown below: 

int number1;    
int method1()  
{  
  int number2;  
  int number3;  
  {  
    int number4;  
    int number5;  
  }  
  int number6;         
  {
   int number7;
   int number8;  
   }  
 }  
  
int method2()  
{  
  int number9;  
  int number10;  
  {  
    int number11;  
    int number12;  
  }  
  int number13;  
}  

The above code can be arranged hierarchically in the following order:

Data Structures

The global symbol table contains one global variable of integer value and two procedure names, which can be accessed by all the child nodes. The names mentioned in the method1 symbol table (and all its child tables) are not available for the method2 table and its child tables.

The hierarchy of the data structures implemented for the symbol table is stored in the semantic analyzer. A name is searched in the symbol table using the following hierarchy

  • First, a symbol will be searched in the current scope, i.e., the current symbol table.
  • if a name is found, then the search is completed; else, it will be searched in the parent symbol table until,
  • Either the name is found, or the global symbol table has been searched for the name.
    Also read - Data Structure MCQ

Frequently Asked Questions

What is a symbol table and what is its use?

A symbol Table is an important data structure created and maintained by the compiler in order to keep track of the semantics of variables i.e. it stores information about the scope and binding information about names, information about instances of various entities such as variables and function names, classes, objects, etc.

What are the data structures used for the implementation of the symbol table?

Binary Search Tree, Hash Tables, and Linear search are the data structures used for the implementation of the symbol table.

What is in the symbol table associated with the name of an object?

A symbol table stores information about the scope and necessary details on names, and instances of several entities like names of variables and functions, classes, objects, etc.

Conclusion

In conclusion, you've learned about symbol tables, a critical component of many programming languages, compilers, and software applications. They allow for the efficient and accurate management of symbols, which are essential for many software development tasks, such as variable and function management.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Happy Learning! 

Live masterclass