Symbol table

A symbol table is a data structure used by the compiler to store information about every identifier (variables, constants, functions, labels, types, parameters) found in the source program. It is created during lexical/syntax analysis and used by every later phase.

Structure

Each entry is a record, and the table is organized for fast lookup and insertion.

Common organizations:

Implementation	Lookup	Remarks
Unordered linear list	$O(n)$	Simple, only for tiny programs
Ordered list / binary search tree	$O(\log n)$	Slower insertion
Hash table	$O(1)$ average	Most common; collisions resolved by chaining

Handling scope: one table per scope, chained to its enclosing scope (or a single stack-like table). Entering a block creates a new table; leaving it discards that table. Lookup searches the innermost scope first, then outwards.

Operations: insert(name, attributes), lookup(name), delete / exit scope, modify attributes.

Information stored for each identifier

Attribute	Meaning
Name	The lexeme (or an index into a string table)
Kind / category	Variable, constant, function, procedure, parameter, label, type name
Data type	int, float, char, array, struct, pointer, ...
Size	Bytes needed (for arrays: element type and dimensions/bounds)
Scope / nesting level	Block or procedure where the name is visible
Storage location	Address or offset in the activation record (or static address)
For functions	Number, order and types of parameters, return type, parameter-passing mode
For records/classes	Fields, their types and offsets
Line numbers	Declaration and usage lines, for error messages and cross-reference
Other flags	Initialized or not, constant value, access mode

Example: for float rate; declared in main, the entry is
<rate, variable, float, 4 bytes, level 1, offset 8>.

Use by the phases: the scanner inserts names, the parser and semantic analyzer add type and scope information and check for undeclared or redeclared names, type checking reads types, and the code generator reads sizes and offsets.