Symbol Table in Compiler Design: Short Notes (Comprehensive Course Section)

A symbol table is the central repository used by a compiler during semantic analysis to keep track of identifiers (e.g., variables, functions, user-defined types) and their attributes (e.g., type, scope level, memory location). In effect, it answers questions like: “What does this identifier refer to?”, “Where is it declared?”, and “What type information is available for type checking?”

In a typical compiler pipeline, the symbol table is built/updated as declarations are encountered, and later queried during semantic checks and code generation. The table supports scope rules by storing bindings for nested blocks or modules, often using a structure that mirrors entering/leaving scopes.

A common way to visualize the relationships is:

Core Concepts: What “Symbol Table” Means

A symbol table stores bindings from an identifier name to information required by later compiler phases. The “information” is usually represented as a record/entry containing some combination of:

• identifier: the key (name of variable/function/type)
• scope level: where it’s valid
• kind/category: what it is
• type information: e.g., int, float, function signature
• storage information: e.g., stack offset or intermediate location
• parameter signature: for functions
• linking/overload info: for languages that support overloading

Symbol tables are not only for variables; they are also used to manage function names, parameters, and user-defined types (structs/classes/enums).

Symbol Table Operations (What You Do With It)

The essential operations are:

• insert: used when declarations are found
• lookup: used when identifiers appear in expressions/statements
• beginScope: triggered by entering a block
• endScope: triggered by exiting a block
• update: e.g., after parsing a full function signature

Visual workflow: scope-aware lookup

Common Data Structures for Symbol Tables

A symbol table is often implemented to support fast operations.

1) Hash table per scope (typical)

• Maintain a stack of scopes.
• Each scope is represented by a hash table mapping identifier names to entries.
• Lookup checks the top scope first, then outer scopes.

2) Balanced tree per scope

• Use a balanced search tree keyed by identifier.
• Useful when ordered traversal is needed (less common in basic compiler designs).

3) Linked structure (scope chain)

• Each scope has a pointer to its parent/outer scope.
• Lookup traverses this chain until the identifier is found.

The key requirement is scope correctness: the “nearest” declaration in the scope nesting hierarchy should be used.

Symbol Table in Semantic Analysis, Type Checking, and Code Generation

Semantic analysis: name resolution

When the parser produces an AST, the semantic phase walks it and uses the symbol table to resolve identifiers. Typical checks include:

• undeclared identifier
• redeclared identifier
• wrong kind

Type checking: using type attributes

For an expression involving identifiers, semantic analysis retrieves the corresponding entry’s type. Examples of where types are needed:

• assignment compatibility
• arithmetic operator operand types
• function call argument matching (signature checking)

Code generation: addresses and layouts

Many compilers store codegen-related attributes in the symbol table:

• local variable offsets in an activation record
• global variable addresses
• function entry points and parameter locations
  This reduces the need for later re-analysis.

Short Notes Template (Exam-Friendly)

You can adapt this exact structure:

1. Definition
   A symbol table stores mappings from identifiers to their attributes (type, scope, kind, storage info) for use in semantic analysis and code generation.

2. Need / Purpose
   It supports scope rules, enabling correct lookup of declarations for identifier uses.

3. Typical Operations
   Insert declarations into the current scope; on lookup, search current scope then outer scopes; pop scope when leaving a block.

4. Implementation
   Common approach: stack of scopes where each scope is a hash table.

5. Where Used

   • semantic checks (undeclared/redeclared names)
   • type checking (using type info from entries)
   • code generation (using storage/address/offset info)