7.4 Internal Structures for Symbol Tables

Once the basic data structure is decided upon, we need to then decide how the names and their attribute are to be stored.

The logical view of a symbol table is a list of names, each with its own list of attributes. Each entry is thus of a variable size since the number of attributes of a name depends on its class. A data structure which allows variable lengthed entries is most space efficient, and usually a symbol "table" is not a single table, but more like a data base or a collection of data structures that work together.

Thus, the symbol table might consist of a string table where the actual characters in the name are stored, a class table where the class of the name is stored, and a name table consisting of pointers to the other two tables for each (different) name in the program.

Example 6 shows a possible symbol structure for a simple declaration. The tables shown here appear to be arrays, but they could be linked lists or some other appropriate data structure.

Here the name table has two pointers, one to A's class (Array). A pointer from the class table points to the attribute table. The attributes there indicate that the array is one-dimensional, with a lower limit of 1 and an upper limit of 100

The second pointer from the name table is to the actual character string, A.

Other attributes might include the block number or embedded procedure level where A is declared.