Re: Symbol tables and scopes

Chris F Clark <>
3 Feb 2006 18:38:45 -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)
Re: Symbol tables and scopes (glen herrmannsfeldt) (2006-02-06)
Re: Symbol tables and scopes (Peter Flass) (2006-02-07)
[16 later articles]
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:38:45 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 06-01-101 06-02-015
Keywords: symbols
Posted-Date: 03 Feb 2006 18:38:45 EST

Using one symbol table and making each entry potentially a stack is
actually described in the literature (1978 Compiler Construction
conference in Boulder). I remember this paper because the presenter
was the student of one of the well-known compiler writer teachers and
in the audiance was another well-known compiler writer, who
essentially asked during the QA period following the presentation,
"isn't this obvious?" There was a mildly heated discussion after the
question was asked, which as a younger aspiring compiler writer in the
audiance I found particularly embarrassing, because the answer clearly
was, "Of course, the solution is obvious, but it's also interesting."

I think that the on string/hash table to do look-ups in has a definite
simplicity. I think the tradeoffs as to whether that links directly
into the symbol table and the stack is per entry or whether it gives
back a simple integer key which is then searched for in a stack of
scope records can be made on a developer-by-developer basis. I can
imagine that both would have advantages in certain situations. I also
suspect that picking the wrong one is far from fatal.

I do like the idea of pushing an "imaginary outer illegal" symbol on
the stack before pushing the first one on a per entry chain. It seems
like it would make the popping process, potentially more uniform. If
your symbol hashes to that entry, then the symbol exists somewhere in
the program, but is not visible in your current scope. Seems like
that would be a nice thing to know.

One thing worth noting is that in languages with explicit open scope
(import) statements, the scopes do not necessarily exhibit stack like
behavior. I can easily imagine (and would potentially want to use) a
language which has "search paths" that specify how a name gets
resolved. In that case, finding the string/hash-value is only a small
part of the symbol look-up process. Once you know the hash value, you
need to find out which instance of that symbol is relevant.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

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