Your parser can recognize an identifier without knowing which declaration it refers to. Once nested blocks can reuse a name, that distinction becomes essential.
Consider this toy-language fragment:
let score = 10;
use score;
{
let score = 20;
use score;
}
use score;
There are three uses of the spelling score, but two declarations. The outer uses must refer to the first declaration; the middle use must refer to the second. A compiler needs a reliable answer before it can decide which value to load or store.
We will implement a small scoped symbol table in Python and give each declaration a stable identity. This is a name-resolution component for a compiler front end. It starts with declaration/use events that an AST visitor could produce; it does not tokenize or parse source text.
Choose the language rules first
For this example, the toy language has these rules:
- A block introduces a lexical scope. Resolution searches the current scope and then its enclosing scopes, from nearest to farthest.
- A declaration becomes visible after its initializer has been resolved. Statements are visited in source order.
- Repeating a declaration in the same scope is an error. A nested scope may declare the same spelling, temporarily shadowing an outer declaration.
- A use with no visible declaration is an error. There are no forward references, hoisted declarations, overloads, or separate namespaces.
Those choices determine what a symbol table must do. They are not a claim about every language. Python, for example, determines function-local bindings across an entire function block; see its name-resolution rules. We are using Python to implement a different, sequential declaration policy.
That policy also settles self-initialization. Inside an inner block, let score = score + 1; resolves the initializer's use to an already visible outer score, then introduces the new declaration. Without an outer declaration, that initializer is an unknown-name error.
A spelling is not a declaration identity
Storing only "score" on every identifier node loses information. A later pass could confuse the inner and outer variables, especially after the resolver has left their scopes.
Instead, create a Symbol object for each successful declaration. It contains a unique integer ID within this resolver, the spelling, and a source location. A use keeps the resolved object, or its ID, on the AST.
The ID is not a register number, memory address, or stack offset. It identifies a declaration. Storage layout can be assigned in a later pass.
The complete component
Save this as scoped_symbols.py and run python scoped_symbols.py. It uses the Python 3.10 standard library and assumes identifier spellings have already been validated by the front end. The demo:N locations are diagnostic labels supplied by the caller.
from contextlib import contextmanager
from dataclasses import dataclass
class BindingError(Exception):
pass
@dataclass(frozen=True)
class Symbol:
id: int
name: str
declared_at: str
class Symbols:
def __init__(self):
self._scopes = [{}] # A permanent outermost scope.
self._next_id = 0
@contextmanager
def scope(self):
self._scopes.append({})
try:
yield
finally:
self._scopes.pop()
def declare(self, name, location):
current = self._scopes[-1]
if name in current:
previous = current[name]
raise BindingError(
f"{location}: duplicate declaration of {name!r}; "
f"first declared at {previous.declared_at}"
)
symbol = Symbol(self._next_id, name, location)
self._next_id += 1
current[name] = symbol
return symbol
def resolve(self, name, location):
for scope in reversed(self._scopes):
if name in scope:
return scope[name]
raise BindingError(f"{location}: unknown name {name!r}")
def label(symbol):
return f"{symbol.name}#{symbol.id}"
if __name__ == "__main__":
names = Symbols()
outer = names.declare("score", "demo:1")
uses = [names.resolve("score", "demo:2")]
with names.scope():
# Before shadowing, the enclosing declaration is visible.
before = names.resolve("score", "demo:4")
inner = names.declare("score", "demo:5")
uses.append(names.resolve("score", "demo:6"))
uses.append(names.resolve("score", "demo:8"))
print("before inner declaration:", label(before))
print("bound uses:", ", ".join(label(symbol) for symbol in uses))
print("saved inner binding:", label(inner))
try:
names.declare("score", "demo:9")
except BindingError as error:
print(error)
The output is:
before inner declaration: score#0
bound uses: score#0, score#1, score#0
saved inner binding: score#1
demo:9: duplicate declaration of 'score'; first declared at demo:1
The #0 and #1 labels make declaration identity visible. They are only a display convention; source code does not contain those suffixes.
Three operations, three separate jobs
declare() checks only the current dictionary for duplicates. If it searched every enclosing dictionary, it would reject the shadowing our language explicitly allows. A failed duplicate declaration leaves the original binding intact and does not consume an ID.
resolve() searches the dictionaries in reverse order. The first match is the visible declaration at that point in the source. Before the inner declaration, the enclosing score remains visible; after it, the inner one wins.
scope() controls visibility. Entering the context adds a dictionary. Exiting removes it, restoring the enclosing bindings automatically. The finally clause also runs when a binding error interrupts the traversal, so an abandoned block does not leave its declarations visible to later work.
Removing a scope dictionary does not invalidate a Symbol retained by an AST node. In the demonstration, inner still refers to score#1 after the block ends. What disappears is the ability to find it through lexical lookup from outside that block.
The ID counter keeps increasing across sibling blocks. Reusing an ID merely because two declarations occurred at the same nesting depth would make distinct declarations indistinguishable to later passes.
Connect resolution to your AST
An AST visitor should traverse statements in source order. Enter with names.scope(): when visiting a block and bind its statements inside that context. When visiting a name expression, attach the result of names.resolve(node.name, node.location) to that node.
For a declaration with an initializer, the order is important. This is integration pseudocode; the node classes and expression visitor belong to your compiler:
bind_declaration(node):
bind_expression(node.initializer)
node.symbol = names.declare(node.name, node.location)
bind_name(node):
node.symbol = names.resolve(node.name, node.location)
Binding an initializer means resolving the names inside it, not executing it. Introducing the declaration first would implement a different rule for self-reference.
Once the AST is bound, later passes use node.symbol.id to find information about that declaration. For example, code generation might maintain a map from symbol IDs to stack slots. It should not repeat string lookup against whatever scopes happen to be active at that later moment.
Test visibility and identity together
Useful tests cover more than a successful lookup. Try these short checks after the class definitions:
names = Symbols()
outer = names.declare("x", "test:1")
with names.scope():
inner = names.declare("x", "test:2")
assert names.resolve("x", "test:3") is inner
assert names.resolve("x", "test:4") is outer
assert inner.id != outer.id
with names.scope():
first = names.declare("temporary", "left block")
with names.scope():
second = names.declare("temporary", "right block")
assert first.id != second.id
Also check unknown names before declaration, duplicate declarations without overwriting the original, local names disappearing after block exit, and cleanup when an exception leaves multiple nested blocks. These cases catch failures that a flat table of globals will not expose. The published component was checked with 12 scenario tests covering these behaviors.
For the stack-of-dictionaries design, a lookup can inspect every active scope. Declaration checks one dictionary. That is a useful starting point for a small compiler; measure real workloads before replacing the structure.
Keep binding separate from later decisions
Resolving a name says which declaration a use denotes. It does not prove the operand has the right type, that a value is initialized on every control-flow path, or that a stack slot is available. Functions, closures, imports, and separate type/value namespaces need additional language rules and data structures.
An earlier binding pass is one design choice. LLVM's Kaleidoscope local-variable tutorial demonstrates another approach, saving and restoring bindings while generating code. Our example retains explicit declaration identities so later passes can work from a bound AST.
For a larger compiler project, my Creating a C Compiler From Scratch Video Course! includes lessons on scopes, symbol resolution, variables, and semantic validation. It provides a broader compiler context for the name-binding problems explored here.
Daniel McCarthy