Symbol Table | Compiler Design - Computer Science Engineering (CSE) PDF Download

Symbol table:
A symbol table is a major data structure used in a compiler:  

• Associates attributes with identifiers used in a program.  
•  For instance, a type attribute is usually associated with each identifier.   

  A symbol table is a necessary component.  

Definition (declaration) of identifiers appears once in a program 

• Use of identifiers may appear in many places of the program text 
• Identifiers and attributes are entered by the analysis phases 
• When processing a definition (declaration) of an identifier   
• In simple languages with only global variables and implici t declarations:   

The scanner can enter an identifier into a symbol table if it is not already there 
In block-
structured languages with scopes and explicit declarations:  

The parser and/or semantic analyzer enter identifiers and corresponding attributes  

• · Symbol table information is used by the analysis and synthesis phases  
• ·To verify that used identifiers have been defined (declared)   
• · To verify that expressions and assignments are semantically correct  type checking   
• · To generate intermediate or target code  
  
  Symbol Table Interface: 
  
  The basic operations defined on a symbol table include: allocate – to allocate a new empty symbol table   
   
• free – to remove all entries and free the storage of a symbol table  
• insert – to insert a name in a symbol table and return a pointer to its entry  
•  lookup – to search for a name and return a pointer to its entry  
• set_attribute – to associate an attribute with a given entry  
• get_attribute – to get an attribute associated with a given entry  
•  Other operations can be added depending on requirement    
  
  For example, a delete operation removes a name previously inserted Some identifiers become invisible (out of scope) after exiting a block  
   
• This interface provides an abstract view of a symbol table.  
• Supports the simultaneous existence of multiple tables  
• Implementation can vary without modifying the interface  

Basic Implementation Techniques:

First consideration is how to insert and lookup names
Variety of implementation techniques

Unordered List 
Simplest to implement
Implemented as an array or a linked list
Linked list can grow dynamically – alleviates problem of a fixed size array
Insertion is fast O(1), but lookup is slow for large tables – O(n) on average

Ordered List
If an array is sorted, it can be searched using binary search – O(log2 n)
Insertion into a sorted array is expensive – O(n) on average
Useful when set of names is known in advance – table of reserved words

Binary Search Tree
Can grow dynamically Insertion and lookup are O(log2 n) on average