Symbol Table Organizing Using Hashing

Hashing is an important technique used to search the records of symbol table. This method is superior to list organization
In hashing scheme, two tables are maintained – hash table and symbol table
The hash table consists of K entries from 0, 1, 2, … to K-1. These entries are basically pointers to symbol table pointing to the names of symbol table.
To determine whether the ‘Name’ is in symbol table, we use a hash function ‘h’ such that h (name) will result any integer between 0 to K-1. We can search any name by
Position = h (name)
Using the position we can obtain the exact locations of name in symbol table.
The hash table and symbol table are shown below

The hash function should not result in uniform distribution of names in symbol able
The hash function should be such that there are minimum number of collisions
Collision is a situation where hash function results in same location for storing the names
Various collision resolution techniques are,

Open addressing

Chaining

Rehashing

Advantage

Tree Structure Representation of Scope Information:

When the scope information is presented in hierarchical manner then it forms a tree structure representation which is an efficient approach for symbol table organization
We add two links left and right in each record in the search trees
Whenever a name is to be added first, the name is searched in the tree
If it does not exist then a record for new name is created and added at the proper position
It is alphabetical accessibility
The typical data structure is shown on the screen

Left Child

Name of Symbol

Information

Right Child

Construction of Binary Tree for Expressions:
The nodes of binary tree for expressions can be constructed by using the following functions. Each function returns a pointer to a newly created node
mlnode(L, op, R) creates an operator node with label op and two fields contain pointers to Left and Right with labels L and R
mkleaf(id, entry) creates a leaf node with label id and field contains a pointer to the symbol table entry for ‘id’
mkleaf(num, value) creates a leaf node with label num and field contains a value of that node

Example: Construction of a binary tree for the expression a + b * 10. Consider the grammar

Steps in the construction of the syntax tree for a + b * 10
Create a leaf node with label b that is p1 = mkleaf(id, b)
Create a leaf node with label 10 that is p2 = mkleaf(num, 10);
Create parent node label * and two children nodes as p1, p2 that is p3 = mknode(‘*’, p1, p2);
Create a leaf node with label a that is p4 = mkleaf(id, a);
Create a parents node with label + and two children nodes as p4, p3 that is p5 = mkknode(‘+’, p4, p3);
Where p1, p2, p3, p4, p5 are the pointer to the newly created nodes.
Syntax tree is