Re: How to handle qualified identifiers such as x.y in a Pascal-like language

On Jun 20, 3:43 pm, noitalmost <noitalm...@cox.net> wrote:
> What I don't quite understand is how to parse access to a variable in
> an outer stack frame. And I think this is similar to the problem of
> nested procedures (which I also don't quite know how to handle).


P.x and x have different scopes, which in this case are obviously
nested. There are two separate issues: 1) How to represent different,
potentially nested scopes in a symbol table and 2) what code to
generate. As John says, any compiler text will deal with both.


For 1) perhaps the simplest to implement is a chain of dictionaries.
Every time a scope opens, create a new dictionary, chain it onto the
current one, and start using the new. When a scope closes, throw away
the current dictionary and resume using the next in the chain.


In your sample program's case, there will be a dictionary for
variables of program (P) scope and then one for each function. Always
the P dictionary will be the last in the chain. Nested functions will
each add to this chain, one per nesting level.


Insertions occur for each declaration, always in the current
dictionary. Lookups of plain identifiers check each dictionary in the
chain until the id is found. The number of chain links followed before
finding the id is important. Stay tuned.


When the language allows (as does yours) explicit scope paths, each
dictionary D should also be paired with its identifier id(D) for the
scope that caused it to be created, here function or program name. The
lookup of a qualified id reference then proceeds right-to-left. In
your example to process s.x, work along the dictionary chain looking
for the x. When it's found (in this case immediately) in a given
dictionary D, match id(D) with s. If the path is longer, say P.s.x,
you'd continue along the chain matching dictionary id's with path
elements. If the whole path matches, you've found the right x.
Otherwise keep looking for x's further down the chain.


When generating code, each function call creates an "activation
record" on the stack to hold parameters and local variables. The
simplest way to implement static scopes is with static links. A SL is
just a pointer at the same position in each activation record that
points to the previous activation of the statically enclosing
function. (It's the norm to have SL's point to the same location in
the AR as the frame pointer would.)


It turns out that when you compile a function call, the code that
computes the new AR's static link must dereference the link of the
current AR N times where N>=0 is the number of symbol table links
needed to find the name of the called function during parsing. (N=0
corresponds to the current frame pointer. N=1 is the current AR's SL,
N=2 is contents of current AR's SL, etc.)


Cool or what? In this manner, static links always form a linked list
of ARs with one AR per scope in the static nesting of the currently
running function. So when you generate code for an identifier
reference x, it will again need to dereference the current static link
N times where N>=0 was the number of links needed to find x in the
symbol table.


If you read this rather confusing recipe a few times, it will at some
point click and you'll see the beauty. If you need a picture, consult
the aforementioned compiler or programming languages textbook.


The "display" method John is talking about merely replaces the static
links between ARs with what is effectively an array of pointers to
ARs. Displays can be more efficient than static links, especially when
functions are deeply nested and/or when the compiler is free to put
oft-used display elements in registers, but implementing them
correctly may be trickier, especially if your language allows function
pointers and/or threads.

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