Name analysis according to scope rules



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 bind single identifiers that occur outside of the range
which forms the scope property, 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
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 the scope property 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.
The modules provide .lido specifications for the following
computational roles:
NAMERangeSnglInh
is a range that inherits a single scope. It is obtained from the
NAMEScope property of the attribute THIS.KEYInhKey .
An upper or lower computation for the attribute THIS.KEYInhKey
has to be provided.
The attribute SYNT.NAMEInheritOk is set to 1 iff the
inheritance relation is legal, i.e. non cyclic and both scopes belong to
the same environment hierarchy.
NAMERangeMulInh
is a range that may inherit several scopes using the role
NAMEInheritScope (described below) or the function
InheritClass (provided by the environment module).
An upper or lower computation for the VOID attribute
THIS.NAMEGotInh has to be provided such that it is the postcondition
stating that all those inheritances are done.
NAMEInheritScope
requires that two attributes of type Environment ,
THIS.NAMEOuterScope and THIS.NAMEInnerScope .
are computed by upper or lower computations.
The inheritance relation from THIS.NAMEOuterScope
to THIS.NAMEInnerScope is established, i.e. definitions of
THIS.NAMEOuterScope are to be inherited by
THIS.NAMEInnerScope .
The attribute SYNT.NAMEInheritOk is set to 1 iff the
inheritance relation is legal, i.e. non cyclic and both scopes belong to
the same environment hierarchy.
NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp
are roles to be associated to an applied identifier occurrence.
They issue a message if several definitions of the identifer
are inherited on different unrelated inheritance paths.
NAMEChkInhIdUse may be used together with NAMEIdUseEnv
or NAMEIdUseScope ;
NAMEChkInhIdUseScopeProp may be used together with
NAMEIdUseScopeProp .
The modules provide also attributes
NAMEAnyScope.NAMEGotInhScopes of type VOID .
This is a precondition for any consistent renaming that may be affected
by an inheritance. It has to be stated in any such user's computation
not provided by 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' ModUseIdent '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.
Hence, the WithBody plays the role of a RangeSnglInh
and its scope is the target of the inheritance relation.
The module's scope property is its source:
RULE: Statement ::= 'with' ModUseIdent 'do' WithBody COMPUTE
WithBody.InhKey = ModUseIdent.Key;
END;
SYMBOL WithBody INHERITS RangeSnglInh END;
Note: In this example the with -expression can only be a simple
identifier, ModUseIdent .
In case of Algol-like scope rules special means have to be taken if
the inherited scope property could be obtained from an arbitrary
part of the tree using qualified names, see Inheritance with Algol-like Scope Rules.
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 resembles that 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 innner 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 RangeScopeProp, RangeMulInh END;
RULE: Declaration ::= 'class' DefIdent Inheritances ClassBlock ';'
COMPUTE
ClassBlock.ScopeKey = DefIdent.Key;
ClassBlock.GotInh =
Inheritances CONSTITUENTS InheritIdent.InheritOk;
Inheritances.ToEnv = ClassBlock.Env;
END;
SYMBOL Inheritances: ToEnv: Environment;
SYMBOL InheritIdent INHERITS
InheritScope, IdUseEnv, ChkIdUse, IdentOcc
COMPUTE
SYNT.InnerScope = INCLUDING Inheritances.ToEnv;
SYNT.OuterScope = GetScope (THIS.Key, NoEnv)
<- INCLUDING RootScope.GotScopeProp;
IF (NOT (THIS.InheritOk),
message (ERROR, CatStrInd ("wrong inheritance: ", THIS.Sym),
0, COORDREF));
END;
Note: In this example the inherited classes are determined by a simple
identifier each, InheritIdent .
In case of Algol-like scope rules that can not be generalized, because
the dependency setting of
the computations in our modules prohibit that the
inherited scope property is obtained from an arbitrary
part of the tree using qualified names, see Inheritance with Algol-like Scope Rules.
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 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.
This module implements consistent renaming of identifiers
according to inheritance relations based on 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 AlgScopeProp are instantiated
with the same values of the generic parameters.
The module provides .lido specifications for the
computational roles NAMERangeSnglInh ,
NAMERangeMulInh , NAMEInheritScope ,
NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp
as described in See Inheritance of Scopes.
However, there is an additional restriction for
NAMERangeSnglInh and NAMERangeMulInh : The computation
of the scopes which they inherit may not depend on
NAMERootScope.NAMEGotInhScopes , in particular not on
computations using NAMEIdUseScopeProp for qualified
identifiers. They may be determined by identification of
non-qualified identifiers, as shown in the example in
See Inheritance of Scopes.
An additional role NAMERangeQualInhScope is provided
for cases where the computation of the scopes which are inherited
may depend on NAMERootScope.NAMEGotInhScopes , in particular
on computations using NAMEIdUseScopeProp for qualified
identifiers. However, the scope of this range may not be
used as a property.
The attribute NAMEAnyScope.NAMEGotInhScopes states that
all inheritance relations are established for
this range and for the direct decendant ranges of all its ancestors.
The attribute is used as precondition for the consistent renaming computations,
NAMEIdUseEnv , NAMEIdUseScope .
For binding of qualified identifiers using the role NAMEIdUseScopeProp
the attribute NAMERootScope.NAMEGotInhScopes is stated as precondition,
because named scopes of arbitrary parts of the tree may be involved.
The symbol roles NAMEIdUseEnv and NAMEIdUseScope may be used
to bind names in constructs which
establish inheritance relations for
NAMERangeSnglInh or NAMERangeMulInh .
Additionally NAMEIdUseScopeProp may be used
to bind names in constructs which
establish inheritance relations for
NAMERangeQualInhScope .
The attribute NAMEAnyScope.NAMEGotInhScopes
should be used in the same way as precondition
of user computations, if they may depend on visible
inheritances, and may contribute to determination of an inheritance
relation of a scope that may be used as a scope property.
The attribute NAMEAnyScope.NAMEGotInhNest states that additionally to
NAMEGotInhScopes the inheritances are established for all
ranges that are immediate descendants of this range.
The attribute NAMERootScope.NAMEGotAllInh states that all
inheritance relations are
established in the whole tree. It can be used as a precondition
for computations which may depend on arbitrary inheritances,
but which do NOT contribute to determination of any inheritance
relation.
This module implements consistent renaming of identifiers
according to inheritance relations based on C-like scope rules
as described in See Inheritance of Scopes.
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 NAMERangeSnglInh ,
NAMERangeMulInh , NAMEInheritScope ,
NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp
as described in See Inheritance of Scopes.
The attribute NAMERootScope.NAMEGotInhScopes states that
all inheritance relations are established for the whole tree.
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 NAMERangeSnglInh ,
NAMERangeMulInh , NAMEInheritScope ,
NAMEChkInhIdUse and NAMEChkInhIdUseScopeProp
as described in See Inheritance of Scopes.
No additional range role 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 identifer is accessed and determined to be the outer
scope to be inherited to the prevoiusly 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++.



|