Eli   Documents
Eli: Translator Construction Made Easy

General Information

o Eli: Translator Construction Made Easy
o Global Index
o Frequently Asked Questions
o Typical Eli Usage Errors

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

Libraries

o Eli library routines
o Specification Module Library

Translation Tasks

o Lexical analysis specification
o Syntactic Analysis Manual
o Computation in Trees

Tools

o LIGA Control Language
o Debugging Information for LIDO
o Graphical ORder TOol

o FunnelWeb User's Manual

o Pattern-based Text Generator
o Property Definition Language
o Operator Identification Language
o Tree Grammar Specification Language
o Command Line Processing
o COLA Options Reference Manual

o Generating Unparsing Code

o Monitoring a Processor's Execution

Administration

o System Administration Guide
Mail Home

Name analysis according to scope rules

Previous Chapter Next Chapter Table of Contents

Inheritance of Scopes

The basic scope rule concepts are described by hierarchically nested environments which reflect the structure of nested ranges in a program. Using scopes as properties of objects, as described in See Scopes Being Properties of Objects, allows to export a scope with bindings from a range, propagate them by a property, and bind single identifiers that occur outside of the range where the binding is established, e.g. a component identifier that is qualified by a module name.

In this section we further extend that concept such that scope rules for language constructs like with statements of Pascal, use qualifications of Ada, or inheritance of classes as in object-oriented languages can be specified. All these constructs allow that non-qualified identifier occurrences may be bound to definitions contained in surrounding ranges or to definitions of scopes that are inherited by a surrounding range, for example 

  module m { int i; float f() {...} }
  { float g;
    with m
      { int i; g = f();}
  }

The new concept is described by an inheritance relation between scopes that is used when applied identifier occurrences in a range are bound to definitions. In the above example the range of the with-statement inherits the scope of the module m and is embedded in the surrounding range.

Name analysis computations for such constructs rely on several different operations: scopes being created, bindings in a scope being established, scope properties being set, inheritance relations between scopes being established. The propagation of scope properties is not limited to strictly nested structures. Hence, the dependencies between the computations are rather sophisticated. That is why the combination of modules is restricted.

There are three modules that provide computations for the consistent renaming task based on inheritance. They rely on the use of the corresponding modules for basic scope rules and for scope properties:

AlgInh
Inheritance with Algol-like Scope Rules (recommended to be used in general)
CInh
Inheritance with C-like Scope Rules
BuInh
Inheritance computed while processing input

Using one of these modules requires that the corresponding basic scope rule module and a suitable scope property module is instantiated with the same generic parameters +instance=NAME and +referto=KEY.

Each of the three modules implements consistent renaming of identifiers. Identifier occurrences are bound to object keys of type DefTableKey according to the following inheritance rule:

An inheritance relation between scopes is introduced: A scope c1 may inherit the bindings of a scope c2, i.e. a definition of c2 is inherited by c1 unless it is hidden by another definition of the same identifier in c1. A scope may inherit from several scopes (multiple inheritance). The inheritance relation is transitive and must be acyclic.

Together with the nesting of ranges the following general scope rule is applied:

An applied occurrence of an identifier a is bound to a definition of a which is contained in or inherited by the smallest enclosing range.

Definitions contained in a range hide definitions inherited (directly or indirectly) by that range.

Definitions inherited by a range hide definitions of enclosing ranges.

Using multiple inheritance a scope c1 may inherit from a scope c2 and from c3, where c2 also inherits from c3. If both c2 and c3 define an identifier a, then the definition of a in c3 is hidden by that of c2. This holds for c1, too, although there is an inheritance path from c3 to c1 that does not pass c2.

If several definitions of an identifier a are inherited via different unrelated inheritance paths, the applied occurrence is bound to an arbitrary one of them. This module provides a means to detect that situation, in order to issue an error message or to access all those definitions, depending on the requirements of the particular language.

If the computations of this module are used to establish inheritance relations, then the computations of identifier roles, like NAMEIdUseEnv, NAMEIdUseScope, and NAMEQualIdUse are modified such that inheritance relations are considered when bindings are looked up.

The modules provide .lido specifications for the following computational roles:

NAMEInhRange is a range that may inherit scopes exported form other ranges, but does not export its own scope. This role is, for example, applied to with-statements. The role NAMEInheritScope (see below) is used to establish the inheritance relations. No distinction is made whether one or more scopes can be inherited. A user computation for the VOID attribute NAMEInhRange.NAMEGotInh has to be provided in upper or lower computation, such that it states the condition that all those inheritances are done. Usually the attributes NAMEInheritScope.NAMEInheritOk are used for that purpose.

