Eli   Documents Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads

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


Scopes Being Properties of Objects

Language constructs like modules, classes, or record types have a body that is a range. The set of bindings for the components defined in that range constitutes its scope. In an applied context of a module, class, or record identifier its components may be selected, e.g. in m.k, where m is a module identifier and k is one of its components. These constructs are also called qualified names in some language descriptions. In order to bind such applied occurrences of component identifiers in contexts outside their defining range, the scope of the range is associated as a property to the key of the module, class, or record identifier.

This specific task of consistent renaming for component identifiers is often closely related to type analysis. If v in v.k is a variable that has a record type, then that type key has the scope of the record range associated as a property (see Type Analysis of Type analysis tasks).

The following four modules extend the basic scope rule modules (see Basic Scope Rules) by facilities that support scope properties. How to select one of the modules is explained below.

ScopeProp
Scope Properties without left-to-right Restrictions (recommended)
CScopeProp
Scope Properties C-like (recommended only with CInh)
BuScopeProp
Scope Properties C-like analyzed while processing input

The design of scope rules and their description needs careful consideration if the concept of scopes being properties is involved. We have to answer some questions on the described language before we can decide which of the library modules is to be used:

It is easily decided that we need the facility of scope properties: Assume the language has named program objects, say modules, which consist of a range with definitions of components or members. Those members are accessible outside their defining range wherever the name of the module is accessible:

  module m
    { int i;
      float f (); {...}
    }
  m:f();
In this example the module body is a range where the members i and f are defined. The scope of the range contains bindings for i and f. It is a property of the module m which is set in the module definition. The construct m:f is a qualified name: A binding for f is to be found in the scope property of the qualifying module name m. The definitions valid in the context of the qualified name are irrelevant for the binding of f.

The same application pattern occurs for example with types that have components, like record types, structure types, and union types. There a component selection is usually qualified with an expression having such a type rather than with the type identifier itself.

It is recommended to use the ScopeProp module for the specification of such scope patterns. It fits to any of the basic scope rule modules, Alg-like, C-like, or bottom-up. It does not impose any ordering restriction that would require the definition of a member to occur before its qualified use. For example in a language with C-like basic scope rules the following sequence would be acceptable:

  module m;
  m:f();
  module m
    { int i;
      float f (); {...}
    }
Even if it should be considered erroneous to use the qualified name f before its definition, it is recommended to specify the binding in the described way, and to enforce that restriction by a check of the related positions. The same holds for bottom-up basic scope rules. One only has to be aware that the binding of qualified names is determined after the bottom-up computations.

There are a few specific reasons where the modules CScopeProp or BuScopeProp, the C-like variants of ScopeProp are to be used instead:

If the basic scope rules are specified C-like using BuScope and the binding of qualified names has to be done by bottom-up computations, then BuScopeProp is to be used.

If the basic scope rules are specified C-like using CScope and the CInh module is used to implement the concept of inheritance, then CScopeProp is to be used. That is always necessary when bindings of scope properties are needed to solve the binding of non-qualified names in ranges where C-like scope rules apply. As a consequence it is enforced that the definitions of such members precede their uses.

The general description of this set of module is given in the section see Scope Properties without left-to-right Restrictions, the deviations of its variants are described in see Scope Properties C-like, and see Scope Properties C-like Bottom-Up.

Scope Properties without left-to-right Restrictions

This module ScopeProp implements consistent renaming of identifiers using scopes which are properties associated to object keys. The module computations ensure that scope properties are associated and bindings are made before they are accessed. This strategy fits to Algol-like scope rules, and to C-like scope rules if qualified names may be used before their definition.

The module is instantiated by

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

It is required that a basic scope rule module is instantiated with the same generic parameters +instance=NAME and +referto=KEY.

Each of the modules introduces a PDL property named NAMEScope where NAME is the value of the instance parameter.

The module provide .lido specifications for the computational roles NAMEExportRange, NAMEQualIdUse, and NAMEChkQualIdUse:

