Description

WHO CREATES SYMBOL TABLE?
I Identifiers and attributes are entered by the analysis phases when processing a definition (declaration) of an identifier.
I In simple languages with only global variables and implicit declarations:
I The scanner can enter an identifier into a symbol table if it is not already there.
I In block-structured languages with scopes and explicit declarations:
I The parser and/or semantic analyzer enter identifiers and corresponding attributes.
USE OF SYMBOL TABLE
I Symbol table information is used by the analysis and synthesis phases.
I To verify that used identifiers have been defined (declared). I To verify that expressions and assignments are semantically correct – type checking.
I To generate intermediate or target code.
Assumptions
For this work, assume we:
I use static scoping.
I require that all names be declared before they are used. I do not allow multiple declarations of a name in the same scope.
I do allow the same name to be declared in multiple nested scopes.
I but only once per scope.
What Operations do we need ?
Using the previous given assumptions, we will need:
I look up a name in the current scope only.
I to check if it is multiply declared.
I Look up a name in the current and enclosing scopes
I to check for a use of an undeclared name, and
I to link a use with the corresponding Symbol-table entry.
I insert a new name into the symbol table with its attributes.
I Do what must be done when a new scope is entered.
I Do What must be done when when a scope is exited.
SYMBOL TABLE DATA STRUCTURES I Issues to consider : Operations required
I Insert – Add symbol to symbol table
I Look Up – Find symbol in the symbol table (and get its attributes)
I Insertion is done only once.
I Look Up is done many times.
I Need Fast Look Up.
I The data structure should be designed to allow the compiler to find the record for each name quickly and to store or retrieve data from that record quickly.
LINKED LIST
I A linear list of records is the easiest way to implement symbol table.
I The new names are added to the symbol table in the order they arrive.
I Whenever a new name is to be added it is first searched linearly or sequentially to check if the name is already present in the table or not and if not , it is added accordingly.
I Time complexity – O(n).
I Advantage – less space, additions are simple.
I Disadvantages – higher access time.
Example:

Hash Table
I Table of k pointers numbered from zero to k − 1 that points to the symbol table and a record within the symbol table. I To enter a name in to the symbol table we found out the hash value of the name by applying a suitable hash function.
I The hash function maps the name into an integer between zero and k − 1 and using this value as an index in the hash table.
HKey = ASCIIid mod 11