Symbol tables

A symbol table is a data structure which supports the following operations:

   enter(s, i): enter information i for symbol s into the table.
   lookup(s): return the last entered information i for s.
   If s is not in the table, return an error.

Typical symbol tables will support additional operations, but these are the fundamental ones. Here is a typical declaration for a symbol table in C++:

       class Info { ... };
       class Symbol_table {
       public:
           void enter(const char* s, Info* i);
           Info* lookup(const char* s);
           // ...
       };

The set of information for a symbol is modeled by a separate class Info (actually, a pointer to an instance of such a class). The symbols themselves are modeled by character strings. Although this representation of a symbol table is quite common, it is also inefficient, for reasons that will shortly become apparent.