Symbol Tables and Scope
Push a scope on entry, pop it on exit, and search inward-out. That is all lexical scoping is.
Skip to the animationA symbol table records everything the compiler knows about each name; scoping is implemented as a stack of tables, pushed on entering a block and popped on leaving it.
Not a phase — a structure every phase uses
| Phase | Uses it to |
|---|---|
| Lexical analysis | create an entry for each identifier |
| Parsing | distinguish a type name from a variable, in some languages |
| Semantic analysis | record types; check declaration before use |
| Intermediate code | look up types to decide which operation to emit |
| Code generation | find the storage location or register for a name |
An entry typically holds the name, its kind (variable, function, type), its type, its scope, and eventually its storage offset.
Scope as a stack
- 1Entering a block, function body or parameter list pushes a new empty table.
- 2A declaration inserts into the table currently on top.
- 3A use searches from the top of the stack downward and stops at the first match.
- 4Leaving the block pops its table, and everything declared in it disappears.
Searching top-down and stopping at the first hit is the entire definition of lexical scoping. Shadowing is not a special case in the implementation — it falls out of that one rule.
Two implementations
- A hash table per scope, held in a stack. Insert and lookup within a scope are O(1); resolution is O(depth), which is never large. Simple, and popping a scope is free.
- One hash table, each name mapping to a stack of entries. Declaration pushes, scope exit pops every name declared in that scope. Lookup is O(1) regardless of nesting, at the cost of tracking what to pop.
Both are used in practice. The second wins when scopes nest deeply; the first is easier to get right.
Static versus dynamic scoping
Static (lexical) scoping resolves a name by where it appears in the source, so the compiler can settle it once, before the program runs. Dynamic scoping resolves against the call stack at run time, so the same expression can mean different things depending on the caller.
Almost every modern language chose static scoping, precisely because it can be checked and optimised ahead of time. Dynamic scoping survives in a few places — shell variables, exception handlers, some Lisp dialects — where the late binding is the point.
Advantages and disadvantages
Advantages
- One structure serves every phase, so information gathered early is available late.
- Scoping and shadowing fall out of a stack discipline with no special cases.
- Hash tables make insert and lookup constant time.
Disadvantages
- Deep nesting makes resolution walk more tables, unless the second implementation is used.
- Forward references need a second pass or a fix-up list, since the name is used before it is declared.
- Overloading and namespaces complicate the simple one-name-one-entry picture considerably.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.