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

noitalmost <noitalmost@cox.net> writes:


> 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).


Parsing qualified names is easy enough, so I think you mean how to get
access to a variable in an outer frame.


John mentioned displays, but I think it is easier to use static links.
Displays can be slightly more efficient, though.


Basically, the stack frame for a procedure g has a pointer (the static
link) to the frame of the procedure f in which g is declared. Note that
this is not necessarily the previous frame, as g can be called from a
procedure declared locally in f or g.


In the simplest case, all variable for f are stored in f's frame, so g
can access these by following the static link to get to f's frame and
then using an offset from this to find the variable. If you need to
access a variable from a scope even further out than f, you first follow
the static link to f's frame and then in f's frame find the static link
to its outer scope and so on, until you find the right frame.


Your compile-time symbol table should contain information about the
scope depth and offset of any variable, so you (by comparing to the
current scope depth) can see how many static links you must follow.


If you register-allocate variables, you must make sure that variables
declared in outer scopes are stored at known offsets in the frames of
their procedure at the time the are accessed in inner scopes. This can
be done by using a caller-saves calling convention: At a call, store all
live variables in known offsets in the frame. Note that variables
accessed in inner scopes should be considered live at the call site. If
you use a mixed caller-saves/callee-saves convention, allocate all
variables that are accessed in inner scope in caller-saves registers and
make sure these are stored at fixed offsets in the frame. If using a
pure callee-saves strategy, spill variables that are called from inner
scopes to the frame, so they have a known location.


An alternative is lambda lifting. This transforms the program so all
procedures are global. Any variables from (previously) outer scopes
that are acccessed inside a lifted procedure are now passed as extra
reference parameters to the procedure. So if g is lifted out of f and
accesses f's local variable x, g is given the address of x as an extra
parameter. You need to handle reference parameters like Pascal's VAR
parameters or the address-of (&) operator in C. Basically, any
variable that gets its address taken in either way should be stored in
the frame of its procedure. This can be done by spilling it.
Variables that can not be modified after initialisation can be passed
by value rather than reference.


Torben

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