Resolving Identifier Uses Against a Stack of Lexical Scopes

A parser produces a tree in which every identifier is a bare string. In { int x = 1; { int x = 2; use(x); } use(x); } the two use(x) calls carry identical token text, and nothing in the grammar distinguishes them. They refer to different storage. Attaching that distinction is the first job of semantic analysis, and every later pass — type checking, capture analysis, code generation — depends on it being done exactly once, correctly, and before anything else looks at a name.

What the syntax tree leaves unresolved

The grammar can say that an identifier appears where an expression is expected. It cannot say which declaration that identifier denotes, because denotation is a property of the surrounding program text, not of the token. Three separate questions hide inside that gap.

The first is whether the name denotes anything at all. An identifier in expression position that matches no visible declaration is a program error, but it is not a syntax error: frobnicate(3) parses perfectly.

The second is which of several visible declarations wins. Lexical scoping resolves this by proximity: the declaration in the innermost enclosing scope shadows all others. The rule is simple to state and easy to get subtly wrong at boundaries — the scope of a variable in C begins at the end of its declarator, not at the start of the statement, so the x in int x = 0; { int x = x + 1; } refers to the inner, uninitialized x, and the initializer reads an indeterminate value rather than the outer zero.

The third is what the name is allowed to be used for. A name may denote a value, a type, a function, a label, or a module. The resolver’s output must carry that classification, because sizeof(x) is legal or illegal depending on whether x is a variable or a type name, and that decision is made before any type checking happens.

The scope stack and what each frame holds

The standard implementation is a stack of frames, one per lexical scope, pushed when the walker enters a construct that introduces names and popped when it leaves. Each frame maps a name to a binding record. Lookup walks frames from the innermost outward and stops at the first hit.

The binding record is the important part, and its contents are dictated by the passes downstream. At minimum it holds the declaration site (for diagnostics and for source-level tooling), a kind tag distinguishing value, type, function, label, and module, and whatever type information the checker will eventually fill in. Implementations commonly add storage class, mutability, whether the entity is exported, and a pre-assigned slot index used by later stages.

Pushing and popping must be tied to the tree structure, not to statement order, because the walker is recursive. A let-like construct pushes a frame, resolves its body, and pops. That single invariant gives shadowing for free: an inner declaration overwrites the mapping in the new frame, and the outer frame is untouched, so the shadowed binding reappears the moment the inner frame is popped.

Two rules are worth stating because they are the ones that produce bugs. A frame must not be mutated after the walker leaves it; a resolver that keeps one dictionary for all scopes and removes entries on pop has to remove exactly the entry it inserted, and a scope with two declarations of one name breaks that bookkeeping. And same-scope duplicates must be detected at insertion time, not at lookup time, because the error is about the declarations, not about any particular use.

One pass, or a declaration pass followed by a resolution pass

The naive design resolves while it walks: on encountering a declaration, insert it; on encountering a use, look it up. This works only for languages that require declaration before use within a scope. It fails the moment a construct refers forward.

Mutually recursive functions are the canonical case. In a module where even calls odd and odd calls even, one of the two definitions necessarily appears first, and a single forward walk cannot resolve the body of the first. Class-like constructs fail the same way: a method body that mentions a field declared further down the class, or a type annotation naming a class defined later in the file.

The fix is to separate collection from resolution. A collection pass walks each scope once and inserts every declaration it contains without resolving any of the bodies. A second pass then walks the same scopes with the complete tables in place and resolves uses. Both passes traverse the same tree; only the first mutates tables.

Languages differ on how much ordering they permit, and the difference is visible in their specifications. Go makes declarations at package level order-independent — a function may call another declared later in the same file — while local variables must be declared before use in the block. C requires a declaration to be visible before use at file scope too, which is why headers exist and why a struct that refers to itself must go through an incomplete type and a pointer.

Ordering rules also determine what an initializer can see. If a language allows a declaration’s initializer to reference the name being declared, resolution must insert the binding before resolving the initializer; if it forbids that, insertion must happen after. In C the scope of the declared identifier begins just after the declarator, so int x = x + 1; initializes the new x from its own indeterminate value rather than from an outer x. Choosing wrongly in a compiler for such a language turns a self-reference into a reference to the outer binding, and no later pass will notice.

A resolver skeleton

The shape below is the resolution pass of the two-pass version, written in Python. Nodes are lists whose first element is a tag, which keeps the example short; the declare method is called by the separate collection walk, and the interesting part is the frame discipline.

