C symbol table structures

I've been working on a compiler for C* (a dialect of C).


I'm using a symbol table structure that I think I heard about here
(comp.compilers) long ago. Can anyone tell me if this has a name, or if
i got it right?


Each scope (block) is numbered, in increasing order. Each identifier
has a list of definitions and scope numbers.


The parser keeps a stack of the currently active scopes. To find an
identifier's current definition we search its definition list for the
first (innermost) active definition.


Structures have their own scopes, which are searched to find member
definitions.


In this scheme, scope entry and exit just increment the scope number
and adjust the scope number stack. Instead of having a table for each
scope, we have a list for each identifier. This is sort of like shallow
binding.


The idea, as I recall, is that C has lots of scopes, but most
identifiers are defined in only one, typically the global level.


The drawback is that heavily overloaded identifiers have slow lookups,
potentially scanning past lots of out-of-scope definitions. Even this
can probably be fixed by discarding them upon redefinition.




-- mac the naif
--
Alex Colvin
alex.colvin@dartmouth.edu

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