Symbol Tables and Scope Resolution

A symbol table is the compiler's dictionary: a data structure mapping each identifier (a name written in source code) to a symbol table entry describing everything the compiler currently knows about that name — its kind (variable, function, type, constant), its declared or inferred type, its storage class (local, global, register, heap), and bookkeeping such as the scope level or a pointer to the enclosing scope where it was declared. Populating and querying this table is a core responsibility of semantic analysis, sitting between parsing (which produces a syntax tree with no notion of "what a name refers to") and later phases that need that notion resolved. A scope is a region of program text — a function body, a block, a class, a module — within which a set of declarations is visible. Scopes nest: an inner scope can see everything visible in its enclosing scope, plus its own local declarations. When an inner scope declares a name that already exists in an outer scope, the inner declaration shadows the outer one: for the remainder of the inner scope, uses of that name refer to the new, inner binding, and the outer binding becomes temporarily invisible (not deleted — it reappears once the inner scope ends). This nesting is precisely why a single flat table will not do: `x` in an inner block and `x` in an outer block are different entities that happen to share a spelling, and the table structure must track which is currently active. The standard resolution discipline is static (lexical) scoping: the scope that determines a name's binding is the one textually enclosing the reference, determined at compile time by the nesting of `{ }` blocks, function bodies, or `begin...end` regions in the source — independent of the runtime call stack. (This is in contrast to dynamic scoping, used by a few languages like early Lisp dialects and shell scripting, where the binding depends on the runtime call chain; dynamic scoping needs a different implementation, typically a single global table with save/restore on call, and is largely a historical curiosity in modern language design.) This article assumes static scoping, which is what essentially every mainstream language (C, Java, Python, Rust, ML) uses for local variables.

The dominant implementation technique is the scope stack of hash tables, sometimes called a chained symbol table or cactus stack when scopes can branch (as with sibling blocks that both exit back to the same parent). Each scope is its own hash table mapping names to entries; each scope table carries a pointer to its enclosing scope. Opening a block pushes a new, empty table linked to the current one; closing a block pops it, discarding its bindings and instantly restoring visibility of whatever the enclosing scope had.

Insertion always targets the current (innermost) scope only — a declaration never silently modifies an outer scope. Lookup starts in the current scope and, on failure, follows the enclosing-scope pointers outward, checking each ancestor table in turn, until either a binding is found or the global (outermost) scope is exhausted, at which point the name is undeclared. This outward walk is exactly what implements shadowing correctly: the search finds the nearest enclosing declaration first, because it checks the innermost scope before any outer one. Some languages (C, most block-structured languages) forbid re-declaring a name within the same scope; the compiler enforces this by checking, on insertion, whether the current scope's table already has an entry for that name. Other languages allow a limited form of re-declaration (e.g., variable shadowing in Rust's `let x = ...; let x = ...;`), which is implemented identically — the new entry simply replaces the old one in the current table only. ```text // Symbol table entry: everything the compiler knows about one binding struct Entry: name : string kind : {VARIABLE, FUNCTION, TYPE, CONSTANT, PARAMETER} type : Type // filled in during / after type checking scopeDepth : integer location : StorageLocation // e.g., stack offset, register, global address // ...additional attributes as needed (mutability, visibility, arity) // A scope: one hash table plus a link to its enclosing scope struct Scope: table : HashMap parent : Scope or NULL // NULL only for the global/outermost scope depth : integer // ---- Core operations ---- function enterScope(current: Scope) -> Scope: new = new Scope(table = empty HashMap, parent = current, depth = current.depth + 1) return new function exitScope(current: Scope) -> Scope: // Discard the innermost table; its bindings vanish, outer ones reappear. assert current.parent != NULL // never pop the global scope return current.parent function declare(scope: Scope, name: string, entry: Entry) -> bool: // Returns false if 'name' is already bound in THIS scope (redeclaration error) if name in scope.table: return false entry.scopeDepth = scope.depth scope.table[name] = entry return true function lookup(scope: Scope, name: string) -> Entry or NULL: s = scope while s != NULL: if name in s.table: return s.table[name] s = s.parent return NULL // undeclared identifier // ---- Driving the whole pass over a syntax tree ---- function resolve(node: ASTNode, scope: Scope) -> Scope: match node.kind: case BLOCK: inner = enterScope(scope) for stmt in node.statements: inner = resolve(stmt, inner) scope = exitScope(inner) case VAR_DECL(name, initExpr): resolve(initExpr, scope) // resolve RHS in OLD scope first ok = declare(scope, name, makeEntry(node)) if not ok: error("redeclaration of " + name + " in same scope") case IDENTIFIER_USE(name): entry = lookup(scope, name) if entry == NULL: error("undeclared identifier " + name) else: node.binding = entry // annotate AST for later phases case FUNCTION_DECL(name, params, body): declare(scope, name, makeEntry(node)) // function name visible in outer scope inner = enterScope(scope) for p in params: declare(inner, p.name, makeEntry(p)) resolve(body, inner) // inner scope discarded on return; outer scope unaffected return scope ``` The one subtlety worth flagging in the pseudocode: for `VAR_DECL`, the initializer expression is resolved before the new name is declared, in the old scope. This mirrors languages like C where `int x = x;` refers to an outer `x` (if one exists) inside the initializer, not the not-yet-declared inner `x` — the declaration only becomes visible to statements after it. Some languages (letrec-style recursive bindings, or `function` declarations that are visible throughout their own scope for recursion) instead declare the name first; the pseudocode's ordering is a design decision each language's specification fixes explicitly, and a compiler's symbol-table pass must match it exactly.

