Symbol Table Management

Learn how compilers track every identifier's name, type, scope, and memory location in a symbol table — the central data structure shared by all compiler phases.

What is a Symbol Table?

A symbol table is a data structure maintained by the compiler that records information about every identifier encountered in the source program — variables, functions, classes, constants, and parameters.

It is not a single phase — it is a shared resource used by all compiler phases:

Example

Source Code

│

▼

Lexical Analysis ── inserts identifiers ──────────────────┐

│ │

▼ ▼

Syntax Analysis ── verifies identifier exists ──────► Symbol Table

│ │

▼ │

Semantic Analysis ── type-checks, assigns types ───────────┤

│ │

▼ │

Code Generation ── looks up memory locations ────────────┘

Without a symbol table, a compiler would have no way to:

Check that a variable is declared before use.
Verify that function calls have the correct number and types of arguments.
Assign memory addresses to variables.
Handle multiple functions that all have a local variable named i.

Information Stored in a Symbol Table

Each entry in the symbol table represents one identifier and stores:

Field	Description	Example
Name	The identifier's lexeme	`total`, `add`, `MAX_SIZE`
Kind	Variable, function, constant, parameter, type	`var`, `func`, `const`
Type	Data type	`int`, `float`, `char*`, `bool`
Scope level	Nesting depth where declared	0 (global), 1 (function), 2 (inner block)
Memory location	Offset in stack frame or global address	`offset: 8`, `addr: 0x1004`
Size	Bytes needed	`int` = 4, `double` = 8
Line number	Where declared (for error messages)	line 12
Parameter list	For functions: types of parameters	`(int, float) → double`

Example Symbol Table Entries

Given the source:

int MAX = 100;
float price;

double compute(int qty, float rate) {
    double total;
    total = qty * rate;
    return total;
}

Symbol table entries:

Example

Name Kind Type Scope Offset Line

────────────────────────────────────────────────

MAX const int global 0x1000 1

price var float global 0x1004 2

compute func double global — 4

qty param int level1 8 4

rate param float level1 12 4

total var double level1 16 5

Symbol Table Operations

A symbol table must support three core operations efficiently:

1. Insert (enter)

Add a new identifier to the table when its declaration is encountered.

Example

insert(name, kind, type, scope, ...)

When: During lexical analysis (for simple cases) or syntax/semantic analysis (for full declaration processing).

Error condition: If the identifier already exists in the same scope, it's a redeclaration error.

2. Lookup (search)

Find an identifier's entry — used when the identifier is referenced (used in an expression, called as a function, etc.).

Example

lookup(name) → entry | NOT_FOUND

Scoping rule: When multiple scopes are active (nested functions/blocks), the lookup must find the innermost declaration.

Error condition: If the identifier is not found in any enclosing scope, it's an undeclared-identifier error.

3. Delete (scope exit)

When a scope closes (e.g., } in C), all identifiers declared in that scope are removed.

Example

delete_scope(current_scope_level)

Some implementations don't delete but instead mark entries as "out of scope" — useful for error recovery and IDE features like "go to declaration".

Scope Management — Nested Scopes

Real programs have nested scopes — each function and each block ({…}) creates a new scope. The symbol table must handle identifier shadowing (an inner declaration hiding an outer one).

Example Program with Nested Scopes

int x = 10;          // Scope 0 (global)

int foo(int x) {     // Scope 1 — parameter x shadows global x
    int y = x + 1;   // Scope 1 — y declared here
    {
        int x = 42;  // Scope 2 — local x shadows parameter x
        y = y + x;   // uses Scope 2 x (= 42) and Scope 1 y
    }                // Scope 2 ends — Scope 2 x is gone
    return y;        // uses Scope 1 y
}                    // Scope 1 ends

How the Symbol Table Tracks Scopes

Method 1 — Stack of hash tables:

Example

Scope stack (top = innermost):

