Symbol table

In computer science, a symbol table is a data structure where each identifier or symbol (referring to variables, constants, procedures, functions, etc.) in a program's code is associated with the necessary information for its functioning. This may come in two main forms:

1. With object file and executables, the "code" is machine code, and the "information" is typically the memory address of the entity referred to by the symbol.
2. With language translators such as a compiler or interpreters, the "code" is generally a source code, and the "information" refers to the entry's declaration or appearance in the source. (Interpreters also need a way to find the entry's "value" in the table, often an address pointing to another data structure.)
3. With intermediate code files, the "information" may be intermediate between the two above types.

A symbol table of the second type usually only exists in memory during the translation process. A symbol table of the first type is embedded in the output of the translation, such as in an ABI object file for later use. For example, it might be used when loading a dynamic library, during an interactive debugging session, or as a resource for formatting a diagnostic report during or after execution of a program.

Object files and executables

The minimum information contained in a symbol table used by a machine-code file includes the symbol's name and its location or address. For a compiler targeting a platform with a concept of relocatability, it will also contain relocatability attributes (absolute, relocatable, etc.) and needed relocation information for relocatable symbols. Symbol tables for high-level programming languages may store the symbol's type: string, integer, floating-point, etc., its size, and its dimensions and its bounds. Not all of this information is included in the output file, but may be provided for use in debugging. In many cases, the symbol's cross-reference information is stored with or linked to the symbol table. Most compilers print some or all of this information in symbol table and cross-reference listings at the end of translation.

Machine-code symbol tables are optimized for compactness and is typically a flat array of structs. (Conversion into a "smarter" data structure, if at all needed, can happen in the computer kernel once it loads the file.)

Applications

An object file will contain a symbol table of the identifiers it contains that are externally visible. During the linking of different object files, a linker will identify and resolve these symbol references. Usually all undefined external symbols will be searched for in one or more object libraries. If a module is found that defines that symbol it is linked together with the first object file, and any undefined external identifiers are added to the list of identifiers to be looked up. This process continues until all external references have been resolved. It is an error if one or more remains unresolved at the end of the process.

While reverse engineering an executable, many tools refer to the symbol table to check what addresses have been assigned to global variables and known functions. If the symbol table has been stripped or cleaned out before being converted into an executable, tools will find it harder to determine addresses or understand anything about the program.

Example: C

Consider the following program written in C:

// Declare an external function
extern double bar(double x);

// Define a public function
double foo(int count)
{
    double sum = 0.0;

    // Sum all the values bar(1) to bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

The object file would consist of at least two things: an address of the function foo and a way indicating usage of bar.

Example: SysV ABI

An example of a symbol table can be found in the SysV Application Binary Interface (ABI) specification, which mandates how symbols are to be laid out in a binary file, so that different compilers, linkers and loaders can all consistently find and work with the symbols in a compiled object. This format uses a sorted memory address field, a "symbol type" field, and a symbol identifier (called "Name"). The symbol table may be read through the nm utility.

The symbol types in the SysV ABI (and nm's output) indicate the nature of each entry in the symbol table. Each symbol type is represented by a single character. For example, symbol table entries representing initialized data are denoted by the character "d" and symbol table entries for functions have the symbol type "t" (because executable code is located in the text section of an object file). Additionally, the capitalization of the symbol type indicates the type of linkage: lower-case letters indicate the symbol is local and upper-case indicates external (global) linkage.

By compiling the above code (foo.c) to an object file foo.o using gcc -c foo.c, we can use nm foo.o to examine its symbol table:

                 U bar
0000000000000000 T foo

The above output indicates that "bar" is present as a global undefined symbol (U), awaiting resolution by the linker, and that "foo" is present as a global text symbol (G) at offset 0, which can be verified by objdump -d foo.o:

foo.o:     file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 83 ec 20             sub    $0x20,%rsp
(...)

A more in-depth example is available at nm (Unix) § nm output sample.

Language translators

Language translators have much more leeway in how they implement the symbol table. Numerous data structures are available for implementing tables. Trees, linear lists and self-organizing lists can all be used to implement a symbol table. The symbol table is accessed by most phases of a compiler, beginning with lexical analysis, and continuing through optimization.

A compiler may use one large symbol table for all symbols or use separated, or hierarchical symbol tables for different scopes. For example, in a scoped language such as Algol or PL/I a symbol "p" can be declared separately in several procedures, perhaps with different attributes. The scope of each declaration is the section of the program in which references to "p" resolve to that declaration. Each declaration represents a unique identifier "p". The symbol table must have some means of differentiating references to the different "p"s.

As the semantic analyser and the code generator spend a large proportion of their time looking up entries in the symbol table, these stages have a critical effect on the overall speed of the compiler; the symbol table must be organised in a way such that entries can be found as quickly as possible. A common data structure used to implement symbol tables is the hash table. The time for searching in hash tables is relatively independent of the number of elements stored in the table (constant time), so it is efficient for a large number of elements. It also simplifies the classification of literals in a tabular format by including the classification in the calculation of the hash key.

Example: C compiler

A C compiler that parses the code from the C example above will contain at least the following symbol table entries:

Symbol name	Type	Scope
bar	function, double	extern
x	double	function parameter
foo	function, double	global
count	int	function parameter
sum	double	block local
i	int	for-loop statement

In addition, the symbol table may also contain entries generated by the compiler for intermediate expression values (e.g., the expression that casts the i loop variable into a double, and the return value of the call to function bar()), statement labels, and so forth.

Example: the Python symbol table

The Python programming language includes extensive support for creating and manipulating symbol tables. Properties that can be queried include whether a given symbol is a free variable or a bound variable, whether it is block scope or global scope, whether it is imported, and what namespace it belongs to.

Example: Dynamic symbol tables

Some programming languages allow the symbol table to be manipulated at run-time, so that symbols can be added at any time. Racket is an example of such a language.

Both the LISP and the Scheme programming languages allow arbitrary, generic properties to be associated with each symbol.

The Prolog programming language is essentially a symbol-table manipulation language; symbols are called atoms, and the relationships between symbols can be reasoned over. Similarly, OpenCog provides a dynamic symbol table, called the atomspace, which is used for knowledge representation.

See also

• Debug symbol
• .debug_info

Bibliography

• Copper, Keith D.; Torczon, Linda (18 January 2011). Engineering a Compiler (2 ed.). Houston, Texas: Elsevier, Rice University. doi:10.1016/C2009-0-27982-7. ISBN 978-0-12-088478-0. S2CID 40425497.