Symbol Tables

Symbol Tables

A symbol table is a central data structure used by a compiler to store information about identifiers (variables, functions, arrays, labels, constants).

Why Symbol Tables Are Needed

• Track declarations and uses
• Support type checking
• Enable storage allocation
• Facilitate scope management

Typical Information Stored

Field	Description
Name	Identifier lexeme
Type	int, float, array, function
Scope	Global / local / block
Size	Memory requirement
Address	Storage location
Parameters	For procedures/functions

Data Structures for Symbol Tables

Choosing the right data structure affects lookup speed and compiler performance.

Common Data Structures

Data Structure	Advantages	Limitations
Linear List	Simple	Slow lookup (O(n))
Hash Table	Fast average lookup (O(1))	Collision handling
Binary Search Tree	Ordered traversal	Can degrade to O(n)
Trie	Efficient prefix search	Higher memory usage

Most compilers use hash tables due to efficiency.

Representing Scope Information

Scope defines the region of the program where an identifier is valid.

Types of Scope

• Global scope: visible throughout the program
• Local scope: visible within a function/block
• Nested (block) scope: inner blocks shadow outer names

Scope Handling Techniques

Technique	Description
Separate Tables	One table per scope
Scope Stack	Push on entry, pop on exit
Chained Hash Tables	Parent pointer to enclosing scope

Run-Time Administration

Run-time administration manages memory allocation, activation records, and control flow during program execution.

Key Responsibilities

• Allocate/deallocate storage
• Manage procedure calls/returns
• Support recursion

Implementation of Simple Stack Allocation Scheme

A stack allocation scheme uses a run-time stack to manage memory for procedure calls.

Activation Record (Stack Frame)

Field	Purpose
Parameters	Passed values
Return Address	Control transfer
Local Variables	Local storage
Temporaries	Intermediate values
Control Link	Access caller frame

Characteristics

• LIFO discipline
• Efficient for block-structured and recursive programs
• Used by most modern languages (C, Java)

Storage Allocation in Block-Structured Languages

Block-structured languages (C, Pascal) allow nested blocks with local declarations.

Allocation Strategies

Strategy	Description
Static Allocation	Fixed at compile time
Stack Allocation	Dynamic, supports recursion
Heap Allocation	Dynamic objects with unknown lifetime

Scope-Based Allocation

• Enter block → allocate locals
• Exit block → deallocate locals automatically

Error Detection & Recovery

Compilers must detect, report, and recover from errors to continue processing.

Lexical Phase Errors

Detected by the lexical analyzer while scanning characters.

Examples

• Invalid character: @
• Unterminated string
• Illegal numeric format

Recovery Techniques

Technique	Description
Panic Mode	Skip invalid characters
Error Token	Replace with dummy token
Ignore Character	Continue scanning

Syntactic Phase Errors

Detected by the parser when token sequences violate grammar.

Examples

• Missing semicolon
• Unmatched parentheses
• Incorrect keyword order

Recovery Methods

Method	Description
Panic Mode	Skip tokens until synchronizing symbol
Phrase-Level	Insert/delete tokens
Error Productions	Grammar rules for errors

Semantic Errors

Detected during semantic analysis.

Examples

• Undeclared variable
• Type mismatch (int + float)
• Wrong number of arguments
• Array index out of bounds (partial)

Detection Mechanism

• Symbol table lookup
• Type checking rules
• Attribute evaluation

Error Handling Comparison

Phase	Error Type	Examples
Lexical	Invalid token	Illegal character
Syntactic	Grammar violation	Missing ;
Semantic	Meaning error	Type mismatch

Exam-Oriented Summary Table

Topic	Key Points
Symbol Table	Stores identifier info
Data Structures	Hash table preferred
Scope	Global, local, nested
Stack Allocation	Activation records
Block Structure	Scope-based storage
Lexical Errors	Invalid tokens
Syntax Errors	Grammar violations
Semantic Errors	Type/scope issues