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


Basic Scope Rules

The consistent renaming task associates to each identifier occurrence a key that uniquely identifies the object named by the identifier. The following modules solve the basic problems of that task.

AlgScope
Algol-like scope rules
CScope
C-like scope rules
BuScope
C-like scope rules analyzed while processing input

Each of the three modules implements consistent renaming of identifiers. Identifier occurrences are bound to object keys of type DefTableKey.

The AlgScope module applies Algol-like scope rules. They are characterized by the following description:

A binding is valid within the whole smallest range containing the definition, except in inner ranges where a binding for the same identifier holds. That means a definition of an a in an inner range hides definitions of a in outer ranges. An identifier may be used before its definition.

Usually, the scope rules of a real language are further elaborated. We call them Algol-like, if the above description is their underlying principle. For example Pascal's scope rules are Algol-like. They additionally require that an identifier is not used before its definition. That restriction can be checked using an instance of the SetFirst module (see Set a Property at the First Object Occurrence of Association of properties to definition).

The CScope module applies C-like scope rules. They are characterized by the following description:

A binding is valid from the definition up to the end of the smallest range containing the definition, except in inner ranges from a definition of the same identifier to the end of that range. That means definitions of a in outer range are hidden by a definition of an a in an inner range from the point of the definition up to the end of the range. It implies that an identifier is not used before its definition.

Usually, the scope rules of a real language are further elaborated. We call them C-like, if the above description is their underlying principle. For example the scope rules of the language C are defined for variable names C-like. But for labels names of jumps they are defined Algol-like.

The BuScope module applies C-like scope rules. Its computations can be executed while the input is read (i.e. while the tree is constructed bottom-up). An application may need this technique if results of the name analysis task influence further reading of input, or results are to be presented to the user while typing the input.

Both Algol-like and C-like scope rules are described by six basic concepts. The modules provide .lido specifications with symbol computations for each concept:

IdDefScope is a symbol representing a defining identifier occurrence that is bound in the scope of the smallest enclosing range.

IdUseEnv is a symbol representing an applied identifier occurrence that is bound in the enclosing environment.

IdUseScope is a symbol representing an applied identifier occurrence that is bound in the scope of the smallest enclosing range.

ChkIdUse is a role that may be inherited by an applied identifier occurrence. If no definition is bound to that identifier, then the attribute ChkIdUse.SymErr has the value 1 and a message is issued by the computation:

SYNT.SymMsg=
  IF(THIS.SymErr,
    message (ERROR, CatStrInd ("Identifier is not defined: ", THIS.Sym),
    0, COORDREF));

RootScope is the root symbol containing all identifier occurrences and all RangeScope. It is automatically inherited by the root of the grammar.

RangeScope is a symbol representing a range for the binding of defining identifier occurrences IdDefScope. It may be nested in RootScope or other ranges.

These computational roles are associated to symbols of the user's grammar to solve the basic consistent renaming task. Make sure that your tree grammar is constructed according to the advices given in Tree Grammar Preconditions. More details about symbol computations and attributes provided by the three modules are given in the description of each module.

Complete executable specifications of our running example for each of the three scope rule variants are available in

   $/Name/Examples/AlgLike.fw
   $/Name/Examples/CLike.fw
   $/Name/Examples/BuCLike.fw

In our running example the roles are used as follows:

   SYMBOL Program      INHERITS RootScope END;
   SYMBOL Block        INHERITS RangeScope END;
   SYMBOL DefIdent     INHERITS IdDefScope END;
   SYMBOL UseIdent     INHERITS IdUseEnv END;
   SYMBOL TypeUseIdent INHERITS IdUseEnv END;
Depending on which of the three modules is instantiated Algol-like or C-like name analysis is performed for this example.

The main result of the task is the computation of the attributes IdDefScope.Key, IdUseEnv.Key, i.e. DefIdent.Key, UseIdent.Key, and TypeUseIdent.Key in our example. They identify the object each identifier is bound to. It may be used in further computations to associate properties to it.

If no binding is found for an applied identifier occurrence the Key attribute has the value NoKey. If that is a violation of language rules an error message can be issued using the role ChkIdUse:

   SYMBOL UseIdent INHERITS ChkIdUse END;

Along with each Key attribute there is an attribute Bind of type Binding, e.g. UseIdent.Bind. Its value characterizes a binding of an identifier idn in the innermost scope of an environment env to a key k. The three values idn, env, and k can be obtained from a Binding using functions defined in Environment Module. If no binding is found for an applied identifier occurrence the Bind attribute has the value NoBinding.