Time complexity. With each scope implemented as a hash table, `declare` and a single-scope `lookup` are `O(1)` expected time (amortized, assuming a reasonable hash function and load-factor-bounded resizing), exactly as for any hash table. A full `lookup(scope, name)` call visits at most `d + 1` scopes, where `d` is the nesting depth of `scope`, so the worst case is `O(d)` expected time. Since real programs rarely nest more than a small constant number of blocks/functions deep (say, single digits to low tens), lookup is effectively `O(1)` in practice; pathological cases (deeply nested generated code) still only cost `O(d)`, which is linear in a quantity bounded by the source file's own nesting, not by program size. Over an entire compilation pass that resolves every identifier occurrence once, if there are `n` identifier occurrences total, the whole pass costs `O(n · d_max)` expected time — for well-structured code, effectively `O(n)`. If hash tables are replaced by balanced trees (e.g., to guarantee worst-case bounds or support ordered iteration), each scope operation costs `O(log k)` where `k` is the number of names in that scope, giving `O(d log k)` per lookup — a common trade in compilers that need deterministic (non-amortized) performance guarantees, such as some safety-critical toolchains.

Space complexity. Total space is `O(N)` where `N` is the total number of declarations across the whole program, since each declaration occupies exactly one entry in exactly one scope table at the time it is live; entries are freed (the table is discarded) when their scope closes. Peak space is bounded by the number of simultaneously-open scopes' worth of declarations, which is at most `O(N)` but in practice far smaller, proportional to the maximum number of live bindings at any single program point.

Correctness argument. The key invariant maintained by `enterScope` / `exitScope` / `declare` / `lookup` is: > Invariant (scope stack faithfulness). At any point during traversal of the AST, the chain of `Scope` records reachable from `current` via `parent` pointers is exactly the sequence of lexically enclosing blocks of the AST node currently being processed, ordered from innermost to outermost, and each table contains exactly the set of names declared (and not yet superseded within that same scope) in statements of that block processed so far. This invariant holds initially (only the global scope exists, matching the top level of the program), and each AST-traversal case preserves it:

