---
title: Symbol Tables and Scopes
url: https://doc.liz6.com/en/compilers/03-semantic-analysis/01-symbol-tables-and-scopes
locale: en
area: compilers
tags:
- compilers
- semantic-analysis
date: null
modified: 2026-07-19
description: 'Symbol Tables and Scopes The compiler''s "contact list": associating every identifier with its definition—from stack-based lookups in lexical scope to closure ca…'
---

# Symbol Tables and Scopes

> The compiler's "contact list": associating every identifier with its definition—from stack-based lookups in lexical scope 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 (storing a mapping from names to information), once scope rules are introduced, the design of the symbol table directly impacts the correctness and efficiency of the compiler. Closure capture, 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:

| Operation | Semantics |
|------|------|
| `insert(name, info)` | Register a name in the current scope |
| `lookup(name)` | Look up the definition of the name, searching outward from the current scope |

Additionally:
- `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 countless times during the compiler's name resolution phase and must be O(1) or close to O(1).

## Stack-Based Symbol Tables: Native Mapping for Lexical Scope

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 scope 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 Map?

A single hash map `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 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 the `public` symbols of the imported module into the current scope chain (or maintains a separate "imported symbols" list). The Rust compiler expands `use` statement imports into the symbol table during the `resolve` phase.

## Closure Capture: 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 capture in the symbol table:
1. When entering the `inner` scope, `lookup("x")` finds `x` in `outer` by following the scope chain.
2. Mark `x` as "captured by closure"—this is a crucial semantic marker. During subsequent code generation, `x` cannot be allocated on the stack (otherwise the stack would be reclaimed after `outer` returns); it must be **heap-allocated or use an upvalue mechanism**.
3. Record the capture list in the closure's symbol information: `[(x, by_ref_or_by_value)]`.

The Rust compiler distinguishes 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), the same name may have **multiple definitions** in a single scope (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 selected depends on the argument types at the call site—this falls under the domain of type checking (discussed in [Type Systems](/compilers/03-semantic-analysis/02-type-systems.md)). 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++—a separate copy of machine code is generated for each actual value of the type parameter T (e.g., `i32`, `String`). This implies for the symbol table:

- The generic definition itself is a single 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, `lookup` always returns the first inserted symbol with the same name → Must use a stack-based approach.
- **`lookup` skipping the full chain**: Some implementations skip the `parent` chain for performance, querying a global cache directly → Scope shadowing fails.
- **Missing closure capture markers**: The symbol table detects capture but fails to mark it → Code generation allocates stack space for captured variables → Use-after-free 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 name spaces, e.g., C's `struct foo` vs `foo` variable) → The symbol table needs separate name spaces (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/` — Industrial-grade implementation of name resolution, including modules, closure capture, 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*