Symbol Tables & Storage Management: Structures, Operations & Runtime Allocation

Core Concepts

1. What is a Symbol Table?

A symbol table is a data structure that stores information about program identifiers (variables, functions, types, etc.) during compilation. It acts as a dictionary mapping names to their attributes (e.g., type, scope, memory address).

Why is a Symbol Table Necessary?

• Compiler Phase Interaction: Used in lexical analysis (storing tokens), syntax analysis (resolving declarations), semantic analysis (type checking), and code generation (memory allocation).
• Error Detection: Detects undeclared variables, duplicate declarations, or type mismatches.
• Optimization: Helps in dead code elimination and constant propagation.

Typical Entries in a Symbol Table

2. Data Structures for Symbol Tables

Three common implementations, each with trade-offs:

A. Linear List (Array/Linked List)

• Structure: Simple list where entries are stored sequentially.
• Operations:
  • Insertion: $O(n)$ (must search entire list).
  • Lookup: $O(n)$ (linear search).
• Pros: Easy to implement.
• Cons: Inefficient for large tables.

B. Hash Table

• Structure: Uses a hash function to map keys (symbol names) to indices in an array.
• Operations:
  • Insertion: $O(1)$ average case (with good hash function).
  • Lookup: $O(1)$ average case.
• Pros: Fast access, scalable.
• Cons: Collisions require chaining/open addressing; memory overhead.

C. Binary Search Tree (BST)

• Structure: Nodes store symbols, ordered by name (lexicographical).
• Operations:
  • Insertion: $O(\log n)$ average case (balanced tree).
  • Lookup: $O(\log n)$ average case.
• Pros: No collisions, ordered traversal useful for debugging.
• Cons: Slower than hash tables for large datasets; $O(n)$ if unbalanced.

Comparison Table

*Assuming good hash function and no collisions.

3. Operations on Symbol Tables

A. Insertion

• Process:
  1. Check if the symbol already exists (avoid duplicates).
  2. If not, add the symbol with its attributes.
  3. Update scope/address if needed.

B. Lookup

• Process:
  1. Search for the symbol using its name.
  2. Return its attributes (e.g., type, address).

C. Deletion

• Process:
  1. Remove the symbol from the table (used in scope exit, e.g., end of a block).

D. Traversal

• Used for debugging or optimization (e.g., printing all variables in scope).

In the Real World

1. eSewa (Nepal):

   • Symbol Table Use: When you book a bill payment, eSewa’s backend compiler/interpreter uses a symbol table to track user sessions, transaction IDs, and payment statuses. Each "user" is a scope, and transactions are symbols with attributes like amount, status, and timestamp.
   • Storage Management: Dynamic allocation ensures temporary variables (e.g., temp_total) are freed after use.

2. Khalti’s Payment Gateway:

   • Symbol Table: Stores merchant IDs, API keys, and transaction logs. For example, the symbol merchant_123 might have attributes:

     {
       "name": "merchant_123",
       "api_key": "sk_abc123",
       "balance": 50000,
       "scope": "global"
     }
     

   • Hash Table: Used for $O(1)$ lookup of merchant details during payment processing.

3. Ncell’s Billing System:

   • Activation Records: When a user logs in, a new activation record is created for their session. The symbol table tracks:
     • user_id, plan_type, remaining_data, expiry_date.
   • Dynamic Allocation: Temporary variables (e.g., current_usage) are allocated on the stack and freed when the session ends.

Worked Example: Symbol Table for a C Program

Consider this C code snippet:

#include <stdio.h>
int global_var = 10; // Global scope

void func1() {
    int local_var = 20; // Local to func1
    printf("%d", global_var);
}

int main() {
    int main_var = 30; // Local to main
    func1();
    return 0;
}

Symbol Table After Compilation

Visualization: Scope Hierarchy

graph TD
    A["Global Scope"] --> B["func1 Scope"]
    A --> C["main Scope"]
    B --> D["local_var"]
    C --> E["main_var"]
    A --> F["global_var"]

Storage Management Techniques

Compilers manage memory for variables using two main approaches:

1. Static Storage Allocation

• Definition: Memory is allocated before program execution (e.g., global variables).
• Example: In C, int x; is statically allocated.
• Pros: Fast access, no runtime overhead.
• Cons: Wastes memory if variables are unused.

2. Dynamic Storage Allocation

• Definition: Memory is allocated during runtime (e.g., local variables, heap allocation).
• Types:
  • Stack Allocation: Used for function parameters and local variables (LIFO order).
  • Heap Allocation: Used for dynamic memory (e.g., malloc in C).
• Pros: Efficient memory usage.
• Cons: Slower access; risk of memory leaks.

Activation Records (Runtime Stack)

• Definition: A data structure that stores information about a function call (e.g., parameters, return address, local variables).
• Example: When func1() is called in the earlier C program, an activation record is pushed onto the stack:

Activation Tree

• Definition: Represents the nested call hierarchy of functions.
• Example:

Exam Tip

1. Symbol Table Questions:

   • Always draw a table for symbol entries (name, type, scope, address).
   • Compare hash tables vs. BSTs in terms of time complexity.
   • Explain scope rules (e.g., how global_var is accessible in all functions).

2. Storage Management:

   • Differentiate static vs. dynamic allocation with examples.
   • Draw an activation record for a function call (include parameters, return address, local variables).
   • Mention stack vs. heap allocation (e.g., local variables use stack; malloc uses heap).

3. Common Pitfalls:

   • Don’t confuse symbol table with intermediate code (e.g., three-address code).
   • Remember that hash tables can degrade to $O(n)$ if collisions are high.
   • For activation records, always show the LIFO order in the stack.

Practice Question with Solution

Question: For the following C code, draw the symbol table and activation tree after func2() is called:

int x = 10;
void func1() {
    int y = 20;
    func2();
}
void func2() {
    int z = 30;
}

Solution:

Symbol Table

Activation Tree

Stack After func2() Call