Although both Algol-like and C-like scope rules are defined for nested ranges, the modules may be used for languages that do not have nested ranges, i.e. there is only one single flat range in which definitions are valid. In such a case RootScope is used for that range, and RangeScope is not used.

Another variant of these scope rules arises if a language does not distinguish between defining and applied identifier occurrences: identifiers are defined implicitly by their occurrences. In that case IdDefScope is used for that kind of occurrences, and IdUseEnv is not used. Of course, this concept does not make sense in languages that have ranges: One could not refer to an outer identifier definition from within an inner range.

We extend our running example to show implicit definitions within a flat range. We add a new kind of variables, say control variables to the language. They are implicitly defined by their use in special statements or operands, given by the following concrete productions:

   Statement:      'set' Ident 'to' Expression ';'.
   Operand:        'use' Ident.

These control variable identifiers are bound in a new name space separate from that of the other entities. Hence, we use a second instance of one of the modules. That instance is identified by the generic instance parameter CtrlVar:

   $/Name/AlgScope.gnrc +instance=CtrlVar :inst

There is only one kind of occurrences for these variables, CtrlVarUse, which has the role CtrlVarIdDefScope. The Program symbol has the role CtrlVarRootScope:

   RULE:  Statement  ::= 'set' CtrlVarUse 'to' Expression ';' END;
   RULE:  Expression ::= 'use' CtrlVarUse END;
   SYMBOL CtrlVarUse INHERITS CtrlVarIdDefScope, IdentOcc END;
   SYMBOL Program    INHERITS CtrlVarRootScope END;

Algol-like Basic Scope Rules

This module implements consistent renaming of identifiers. Identifier occurrences are bound to object keys of type DefTableKey according to Algol-like scope rules:

A binding is valid within the whole smallest range containing the definition, except in inner ranges where a binding for the same identifier holds.

Make sure that you have considered the advices given in Basic Scope Rules.

The module is instantiated by

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

Both generic parameters can be omitted in most of the usual applications. The instance parameter is used to distinguish several instances of this module. The scope rules of a language may require that identifiers are bound in different name spaces that do not affect each other. Then for each name space an instance of this or of the other basic scope modules is used. The referto parameter modifies the names of Key attributes and of Bind attributes. It is only used if there is an identifier occurrence in the language that is bound in more than one name space. These bindings are then described by one pair of Key and Bind attribute each.

The module provides computational roles for the symbols NAMERootScope, NAMERangeScope, NAMEAnyScope, NAMEIdDefScope, NAMEIdUseEnv, NAMEIdUseScope, and NAMEChkIdUse to be used in .lido specifications. The computations of the module use functions of the library's environment module.

NAMEIdDefScope is a symbol representing a defining identifier occurrence.

NAMEIdUseEnv is a symbol representing an applied identifier occurrence.

NAMEIdUseScope is a symbol representing an applied identifier occurrence that is bound in the scope of the smallest enclosing range. The outer environment of this range is not considered.

NAMEChkIdUse is a role that may be inherited by an applied identifier occurrence. It issues an error message identifier is not defined: if no definition is bound to that identifier.

NAMERootScope is the root symbol containing all identifier occurrences and all NAMERangeScope. It is automatically inherited by the root of the grammar.

NAMERangeScope is a symbol representing a range for the binding of defining identifier occurrences NAMEIdDefScope. It may be nested in NAMERootScope or in other ranges.

NAMEAnyScope comprises the roles of NAMERootScope and NAMERangeScope. It may be used in constructs like

   INCLUDING NAMEAnyScope.NAMEGotKeys

The main results of using this module are the bindings of identifier occurrences represented by the attributes NAMEIdDefScope.KEYKey and NAMEIdUseEnv.KEYKey. Along with each Key attribute there is an attribute KEYBind of type Binding, e.g. UseIdent.Bind. Its value characterizes a binding of an identifier idn in the innermost scope of an environment env to a key k. The three values idn, env, and k can be obtained from a Binding using functions defined in Environment Module. If no binding is found for an applied identifier occurrence the Bind attribute has the value NoBinding.

Usually both NAMEIdDefScope and NAMEIdUseEnv are used. In specific cases of language rules any combination of NAMEIdDefScope, NAMEIdUseEnv, NAMEIdUseScope may be used.

The attributes NAMEIdDefScope.Sym, NAMEIdUseEnv.Sym, NAMEIdUseScope.Sym must represent the identifier encoding.

