Re: Symbol tables and scopes

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

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