Symbol Tables and Scope

When the compiler meets the name x for the second time, it faces a deceptively hard question: which x? The one declared in this block, the parameter of the enclosing function, a global, or an error because there is none? Answering it — turning every use of a name into a reference to the exact declaration it denotes — is the job of the symbol table, the compiler's memory of "what names exist and what does each one mean." Every later phase leans on it: type checking asks it for a name's type, code generation asks it for a name's storage location.

A symbol table is, at heart, a dictionary from a name to its attributes. What makes it interesting is scope: the same name can denote different things in different regions of the program, and the table must model exactly which declaration is "in view" at each point. Get the structure right and name resolution is a two-line lookup; get it wrong and the compiler cheerfully binds a use to the wrong declaration, a bug that survives all the way to a mysterious runtime.

What a symbol carries

Each entry — one per declaration — records everything later phases will ask for. The name is only the key; the value is a small record:

Field	Meaning	Used by
name	the identifier (the lookup key)	the resolver
kind	variable, function, type, parameter, constant…	semantic checks
type	the declared or inferred type	type checking
scope / level	the region it belongs to (nesting depth)	resolution, shadowing
offset / address	storage location (stack offset, register, label)	code generation

The container is almost always a hash table: name resolution is the hottest operation in a compiler, and hashing gives expected O(1) insert and lookup. One hash table per scope, chained together, is the workhorse structure — and the chaining is exactly what models nesting.

Nested scopes: a stack of tables

Blocks nest, so scopes nest, so the tables nest. The classic organisation is a stack of hash tables (equivalently, a chain of environments, each pointing at its enclosing one). When the compiler enters a block it pushes a fresh empty table; declarations in that block go into the top table; when it leaves the block it pops that table, and every local name vanishes at once. Look-up walks the chain outward: search the top table, then its parent, then its parent, until the name is found or the chain runs out.

Because look-up always starts at the innermost table and moves outward, the nearest declaration wins automatically — no special case needed. That single rule is the whole mechanism behind shadowing: an inner x hides an outer x simply because the inner table is searched first. Pop the inner scope and the outer x is visible again, untouched.

Lexical scope vs dynamic scope

There are two rival answers to "which declaration does a name refer to," and the difference is one of the deepest in language design.

Lexical (static) scope: a name refers to the declaration that textually encloses its use, decided by reading the source. The chain of tables above follows the program's block structure, so resolution is fixed at compile time. Nearly every modern language — C, Java, Python, Rust, JavaScript — is lexically scoped.
Dynamic scope: a name refers to the most recent binding still live on the call stack at run time — who called you, not who encloses you textually. The resolution can differ from call to call. Older Lisps, some shells, and Emacs Lisp's classic default used it.

The contrast is stark: under lexical scope a function's free variables are pinned by where it is written; under dynamic scope, by where it is called from. Lexical scope is what makes closures and modular reasoning possible — you can understand a function by reading it, not by tracing every caller. It is why the symbol-table chain mirrors the syntax tree, not the call sequence.

A scoped symbol table, in code

The full mechanism is short: a stack of maps, four operations (enterScope, exitScope, declare, lookup), and the outward-walking search. Watch shadowing and restoration fall out for free.

type Sym = { name: string; type: string; level: number }; class SymbolTable { private scopes: Map<string, Sym>[] = [new Map()]; // scope 0 = global enterScope(): void { this.scopes.push(new Map()); } exitScope(): void { this.scopes.pop(); } // locals vanish at once // Declare in the CURRENT (innermost) scope. Redeclaring here is an error. declare(name: string, type: string): void { const top = this.scopes[this.scopes.length - 1]; if (top.has(name)) throw new Error(`duplicate declaration of '${name}' in this scope`); top.set(name, { name, type, level: this.scopes.length - 1 }); } // Look up: innermost scope first, then outward. Nearest declaration wins. lookup(name: string): Sym | undefined { for (let i = this.scopes.length - 1; i >= 0; i--) { const found = this.scopes[i].get(name); if (found) return found; } return undefined; // unresolved name } } const st = new SymbolTable(); st.declare("x", "int"); // global x : int console.log("outer x ->", st.lookup("x")?.type, "at level", st.lookup("x")?.level); st.enterScope(); st.declare("x", "string"); // inner x SHADOWS the global console.log("inner x ->", st.lookup("x")?.type, "at level", st.lookup("x")?.level); st.exitScope(); console.log("after exit, x ->", st.lookup("x")?.type); // outer int is back console.log("unknown y ->", st.lookup("y")); // undefined: unresolved

The output tells the whole story: the inner string x shadows the global int x while the scope is open, and the instant we exitScope the global is visible again, unharmed. Redeclaring x in the same scope, by contrast, throws — that is a duplicate declaration, a genuine error, not shadowing.

Forward references and two-pass resolution

One wrinkle breaks the tidy "declare before use" story: forward references. A method may call another method declared later in the same class; two functions may be mutually recursive. A single left-to-right pass would reach the use before the declaration exists in the table. Compilers solve this with a two-pass approach over each scope that permits forward references: first collect all declarations of the scope into the table, then resolve every use against the now-complete table. C, by contrast, historically required a forward prototype precisely because its one-pass model would otherwise not know the callee yet.

You could keep a single global hash table and tag every entry with its scope level, popping entries as scopes close. Some classic compilers did exactly that, threading a per-name list of declarations with the most recent at the front. But a stack-of-tables has two quiet virtues: exitScope is O(1) — pop one table and every local dies together, with no scan to evict individual entries — and the structure is the scope chain, so lookup and closure-capture read straight off it. The trade is a little more memory for many tiny tables; in practice the clarity and the cheap scope-exit win handily, which is why the chained-environment design is the textbook default.

Two mistakes look alike and are opposites. Shadowing declares a name in an inner scope that already exists in an outer one — perfectly legal, and it simply hides the outer name for the duration of the inner block. Redefinition declares the same name twice in the same scope — an error, because there is now no way to say which one a use means. The rule is about which scope, not merely whether the name already exists: check for a clash only in the current table, never in the whole chain.

The dual error is resolving at the wrong scope: binding a use to a declaration that is textually visible but not the nearest one, or to one that has already been popped. Always resolve innermost-first, and remember that a name declared later in a forward-reference scope is still in that scope — miss it and you will wrongly report an undefined name, or bind to a stale outer one. Name resolution is precise or it is wrong; there is no "close enough."