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

Scope Handling

Gentle
Applications
Concepts
Examples
Handbook
Support
Download

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

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


   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:

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

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

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

UndeclareList(Decls) invokes the predicate Undeclare for each member of Decls.

Undeclare

Undeclare(dcl(Ident, Def, Pos)) resets the meaning of Ident to its old value.

CurObject

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

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

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.

[NEXT] [PREV]