Symbol Tables and Scopes

The compiler's "contact list": associating every identifier with its definition—from stack-based lookups in lexical scopes to closure capture markers, from module imports to generic monomorphization. All semantic analysis begins with this table.

Overview

The first step in semantic analysis is not type checking, but name resolution—associating every identifier in the source code (variable names, function names, type names) with its definition. The symbol table is the data structure used for this purpose. While it may seem simple (a mapping from names to information), the introduction of scope rules means that the design of the symbol table directly impacts the correctness and efficiency of the compiler. Closure captures, module imports, generic specialization, and overload resolution each impose different operational requirements on the symbol table.

Basic Operations of a Symbol Table

Any symbol table must efficiently support two core operations:

Additionally, the following are required:

• enter_scope() / exit_scope(): Enter/leave a lexical scope
• lookup_current(name): Search only in the current scope (used to detect duplicate definitions)

Complexity is critical: insert and lookup are called a massive number of times during the compiler's name resolution phase, so they must be O(1) or close to O(1).

Stack-Based Symbol Tables: Native Mapping for Lexical Scopes

The scopes in source code are naturally nested (braces within braces), which maps directly to a stack-based symbol table:

struct Scope {
    symbols: HashMap<String, SymbolInfo>,   ← Names in this scope
    parent: u32,                            ← Index of the outer scope
}

symbol_table: Vec<Scope>   ← Stack, with the current scope at the top

enter_scope():  push new Scope {parent: current top index}
exit_scope():   pop

lookup(name):
    scope = top of stack
    while scope != nil:
        if name in scope.symbols:
            return scope.symbols[name]
        scope = scope.parent              ← Search outward along the parent chain
    return NOT_FOUND

• insert: Writes only to the current scope (top of the stack).
• lookup: Searches outward from the top of the stack along the parent chain; the first match is the nearest definition (adhering to the lexical scoping rule where "inner scopes shadow outer scopes").
• Complexity: insert is O(1); lookup is O(depth), where depth is typically constant (nesting is rarely deep).

This is the implementation used by the vast majority of compilers—Clang, parts of the Rust compiler, and C/C++ compilers all use this pattern.

Why Not a Single Global Hash Table?

A single hash table HashMap<String, Vec<SymbolInfo>> could also work, but when exit_scope() is called, it would need to iterate through and delete all entries inserted in that scope. This is less clean than simply popping a Scope from the stack.

Modules and Namespaces: Secondary Lookups

When a language has modules or namespaces ("importing names from another file"), the symbol table needs to perform lookups across "current file → current module → imported modules":

lookup(name, current_module):
    result = lookup_local(name)                   ← 1. Current scope chain
    if result: return result
    result = lookup_imported(name, current_module) ← 2. Public symbols from other imported modules
    if result: return result
    return lookup_global(name)                    ← 3. Global (e.g., built-in types/functions)

The module system introduces visibility to the symbol table:

• public: The name is visible to importers
• private: Visible only within the current module

When handling module imports, the symbol table only inserts public symbols from the imported module into the current scope chain (or maintains a separate list of "imported symbols"). The Rust compiler, during the resolve phase, expands use statement imports into the symbol table.

Closure Captures: From Scope Chains to "Escaping" Names

When a language supports closures, the closure body may reference variables from an outer scope—these variables need to remain accessible even after exit_scope() is called for the outer scope:

fn outer():
    x = 10
    return fn inner():       ← inner captures x
        return x + 1         ← x is in outer's scope, but inner escapes as a return value

The process for handling closure captures in the symbol table:

1. When entering the inner scope, lookup("x") finds x in outer by traversing the scope chain.
2. Mark x as "captured by a closure"—this is a crucial semantic marker. During code generation, x cannot be allocated on the stack (otherwise the stack would be reclaimed after outer returns); it must be heap-allocated or handled via an upvalue mechanism.
3. Record the capture list in the closure's symbol information: [(x, by_ref_or_by_value)].

The Rust compiler distinguishes between capture modes for Fn/FnMut/FnOnce (shared reference/mutable reference/transfer ownership) during the symbol resolution phase—these decisions all stem from the symbol table's capture analysis.

Overload Resolution: lookup No Longer Returns a Single Value

In languages with function overloading (C++, Java), a single name may have multiple definitions in one scope (with different parameter types). In this case, lookup does not return a single symbol, but an overload set:

lookup("foo") → [
    foo(int, int) → int,
    foo(float, float) → float,
    foo(string, string) → string,
]

Which one is chosen depends on the argument types at the call site—this falls under the domain of type checking (discussed in Type Systems). The symbol table's responsibility is to maintain the overload set, not to make the selection.

Generics and Monomorphization: Multiple "Incarnations" of a Name

Generic functions like fn identity<T>(x: T) -> T are monomorphized in Rust/C++—generating independent machine code for each actual type argument T (e.g., i32, String). This implies for the symbol table:

• The generic definition itself is a symbol, accompanied by a list of type parameters.
• Each instantiation (identity::<i32>) produces a new symbol table entry—but its reference information (captures, dependencies) is copied from the generic template.
• The symbol table needs to support "instantiating templates"—copying the symbol information of the generic definition and replacing its type parameters with actual types.

The Rust compiler performs monomorphization at the MIR layer (not the AST layer), so the symbol table carries different granularities across the AST→HIR→MIR stages.

Trade-offs and Failure Modes

• Single-layer global table: Does not distinguish scopes → Inner names shadowing outer names is invalid, and lookup always returns the first inserted symbol with the same name → A stack-based approach is mandatory.
• lookup skipping the full chain: Some implementations skip the parent chain for performance, searching directly in a global cache → Scope shadowing fails.
• Missing closure capture markers: The symbol table detects captures but fails to mark them → Code generation allocates stack space for captured variables → Use-after-free errors when the closure is invoked.
• Circular module imports: A imports B, B imports A → Infinite loop during symbol table resolution → The resolution phase needs to maintain a set of "modules currently being resolved" to detect cycles and report errors.
• Same name, different types: In some languages, functions and variables can share the same name (in different namespaces, e.g., C's struct foo vs. foo variable) → The symbol table needs separate namespaces (tag namespace, object namespace, label namespace), each with independent stack-based lookups.

References

• Dragon Book: Chapter 2 (symbol table) & Chapter 6 (type checking via symbol table)
• Cooper/Torczon: "Engineering a Compiler", Chapter 4 (symbol tables & scoping)
• Rust compiler source: compiler/rustc_resolve/src/ — An industrial-grade implementation of name resolution, including modules, closure captures, and macro expansion

Keywords: symbol table, stack-based symbol table, scope, name resolution, lexical scope, shadowing, module, namespace, visibility, public/private, closure capture, upvalue, overload set, overload resolution, monomorphization, generic instantiation, cyclic import, name space