[ Scope 2: {x → 42} ]

[ Scope 1: {x → param, y → var} ]

[ Scope 0: {x → 10, foo → func} ]

Lookup("x") → start at top, find Scope 2 x = 42 ✓

Method 2 — Chained hash table with scope level: Each entry has a scope level. Lookup scans from highest scope level downward.

Method 3 — Single hash table with shadowing list: Each bucket is a stack — insert always pushes onto the bucket's stack, lookup reads the top of the stack.

Scope Entry and Exit

Example

Enter scope:

push a new hash table onto the scope stack

increment scope_level

Exit scope:

pop the top hash table (removing all declarations at this level)

decrement scope_level

Trace through the example:

Example

Scope 0 entered:

insert(x, var, int, 0)

insert(foo, func, int(int), 0)

Scope 1 entered (foo called):

insert(x, param, int, 1) ← shadows global x

insert(y, var, int, 1)

Scope 2 entered (inner block):

insert(x, var, int, 2) ← shadows parameter x

lookup(x) → finds Scope 2 x = 42

lookup(y) → Scope 2 has no y → try Scope 1 → found y

Scope 2 exited:

Scope 2 x is removed

lookup(x) → now finds Scope 1 x (parameter)

Scope 1 exited:

Scope 1 x and y are removed

lookup(x) → now finds Scope 0 x = 10

Data Structures for Symbol Tables

The efficiency of lookup determines how fast the compiler runs. Three common data structures:

1. Hash Table (most common)

Example

Hash function h(name) → bucket index

Collision resolution: chaining (linked list per bucket)

Insert: O(1) average

Lookup: O(1) average

Pros: Fast average case, simple to implement. Cons: Worst case O(n) with bad hash function; doesn't naturally support ordered traversal.

Most real-world compilers (GCC, Clang, Go compiler) use hash tables for symbol lookup.

2. Balanced Binary Search Tree (BST)

Example

Keys = identifier names (lexicographically ordered)

AVL tree or Red-Black tree

Insert: O(log n)

Lookup: O(log n)

Pros: Predictable O(log n) worst case; supports ordered operations (list all symbols in alphabetical order). Cons: Higher constant factor than hash tables.

3. Linked List (only for small scopes)

Example

Each scope is a simple linked list of entries.

Lookup = linear scan.

Insert: O(1) (prepend)

Lookup: O(n)

Pros: Dead simple to implement, low overhead for tiny scopes. Cons: Unacceptably slow for large scopes (hundreds of declarations).

Summary Comparison

Structure	Insert	Lookup	Space	Used When
Hash table	O(1) avg	O(1) avg	O(n)	Most production compilers
BST (AVL/RB)	O(log n)	O(log n)	O(n)	When ordering matters
Linked list	O(1)	O(n)	O(n)	Tiny scopes, pedagogical use

Summary — Symbol Table at a Glance

Aspect	Detail
What	A data structure mapping identifiers → attributes (type, scope, location, …)
Who uses it	All compiler phases: lexer inserts names, semantic analyser type-checks, code generator looks up addresses
Core operations	insert, lookup, delete-scope
Scope model	Stack of tables (one per scope level); innermost scope wins on lookup
Best implementation	Hash table per scope level, stacked for nested scopes
Errors detected	Undeclared identifiers, redeclarations, type mismatches, wrong argument counts

Where the Symbol Table Lives in the Pipeline

Example

Phase 1 — Lexical Analysis:

→ insert each identifier name when first seen

Phase 2 — Syntax Analysis:

→ verify identifiers have been declared (lookup)

Phase 3 — Semantic Analysis:

→ fill in type, size, scope, parameter lists

→ check type correctness of expressions

Phase 4 — Code Generation:

→ lookup memory offsets and addresses

→ allocate stack frames based on symbol sizes

After compilation:

→ optionally serialised into debug symbols (DWARF, PDB)

so debuggers can show variable names at runtime

