Symbol Tables in Compilers: Structure, Scope, and Semantic Analysis

A symbol table in a compiler records information about program identifiers (e.g., variables, functions, types) so later phases can do name resolution, type checking, and scope management. In most compilers, the symbol table is built during parsing and/or a dedicated analysis pass, and it is updated as the compiler enters and exits scopes.

Conceptually, each entry in a symbol table stores at least:

• the identifier’s name (lexeme),
• a link/representation to its declaration,
• semantic attributes such as type, storage location (or an IR handle), and source location.

A standard approach is to organize symbols by scope using a stack of tables: when the compiler enters a new block, it pushes a new scope; when it leaves, it pops the scope so that shadowed names are naturally handled.

This supports semantic analysis because the compiler can “look up” what a name means at a specific program point, then verify that usage is consistent with the declaration.
Important: Symbol tables enable semantic analysis to be mostly local: once you can resolve each identifier to its declaration, many checks (undeclared names, wrong argument counts, type mismatches, misuse of variables vs functions) become straightforward queries against stored attributes.

Key terminology and invariants

• identifier: e.g., x, add.
• scope: e.g., function scope, block scope.
• declaration: e.g., int x;, int f(int a){...}.
• semantic attribute: e.g., type, parameter list, whether initialized.

A good symbol table design preserves these invariants while compiling:

1. Uniqueness per scope: no two declarations of the same name in the same scope (or a well-defined rule for duplicates).
2. Shadowing correctness: inner scopes can redeclare names that temporarily hide outer ones.
3. Fast lookup: lookup at point $p$ should find the nearest (most recent) enclosing declaration.
4. Type consistency availability: type (and other attributes) for each declaration must be stored so semantic rules can query it.
5. Correct lifetime: when a scope ends, its declarations should stop being visible (hence scope stack pop).

Typical structure of a symbol table

A practical symbol table is usually implemented as one of these (often combined):

1. Hash map per scope

   • Each scope owns a dictionary: name -> entry.
   • Lookup: search from innermost to outermost scope.

2. Stack of scopes (linked symbol tables)

   • Maintain currentScope.
   • Each scope has a parent pointer to the next outer scope.
   • Lookup walks parent pointers until it finds the identifier or reaches global scope.

3. Tree/forest for nested scopes

   • Each scope node references child scopes.
   • Useful if you need to re-analyze or traverse for later tooling (e.g., IDE support).

A symbol table entry often includes:

• kind: variable vs function vs type vs parameter
• type: static type information (e.g., int, float, function signature)
• params (for functions): parameter types and count
• offset / address / IR value: backend or intermediate representation linkage
• defined?: distinction between declaration-only vs definition (for languages that have both)
• sourceSpan: file/line/column for error reporting

[CalloutBlock]{type="tip" title="Pro Tip" content="When designing entries, include enough semantic attributes so type checking can be a set of attribute queries—avoid recomputing type by re-parsing the declaration text."}

Mermaid: scope stack and lookup order

This “nearest enclosing declaration” behavior is the key to correct shadowing.

Example: Constructing and maintaining the symbol table

Consider the following toy language with block scopes and type annotations inferred/checked from declarations:

1int x = 1;
2int f(int a) {
3  int y = x + a;
4  {
5    int x = 2;
6    y = y + x;
7  }
8  return y;
9}

Step A: Global scope after processing top-level declarations

At the start:

• current scope = Global

Insert:

• x : int (initialized with 1)
• f : function with parameter list (int a) and return type int (if declared or inferred from body)

Symbol tables (conceptual):

Step B: Enter function scope for f

When compiling f’s body:

• push Function scope for f
• insert function parameter a

Now:

• current scope = f (function scope)

Entries:

Step C: Inside the first inner statement int y = x + a;

At this point:

• x is referenced, so lookup proceeds:
  • Function scope: no x
  • Global scope: finds x
• a is referenced, so lookup:
  • Function scope: finds a

Insert y into the function scope (since y is declared in the function body block, not inside the later nested block):

Semantic analysis examples enabled by symbol table attributes:

• x + a requires both operands to be numeric/compatible → verify both are int.
• y’s type becomes int (from declared type or inferred from initializer).

Step D: Enter the nested block { ... }

Push a new inner block scope:

• current scope = inner block scope

Now parse int x = 2;:

• declare a new x in the inner scope
• this shadows global x within the block

Step E: Inside y = y + x;

Lookups:

• y:
  • inner block scope: not found
  • function scope: found y
• x:
  • inner block scope: found x (shadowing active)

Semantic checks:

• assignment y = ... requires RHS type compatible with LHS type
• RHS y + x must be a valid numeric addition

Because the symbol table resolves names to the correct declarations, semantic analysis uses:

• y (function-scope y)
• x (inner-block x)

Step F: Exit nested block

When leaving { ... }:

• pop inner block scope
• x from inner block no longer exists/visible
• subsequent statements see the outer x again (global or function-scoped, depending on language)

Step G: return y;

Lookup y:

• inner scopes popped, so found in function scope
• verify return type is compatible with int