Symbol tables and scopes

Hans-Peter Diettrich <>
28 Jan 2006 15:17:40 -0500

          From comp.compilers

Related articles
Symbol tables and scopes (Hans-Peter Diettrich) (2006-01-28)
Re: Symbol tables and scopes (David R Tribble) (2006-02-02)
Re: Symbol tables and scopes (Chris F Clark) (2006-02-03)
Re: Symbol tables and scopes (Peter Flass) (2006-02-03)
Re: Symbol tables and scopes (Gabriel Dos Reis) (2006-02-06)
Re: Symbol tables and scopes (Hans-Peter Diettrich) (2006-02-06)
Re: Symbol tables and scopes (Hans-Peter Diettrich) (2006-02-06)
[18 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <>
Newsgroups: comp.compilers
Date: 28 Jan 2006 15:17:40 -0500
Organization: Compilers Central
Keywords: symbols, question
Posted-Date: 28 Jan 2006 15:17:40 EST

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

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

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 :-(


Post a followup to this message

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