Structure of a Symbol Table and Per-Identifier Information

A symbol table is typically the central runtime data structure used during semantic analysis to manage scopes and to attach language meaning to each identifier (name) encountered in source code. Conceptually, a symbol table is a map from an identifier to an “entry” that stores all relevant attributes needed for later phases like type checking, intermediate-code generation, and code generation. The same identifier name may have different meanings in different scopes, so the table structure must support scope nesting and lifetime.

A common structural pattern is: (1) a hierarchy of scopes (often stacked), and (2) within each scope, a lookup structure (e.g., a hash map) from identifier to a symbol-table entry that holds attributes such as type, storage class, declaration node references, and (later) memory/register location metadata.

Even when different compilers choose different concrete data structures (e.g., hash tables, balanced trees, tries, or custom internals), the per-identifier information is remarkably consistent across language implementations: what the identifier is (variable/function/type/label), its type (including parameter/return types), and how it should be used (e.g., lvalue/rvalue, constant-ness, addressability). This section focuses on the structural design of the symbol table and the typical fields stored per identifier entry, including how scope affects lookup and updates.

Key concepts and terms

• identifier: the source-level name being resolved (e.g., x, sum, printf).
• scope: controls visibility and meaning.
• symbol-table entry: the “row” for one identifier instance in one scope.
• attribute: type, storage info, constness, etc.

Structural overview: scopes + per-scope mappings

Most symbol table implementations separate two concerns:

1. Scope nesting management
   • Maintain a stack of scopes during traversal of the syntax tree (entering a block/function pushes a new scope; leaving it pops).
   • Alternatively, maintain a linked tree where each scope has a pointer to its parent scope.
2. Efficient lookup inside a scope
   • Use a hash table or balanced BST keyed by identifier name.
   • The lookup algorithm typically searches the current scope first, then moves outward through parent scopes until it finds a declaration or reaches the global scope.

This yields a clear design: a scope object contains a mapping name -> entry, and each scope knows its parent.

Per-identifier information: what a symbol-table entry usually stores

A symbol-table entry is a structured record. The exact fields depend on the language and compiler stage, but typical contents can be grouped into:

1. Identity / linkage to syntax

   • The identifier’s name (often redundant since it’s the map key, but stored sometimes for debugging/error messages).
   • A reference to the declaration node in the AST (or parse-tree token) for later checks and for meaningful diagnostics.

2. Kind of entity (what it represents)

   • Variable / field / parameter
   • Function / method
   • Type name / typedef / class name / enum
   • Labels (for languages with goto-like constructs)

   This is often encoded as an enum-like entity kind so the compiler can apply correct rules.

3. Type information

   • The type of the identifier (e.g., int, float, array-of-T, pointer-to-T).
   • For functions: return type and parameter types.
   • Sometimes qualifiers: const, mutability, reference-ness, etc.

4. Storage and usage attributes

   • For variables:
     • Whether it is local/global, addressable, and (in some IRs) the memory location model.
     • Whether it is a constant (compile-time constant evaluation).
     • Whether it is an lvalue/rvalue category (languages with expression categories).
   • For functions:
     • Calling convention / signature details.
     • Whether it is declared/defined (important for forward declarations).
   • For types:
     • Whether it’s complete/incomplete (e.g., forward struct declarations in C-like languages).

5. Scope-life / visibility

   • The scope level or depth where the entry was created.
   • A “serial number” or unique id for internal consistency.

6. Later-stage code generation hooks

   • Offsets in activation records (stack frame) for locals.
   • Global symbol address references.
   • Intermediate representation handles (e.g., a pointer to an IR variable).
   • For register allocation, some compilers store enough info to connect the entry to register/temporary decisions.

These categories appear repeatedly because the compiler needs the same answers during later passes: what is this identifier? what is its type? how can it be used? where does it live?

Concrete entry layout: a “field checklist”

Below is a practical checklist you can use to understand what fields a symbol table entry often contains. (Different compilers abbreviate or defer fields until later passes.)

This organization supports both static semantics (meaning and correctness) and engineering practicality (later phases can reuse the stored attributes rather than recompute them).

Data structure alternatives and why they matter

The structure of the symbol table can vary, but scope + mapping is the conceptual invariant.

• Hash map per scope: average $O(1)$ lookup/insertion per scope level, good for large programs.
• Balanced BST per scope: $O(\log n)$ lookup/insertion per scope, sometimes useful for ordered iteration (e.g., for tooling).
• Single global map with scoped keys: embed scope id into the key (e.g., (name, scopeId)), allowing faster access without walking parents, but needs careful handling for shadowing and redeclarations.
• Persistent/functional style: represent scopes as persistent maps (common in theory/functional compilers), good for immutability and easy backtracking.

The key point for learning is that the symbol table structure is chosen to optimize lookup under the required scope resolution semantics.