Data structure in CD


Symbol Table:

Symbol table is an important data structure created and maintained by compilers in order to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc. 
Symbol table is used by both the analysis and the synthesis parts of a compiler.
A symbol table may serve the following purposes:-
  • To store the names of all entities in a structured form at one place.
  • To verify if a variable has been declared.
  • To implement type checking, by verifying assignments and expressions in the source code are semantically correct.
  • To determine the scope of a name (scope resolution).


If a compiler is to handle a small amount of data, then the symbol table can be implemented as an unordered list, which is easy to code, but it is only suitable for small tables only. 

A symbol table can be implemented in one of the following ways:
  1. Linear (sorted or unsorted) list
  2. Binary Search Tree
  3. Hash table
Among all, symbol tables are mostly implemented as hash tables, where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.


A symbol table, either linear or hash, should provide the following operations.
  1. Allocate: to allocate a new empty symbol table.
  2. Free: to remove all entries and free the storage of a symbol table.
  3. Insert: to insert a name in a symbol table and return a pointer to its entry.
  4. lookup: to search for a name and return a pointer to its entry.
  5. set_ attribute: to associate an attribute with a given entry.
  6. get _attribute: to get an attribute associated with a given entry.

Scope Management:

A compiler maintains two types of symbol tables:-
  1. Global symbol table: which can be accessed by all the procedures .
  2. Scope symbol tables: that are created for each scope in the program.
To determine the scope of a name, symbol tables are arranged in hierarchical structure as shown in the example below:

This symbol table data structure hierarchy is stored in the semantic analyzer and whenever a name needs to be searched in a symbol table, it is searched using the following algorithm:
  1. First a symbol will be searched in the current scope, i.e. current symbol table.
  2. If a name is found, then search is completed, else it will be searched in the parent symbol table until.
  3. Either the name is found or global symbol table has been searched for the name.

More topics to read in Compiler Design

Compiler Design
Python Programming ↓ 👆
Java Programming ↓ 👆
JAVA covered following topics in these notes.
JAVA Programs
Principles of Programming Languages ↓ 👆
Principles of Programming Languages covered following topics in these notes.

Previous years solved papers:
A list of Video lectures References:
  1. Sebesta,”Concept of programming Language”, Pearson Edu 
  2. Louden, “Programming Languages: Principles & Practices” , Cengage Learning 
  3. Tucker, “Programming Languages: Principles and paradigms “, Tata McGraw –Hill. 
  4. E Horowitz, "Programming Languages", 2nd Edition, Addison Wesley

    Computer Organization and Architecture ↓ 👆

    Computer Organization and Architecture covered following topics in these notes.

    1. Structure of desktop computers
    2. Logic gates
    3. Register organization
    4. Bus structure
    5. Addressing modes
    6. Register transfer language
    7. Direct mapping numericals
    8. Register in Assembly Language Programming
    9. Arrays in Assembly Language Programming


    1. William stalling ,“Computer Architecture and Organization” PHI
    2. Morris Mano , “Computer System Organization ”PHI

    Computer Network ↓ 👆
    Computer Network covered following topics in these notes.
    1. Data Link Layer
    2. Framing
    3. Byte count framing method
    4. Flag bytes with byte stuffing framing method
    5. Flag bits with bit stuffing framing method
    6. Physical layer coding violations framing method
    7. Error control in data link layer
    8. Stop and Wait scheme
    9. Sliding Window Protocol
    10. One bit sliding window protocol
    11. A protocol Using Go-Back-N
    12. Selective repeat protocol
    13. Application layer
    1. Andrew S. Tanenbaum, David J. Wetherall, “Computer Networks” Pearson Education.
    2. Douglas E Comer, “Internetworking with TCP/IP Principles, Protocols, And Architecture",Pearson Education
    3. KavehPahlavan, Prashant Krishnamurthy, “Networking Fundamentals”, Wiley Publication.
    4. Ying-Dar Lin, Ren-Hung Hwang, Fred Baker, “Computer Networks: An Open Source Approach”, McGraw Hill.