Module 4

Symbol table: Symbol table format, organization of symbol table-Linear, hashing ,tree.

Storage allocation: Activation record, Runtime stacks and heap allocation

Symbol Table

A Symbol Table is a fundamental data structure used in compilers, interpreters, and

assemblers to keep track of identifiers (such as variable names, function names, object
names, etc.) and associated information about them during program translation or
execution.

Role of Symbol Table in Compiler Phases

he 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.
Organization of Symbol Table: Linear

The Linear Symbol Table is the simplest way to organize a symbol table. It stores entries in a
linear list (array or linked list) and performs operations like insertion, lookup, and deletion
using linear search.

 Insertion of an item in the symbol table.

 Deletion of any item from the symbol table.

 Searching of desired item from symbol table.

Hashing
Hashing is a technique that uses a hash function to map an identifier (name) to an index in a
hash table.

omponents:

 Hash Table: An array-like structure to store symbols.

 Hash Function: Converts the identifier name into a numeric index.

🔹 Collision Handling:

 Chaining: Each table index stores a linked list of entries.

 Open Addressing: Find next available index (linear/quadratic probing).

Tree-Based Symbol Table

Binary Search Tree (BST) or a Balanced Tree (AVL/Red-Black) organizes entries in sorted
order using node structures.

🔹 Binary Search Tree (BST) Rule:

 Left child < root < right child (based on lexeme name).

🔹 Self-Balancing Trees:

 AVL Tree and Red-Black Tree keep the tree balanced.

 Ensures O(log n) time for search, insert, delete.

 Storage Allocation
compiler is a program that converts HLL(High-Level Language) to LLL(Low-Level
Language) like machine language. It is also responsible for organizing the memory
layout of a program by allocating space for global and local variables, constants, and
dynamic data structures.
 As the program begins execution, it is under the control of the operating system,
which sets up the environment by allocating space for the whole process.

 Compiler is responsible for deciding which variable gets which part of the memory.

 For example, the compiler needs to decide whether variables are best placed in the
stack (for local variables) or in the heap (for dynamically allocated memory) or data
segment (global and stack variables)

Activation Record
An Activation Record is a data structure that is activated/ created when a
procedure/function is invoked, and it includes the following data about the function.

 Temporaries: used in expression evaluation

 Local data: field for local data

 Saved machine status: holds info about machine status before procedure call

 Access link : to access non local data

 Control link : points to activation record of caller

 Actual parameters: field to hold actual parameters

 Returned value : field for holding value to be returned

The activation record is used to store the information required by a single procedure
call. Not all the fields shown in the figure may be needed for all languages. The
record structure can be modified as per the language/compiler requirements. For
Pascal and C, the activation record is generally stored on the runtime stack during the
period when the procedure is executing. Of the fields shown in the figure, access link
and control link are optional (e.g. FORTRAN doesn't need access links). Also, actual
parameters and return values are often stored in registers instead of the activation
record, for greater efficiency.

 The activation record for a procedure call is generated by the compiler. Generally,
all field sizes can be determined at compile time.

Here, Old SP stores the value of stack pointer of Activation Record of procedure
which has called this procedure which leads to the generation of this Activation
Record, i.e., It is a pointer to the activation record of the caller.

In Stack Allocation Scheme, when procedure A calls Procedure B, the activation

record for B will be pushed above the activation record for A. When Procedure B calls
procedure C, C’s activation record will be pushed above B’s activation record as in
figure −
 Run Time Stack
To study the run-time storage management system it is sufficient to focus on the statements:
action, call, return and halt, because they by themselves give us sufficient insight into the
behavior shown by functions in calling each other and returning. And the run-time allocation
and de-allocation of activations occur on the call of functions and when they return. There
are mainly two kinds of run-time allocation systems: Static allocation and Stack Allocation.
While static allocation is used by the FORTRAN class of languages, stack allocation is used by
the Ada class of languages.

Heap Allocation

Heap allocation is the most flexible allocation scheme. Allocation and deallocation of
memory can be done at any time and any place depending upon the user's requirement.
Heap allocation is used to allocate memory to the variables dynamically and when the
variables are no more used then claim it back.
Heap management is specialized in data structure theory. There is generally some time and
space overhead associated with heap manager. For efficiency reasons, it may be useful to
handle small activation records of a particular size as a special case

There are two methods used for Heap management are as follows −

Garbage Collection Method

When the all-access path to an object is destroyed, but data object continues to exist, such
types of objects are said to be garbage. Garbage collection is a technique that is used to
reuse that object space.

In garbage collection, firstly, we mark all the active objects, and all the remaining elements
whose garbage collection is 'on' are garbaged and returned to the free space list.

Reference Counter

By reference counter, an attempt is made to reclaim each element of heap storage

immediately after it can no longer be accessed.

Each memory cell on the heap has a reference counter associated with it that contains a
count of the number of values that points to it. The count has incremented each time a new
value point to the cell and decremented each time an amount ceases to point to it. When
the counter becomes zero, the cell is returned to the free list for further allocation.

Properties of Heap Allocation

There are various properties of heap allocation which are as follows −

 Space Efficiency− A memory manager should minimize the total heap space needed
by a program.

 Program Efficiency− A memory manager should make good use of the memory
subsystem to allow programs to run faster. As the time taken to execute an
instruction can vary widely depending on where objects are placed in memory.

 Low Overhead− Memory allocation and deallocation are frequent operations in

many programs. These operations must be as efficient as possible. That is, it is
required to minimize the overhead. The fraction of execution time spent performing
allocation and deallocation.