Editing Symbol table (section)

==Implementation==
Numerous [[data structure]]s are available for implementing tables. Trees, linear lists and [[self-organizing list]]s 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 [[Scope (programming)|scopes]]. For example, in a scoped language such as [[ALGOL|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.

A common data structure used to implement symbol tables is the [[hash table]]. The time for searching in hash tables is independent of the number of elements stored in the table, so it is efficient for a large number of elements. It also simplifies the classification of literals in tabular format by including the classification in calculation of the hash key.{{sfn|Copper|Torczon|2011|p=254}}

As the lexical analyser spends a great proportion of its time looking up the symbol table, this activity has a crucial effect on the overall speed of the compiler. A symbol table must be organised in such a way that entries can be found as quickly as possible. Hash tables are usually used to organise a symbol table, where the keyword or identifier is 'hashed' to produce an array subscript. [[hash collision|Collisions]] are inevitable in a hash table, and a common way of handling them is to store the synonym in the next available free space in the table.