class Resolver:
    def __init__(self):
        self.scopes = [{}]        # global frame
        self.errors = []

    def declare(self, name, kind, node):
        frame = self.scopes[-1]
        if name in frame:
            self.errors.append(f"{name} redeclared in the same scope")
            return
        frame[name] = {"kind": kind, "decl": node, "type": None}

    def lookup(self, name):
        for frame in reversed(self.scopes):
            if name in frame:
                return frame[name]
        return None

    def resolve_uses(self, node):
        if node[0] == "use":
            binding = self.lookup(node[1])
            if binding is None:
                self.errors.append(f"unresolved name {node[1]}")
                node.append(None)
            else:
                node.append(binding)          # the resolved edge
            return
        if node[0] == "block":
            self.scopes.append({})
            for child in node[1]:
                self.resolve_uses(child)
            self.scopes.pop()
            return
        for child in node[1:]:
            if isinstance(child, list):
                self.resolve_uses(child)

The important property is that lookup returns the record itself, and the use node stores a reference to it. Downstream passes then follow a pointer instead of searching for a string, which removes both the cost and the ambiguity of repeated lookup. When a checker later needs to know the type of x, it reads it from the record, and every use of that x observes the same value.

Why the resolved edge should be an index, not a name

Storing the binding record in the tree is enough for a compiler that never leaves the front end. Compilers that generate code need something cheaper: at runtime, a variable access must become an address, and finding it by name would reintroduce the whole scope walk at execution time.

Two techniques avoid that. The first is to resolve each binding to a pair of coordinates — frame depth from the current point, and slot index within that frame — and to rewrite the use node to carry the pair. Reading a variable then costs one pointer chase down the environment chain and one indexed load, independent of how many names are in scope. The second, used in calculi and in some intermediate forms, replaces names entirely with de Bruijn indices: with zero-based numbering from the innermost binder, a use of the variable bound by the enclosing binder two levels out is written as the number 2, and names disappear from the representation.

Both approaches require the same invariant the string-based resolver maintains: exactly one binding per use, decided once. A resolver that leaves ambiguity in the tree, on the theory that a later pass will sort it out, produces exactly the failures that are hardest to diagnose — a name silently bound to the wrong scope, an inner declaration that captures a use intended for the outer one, a generated access that reads uninitialized storage.

Constructs that defeat lexical resolution

Not every binding is decided by the shape of the source text. Dynamic scoping, found in early Lisp dialects and still visible in the declare-style special variables of some Lisp implementations, looks the name up in the caller’s environment at run time; a resolver cannot compute that edge, and the compiler must instead emit a lookup.

JavaScript’s sloppy-mode with and direct eval can introduce bindings into a scope that the static walk never saw, which is why code containing them loses optimizations and why strict mode restricts them. Macro systems raise the same problem from the other side: a macro body written in one scope is expanded in another, and naive textual substitution produces accidental capture, where an identifier introduced by the macro collides with one at the use site. Hygienic macro systems solve it by renaming introduced identifiers during expansion, so that the resolver sees names that cannot collide.

Reflection and string-keyed access sit outside the resolver’s reach by construction. A field read by a string computed at run time is not an identifier use, and no scope stack applies to it.

Failure modes worth designing for

Deep nesting is the obvious performance hazard: lookup cost is proportional to the number of enclosing frames, and a pathological program with hundreds of nested blocks turns resolution quadratic in nesting depth. Real programs rarely nest more than a few dozen deep, but generated code does, and a resolver that walks the whole stack on every use pays for it. Caching per-frame maps, or keeping a side table from name to frame, removes the walk without changing semantics.

The more consequential failures are diagnostic. Unresolved names should be reported once and then suppressed: a function whose parameter is missing will otherwise generate an error at every use of that parameter, and the cascade buries the one message that matters. The usual technique is to bind the failed use to a synthetic error binding so the walk can continue with a consistent tree; the design of those synthetic bindings is taken up in Error Types and Recovery in a Type Checker.

Redefinition inside a single scope is a different error from shadowing across scopes, and conflating them trains users to ignore the diagnostic. And every resolver needs a decision about the implicit bindings of the language — self, this, the module object, predeclared types — because those are looked up by the same machinery and must not appear as unresolved names. Once a language adds a second kind of name that lives in its own table, such as a struct tag or a type name that may coexist with a variable of the same spelling, the single-map frame is no longer sufficient; that split is the subject of Separate Namespaces and Overload Sets in a Symbol Table.