Symbol Table Organizing Using Hashing

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

• Quick search is possible
• Limitations
• Implementing hashing is complicated
• Extra space is required
• Obtaining scope of variable is very difficult. 

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

Example:

int index, total, velocity, current, answers;

The tree structure representation of above identifiers is:

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.