Symbol tables and scopes

Currently I want to implement an efficient symbol table, for
navigation in some source code. This means that searching the symbol
table(s) should be sufficiently fast, for use in an interactive
application.


In my latest parser I used a single global symbol table, implemented
as a stack with clever hashing. Local symbols are pushed onto the
stack, and are removed again when a scope is closed (LiFo). The hash
function only has to return the last added matching symbol first, so
that the time for the lookup of any symbol is affected only by the
number of symbols with the same hash code.


In an IDE instead a tree of scopes must be used, and a symbol must be
searched in all scopes, from the current (innermost local) scope up to
the global scope in the root of the tree. Any suggestions on the
implementation of such a data structure, or should I stay with my
existing approach, extended by a search through multiple symbol
tables?




And how to implement namespaces?


IMO namespaces have been "invented" to reduce the amount of
concurrently used symbols, what's fine in a sequential parser for
single source modules, but what doesn't help much in a development
environment, where all used namespaces must be accessible at the same
time. A separation of every symbol table into namespaces will increase
the number of tables to search, with little benefits. The ability to
load an namespace on demand will add the time for the disk access to
the search time, what can make such an approach unusable in
interactive applications :-(


DoDi

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