Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 61 ยท Semantic Analysis

Symbol Tables and Scopes

Learn how compilers track names with symbol tables and scope chains: shadowing, declare-before-use, a resolver pass, and runnable Python examples.

When your program says total = price * 3, the parser sees three names and an operator. It has no idea what price is. Is it a variable or a function? Was it declared? What is its type? Is it the price from this function or the one from the file level? Answering these questions is the job of the symbol table, the compiler's database of names, and of the scope rules that decide which declaration a use of a name refers to.

Nearly every later phase relies on this information. The type checker asks the table for the type of a variable, code generation asks where it lives, and error reporting asks whether it exists at all. In this lesson you will build a scope chain, see how shadowing works, and write a resolver pass that links each use of a name to its declaration and reports mistakes.

What a symbol table stores

A symbol table maps a name to information about it. What the information contains depends on the language, but typical fields are:

  • the kind: variable, constant, function, parameter, type, module
  • the type (for statically typed languages)
  • the scope or nesting level where it was declared
  • the storage: a position in the stack frame, a global address, or a register
  • for functions: the parameter list and return type
  • the line of the declaration, for good error messages
  • flags such as "has been initialized" or "has been used"

Implementations are usually hash tables, because lookups must be fast: the compiler may query it millions of times. A compiler also rarely has just one table. Each scope gets its own, and the tables are connected.

Scopes

A scope is a region of the program in which a declaration is visible. Most languages have lexical (also called static) scoping: the scope is determined by the structure of the source text, so the compiler can resolve names without running anything. A block { ... } opens a new scope, and a function opens one for its parameters and locals.

Scopes nest like boxes. A name is looked up in the innermost scope first, and if it is not found there the search moves outward, one level at a time, until it reaches the global scope. If the global scope does not have it either, the name is undeclared.

flowchart TD
    G["Global scope<br/>x = 1, y = 2"]
    B["Block scope<br/>x = 10"]
    I["Inner scope<br/>z = 99"]
    I -- "parent" --> B
    B -- "parent" --> G

A chain of scopes. Lookup starts at the bottom and follows the parent links upward.

Because each scope points to its parent, this structure is often called a scope chain (or a stack of tables). Entering a block creates a new scope whose parent is the current one. Leaving the block discards it, so its names disappear.

Shadowing

When an inner scope declares a name that also exists outside, the inner declaration shadows the outer one. Lookups from inside find the inner one first, and the outer one is untouched, becoming visible again when the block ends. Shadowing is not an error, but declaring the same name twice in the same scope normally is.

The code below builds the chain from the diagram and shows each of these behaviours.

Python A scope chain with shadowing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lookups from inner show how far each search travelled. z is found right away (0 scopes up). x is found in block (1 scope up), and that is the shadowing version, not the global one. y needs two steps, and w runs off the end of the chain and returns nothing, which a compiler would turn into an "undeclared variable" error. The number of steps taken is not a detail: a compiler can record it, so that at run time the variable can be found directly, without searching by name.

Some languages differ in subtle ways. In Python, a function's local scope is decided by looking at the whole function body: assigning to a name anywhere in it makes that name local to the function. In JavaScript, var is function-scoped while let and const are block-scoped. When you design a language, decide these rules in writing first, then implement them in the table.

Declare before use

Another design question is: when does a declaration take effect? Look at this line, inside a block where an outer a exists:

TEXT
let a = a + 1

Which a is on the right-hand side? There are three common answers. C lets the new a be visible already in its own initializer (so this reads an uninitialized variable). Some languages refer to the outer one. A third option, used by Lox and by JavaScript's let, is to make it an error to use a variable in its own initializer.

The resolver below follows the third rule with a small trick: when it sees a declaration, it first marks the name as declared but not yet defined, then it resolves the initializer, and only afterwards marks the name as defined. A use that finds the name in the "declared but not defined" state is reported as a mistake.

A related rule concerns forward references. Local variables must be declared before use in nearly every language. At the top level of a file, many languages let functions call functions that appear later, so the compiler makes a first pass to collect all declared names, and a second pass to resolve the bodies.

