Symbol Table Structure
1. Requirements
Must support fast lookup/insert, nested scopes, and many entries (thousands). Common structures: hash table + scope stack, linked list of scopes, tree.
2. Hash Table with Scope Chaining (standard)
hash(name) → bucket → list of records
each scope = separate hash table; scopes linked parent → child
lookup: hash in current → if miss, go parent → ... → global
exit scope: discard its table (pop)
- Average O(1) insert/lookup via hashing.
- Handles shadowing naturally (inner entry found first).
3. Record Layout
| name | kind(var/func/type) | type | scope id | offset | size | lineno | extra |
Example:
| x | var | float | 2 | 12 | 4 | 15 | live |
| foo | func | int(int) | 1 | — | — | 3 | params=(a,b), label L_foo |
4. Alternatives
| Structure | Pros / Cons |
|---|---|
| Sorted list | simple, O(n) — only tiny programs |
| Binary tree | O(log n), ordered dump easy |
| Hash + scope stack | best all-round — used in GCC/LLVM frontends |
5. Exam Points
- Draw hash + scope-chain structure — 5-7 marks, very frequent.
- Record fields list — 3 marks, frequent.
- Compare list vs tree vs hash — 3 marks, frequent.