Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #166

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

Show all headers | View raw

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.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-20 15:43 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-06-22 10:57 +0200
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-22 11:47 +0100
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-06-24 18:13 -0400
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-06-29 12:31 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-01 12:46 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-07-02 17:13 +0000
          Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-03 13:14 -0700
            Re: How to handle qualified identifiers such as x.y in a Pascal-like language torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-07-07 10:27 +0200
            Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-07 04:14 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-07-02 16:58 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language Gene <gene.ressler@gmail.com> - 2011-06-22 19:21 -0700
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-24 07:56 +0100
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language Gene <gene.ressler@gmail.com> - 2011-06-24 19:19 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-25 11:55 +0100
          Re: How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-29 13:13 -0400
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language "[Linux Magazine]" <uu3kw29sb7@snkmail.com> - 2011-06-24 13:58 +0200
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-06-25 17:11 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-23 12:43 -0400
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language Tony Finch <dot@dotat.at> - 2011-06-29 18:55 +0100
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-06-29 15:51 -0700

csiph-web