Symbol Table in Compiler

Every compiler uses a symbol table to track all variables, functions, and identifiers in a program. It stores
information such as the name, type, scope, and memory location of each identifier. Built during the early
stages of compilation, the symbol table supports error checking, scope management, and code
optimization for runtime efficiency. It plays a crucial role in ensuring the correct usage of identifiers
according to language rules.

Role of Symbol Table in Compiler Phases

The symbol table acts as a bridge between the analysis and synthesis phases of the compiler. It collects
information during the analysis phases and utilizes it during the synthesis phases to generate efficient
code, ultimately enhancing compile-time performance.

It is used by various phases of the compiler as follows:-

 Lexical Analysis: Creates new table entries in the table, for example, entries about tokens.

 Syntax Analysis: Adds information regarding attribute type, scope, dimension, line of reference,
use, etc in the table.

 Semantic Analysis: Uses available information in the table to check for semantics i.e. to verify
that expressions and assignments are semantically correct(type checking) and update it
accordingly.

 Intermediate Code Generation: Refers to symbol table for knowing how much and what type of
run-time is allocated and table helps in adding temporary variable information.

 Code Optimization: Uses information present in the symbol table for machine-dependent
optimization.

 Target Code generation: Generates code by using the address information of the identifier
present in the table.

 Symbol Table entries – Each entry in the symbol table is associated with attributes that support
the compiler in different phases.

Example of Using Symbol Table

Imagine a program that includes a series of mathematical expressions, such as:

 A variable distance representing the distance traveled.

 A constant pi representing the value of Pi.

 A function calculateArea that computes the area of a circle.

distance variable Global 0x1000 Uninitialized Data type: float

pi constant Global 0x1004 3.14159 Data type: float, read-only

calculateArea function Global 0x1008 N/A Return type: float

radius parameter Local 0x2000 0x1000 Data type: float

In this example:

 The symbol table records that distance is a global variable of type float that has not been
initialized.

 Pi is a global value of type float with a constant value of 3.14159 and is marked as read-only.

 It registers the function calculateArea that returns a value of type float.

 The parameter radius is declared as a local variable – in the scope of the function – also of type
float.

 It is this organization that serves the compiler when it does various tasks, such as checking for
type errors, optimization of code, knowing the value of pi because it is a constant, declaring and
using variables according to its scope.

Items stored in Symbol table

 Variable names and constants

 Procedure and function names

 Literal constants and strings

 Compiler generated temporaries

 Labels in source languages

Information used by the compiler from Symbol table

 Data type and name

 Declaring procedures

 Offset in storage
  If structure or record then, a pointer to structure table.

 For parameters, whether parameter passing by value or by reference

 Number and type of arguments passed to function

 Base Address

Operations of Symbol table

The basic operations defined on a symbol table include

Operations on Symbol Table

Following operations can be performed on symbol table-

 Insertion of an item in the symbol table.

 Deletion of any item from the symbol table.

 Searching of desired item from symbol table.

Implementation of Symbol table

Following are commonly used data structures for implementing symbol table:

List

We use a single array or equivalently several arrays, to store names and their associated information.
New names are added to the list in the order in which they are encountered .

Linked List

 This implementation is using a linked list. A link field is added to each record.

 Searching of names is done in order pointed by the link of the link field.

 A pointer “First” is maintained to point to the first record of the symbol table.
Hash Table

 In hashing scheme, two tables are maintained – a hash table and symbol table and are the most
commonly used method to implement symbol tables. A hash table is an array with an index
range: 0 to table size – 1. These entries are pointers pointing to the names of the symbol table.

 The advantage is quick to search is possible and the disadvantage is that hashing is complicated
to implement.

Binary Search Tree

 Another approach to implementing a symbol table is to use a binary search tree i.e. we add two
link fields i.e. left and right child.

 All names are created as child of the root node that always follows the property of the binary
search tree.

Advantages of Symbol Table

 The efficiency of a program can be increased by using symbol tables, which give quick and simple
access to crucial data such as variable and function names, data kinds, and memory locations.

 better coding structure Symbol tables can be used to organize and simplify code, making it
simpler to comprehend, discover, and correct problems.

 Faster code execution: By offering quick access to information like memory addresses, symbol
tables can be utilized to optimize code execution by lowering the number of memory accesses
required during execution.

 Symbol tables can be used to increase the portability of code by offering a standardized method
of storing and retrieving data, which can make it simpler to migrate code between other systems
or programming languages.

 Improved code reuse: By offering a standardized method of storing and accessing information,
symbol tables can be utilized to increase the reuse of code across multiple projects.

 Symbol tables can be used to facilitate easy access to and examination of a program’s state
during execution, enhancing debugging by making it simpler to identify and correct mistakes.

Disadvantages of Symbol Table

 Increased memory consumption: Systems with low memory resources may suffer from symbol
tables’ high memory requirements.

 Increased processing time: The creation and processing of symbol tables can take a long time,
which can be problematic in systems with constrained processing power.

 Complexity: Developers who are not familiar with compiler design may find symbol tables
difficult to construct and maintain.
  Limited scalability: Symbol tables may not be appropriate for large-scale projects or applications
that require o the management of enormous amounts of data due to their limited scalability.

 Upkeep: Maintaining and updating symbol tables on a regular basis can be time- and resource-
consuming.

 Limited functionality: It’s possible that symbol tables don’t offer all the features a developer
needs, and therefore more tools or libraries will be needed to round out their capabilities.

Applications of Symbol Table

 Resolution of variable and function names: Symbol tables are used to identify the data types
and memory locations of variables and functions as well as to resolve their names.

 Resolution of scope issues: To resolve naming conflicts and ascertain the range of variables and
functions, symbol tables are utilized.

 Symbol tables, which offer quick access to information such as memory locations, are used to
optimize code execution.

 Code generation: By giving details like memory locations and data kinds, symbol tables are
utilized to create machine code from source code.

 Error checking and code debugging: By supplying details about the status of a program during
execution, symbol tables are used to check for faults and debug code.

 Code organization and documentation: By supplying details about a program’s structure, symbol
tables can be used to organize code and make it simpler to understand.