Symbol table in compiler AND Data structure used to implement Symbol Table.

 

Symbol table is an important data structure created and maintained by compiler in order to store information about the occurrence of various entities such as variable name, function name,object classes,interface etc.

Purpose to use symbol table

• To store the name of all entities in a structured form at one place.
• To verify if a variable has been declared.
• To implement type checking.
• To determine the scope of a name.
• For analysis and synthesis symbol table is used by compiler.
• Help in code optimization.
• Aid in error handling. 

Data structure used for the implementation of symbol table are

If a compiler is to handle small amount of data then the symbol table can be implemented as an unordered list.which is easy to code but it is only suitable for small table only. A symbol table can be implemented in one of the following ways.

• List.
• Binary search Trees
• Hash table.

List

It is simple and easy to implement data structure.Use single array to store the name and its associated information.New name are added to end of list on first come first serve basis.Method of access is sequential.

Binary search trees

Symbol table can also be stored in form of binary search tree. Each node can have atmost two childern Left child and right child.Key value stored in parent.

Height of binary search tree is of order of logn.

Hash table

Symbol table are mostly implemented as hash table where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.

In hashing scheme two tables are maintained

• Hash table.
• Symbol table.

In hash table consist of N entries from 0 to N-1. These entries pointer to symbol table pointing to names of symbol table.

To determine name is in symbol table use hash function 'h'. Position=h(Name).

Using these position obtain exact location.

If hash function result in same location for storing names that is collision.

Various collision resolution techniques are

• Open addressing.
• chaining.
• rehashing.

Advantage of using hashing

• Quick search.

Disadvantage of using hashing

• Hashing is complicated to implement.
• Extra  space is required.

Hash function that are used in hashing are

• Mid square method.
• Division method.
• Folding method.
• Shift Folding method.

Example find location in symbol table if key is K=3230 using Mid square method.

Solution

K=3230

K²=(3230)*(3230)=10432900

Hash function eliminate few digit from both sides.

Hence H(K)=32.

Method of representing name in symbol table

• Fixed length representation.
• Variable length representation.
• Two array Representation.