NAMEExportInhRange is both an NAMEExportRange and a NAMEInhRange, i.e. it inherits scopes and exports its own scope. This role is, for example, applied to bodies of class declarations. It is essential to use this role, instead of inheriting both roles, NAMEExportRange and NAMEInhRange, to one grammar symbol; otherwise the dependences provided by the two roles could cause conflicts.

NAMEInheritScope is used to establish one inheritance relation between two scopes: THIS.NAMEInnerScope is stated to inherit from THIS.NAMEOuterScope, both of type Environment. THIS.NAMEInnerScope has to be set by a user computation, either in upper or lower context. Another user computation is required to set THIS.NAMEScopeKey in in upper or lower context. A provided computation obtains the NAMEScope property from it and sets SYNT.NAMEOuterScope. The inheritance relation is established by a call of the function NAMEInheritClass provided by the environment module. The attribute SYNT.NAMEInheritOk is set to 1 iff the inheritance relation is legal, i.e. both scopes exist and belong to the same environment hierarchy, in the outer scope bindings have not been looked up before, and this inheritance does not establish a cyclic inheritance relation.

NAMEChkInherit can be used to issue error messages at a NAMEInheritScope node. If the outer scope does not exist, then the attribute NAMEInheritScope.SrcErr has the value 1 and a message is issued by the computation: 

SYNT.SrcMsg=
  IF(THIS.SrcErr,
    message (ERROR, "Source of inheritance is missing", 0, COORDREF));

If the stated inheritance is invalid, then the attribute NAMEInheritScope.ScpErr has the value 1 and a message is issued by the computation: 

SYNT.InhMsg=
  IF(THIS.InhErr,
    message (ERROR, "Wrong scope inherited", 0, COORDREF));

NAMEChkInhIdUse and NAMEChkInhQuaIdUse are roles to be associated to an applied identifier occurrence. If several definitions of the identifier are inherited on different unrelated inheritance paths, then the attribute NAMEChkInhIdUse.MulErr (or NAMEChkInhQuaIdUse.MulErr) has the value 1 and a message is issued by the computation: 

SYNT.MulMsg=
  IF(THIS.MulErr,
    message (ERROR,
      CatStrInd(
        "Several definitions are inherited for: ",
	IdnOf(THIS.|KEY|Bind)),
      0, COORDREF));

NAMEChkInhIdUse may be used together with NAMEIdUseEnv or NAMEIdUseScope; NAMEChkInhQualIdUse may be used together with NAMEQualIdUse.

We demonstrate the use of inheritance by extending our running example by a with statement for modules (see Scopes Being Properties of Objects). 

   Statement:    'with' WithClause 'do' WithBody.
   WithClause:   ModUseIdent.
   WithBody:     Statement.

The identifier should be bound to a module. The WithBody inherits the module's scope. I.e. the definitions of the module body are valid in the WithBody. They may be hidden by definitions in ranges contained in the WithBody. They may hide definitions in ranges enclosing the with statement. Hence, the WithBody plays the role of a InhRange and its scope is the target of the inheritance relation. (The WithBody does not export its bindings.) The module's scope property is its source: 

   SYMBOL WithBody INHERITS InhRange END;
   SYMBOL WithClause INHERITS InheritScope, ChkInherit END;

   RULE: Statement ::= 'with' WithClause 'do' WithBody COMPUTE
     WithClause.InnerScope = WithBody.Env;
     WithBody.GotInh = WithClause.InheritOk;
   END;

   RULE: WithClause ::= ModUseIdent COMPUTE
     WithClause.ScopeKey = ModUseIdent.Key;
   END;

Note: In this example the WithClause can only be a simple identifier, ModUseIdent. If a typed expression would be allowed there instead, as in Pascal, the scope property would be associated to and obtained from type keys.

Similarly we can extend the language of our running example by classes with multiple inheritance: 

   Declaration:   'class' DefIdent Inheritances ClassBlock ';'.
   ClassBlock:    Compound.
   Inheritances:  Inheritance*.
   Inheritance:   ':' InheritIdent.
   InheritIdent:  Ident.