A resolver pass

A resolver (or name-binding pass) walks the program once, maintains the current scope, and for every use of a name does three things: finds the declaration, records the connection, and reports problems. It runs after parsing and before type checking. Real resolvers walk an abstract syntax tree; to keep this example short, our toy language is read line by line, where a line such as let b = a + 2 is a declaration with an initializer, and a line with { or } opens and closes a block.

Python A resolver that links uses to declarations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the output against the program. On line 4 a new a shadows the first. On line 5 a + b finds the inner a (0 scopes up, declared on line 4) and the b of line 2 (1 scope up). After the block closes on line 7, print a on line 8 sees the original a from line 1 again, which shows shadowing being undone.

The problems are caught in a single pass: c is used in its own initializer (line 6), d was never declared (line 9), and line 10 declares a twice in the same scope. The final warnings come from the used flags in the table, so unused-variable warnings cost almost nothing once a table exists. Because the resolver does not stop at the first error, a user sees all name problems at once, as discussed in error recovery.

The resolver also produced a very useful by-product: for each use, the number of scopes to walk up (hops). Compilers store such a number on the AST node, which turns a name lookup into a direct address calculation later on.

Storing more than names

A table entry for a variable usually also records where it will live. The next example attaches a type and a frame offset to each variable, which code generation will use when it needs the address. Functions store their return type, and could also store a parameter list.

Python Symbol table entries with types and frame offsets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The offsets here are packed with no gaps. Real compilers add alignment padding: a 4-byte int after a 1-byte bool normally starts at a multiple of 4, so the frame is larger than the sum of the sizes. The principle is the same, and you will see frames again in runtime environments.

Design choices worth knowing

Question Common options
How is scope decided? Lexical (by source structure, nearly all modern languages) or dynamic (by call chain; old Lisps, shell variables)
What opens a scope? blocks, functions, classes, modules, for headers
Can a name be redeclared? not in the same scope; shadowing in inner scopes is usually allowed
When is a function name visible? everywhere in the file (two passes), or only after its declaration
Different kinds of names one namespace for everything (Python), or separate ones for types, variables and labels (C)
Closures an inner function keeps a link to its defining scope after the outer one ends

The last row has a big consequence: a closure can use a variable from a scope that has already finished, so such variables cannot live in a simple stack frame. This is the topic of the closures section in runtime environments.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a compiler do when a name is not found in the innermost scope?

    Lookup follows the parent links from the innermost scope outward. Only when the global scope also lacks the name is it reported as undeclared.
  2. 2. An inner block declares x, and an outer scope also has x. What happens inside the block?

    Shadowing hides the outer name only while the inner scope is active; the outer variable is untouched and visible again afterwards.
  3. 3. Why does the resolver mark a name 'declared but not defined' while resolving its initializer?

    If the initializer mentions the name while it is in the declared-but-not-defined state, the resolver knows the variable is being read before it has a value.
  4. 4. What is lexical (static) scoping?

    With lexical scoping, the visible declarations depend only on where the code is written, so a compiler can resolve names before the program runs.
  5. 5. Which extra piece of information does a symbol table commonly store for a local variable, besides its name?

    Type checking and code generation need the variable's type and storage location, so they are stored in or linked to the table entry.

Summary

  • A symbol table maps names to information (kind, type, storage, declaration line) and is queried by almost every later phase.
  • Lexical scopes nest; each scope has a parent link, and lookup walks outward from the innermost scope.
  • An inner declaration shadows an outer one and is undone when the block ends; redeclaring a name in the same scope is an error.
  • Rules such as "no use in its own initializer" and forward-reference handling are language design decisions that the resolver enforces.
  • A resolver pass links every use to its declaration, can record how many scopes up it is, and reports undeclared names, redeclarations and unused variables in one sweep.
  • Entries can carry types and frame offsets, which prepare the ground for type checking and code generation.

Next: Type Checking