Symbol Table: Operations and Data Structures

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;  
}  

You can also try this code with Online C Compiler

Run Code

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

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:

• First and Follow in Compiler Design
• Operator Precedence Parsing
• Shift Reduce Parsing
• Top Down Parsing
• Bottom Up Parsing
• Phases of a Compiler
• Back Patching In Compiler Design
• Difference Between Compiler and Assembler
• Input Buffering in Compiler Design
   

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 Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

Happy Learning!