NAMERootScope.NAMEEnv is a root environment where all environments of this name space are embedded in. It has the value of a global variable NAMERootEnv that is assigned in the initialization phase of the processor. It allows to introduce predefinitions by initialization code, which then must include the file NAMEAlgScope.h. (see Predefined Identifiers)

NAMERangeScope.NAMEEnv is an inherited attribute for the environment of bindings of this range.

NAMEAnyScope.NAMEGotKeys indicates that all keys defined in this and in all enclosing ranges are defined in NAMEAnyScope.NAMEEnv. NAMEAnyScope.NAMEGotKeys is a precondition for finding a binding using IdUseEnv.

NAMEAnyScope.NAMEGotLocKeys indicates that all keys are defined in this range are in
NAMEAnyScope.NAMEEnv.

C-like Basic Scope Rules

This module implements consistent renaming of identifiers. Identifier occurrences are bound to object keys of type DefTableKey according to C-like scope rules:

A binding is valid from the definition up to the end of the smallest range containing the definition, except in inner ranges from a definition of the same identifier to the end of that range.

Note: The scope rules of the programming language C are defined C-like in most but not in all respects: For example the scopes of names of variables and functions are defined C-like, but those of jump labels are defined Algol-like.

Make sure that you have considered the advices given in Basic Scope Rules.

The module is instantiated by

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

Both generic parameters can be omitted in most of the usual applications. The instance parameter is used to distinguish several instances of this module. The scope rules of a language may require that identifiers are bound in different name spaces that do not affect each other. Then for each name space an instance of this or of the other basic scope modules is used. The referto parameter modifies the names of Key attributes. It is only used if there is an identifier occurrence in the language that is bound in more than one name space. These bindings are then described by one Key attribute each.

The module provides computational roles for the symbols NAMERootScope, NAMERangeScope, NAMEAnyScope, NAMEIdDefScope, NAMEIdUseEnv, NAMEIdUseScope, NAMEChkIdUse, NAMEIdDefUse, NAMEDeclaratorWithId, and NAMEIdInDeclarator to be used in .lido specifications. The computations of the module use functions of the library's environment module.

NAMEIdDefScope is a symbol representing a defining identifier occurrence.

NAMEIdUseEnv is a symbol representing an applied identifier occurrence.

NAMEChkIdUse is a role that may be inherited by an applied identifier occurrence. It issues an error message identifier is not defined: if no definition is bound to that identifier.

NAMEIdUseScope is a symbol representing an applied identifier occurrence that is bound in the scope of the smallest enclosing range. The outer environment of this range is not considered.

NAMEIdDefUse represents a defining identifier occurrence like NAMEIdDefScope if
INH.NAMEDefCond is non-zero, otherwise an applied occurrence like NAMEIdUseEnv. NAMEDefCond is to be computed by an upper computation. There is a default computation provided that sets INH.NAMEDefCond to 1 iff the identifier is not yet bound in the current environment.

The pair of roles NAMEDeclaratorWithId and NAMEIdInDeclarator are used to model the scope concept of declarators as defined in the programming language C: A defining occurrence of an identifier may be part of Declarator, that is a larger construct which determines the type of the defined identifier, for example the definition of the array a in

   int a[a+1];
Here a[a+1] is the Declarator and the first a is its defining occurrence. The scope rules of C state that the scope of the defined identifier begins immediately after the end of the declarator, rather than at the position of the defining occurrence. Hence, the a within the brackets is not bound to the defined array. This rule is only relevant if declarators may contain applied identifier occurrences. To achieve this effect, the role NAMEDeclaratorWithId is to be inherited by a symbol which is the root of the declarator construct, and the role NAMEIdInDeclarator is inherited by the symbol that characterizes defining identifier occurrences within declarators. Make sure that the grammar guarantees a 1:1 relation the nodes of these symbol roles in any declarator tree. The attribute NAMEIdInDeclarator.Sym has to be provided as usual. The symbol roles compute the Sym attribute for NAMEDeclaratorWithId and the KEYKey attribute for both symbols.

NAMERootScope is the root symbol containing all identifier occurrences and all NAMERangeScope. It is automatically inherited by the root of the grammar.

NAMERangeScope is a symbol representing a range for the binding of defining identifier occurrences NAMEIdDefScope. It may be nested in NAMERootScope or other ranges.

NAMEAnyScope comprises the roles of NAMERootScope and NAMERangeScope. It may be used in constructs like

   INCLUDING NAMEAnyScope.NAMEEnv

The main results of using this module are the bindings of identifier occurrences represented by the attributes NAMEIdDefScope.KEYKey and NAMEIdUseEnv.KEYKey.