NAMEExportRange is a NAMERangeScope the scope of which is associated as a value of the NAMEScope property to the value of the attribute KEYScopeKey. All local definitions are bound in this scope. The scope may be used to bind qualified names (NAMEQualIdUse), or to provide the source for inheritance. Such uses may occur outside as well as inside of that NAMEExportRange. A user computation is required to set the attribute THIS.KEYScopeKey. The scope will be set as a value of its property NAMEScope. This role is typically inherited by a grammar symbol that represents the body of a module, of a class, or of a record type. The KEYScopeKey attribute is then set to the key representing the module, class, or record type.

NAMEQualIdUse is inherited by an applied occurrence of a qualified identifier. Its binding is looked up in a scope that is obtained as a NAMEScope property from the attribute THIS.NAMEScopeKey. A computation of INH.NAMEScopeKey has to be provided. The obtained scope is available in the attribute THIS.NAMEScope, e.g. to support a check whether the qualification is correct. Alternatively, a user computation may compute THIS.NAMEScope instead of THIS.NAMEScopeKey. This role is typically inherited by a grammar symbol that represents a qualified identifier occurrence like sleep in Thread.sleep or push in st.push. The binding may be looked up in a scope associated to Thread or to the type of st, for example.

NAMEChkQualIdUse can be inherited together with NAMEQualIdUse. It causes a message to be given, if no binding is found for the identifier.

Computations of these modules also establish attributes NAMEGotVisibleScopePropNest, NAMEGotVisibleKeys, and NAMEGotVisibleKeysNest of including NAMERangeScopes and NAMERootScope. They are used in modules computations which access the NAMEScope property or which look up bindings in those scopes. In general these attributes need not be considered in in user computations.

We demonstrate the use of these facilities by extending the language of our running example by module declarations and access of module components. (For a complete example see the Tutorial on Name Analysis.) The notation is specified by the following two concrete productions:

   Declaration:    'module' DefIdent ModBlock ';'.
   ModBlock:       Compound.
   Operand:        ModUseIdent '::' QualIdent.
   ModUseIdent:    Ident.
   QualIdent:      Ident.

The symbols inherit the roles provided by the scope property module as described above:

   SYMBOL ModBlock INHERITS ExportRange END;

   RULE: Declaration ::= 'module' DefIdent ModBlock ';' COMPUTE
         ModBlock.ScopeKey = DefIdent.Key;
   END;

In the context of the module declaration it is specified that the scope of the module body is to be associated to the key of the module identifier.

In the context of a selection the scope is specified in which the selected component is to be bound. It is accessed from the key of the module identifier. Module computations establish dependences such that all scope properties are associated before they are accessed here:

   SYMBOL ModUseIdent INHERITS
          IdUseEnv, ChkIdUse, IdentOcc
   END;

   SYMBOL QualIdent   INHERITS
          QualIdUse, ChkQualIdUse, IdentOcc
   END;
   RULE: Expression  ::= ModUseIdent '::' QualIdent COMPUTE
         QualIdent.ScopeKey = ModUseIdent.Key;
   END;

In order to make sure that the it is really a module identifier to which the selection is applied we specify the following check

   RULE: Expression  ::= ModUseIdent '::' QualIdent COMPUTE
     IF (AND (NE (QualIdent.ScopeKey, NoKey),
              EQ (QualIdent.Scope, NoEnv)),
     message (FATAL, CatStrInd ("module identifier required: ",
                                ModUseIdent.Sym), 
              0, COORDREF));
   END;

The message is only issued if the identifier is defined but does not have a scope property.

(The Strings module is used to compose the message text (see String Concatenation of Solutions of common problems).)

Scope Properties C-like

This module implements consistent renaming of identifiers using scopes which are properties associated to object keys. The module computations establish bindings, lookup names, associate scope properties, 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.

