Symbol Table

Symbol table is an important data structure used in a compiler.

Symbol table is used to store the information about the occurrence of various entities such as objects, classes, variable name, interface, function name etc. it is used by both the analysis and synthesis phases.

The symbol table used for following purposes:

• It is used to store the name of all entities in a structured form at one place.
• It is used to verify if a variable has been declared.
• It is used to determine the scope of a name.
• It is used to implement type checking by verifying assignments and expressions in the source code are semantically correct.

A symbol table can either be linear or a hash table. Using the following format, it maintains the entry for each name.

1. <symbol name, type, attribute>  

For example, suppose a variable store the information about the following variable declaration:

1. static int salary   

then, it stores an entry in the following format:

1. <salary, int, static>  

The clause attribute contains the entries related to the name.

Implementation

The symbol table can be implemented in the unordered list if the compiler is used to handle the small amount of data.

A symbol table can be implemented in one of the following techniques:

• Linear (sorted or unsorted) list
• Hash table
• Binary search tree

Symbol table are mostly implemented as hash table.

Operations

The symbol table provides the following operations:

Insert ()

• Insert () operation is more frequently used in the analysis phase when the tokens are identified and names are stored in the table.
• The insert() operation is used to insert the information in the symbol table like the unique name occurring in the source code.
• In the source code, the attribute for a symbol is the information associated with that symbol. The information contains the state, value, type and scope about the symbol.
• The insert () function takes the symbol and its value in the form of argument.

For example:

1. int x;  

Should be processed by the compiler as:

1. insert (x, int)  

lookup()

In the symbol table, lookup() operation is used to search a name. It is used to determine:

• The existence of symbol in the table.
• The declaration of the symbol before it is used.
• Check whether the name is used in the scope.
• Initialization of the symbol.
• Checking whether the name is declared multiple times.

The basic format of lookup() function is as follows:

1. lookup (symbol)  

This format is varies according to the programming language.