Symbol tables and scopes

Intermediate

Introduction

After parsing, the compiler knows the shape of the program but not what its names mean. In total = total + i, which total is it, and which i? The symbol table answers that. It records every declaration, and the compiler consults it for every use of a name. Errors such as "name is not defined", warnings such as "unused variable", and editor features such as "go to definition" all come from this phase.

How it works

Most languages use lexical scope: a name is visible inside the block where it is declared, including nested blocks, from its declaration onwards. A natural structure for this is a stack of dictionaries, one dictionary per open scope:

  • at the start, the stack holds one dictionary, the global scope;
  • entering a block ({, a function body) pushes an empty dictionary;
  • a declaration adds the name to the top dictionary, with whatever the compiler knows about it: the line, the type, whether it is a variable or a function;
  • leaving a block pops the top dictionary, so its names disappear.

To resolve a use, search the dictionaries from the top of the stack down. The first one that contains the name wins. If an inner block declares a name that also exists outside, the inner one is found first: it shadows the outer one until the block ends. If no dictionary contains the name, the compiler reports that it is not declared.

Declaring a name twice in the same scope is usually an error, because both declarations would be visible at once. Declaring it again in an inner scope is allowed, and simply shadows.

Real symbol tables store more for each entry: its type (used by the type checker), and where its value will live in memory (used by the code generator).

Syntax

scopes = [{}]                       # the global scope
scopes.append({})                   # enter a block
scopes[-1][name] = info             # declare
for scope in reversed(scopes):      # resolve, innermost first
    if name in scope: ...
scopes.pop()                        # leave the block

Example

program = """let total
let i
{
let i
use i
use total
use count
}
use i
let total""".splitlines()

scopes = [{}]
for number, line in enumerate(program, start=1):
    parts = line.split()
    if parts == ["{"]:
        scopes.append({})
        print(f"line {number}: enter scope {len(scopes) - 1}")
    elif parts == ["}"]:
        scopes.pop()
        print(f"line {number}: leave scope")
    elif parts[0] == "let":
        name = parts[1]
        if name in scopes[-1]:
            print(f"line {number}: error, {name} is already declared in this scope (line {scopes[-1][name]})")
        else:
            scopes[-1][name] = number
    else:
        name = parts[1]
        for depth in range(len(scopes) - 1, -1, -1):
            if name in scopes[depth]:
                print(f"line {number}: {name} -> declared on line {scopes[depth][name]}")
                break
        else:
            print(f"line {number}: error, {name} is not declared")
Open in compiler

Line by line

  1. The tiny language has four kinds of line: let declares, use refers to a name, and braces open and close a block.
  2. Line 4 declares a new i inside the block; the use on line 5 finds it first, so it shadows the i on line 2.
  3. total on line 6 is not in the inner scope, so the search continues outwards and finds line 1.
  4. count is in no scope at all, so it is reported as not declared.
  5. After the block closes, i on line 9 resolves to line 2 again, and the second let total on line 10 is a duplicate in the global scope.

Expected result

line 3: enter scope 1
line 5: i -> declared on line 4
line 6: total -> declared on line 1
line 7: error, count is not declared
line 8: leave scope
line 9: i -> declared on line 2
line 10: error, total is already declared in this scope (line 1)

In the real world

CPython's compiler builds a symbol table for every module, class and function, which is how it knows whether a name is local, global or a closure variable. Language servers keep symbol tables for open files so editors can offer completion, rename and "find all references". Linters such as ESLint and Pyflakes use them to warn about unused and undefined names.

Common mistakes

  • Searching from the outermost scope first, so shadowing never works.
  • Forgetting to pop a scope, so names leak out of their block.
  • Treating a redeclaration in an inner scope as an error: it is shadowing.
  • Resolving names by text search instead of by scope, which breaks as soon as two scopes use the same name.

Best practices

  • Store a record for each name (line, kind, type), not just a flag.
  • Report errors with the line of the use and, for duplicates, the line of the first declaration.
  • Resolve every name once, and store the result in the AST for later phases.

Summary

A symbol table records declarations. With a stack of scopes, entering a block pushes a scope, leaving it pops one, declarations go on top, and lookups search from the top down. That gives shadowing, block-local names and clear errors for undeclared and duplicate names.

Quick check

1. In which order are scopes searched when resolving a name?
2. What happens to a block's names when the block ends?
3. An inner block declares x, and x also exists outside. What is that?
4. When is declaring the same name twice an error?

Key takeaways

  • Entering a block pushes a new scope; leaving it pops the scope and forgets its names.
  • Look a name up from the innermost scope outwards; the first match wins.
  • Duplicate names are an error only within the same scope; across scopes they shadow.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.