Symbol Tables in Compilers: Uses and Identifier Storage

A symbol table is a core component of the compilation pipeline. Its primary purpose is to let the compiler (1) recognize whether an identifier has been declared, (2) associate the identifier with semantic information such as its type, scope, and storage properties, and (3) support later stages like name resolution and code generation via that recorded metadata 2.

In typical compilers, the semantic analysis phase builds and consults the symbol table to perform tasks such as:

• detecting undeclared or duplicate identifiers,
• ensuring type consistency for operations and assignments,
• tracking where variables live (e.g., stack frame offsets or global addresses),
• handling scope and name binding across nested blocks and functions 2.

A key idea is that the symbol table is not merely a list of names: it stores structured entries (often called “records”) that represent different kinds of identifiers (variables, functions, types, constants) with their relevant attributes.

What the symbol table is used for

Most compiler textbooks describe symbol tables as the mechanism that supports semantic rules by maintaining identifier information. Common concrete uses include:

1. Declaration tracking & duplicate checking
   When a declaration appears, the compiler inserts an entry into the symbol table; when another declaration in the same scope conflicts, it can report an error 2.

2. Name resolution (binding identifier uses to declarations)
   When an identifier is used in an expression, the compiler consults the symbol table—typically respecting scope nesting—to find the nearest applicable declaration 2.

3. Type checking and semantic validation
   Once binding is known, the compiler uses the stored type and other attributes to validate operations (e.g., arithmetic between compatible types) 2.

4. Support for code generation (addresses/storage locations)
   For variables, symbol table entries often include information needed to generate correct memory references later (e.g., stack offset for locals, global addresses) 2.

Key terms to connect the ideas

• identifier
• scope
• binding
• semantic checking

How identifiers are stored in the symbol table

In practice, compilers store identifiers as keys (often strings) mapped to symbol-table entries.

1) The key: the identifier name

At minimum, each entry uses the identifier’s spelling as a key. The compiler can then retrieve stored metadata quickly when the identifier appears later in the program .

Common representation choices:

• Hash table mapping name -> entry for expected $O(1)$ average lookup.
• Balanced tree / ordered map for $O(\log n)$ worst-case lookup.
• Chained scopes implemented as a stack of maps for nested scope lookup 2.

2) Values: structured entry records (attributes)

Symbol-table entries typically contain fields such as:

• kind/category: variable vs function vs type vs constant,
• type information: the type of the identifier,
• scope level / declaring block: where it was declared,
• parameter list & return type for functions,
• storage details for variables (e.g., whether it’s local/global and its address/offset),
• additional semantic attributes (e.g., mutability, constness, array dimensions) 2.

3) Scope-aware storage: separate entries per scope

A crucial implementation detail is that the “same” name can refer to different entities in different scopes. Therefore, compilers usually:

• keep a separate map per scope, and
• on lookup, search from the innermost scope outward until a binding is found 2.

4) Insertion vs lookup rules (typical behavior)

• Insertion: check only the current scope for duplicates; if none found, insert/update the current scope’s map.
• Lookup: search outward across nested scopes to implement lexical scoping.