The symbol table is the compiler's "knowledge base" about the program — built incrementally, consulted constantly, and eventually discarded (or saved as debug info).

What is a Symbol Table?

It is not a single phase — it is a shared resource used by all compiler phases:

Example

Source Code

│

▼

Lexical Analysis ── inserts identifiers ──────────────────┐

│ │

▼ ▼

Syntax Analysis ── verifies identifier exists ──────► Symbol Table

│ │

▼ │

Semantic Analysis ── type-checks, assigns types ───────────┤

│ │

▼ │

Code Generation ── looks up memory locations ────────────┘

Without a symbol table, a compiler would have no way to:

Check that a variable is declared before use.
Verify that function calls have the correct number and types of arguments.
Assign memory addresses to variables.
Handle multiple functions that all have a local variable named i.

Information Stored in a Symbol Table

Each entry in the symbol table represents one identifier and stores:

Field	Description	Example
Name	The identifier's lexeme	`total`, `add`, `MAX_SIZE`
Kind	Variable, function, constant, parameter, type	`var`, `func`, `const`
Type	Data type	`int`, `float`, `char*`, `bool`
Scope level	Nesting depth where declared	0 (global), 1 (function), 2 (inner block)
Memory location	Offset in stack frame or global address	`offset: 8`, `addr: 0x1004`
Size	Bytes needed	`int` = 4, `double` = 8
Line number	Where declared (for error messages)	line 12
Parameter list	For functions: types of parameters	`(int, float) → double`

Example Symbol Table Entries

Given the source:

int MAX = 100;
float price;

double compute(int qty, float rate) {
    double total;
    total = qty * rate;
    return total;
}

Symbol table entries:

Example

Name Kind Type Scope Offset Line

────────────────────────────────────────────────

MAX const int global 0x1000 1

price var float global 0x1004 2

compute func double global — 4

qty param int level1 8 4

rate param float level1 12 4

total var double level1 16 5

Symbol Table Operations

A symbol table must support three core operations efficiently:

1. Insert (enter)

Add a new identifier to the table when its declaration is encountered.

Example

insert(name, kind, type, scope, ...)

When: During lexical analysis (for simple cases) or syntax/semantic analysis (for full declaration processing).

Error condition: If the identifier already exists in the same scope, it's a redeclaration error.

2. Lookup (search)

Find an identifier's entry — used when the identifier is referenced (used in an expression, called as a function, etc.).

Example

lookup(name) → entry | NOT_FOUND

Scoping rule: When multiple scopes are active (nested functions/blocks), the lookup must find the innermost declaration.

Error condition: If the identifier is not found in any enclosing scope, it's an undeclared-identifier error.

3. Delete (scope exit)

When a scope closes (e.g., } in C), all identifiers declared in that scope are removed.

Example

delete_scope(current_scope_level)

Some implementations don't delete but instead mark entries as "out of scope" — useful for error recovery and IDE features like "go to declaration".

Scope Management — Nested Scopes

Real programs have nested scopes — each function and each block ({…}) creates a new scope. The symbol table must handle identifier shadowing (an inner declaration hiding an outer one).

Example Program with Nested Scopes

int x = 10;          // Scope 0 (global)

int foo(int x) {     // Scope 1 — parameter x shadows global x
    int y = x + 1;   // Scope 1 — y declared here
    {
        int x = 42;  // Scope 2 — local x shadows parameter x
        y = y + x;   // uses Scope 2 x (= 42) and Scope 1 y
    }                // Scope 2 ends — Scope 2 x is gone
    return y;        // uses Scope 1 y
}                    // Scope 1 ends

How the Symbol Table Tracks Scopes

Method 1 — Stack of hash tables:

Example

Scope stack (top = innermost):

[ Scope 2: {x → 42} ]

[ Scope 1: {x → param, y → var} ]

[ Scope 0: {x → 10, foo → func} ]