• `BLOCK` pushes a new table exactly when entering the block's statements and pops it exactly when leaving, so the chain always mirrors the current nesting;
• `VAR_DECL` inserts only into the current table — never an ancestor — so an inner declaration cannot corrupt an outer scope's bindings, which is precisely what "shadowing without deletion" requires;
• `lookup`'s outward walk checks the innermost table first, so if a name is bound both in the current scope and some ancestor, the innermost (most local) binding is returned — this is the formal statement of "shadowing resolves to the nearest enclosing declaration," matching the static-scoping rule by construction, not by accident.

Because the traversal order of `resolve` follows the AST's structure — recursing into a block's body only between the corresponding `enterScope`/`exitScope` calls — the chain of scopes at the moment any `IDENTIFIER_USE` node is visited is guaranteed by structural induction on the AST to be exactly its lexically enclosing scopes. Hence `lookup` at that point searches precisely the scopes the language specification says are visible, in precisely the priority order (innermost first) that specification requires. This is the formal justification that the algorithm resolves names correctly, not merely plausibly.

Honest tradeoffs. The chain-of-hash-tables design assumes scopes are used in a strictly nested, stack-like fashion (open, then close, matching parentheses) — true for ordinary blocks and function bodies but not automatically true for closures, which must retain access to an enclosing scope's variables even after that scope's stack frame would normally be discarded. Supporting closures correctly requires either keeping the closed-over scope alive on the heap (escape analysis decides which variables must be heap-allocated) or flattening captured variables into an explicit environment record — an extension layered on top of, not a replacement for, the scope-chain idea. Similarly, languages with forward references (e.g., calling a function defined later in the same file) or hoisting (JavaScript's `var`) need a preliminary pass that declares all names in a scope before resolving any uses, rather than the single interleaved pass shown above.

Consider this snippet, with line numbers, resolved with the algorithm above: ```text 1 int y = 10; // global 2 int f(int x) { 3 int z = x + y; // uses param x, global y 4 { 5 int x = z * 2; // shadows parameter x 6 print(x); // which x? 7 } 8 print(x); // which x? 9 } ``` Trace of scope operations and lookups:

The payoff of the trace is line 6 versus line 8: the identical source syntax `print(x)` resolves to two different bindings — the shadowing local `int x` on line 6, and the original parameter `x` on line 8 — purely because of where each use sits in the scope chain at the moment it is visited. No renaming, no special-casing: the outward-search invariant produces the right answer automatically, and popping scope2 at line 7 is what makes the parameter binding "reappear" for line 8.

The scope-stack symbol table crystallized alongside the development of block-structured languages, where the very idea of nested `begin...end` regions with local declarations was new and needed a matching compiler data structure. ALGOL 60's committee formalized lexical block structure and the display/static-link mechanisms for accessing enclosing scopes at runtime, directly motivating the compile-time scope-chain design used ever since. The theoretical grounding for treating identifiers as bound occurrences resolved against a nested environment traces further back to formal work on variable binding and substitution in logic and the lambda calculus.

Every production compiler and interpreter — GCC, Clang/LLVM, javac, the Rust compiler, CPython's compiler, V8's JavaScript parser — implements some variant of the nested scope-table architecture described here, because every one of these languages has lexically nested blocks and shadowing rules that must be honored exactly. IDEs and language servers (the machinery behind "go to definition," autocomplete, and rename-refactoring in VS Code, IntelliJ, and similar tools) build and query symbol tables incrementally as you type, using the same scope-chain search to answer "what does this identifier refer to right here." Linkers and module systems extend the same idea across file boundaries, with a global "module scope" acting as the outermost table in the chain. Debuggers rely on symbol tables (often persisted into debug-info formats like DWARF) to map a running program's memory locations back to source-level variable names, reusing the scope-depth and location fields exactly as populated during the compiler's original symbol-table pass. Once identifiers are resolved to bindings, those bindings carry (or acquire) type information, which is exactly the handoff into Type Checking in Compilers — the symbol table entry populated here is the very record a type checker will annotate and query next.

Ask the tutor: How would you modify this scope-chain design to correctly support closures that capture mutable local variables?