/ CASE STUDY
/ The Compiler
We now discuss scope handling, a topic that has to be
treated in most compilers.
While in most cases the translation of a phrase can be constructed from the translation of its constituents, the meaning of identifiers depends on the context.
The Gentle library provides the type IDENT and predicates for defining and querying the meaning of IDENT values.
In order to allow fast access, IDENT values are not merely strings that stand for identifiers, but references into a ``symbol table''. The library module idents provides a procedure string_to_id for converting a string into an IDENT value. This procedure is used in the token description for identifiers.
Given a value Id of type IDENT
DefMeaning(Id, M)associates a meaning M with Id.
GetMeaning(Id -> M)later returns the meaning M associated with Id. GetMeaning is defined as a condition: it signals failure if there was no previous DefMeaning for Id. Thus it can be used to check whether an identifier is undeclared.
Here is the signature of these predicates ( IDENT is an abstract type defined by the library, and OBJ is a user-defined type, discussed below):
These predicates can be used to implement a flat name space, i.e. they can be used directly to deal with languages without nested scopes.
Most languages (including MiniLAX) support nested scopes. These can be implemented on top of the predicates discussed so far.
Consider the program
PROGRAM test; DECLARE x : BOOLEAN; PROCEDURE P; DECLARE x : INTEGER BEGIN x := 1 END BEGIN x := TRUE END.Here the x declared as INTEGER local to procedure P hides the globally declared x of type BOOLEAN.
We want to associate a descriptor with each declared item. For this we introduce the type DESCR:
varobj( 3, boolean )The local x gets the descripror
varobj( 3, integer )In the case of a flat name space we could merely associate the descriptor with an identifier, using the action DefMeaning. In case of nested scopes the situation is sligthly more complex.
In the discussion of translating procedures we already sketched the general strategy:
When we enter a procedure (recall that the program itself is treated as a procedure), we make the items declared there visible. We do this by invoking DeclareList for the formal parameters and the local declarations, thereby hiding possible declarations for items with the same name. When leaving the procedure, the hidden declarations are made visible again. This is done by invoking UndeclareList.
We therefore associate an entry with an identifier, that not only specifies its descriptor but also what is currently hidden by the actual declaration. When we use the identifier we get the actual descriptor. When leaving the procedure, we can return to the old meaning. For this prpose we introduce the type OBJ:
object( Descr, Level, Hidden )is associated with an identifier, this means that the actual descriptor is Descr, that the corresponding declaration was at nesting level Level, and that Hidden was the previous association of the identifier (the Hidden entry forms a list of zero or more associations).
For example, if we access the identifier x at the assignment x := TRUE in the global scope, the association is
object( varobj( 3, boolean ), 1, none )The current descriptor is
varobj( 3, boolean )the nesting level is 1, and there is no hidden item.
If we access x at the assignment x := 1 in the local scope, we get the association
object( varobj( 3, integer ), 2, object( varobj( 3, boolean ), 1, none ) )The current descriptor is
varobj( 3, integer ),the nesting level is 2, and the previous association is defined as hidden.
We use the predicates GetMeaning and HasMeaning define and query these associations.
Note that with this strategy accessing the meaning of identifiers has the same cost as in the case of a flat name space. It is done in constatnt time because the library predicates use a hash table algorithm.
Here are the predicates for scope handling:
DeclareList(List, Loc -> Size) declares the items appearing in the declaration list List, i.e. it makes them visible. The items start at Loc in the stackfame and occupy Size locations.
Declare(dcl(Ident, Def, Pos), Loc -> Size) declares the identfier Ident with definition Def. It determines the current nesting level ( Level), gets the current association of Ident ( Hidden), builds a descriptor ( Descr), and the defines
object(Descr, Level, Hidden)as the the new meaning of Ident.
UndeclareList(Decls) invokes the predicate Undeclare for each member of Decls.
Undeclare(dcl(Ident, Def, Pos)) resets the meaning of Ident to its old value.
CurObj(Ident -> Obj) returns the current object associated with Ident (which is none if there was no previous declaration for Ident.
'rule' CurObject(Ident -> Obj) : HasMeaning(Ident -> Obj) 'rule' CurObject(Ident -> none)relies on the fact the rules are evaluated in the given order. Hence we know in the second rule that HasMeaning was not applicable (failed) for Ident and that we have to return none.
This could also have been written in one rule using a conditional statement.
Apply(Ident, Pos -> Obj) is similar to CurObj(Ident -> Obj) except that it emits an error message if there is no current association for Ident.
Descriptor(Def, Loc, Pos -> Descr, Size), where Def is a definition of an item that should be placed at location Loc and was declared at position Pos, construct a corresponding descriptor Descr. It also computes the size Size of the item. The invocation also checks the definition for semantic constraints.