Re: Symbol tables and scopes

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
14 Feb 2006 10:16:50 -0500

          From comp.compilers

Related articles
[7 earlier articles]
Re: Symbol tables and scopes gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-06)
Re: Symbol tables and scopes Peter_Flass@Yahoo.com (Peter Flass) (2006-02-07)
Re: Symbol tables and scopes alexc@TheWorld.com (Alex Colvin) (2006-02-11)
Re: Symbol tables and scopes cfc@shell01.TheWorld.com (Chris F Clark) (2006-02-11)
Re: Symbol tables and scopes cbarron413@adelphia.net (Carl Barron) (2006-02-12)
Re: Symbol tables and scopes DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-14)
Re: Symbol tables and scopes DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-14)
Re: Symbol tables and scopes david.thompson1@worldnet.att.net (Dave Thompson) (2006-02-14)
Re: Symbol tables and scopes alexc@TheWorld.com (Alex Colvin) (2006-02-14)
Re: Symbol tables and scopes nathan.moore@cox.net (Nathan Moore) (2006-02-17)
Re: Symbol tables and scopes alexc@TheWorld.com (Alex Colvin) (2006-02-17)
Re: Symbol tables and scopes david@tribble.com (David R Tribble) (2006-02-24)
Re: Symbol tables and scopes david@tribble.com (David R Tribble) (2006-02-24)
[4 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 14 Feb 2006 10:16:50 -0500
Organization: Compilers Central
References: 06-01-101 06-02-027 06-02-045 06-02-056 06-02-063
Keywords: symbols

Alex Colvin wrote:
>
> >> It looks like inefficient to me, when for every currently visible scope
> >> the block id must be compared with the id's of *all* possible blocks?
>
> Figure that a name is declared in very few blocks, but some blocks contain
> very many names. Typically, the outermost scope contains hundreds of
> global names that are never redeclared. I believe this is called the "Big
> Inhale"


ACK.


>
> Under the circumstances, a single hash lookup by name is followed by a
> usually short scan for scope. And the cost of block entry and exit is a
> single stack push/pop and increment.


I don't see your intended implementation. The shortest path, with the
least scopes to explore, goes from the current scope towards the root of
the scope tree. In a search for an match of the scopes on this path, and
the scopes which include a definition of the given symbol, I still miss
an efficient searching strategy. Either you traverse the path, and try
to match every scope with one in the scope list of the symbol, then the
search will terminate on the first match. When you traverse the scope
list, and try to find the scope in the path, you'll have to traverse the
whole list, before you can be sure that you found the *closest* matching
scope with regards to the path.


Your push/pop operations sound like you disregard the existence of
parallel scopes, in a scope tree?


DoDi



Post a followup to this message

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