Symbol Table Computer Science Engineering (CSE) Notes | EduRev

Compiler Design

Computer Science Engineering (CSE) : Symbol Table Computer Science Engineering (CSE) Notes | EduRev

The document Symbol Table Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

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

 

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Extra Questions

,

Sample Paper

,

practice quizzes

,

past year papers

,

Symbol Table Computer Science Engineering (CSE) Notes | EduRev

,

pdf

,

mock tests for examination

,

ppt

,

Important questions

,

Previous Year Questions with Solutions

,

Viva Questions

,

Free

,

video lectures

,

Symbol Table Computer Science Engineering (CSE) Notes | EduRev

,

MCQs

,

Symbol Table Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

Exam

,

study material

,

Objective type Questions

,

shortcuts and tricks

,

Summary

;