Re: C++ symbol table

jdass@cssc-melb.tansu.com.au (Joydip Dass) writes:
> [desperately seeking symbol table.]


I don't have a complete answer, but I do have a suggestion. There was a
nifty trick proposed by Paul Dietz in STOC '81, and it has been used with
some success by several people that I know (in fact, it has been
rediscovered with some success by several people, and we (= me, Wegman,
Zadeck) used it in a different context to get good time bounds for a sort
of incremental SSA. The "trick" is that instead of posing the problem as


    given location (scope) what symbol table do I use?
    given symbol table, what is the information for symbol "foo"?


you invert it, as in


    given a symbol "foo", what "scope table" do I use?
    given a scope table and a location, what information do I have?


The next part of the trick is to encode the "scopes" appropriately. Dietz
proposed to do this (I'm working from memory, so the errors are probably
mine) by recording the entry and exit numbers for each node in a
depth-first walk of the block-structure of the program (watch out for
Duff's device in C). Each new declaration of a variable V is assoicated
with a block, and to record that declaration you enter the entry and exit
numbers in V's scope table. The exact structure of the scope table is
left as an exercise, but for small numbers of declarations (usual case),
something based on linear search will probably serve well.


So, your lookup algorithm becomes something like:


    use hash table to get a scope table, given an identifier.
    use scope table to get information, given a location.


This has been used in an attribute grammar system (Rodney Farrow of
Declarative Systems) because the symbol tables produced in this way can be
made to appear "applicative", yet are efficient in terms of both time and
space. It also helps in the situation where there may not be a
declaration, because you have handy access to any declarations that there
might be.


For C++, note that your notion of "scopes" may be very fine-grained, and
probably does not correspond one-to-one with curly braces. You'll also
need something to cope with the scopes associated with different types.


I hope this helps.


David Chase
Sun
--

Return to the comp.compilers page.
Search the comp.compilers archives again.