[NEXT] [PREV]    HANDBOOK / CASE STUDY / The Compiler /

Scope Handling


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


312  'type' IDENT 
313  'action' DefMeaning(Id: IDENT, Obj: OBJ) 
314  'condition' HasMeaning(Id: IDENT -> Obj: OBJ) 

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;
     x : BOOLEAN;
       x : INTEGER
       x := 1
     x := TRUE
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:

315  'type' DESCR 
316     varobj(INT, TYPE) 
317     varparamobj(INT, TYPE) 
318     valueparamobj(INT, TYPE) 
319     procobj(LABEL, DECLLIST) 

For example, if an item is declared as a variable with offset 3 and BOOLEAN (such as the global x) it gets the descriptor

   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:

320  'type' OBJ 
321     object(DESCR, INT, OBJ) 
322     none 

If a term

   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

      varobj( 3, boolean ),
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

      varobj( 3, integer ),
         varobj( 3, boolean ),
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:


323  'action' DeclareList(Decls: DECLLIST, Location: INT -> Size: INT) 
324     'rule' DeclareList(decllist(D, Ds), Loc -> Size1+Size2) : 
325        Declare(D, Loc -> Size1) DeclareList(Ds,Loc+Size1 -> Size2) 
326     'rule' DeclareList(nil, Loc -> 0) 
327  'action' Declare(Decl: DECL, Location: INT -> Size: INT) 
328     'rule' Declare(dcl(Ident, Def, Pos), Loc -> Size) : 
329        GetCurrentNesting(-> Level) 
330        CurObject(Ident -> Hidden) 
331        CheckNotYetDeclared(Hidden, Level, Pos) 
332        Descriptor(Def, Loc, Pos -> Descr, Size) 
333        DefMeaning(Ident, object(Descr, Level, Hidden)) 
334  'action' UndeclareList(Decls: DECLLIST) 
335     'rule' UndeclareList(decllist(D, Ds)) : 
336        Undeclare(D) UndeclareList(Ds) 
337     'rule' UndeclareList(nil) 
338  'action' Undeclare(Decl: DECL) 
339     'rule' Undeclare(dcl(Ident, Def, Pos)) : 
340        HasMeaning(Ident -> object(Descr, Level, Hidden)) 
341        DefMeaning(Ident, Hidden) 
342  'action' CurObject(Ident: IDENT -> Obj: OBJ) 
343     'rule' CurObject(Ident -> Obj) : HasMeaning(Ident -> Obj) 
344     'rule' CurObject(Ident -> none) 
345  'action' Apply(Ident: IDENT, Pos: POS -> Obj: OBJ) 
346     'rule' Apply(Ident, Pos -> Obj) : HasMeaning(Ident -> Obj) 
347     'rule' Apply(Ident, Pos -> none) : Error("id not declared", Pos) 
348  'action' Descriptor(Def: DEF, Loc: INT, Pos: POS 
349           -> Descr: DESCR, Size: INT) 
350     'rule' Descriptor(variable(T), Loc, Pos 
351            -> varobj(Loc, T), Size) : 
352        CheckType(T, Pos) TypeSize(T -> Size) 
353     'rule' Descriptor(valueparam(T), Loc, Pos 
354            -> valueparamobj(Loc, T), 1) : 
355        CheckType(T, Pos) CheckSimple(T, Pos) 
356     'rule' Descriptor(varparam(T), Loc, Pos 
357            -> varparamobj(Loc, T), 1) : 
358        CheckType(T, Pos) 
359     'rule' Descriptor(proc(Fs, Ds, S), _, _ 
360            -> procobj(Start, Fs), 0) 
361        NewLabel(-> Start) 


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.

The specification

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