A declaration of a class exports the bindings of the class body, like the declaration of a module (see Scopes Being Properties of Objects). Additionally other classes may be inherited by a class, i.e. their definitions are valid within the class body, if not hidden by inner definitions. The inherited definitions may hide definitions in ranges the class declaration is contained in. Hence, the scope of the class body is the target of all Inheritances, their sources are given by the scope property associated to the classes identified in the Inheritances. 

   SYMBOL ClassBlock INHERITS ExportRange, InhRange END;

   RULE: Declaration ::= 'class' DefIdent Inheritances ClassBlock ';'
   COMPUTE
     ClassBlock.ScopeKey = DefIdent.Key;
     ClassBlock.GotInh =
        Inheritances CONSTITUENTS InheritIdent.InheritOk;
     Inheritances.InnerScope = ClassBlock.Env;
   END;

   SYMBOL Inheritances:  InnerScope: Environment;

   SYMBOL InheritIdent INHERITS
          InheritScope, ChkInherit, IdUseEnv, ChkIdUse, IdentOcc
   COMPUTE
     SYNT.InnerScope = INCLUDING Inheritances.InnerScope;
     SYNT.Scopekey = THIS.KeyK;
   END;

Note: In this example the inherited classes are determined by an unqualified identifier each, InheritIdent. In case of Algol-like scope rules that can not be extended to qualified identifiers, because of the dependence pattern used by the AlgInh module. It would cause cyclic attribute dependences, in general.

Languages (like C++) allow that different definitions of an identifier may be inherited on different inheritance paths to a range. But in that case such an identifier may not be applied in that range. This restriction is checked by the roles ChkInhIdUse and ChkInhIdUseScopeProp. They have to be associated to applied identifier symbols which are bound in the enclosing environment or in the scope obtained from a property, respectively: 

   SYMBOL UseIdent INHERITS ChkInhIdUse END;
   SYMBOL QualIdent INHERITS ChkInhIdUseScopeProp END;

The error messages can be changed globally by symbol computations overriding the computations of the ...Msg attributes: 

   SYMBOL UseIdent COMPUTE
     SYNT.MulMsg=IF(THIS.MulErr,message (ERROR,
      CatStrInd("Ambiguous symbol: ", IdnOf(THIS.|KEY|Bind)),
      0, COORDREF));
   END;

The above specification also fits to the specification for identifiers that are qualified by a module name given in (see Scopes Being Properties of Objects). If in a construct c::x c is a class, then x is bound to a component defined in c or in a class inherited by c. This is the concept of the scope operator in C++.

These examples are applied in the same way for Algol-like and for C-like scope rules. The differences for bottom-up computation are explained in the description of the BuInh module.

Inheritance with Algol-like Scope Rules

This module implements consistent renaming of identifiers according to inheritance relations. It assumes that the scope rules do not restrict defining and applied occurrences of identifiers by a certain order in the program text, as the C-like scope rules do. The module computation in particular fit to Algol-like scope rules as described in See Inheritance of Scopes.

The module is instantiated by 

   $/Name/AlgInh.gnrc+instance=NAME +referto=KEY :inst

Using this module requires that the modules AlgScope and ScopeProp are instantiated with the same values of the generic parameters.

The module provides .lido specifications for the computational roles NAMEInhRange, NAMEExportInhRange, NAMEInheritScope, NAMEChkInherit, NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp as described in See Inheritance of Scopes.

The dependence pattern used in the computations of this module, as described below, imposes a restriction on the use of the role NAMEInheritScope, that determines an inheritance: In case that the inheritance is established for a NAMEExportInhRange, the corresponding NAMEInheritScope may not depend on a qualified name that is bound using the role NAMEQualIdUse, because the computations then may cause cyclic dependences.

Computations of the module provide attributes NAMEAnyScope.NAMEGotVisibleKeys. They describe that for all NAMEExportRanges visible from this range its keys have been bound, the scope property has been set, and its inheritance relation has been established (if any). Module computations use these attributes as precondition for the lookup of unqualified names. Computations of the module also provide attributes NAMEAnyScope.NAMEGotVisibleKeysNest. They specify that the state described above additionally holds for the visible and their recursively, directly nested NAMEExportRanges. Module computations use these attributes as precondition for the lookup of qualified names. Usually these attributes and their dependence patterns need not be considered by user specifications. Only is cases where unconventional language rules for the export or the inheritance of bindings cause conflicts with these dependence patterns the computations of these attributes may be considered for being overridden.

Inheritance with C-like Scope Rules

This module implements consistent renaming of identifiers according to inheritance relations as described in See Inheritance of Scopes. However, the module computations establish bindings, lookup names, associate scope properties, establish inheritance relations, and lookup qualified names in left-to-right depth-first order. It imposes the strong requirement that a qualified name, for example the f in m.f, may not precede its definition.

The module is instantiated by 

   $/Name/CInh.gnrc+instance=NAME +referto=KEY :inst

Using this module requires that the modules CScope and CScopeProp are instantiated with the same values of the generic parameters.

