Review Two Papers on Symbol Table Implementation

The papers by Graham/Joy/Roubine and by Cook/LeBlanc discuss some symbol table implementation techniques for languages with explicit scope control. The papers are now somewhat old and they reflect an active period for language design ideas, only some of which have survived. Read these papers in order to determine the key ideas and their application to contemporary implementation. Following are some issues to consider:

• What are the key ideas in each paper?
• Which of the key ideas are motivated by one-pass processing? What can be done instead if multiple passes are used?
• Which ideas are intended for ``non-persistent'' symbol tables? How are they changed if the symbol table structure is retained?
• Which ideas are motivated by saving space? How can the implementation be made easier at the price of more space?
• Which methods can be simplified if more time is allowed? Is the additional time a linear or nonlinear function of program size?
• Which methods are appropriate to object-oriented languages (relate to a particular OO language if you can)?
• In summary, what are the set of techniques that are important today, given what you regard as the typical language features and time/space/persistence requirements? Be sure to state those assumptions.