Algorithms for Compiler Design: VARIOUS APPROACHES TO SYMBOL TABLE ORGANIZATION

There are several methods of organizing the symbol table. These methods are discussed below.

1 The Linear List

A linear list of records is the easiest way to implement a symbol table. The new names are added to the table in the order that they arrive. Whenever a new name is to be added to the table, the table is first searched linearly or sequentially to check whether or not the name is already present in the table. If the name is not present, then the record for new name is created and added to the list at a position specified by the available pointer, as shown in the Figure 1.

Figure 1: A new record is added to the linear list of records.

To retrieve the information about the name, the table is searched sequentially, starting from the first record in the table. The average number of comparisons, p, required for search are p = (n + 1)/2 for successful search and p = n for an unsuccessful search, where n is the number of records in symbol table. The advantage of this organization is that it takes less space, and additions to the table are simple. This method's disadvantage is that it has a higher accessing time.

2 Search Trees

A search tree is a more efficient approach to symbol table organization. We add two links, left and right, in each record, and these links point to the record in the search tree. Whenever a name is to be added, first the name is searched in the tree. If it does not exist, then a record for the new name is created and added at the proper position in the search tree. This organization has the property of alphabetical accessibility; that is, all the names accessible from name_i will, by following a left link, precede name₁ in alphabetical order. Similarly, all the name accessible from name_i will follow name_i in alphabetical order by following the right link (see Figure 2). The expected time needed to enter n names and to make m queries is proportional to (m + n) log₂n; so for greater numbers of records (higher n) this method has advantages over linear list organization.

Figure 2: The search tree organization approach to a symbol table.

3 Hash Tables

A hash table is a table of k pointers numbered from zero to k−1 that point to the symbol table and a record within the symbol table. To enter a name into symbol table, we find out the hash value of the name by applying a suitable hash function. The hash function maps the name into an integer between zero and k−1, and using this value as an index in the hash table, we search the list of the symbol table records that is built on that hash index. If the name is not present in that list, we create a record for name and insert it at the head of the list. When retrieving the information associated with the name, the hash value of the name is first obtained, and then the list that was built on this hash value is searched for information about the name (Figure 3).

Figure 3: Hash table method of symbol table organization.