Name analysis according to 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;
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.
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.
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.
|
