Re: C symbol table structures

Alex Colvin wrote:
>
> The parser keeps a stack of the currently active scopes. To find an
> identifier's current definition we search its definition list for the
> first (innermost) active definition.
>
> Structures have their own scopes, which are searched to find member
> definitions.
>
> In this scheme, scope entry and exit just increment the scope number
> and adjust the scope number stack. Instead of having a table for each
> scope, we have a list for each identifier. This is sort of like shallow
> binding.
>
> The idea, as I recall, is that C has lots of scopes, but most
> identifiers are defined in only one, typically the global level.
>
> The drawback is that heavily overloaded identifiers have slow lookups,
> potentially scanning past lots of out-of-scope definitions. Even this
> can probably be fixed by discarding them upon redefinition.


You might want to have a look at the following paper:


@Article{Envmod,
    author = "Uwe Kastens and William M. Waite",
    title = "An Abstract Data Type for Name Analysis",
    journal = "Acta Informatica",
    year = 1991,
    volume = 28,
    pages = "539--558"
}


The ADT described in the paper is a bit different from the one you
describe. The big difference is that it keeps an array with a "current"
set of bindings. This is updated every time you enter or leave a scope.
It increases computation at block entry and exit, but reduces the
computation associated with each lookup. The assumption is that you will
do more lookups than block entries and exits.


Basim Kadhim

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