Along with each Key attribute there is an attribute Bind of type Binding, e.g. UseIdent.Bind. Its value characterizes a binding of an identifier idn in the innermost scope of an environment env to a key k. The three values idn, env, and k can be obtained from a Binding using macros defined in Environment Module. If no binding is found for an applied identifier occurrence the Bind attribute has the value NoBinding.

Usually both NAMEIdDefScope and NAMEIdUseEnv are used. In specific cases of language rules any combination of NAMEIdDefScope, NAMEIdUseEnv, NAMEIdUseScope, NAMEIdDefUse may be used.

The attributes NAMEIdDefScope.Sym, NAMEIdUseEnv.Sym, NAMEIdUseScope.Sym,
NAMEIdDefUse.Sym must represent the identifier encoding.

NAMERootScope.NAMEEnv is a root environment where all environments of this name space are embedded in.

It has the value of a global variable NAMERootEnv that is assigned in the initialization phase of the processor. It allows to introduce predefinitions by initialization code, which then must include the file NAMECScope.h. (see Predefined Identifiers)

NAMERangeScope.NAMEEnv is an inherited attribute for the environment of bindings of this range.

NAMEAnyScope.NAMEGotKeys indicates that all identifier occurrences from the begin of the NAMERootScope up to the end of this range are bound to keys in NAMEAnyScope.NAMEEnv.

C-like Basic Scope Rules Computed Bottom-Up

This module implements consistent renaming of identifiers. The computations of this module are specified such that they are executed while the input program is read. Identifier occurrences are bound to object keys of type DefTableKey according to C-like scope rules.

Make sure that you have considered the advices given in Basic Scope Rules.

The module is instantiated by

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

The functionality provided by this modules is almost the same as that of the CScope module (see C-like Basic Scope Rules). Only the differences are described here.

During the bottom-up computation phase values can not be propagated using inherited (INH) attributes; and computations that affect a whole subtree, like creation of the scope for a range, have to be associated to a symbol node that precedes that subtree. For that purpose this module provides additional computational roles that cooperate with the usual basic name analysis roles.

Usually it is necessary to introduce additional symbols into the concrete grammar preceding range subtrees. They derive to nothing, and are used to carry the specific bottom-up computations.

In our running example we would replace the productions

   Source:         Block.
   Statement:      Block.
by the productions
   Source:         BuBlock Block.
   Statement:      BuBlock Block.
and add
   SYMBOL BuBlock INHERITS CreateNewScope, OpenNewScope END;
to the LIDO specification. All other module roles can be used as described for C-like scope rules.

Usually each symbol representing a NAMERangeScope has to be preceded by a symbol that inherits both roles NAMECreateNewScope and NAMEOpenNewScope.

If scopes are used as properties of objects it may be necessary to inherit the roles NAMECreateNewScope, NAMERecentNewScope, and NAMEOpenNewScope to different symbols which precede a symbol representing a NAMERangeScope. (see Scope Properties C-like Bottom-Up, see C-like Inheritance Bottom-Up)

NAMECreateNewScope creates a new scope that is embedded in the scope of the smallest enclosing range. That scope can be obtained from the attribute SYNT.NAMENewScope, or be accessed by a subsequent role NAMERecentNewScope (see below).

NAMEOpenNewScope makes the scope obtained from SYNT.NAMENewScope become the current scope. The attribute SYNT.NAMEOpenPrecond can be used to specify a precondition for this operation. If NAMEOpenNewScope is inherited by a symbol representing an identifier occurrence SYNT.NAMEOpenPrecond = THIS.KEYKey ensures that the identifier is bound before the new scope is opened.

NAMERecentNewScope accesses the most recently created new scope and provides it by the attribute SYNT.NAMENewScope. This role is used together with NAMEOpenNewScope if
NAMECreateNewScope is inherited by a preceding symbol.

We demonstrate the use of these roles for our running example. The grammar introduced in See Running Example of Introduction of specification modules, has to be modified in order to allow bottom-up computation. A new symbol BuBlock is introduced. It derives to nothing and precedes the symbol Block on right-hand sides of productions:

  Source:         BuBlock Block.
  Statement:      BuBlock Block.

The roles CreateNewScope and OpenNewScope introduce the scope for the subsequent Block:

  SYMBOL Program  INHERITS RootScope END;
  SYMBOL Block    INHERITS RangeScope END;
  SYMBOL BuBlock  INHERITS CreateNewScope, OpenNewScope END;

The other roles for basic scope rules are used as described in See C-like Basic Scope Rules.


Previous Chapter Next Chapter Table of Contents