The use of this module enforces the requirement that for any kind of identifier occurrence strictly hold that the definition precedes its uses.

The module provides .lido specifications for the computational roles NAMEInhRange, NAMEExportInhRange, NAMEInheritScope, NAMEChkInherit, NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp as described in See Inheritance of Scopes.

This module uses a strict left-to-right depth-first dependence pattern for all its attribute computations. The attribute NAMERootScope.NAMEGotInhScopes states that all inheritance relations are established for the whole tree.

C-like Inheritance Bottom-Up

This module implements consistent renaming of identifiers according to inheritance relations based on C-like scope rules. The computations can be executed while input is read.

The module is instantiated by 

   $/Name/BuInh.gnrc+instance=NAME +referto=KEY :inst

Using this module requires that the modules BuScope and BuScopeProp are instantiated with the same values of the generic parameters.

The use of this module enforces the requirement that for any kind of identifier occurrence strictly hold that the definition precedes its uses.

The module provides .lido specifications for the computational roles NAMEInheritScope, NAMEChkInherit NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp as described in See Inheritance of Scopes. No additional range role (as NAMEInhRange or NAMEExportInhRange) is provided by this module. The role NAMERangeScope of the basic scope rule module is to be used for ranges that are affected by inheritance, too.

The role NAMEInheritScope differs from the description in See Inheritance of Scopes:

The target scope for the inheritance relation is assumed to be computed by the role
NAMECreateNewScope in this context or in a preceding context. It is passed via a variable. If NAMECreateNewScope and NAMEInheritScope are used in the same context, a computation SYNT.NAMEInhPrecond = THIS.NAMENewScope; has to be added, in order to guarantee proper use of the variable.

A lower computation of SYNT.NAMEOuterScope is required for this context.

The examples given in See Inheritance of Scopes are modified here to allow for bottom-up computation using this module.

We demonstrate the use of single inheritance by extending our running example by a with statement for modules (see Scopes Being Properties of Objects). 

   Statement:    'with' WithUseIdent 'do' WithBody.
   WithBody:     Statement.

The identifier should be bound to a module. The WithBody inherits the module's scope. I.e. the definitions of the module body are valid in the WithBody. They may be hidden by definitions in ranges contained in the WithBody. They may hide definitions in ranges enclosing the with statement. WithBody plays the role of a RangeScope. In the preceding WithUseIdent context the scope is created and determined to be target of an inheritance relation. The scope property of the module key is stated to be the outer scope of the inheritance relation. 

   RULE: Statement ::= 'with' WithUseIdent 'do' WithBody END;

   SYMBOL WithBody INHERITS RangeScope END;

   SYMBOL WithUseIdent INHERITS
          GetScopeProp, CreateNewScope, InheritScope,
          OpenNewScope, IdUseEnv, ChkIdUse, IdentOcc
   COMPUTE
     SYNT.ScopeKey = SYNT.Key;
     SYNT.OuterScope = SYNT.ScopeProp;
     SYNT.OpenPrecond = SYNT.Key;
   END;

Similarly we can extend the language of our running example by classes with multiple inheritance:

The scope of the class body is created in the context ClassDefIdent, associated a property of the class identifier, and used as a target for the inheritance relations established in all Inheritances. The roles RecentNewScope and OpenNewScope in the newly introduced context BuClass access and open that scope. 

   RULE: Declaration ::= 'class' ClassDefIdent Inheritances
                                 BuClass ClassBlock ';'
   END;

   SYMBOL ClassDefIdent INHERITS
          CreateNewScope, IdSetScopeProp, IdDefScope, IdentOcc
   END;

   SYMBOL BuClass INHERITS RecentNewScope, OpenNewScope END;

In the InheritIdent contexts the scope property of the identifier is accessed and determined to be the outer scope to be inherited to the previously created scope. 

   SYMBOL InheritIdent INHERITS
          GetScopeProp, InheritScope,
          IdUseEnv, ChkIdUse, IdentOcc
   COMPUTE
     SYNT.ScopeKey = SYNT.Key;
     SYNT.OuterScope = SYNT.ScopeProp;

     IF (AND (NOT (THIS.InheritOk), NE (THIS.Key, NoKey)),
     message (FATAL, CatStrInd ("cyclic inheritance: ", THIS.Sym),
              0, COORDREF))
     BOTTOMUP;
   END;

The above specification also fits to the specification for identifiers that are qualified by a module name given in (see Scopes Being Properties of Objects). If in a construct c::x c is a class, then x is bound to a component defined in c or in a class inherited by c. This is the concept of the scope operator in C++.

Previous Chapter Next Chapter Table of Contents