Lookup("x") → start at top, find Scope 2 x = 42 ✓

Method 2 — Chained hash table with scope level: Each entry has a scope level. Lookup scans from highest scope level downward.

Method 3 — Single hash table with shadowing list: Each bucket is a stack — insert always pushes onto the bucket's stack, lookup reads the top of the stack.

Scope Entry and Exit

Example

Enter scope:

push a new hash table onto the scope stack

increment scope_level

Exit scope:

pop the top hash table (removing all declarations at this level)

decrement scope_level

Trace through the example:

Example

Scope 0 entered:

insert(x, var, int, 0)

insert(foo, func, int(int), 0)

Scope 1 entered (foo called):

insert(x, param, int, 1) ← shadows global x

insert(y, var, int, 1)

Scope 2 entered (inner block):

insert(x, var, int, 2) ← shadows parameter x

lookup(x) → finds Scope 2 x = 42

lookup(y) → Scope 2 has no y → try Scope 1 → found y

Scope 2 exited:

Scope 2 x is removed

lookup(x) → now finds Scope 1 x (parameter)

Scope 1 exited:

Scope 1 x and y are removed

lookup(x) → now finds Scope 0 x = 10

Data Structures for Symbol Tables

The efficiency of lookup determines how fast the compiler runs. Three common data structures:

1. Hash Table (most common)

Example

Hash function h(name) → bucket index

Collision resolution: chaining (linked list per bucket)

Insert: O(1) average

Lookup: O(1) average

Pros: Fast average case, simple to implement. Cons: Worst case O(n) with bad hash function; doesn't naturally support ordered traversal.

Most real-world compilers (GCC, Clang, Go compiler) use hash tables for symbol lookup.

2. Balanced Binary Search Tree (BST)

Example

Keys = identifier names (lexicographically ordered)

AVL tree or Red-Black tree

Insert: O(log n)

Lookup: O(log n)

Pros: Predictable O(log n) worst case; supports ordered operations (list all symbols in alphabetical order). Cons: Higher constant factor than hash tables.

3. Linked List (only for small scopes)

Example

Each scope is a simple linked list of entries.

Lookup = linear scan.

Insert: O(1) (prepend)

Lookup: O(n)

Pros: Dead simple to implement, low overhead for tiny scopes. Cons: Unacceptably slow for large scopes (hundreds of declarations).

Summary Comparison

Structure	Insert	Lookup	Space	Used When
Hash table	O(1) avg	O(1) avg	O(n)	Most production compilers
BST (AVL/RB)	O(log n)	O(log n)	O(n)	When ordering matters
Linked list	O(1)	O(n)	O(n)	Tiny scopes, pedagogical use

Summary — Symbol Table at a Glance

Aspect	Detail
What	A data structure mapping identifiers → attributes (type, scope, location, …)
Who uses it	All compiler phases: lexer inserts names, semantic analyser type-checks, code generator looks up addresses
Core operations	insert, lookup, delete-scope
Scope model	Stack of tables (one per scope level); innermost scope wins on lookup
Best implementation	Hash table per scope level, stacked for nested scopes
Errors detected	Undeclared identifiers, redeclarations, type mismatches, wrong argument counts

Where the Symbol Table Lives in the Pipeline

Example

Phase 1 — Lexical Analysis:

→ insert each identifier name when first seen

Phase 2 — Syntax Analysis:

→ verify identifiers have been declared (lookup)

Phase 3 — Semantic Analysis:

→ fill in type, size, scope, parameter lists

→ check type correctness of expressions

Phase 4 — Code Generation:

→ lookup memory offsets and addresses

→ allocate stack frames based on symbol sizes

After compilation:

→ optionally serialised into debug symbols (DWARF, PDB)

so debuggers can show variable names at runtime

The symbol table is the compiler's "knowledge base" about the program — built incrementally, consulted constantly, and eventually discarded (or saved as debug info).