General Information

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

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

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual

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

 Questions, Comments, ....

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 Ordering Restrictions
AlgScopeProp
Scope Properties Algol-like (outdated)
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 consists of a range with definitions of components or members. Those members are accressible 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 component selections are usually qualified with variables 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 Ordering Restrictions, the deviations of its variants are described in see Scope Properties Algol-like, see Scope Properties C-like, and see Scope Properties C-like Bottom-Up.

Scope Properties without Ordering Restrictions

This module ScopeProp implements consistent renaming of identifiers using scopes which are properties associated to object keys. The module computations ensure that all scope properties are associated before any is accessed. This strategy fits to Algol-like and to C-like scope rules.

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 following computational roles:

NAMERangeScopeProp is to be inherited by a symbol representing a range, for example a module body. Its scope is associated as the NAMEScope property to the key THIS.KEYScopeKey. An upper or lower computation of THIS.KEYScopeKey has to be provided, for example the key representing the module. All local definitions are bound in this scope.

NAMEIdUseScopeProp is inherited by an applied ocurrence of a qualified identifier. It is bound in a scope that is obtained as a NAMEScope property from the attribute INH.NAMEScopeKey. A computation of INH.NAMEScopeKey has to be provided in the upper context. The obtained scope is available in the attribute INH.NAMEScope, e.g. to support a check whether the qualification is correct. For compatibility with older versions user computations may access the scope property and set the attribute INH.NAMEScope. In that case a suitable dependency has to be established (see below).

The attribute NAMERootScope.NAMEGotScopeProp represents the condition that the scope properties are associated thoughout the program. It may be used as a precondition for computations that access the NAMEScope property.

We demonstrate the use of these facilities by extending the language of our running example by module declarations and access of module components. 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:

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

   SYMBOL ModBlock INHERITS RangeScopeProp END;

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

In the context of the selection the scope is specified in which the selected component is to be bound. It is accessed from the key of the module identifer. The dependency ensures that all scope properties are associated before accessed here:

   RULE: Expression  ::= ModUseIdent '::' QualIdent COMPUTE
         QualIdent.ScopeKey = ModUseIdent.Key;
   END;

   SYMBOL ModUseIdent INHERITS
          IdUseEnv, ChkIdUse, IdentOcc
   END;

   SYMBOL QualIdent   INHERITS
          IdUseScopeProp, ChkIdUse, IdentOcc
   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 (ModUseIdent.Key, 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 Algol-like

This module AlgScopeProp is outdated; ScopeProp should be used instead. AlgScopeProp will be kept for a while to keep existing specifications valid.

Scope Properties C-like

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 preceed 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
NAMERangeScopeProp and NAMEIdUseScopeProp, as described in see Scope Properties without Ordering Restrictions.

In case of NAMEIdUseScopeProp a user computation has to provide the attribute THIS.NAMEScope (rather than THIS.NAMEScopeKey as described for see Scope Properties without Ordering 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 NAMEIdUseScopeProp 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 preceed 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 NAMEIdUseScopeProp. A role
NAMERangeScopeProp is NOT provided; NAMERangeScope has to be used instead.

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

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