It is recommended to use this module only if it is needed as a companion of the module CInh. Otherwise ScopeProp should be used (see Scopes Being Properties of Objects).

The module is instantiated by

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

Using this module requires that the module CScope is instantiated with the same values of the generic parameters.

The module provides a PDL property named NAMEScope and the computational roles NAMEExportRange, NAMEQualIdUse, and NAMEChkQualIdUse as described in see Scope Properties without left-to-right Restrictions.

All computations of this module follow strictly C-like scope rules, i.e. binding of identifier occurrences, association of scope properties, and access of scope properties are done in left-to-right depth-first order.

Calls of GetNAMEScope in a user computation do not need a specific precondition if they depend on a key attribute of a context which is to the right of the context where the property is set. That is usually true for situations where the module role NAMEQualIdUse is used. Only if a particular computation is to depend on the fact that all scope properties of the program are associated, it may depend on INCLUDING NAMERootScope.NAMEGotScopeProp.

Scope Properties C-like Bottom-Up

This module implements consistent renaming of identifiers using scopes which are properties associated to object keys. The module computations ensure that scope properties are associated and accessed 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.

It is recommended to use this module only if qualified identifiers have to be bound in the bottom-up phase, or if the module is needed as a companion of the module BuInh. Otherwise ScopeProp should be used (see Scopes Being Properties of Objects).

The computations provided by this module are executed while reading the input.

The module is instantiated by

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

Using this module requires that the module BuScope is instantiated with the same values of the generic parameters.

The module provides a PDL property named NAMEScope and the computational roles
NAMEIdSetScopeProp, NAMEIdGetScopeProp, and NAMEQualIdUse. A role
NAMERangeScopeProp is NOT provided; NAMERangeScope has to be used instead.

Note: The role names of the module ScopeProp as NAMEExportRange, QualIdUse and ChkQualIdUse do not apply here.

All computations of this module follow strictly C-like scope rules, i.e. binding of identifier occurrences, association of scope properties, and access of scope properties are done in left-to-right depth-first order.

As a consequence of bottom-up computation the value of a key can not be propagated by an upper computation to the range symbol. Hence, if the defining identifier occurrence precedes the range, the scope has to be created by the role NAMECreateNewScope (see C-like Basic Scope Rules Computed Bottom-Up) and associated to the key in the identifier context using the role NAMEIdSetScopeProp.

The role that opens the range scope (NAMEOpenNewScope, see C-like Basic Scope Rules Computed Bottom-Up) may also be associated to that identifier context, avoiding an additional symbol that derives to empty.

The range symbol has the role NAMERangeScope.

The module declaration of our example then reads:

   RULE: Declaration ::= 'module' ModDefIdent Block ';' END;

   SYMBOL ModDefIdent INHERITS
          CreateNewScope, OpenNewScope, IdSetScopeProp,
          IdDefScope, IdentOcc
   COMPUTE
     SYNT.OpenPrecond = SYNT.Key;
   END;

NAMEOpenPrecond is specified to depend on the key attribute to ensure that the identifier is bound in the enclosing environment before the environment of the module range is opened.

In component selections the scope property needs to be propagated from the context that provides it to the selector context. The module role NAMEGetScopeProp accesses the scope from the key specified by KEYScopeKey and assigns it to a variable. It is used at the selector context right of it by the role NAMEQualIdUse.

Hence, in our running example the selection is specified as follows:

   RULE: Expression  ::= ModUseIdent '::' QualIdent END;

   SYMBOL ModUseIdent INHERITS 
          GetScopeProp, IdUseEnv, ChkIdUse, IdentOcc
   COMPUTE
     SYNT.ScopeKey = THIS.Key;
   END;

   SYMBOL QualIdent   INHERITS 
          QualIdUse, ChkIdUse, IdentOcc
   END;

If we had a typed record expression instead of the module identifier to select from, ScopeKey would be set to the type key instead of the module key.


Previous Chapter Next Chapter Table of Contents