During semantic analysis (scope or type checking), it is necessary to remember declarations (variables, types, functions, etc) so that we can detect inconsistencies and misuses of the identifiers. This identifiers memorization is the task of a symbol table. Note that a symbol table is a compile-time data structure; it's not used during run time.
Formally, a symbol table (also called identifiers table) maps names into declarations (called attributes), such as mapping the variable name x to its type int.
More specifically, a symbol table stores:
- for each "type name", its type definition (eg. for the C type declaration typedef int* mytype, it maps the name mytype to a data structure that represents the type int*).
- for "each variable name", its type. If the variable is an array, it also stores dimension information. It may also store storage class, offset in activation record etc.
- for each "constant name", its type and value.
- for each "function and procedure", its formal parameter list and its output type.
Each formal parameter must have name, type, type of passing (by-reference or by-value), etc. Due to its very efficient search/retrieval algorithm, one convenient data structure for symbol tables is a hash table, that maps names (the hash table keys) to attributs.