Name Analysis Reference Manual
 
Each instantiation of the ScopeGraphs specification module implements a set
of isomorphic scope graphs
(see Scope graphs).
Because the graphs are isomorphic, they can all be described by a single
set of ranges and the relationships among those ranges.
A range is represented by a a value of type NodeTuplePtr.
NodeTuplePtr has a distinguished value, NoNodeTuple,
that represents no range.
By default, an instantiation of the module implements a singleton scope
graph set; for the implementation of larger sets,
see Isomorphic Scope Graphs.
If different kinds of entities are bound in differently-structured ranges,
then the binding and lookup of those kinds of identifiers must appear in
a specific instantiation of the ScopeGraphs for each range structure.
The module provides three computational roles to establish ranges and
relate them to the abstract syntax tree
(see Representation of ranges).
These roles also define any parent edges.
A separate role is used to define path edges that do not depend on applied
occurrences.
(For path edges whose tips are defined by applied occurrences, see
Worklist search.)
A role is also provided to partition a scope graph in order to deal with
path edges whose tips are defined by type-qualified names
(see Interaction with type analysis).
The *RootScope role is automatically inherited by the root
symbol of the grammar.
It provides the following attributes:
*Env
- is a
NodeTuplePtr-valued attribute representing
a range with the bindings defined at the root of the grammar.
This attribute is set by a module computation that must never be
overridden by the developer.
*ScopeKey
- is a
DefTableKey-valued attribute set by a module computation
to the value NoKey.
This computation must never be overridden by the developer.
*GotEnv
- is a
VOID attribute representing the computation state in which:
all scope graph nodes have been created
all defining occurrences have been bound
all computation states represented by *IdDef.*GotDefKeyProp
- attributes have been reached (see Defining Occurrences).
This attribute is set by a module computation that must never be
overridden by the developer.
Whether or not identifiers are actually bound in *RootScope.*Env
depends on the characteristics of the language and how the developer
chooses to model program structure.
For example, some languages provide built-in identifiers that are said to
be "defined in a fictitious outer block".
Such a situation is best handled by binding those identifiers in
*RootScope.*Env.
See The state of an instantiation, for a discussion of
computation state.
The *RangeScope role should be inherited by any symbol
(other than the root of the grammar) that is the root of a subtree
containing defining occurrences
(see Representation of ranges).
It provides the following attributes:
*Env
- is a
NodeTuplePtr-valued attribute representing the range with
the bindings defined in this range.
This attribute is set by a module computation.
*Parent
- is a
NodeTuplePtr-valued attribute representing the range of the
scope graph node that should be the tip of this node's parent edge
(see Fundamentals of Name Analysis).
This inherited attribute is set by a module computation to the value of
INCLUDING *AnyScope.*Env.
*ScopeKey
- is a
DefTableKey-valued attribute allowing the developer to associate
a program entity with this range.
This inherited attribute is set by a module computation to the value
NoKey, indicating that the range has no associated entity.
If an overriding user computation sets the *ScopeKey attribute to
`key', then we say that the program entity represented by `key'
owns the range.
A module computation then sets the following property of `key':
OwnedNodeTuple
- is a
NodeTuplePtr-valued property representing the value of the
*RangeScope.*Env attribute.
If `e' is the value of a *RangeScope.*Env attribute, then
OwnerKeyOfNodeTuple(`e') yields the value `key'.
The default computation of Parent reflects the normal containment
relation among ranges: nested ranges correspond to nested subtrees of the
abstract syntax tree
(see Representation of ranges).
If no such relationship is defined by the language, the developer
should override the default computation:
CLASS SYMBOL RangeScope COMPUTE INH.Parent=NoNodeTuple; END;
This example overrides the computation in every RangeNode
context.
The computation can also be overridden in a single context:
TREE SYMBOL record_type INHERITS RangeScope COMPUTE
INH.Parent=NoNodeTuple;
END;
or
RULE: new_type ::= record_type COMPUTE
record_type.Parent=NoNodeTuple;
END;
Ranges are often owned by program entities such as types or classes.
Those entities are represented by
definition table keys, and the ownership relation between the range and
the entity is established by assigning the entity's definition table key
to the range's *ScopeKey attribute.
The default computation of *ScopeKey must be overridden in this case.
For example, consider a record type whose characteristics are
established by the TypeDenotation role of the Typing module
(see Type denotations of Type Analysis Reference Manual).
That type denotation owns the scope graph node in which field names are
defined, and the ownership relation must be established:
TREE SYMBOL record_type INHERITS TypeDenotation, RangeScope COMPUTE
INH.ScopeKey=THIS.Type;
END;
There is no need for the entity's definition table key to come from the same
syntactic context as the range; the only requirement is that it be assigned
as the value of the *ScopeKey attribute.
The *ScopeKey attribute is also the mechanism by which we tie
together disjoint subtrees that form a single range:
all of the subtrees in the range must have their *ScopeKey
attributes set to the same value.
Consider the example at the end of Representation of ranges.
The appropriate computations are:
SYMBOL ProcedureIdentifier INHERITS IdDefScope END;
SYMBOL ProcedureHeading INHERITS RangeScope END;
SYMBOL ProcedureBody INHERITS RangeScope END;
RULE ProcedureInterface ::=
'procedure' ProcedureIdentifier ProcedureHeading
COMPUTE
ProcedureHeading.ScopeKey=ProcedureIdentifier.Key;
END;
RULE ProcedureInterface ::=
Type 'procedure' ProcedureIdentifier ProcedureHeading
COMPUTE
ProcedureHeading.ScopeKey=ProcedureIdentifier.Key;
END;
RULE ProcedureImplementation ::=
'implementation' ProcedureIdentifier ProcedureBody
COMPUTE
ProcedureBody.ScopeKey=ProcedureIdentifier.Key;
END;
Notice that the ProcedureIdentifier inherits the IdDefScope
role (see Defining Occurrences).
For a given procedure, the Key attribute will be the same for each
ProcedureIdentifier occurrence, because the two occurrences lie in
the same range (see Representation of ranges).
Therefore the ScopeKey attributes of the interface and
implementation will be identical, placing these two disjoint subtrees in
the same range.
This example illustrates an important point: the value of the
*ScopeKey attribute must be obtained from either a defining
occurrence or from an invocation of NewKey.
Never attempt to obtain a key from an applied occurrence; this would
prevent the system from finding an attribute evaluation order.
The *AnyScope role is automatically inherited by any symbol
inheriting either *RootScope or *RangeScope.
There are many situations in which a computation needs information
about the range in which it is embedded.
Any attribute of the enclosing range can be accessed via an
INCLUDING construct
(see INCLUDING of LIDO -- Reference Manual).
AnyScope can be used in INCLUDING constructs if
RootScope and RangeScope need not be distinguished.
It is possible to define attributes and computations for AnyScope,
but there is a small problem: AnyScope is inherited by the root of
the grammar, which cannot have any inherited attributes.
Therefore no attribute can be explicitly declared INH
in AnyScope, and no INH assignment can be defined in
AnyScope
(see Attributes of LIDO -- Reference Manual).
Env is an example of an attribute that is defined for AnyScope.
It has class SYNT at the root of the grammar,
and class INH at all grammar nodes inheriting RangeScope.
The declaration of this attribute in AnyScope
does not explicitly specify a class;
the computation of its value in RootScope specifies SYNT,
and the computation of its value in RangeScope specifies INH.
When the tip of a path edge does not depend on an applied occurrence,
the *BoundEdge role is appropriate.
(Use *WLCreateEdge when the tip depends on an applied occurrence:
see Applied Occurrences.)
*BoundEdge should be inherited by some convenient symbol in
a context where information about the tip and tail of the path edge
can be obtained.
It provides the following attributes:
*tailEnv
- is a
NodeTuplePtr-valued attribute representing the range that is
the tail of the edge.
This attribute must be set by a developer computation.
*toEnv
- is a
NodeTuplePtr-valued attribute representing the range that is
the tip of the edge.
This attribute must be set by a developer computation.
*label
- is an integer-valued attribute that contains the edge label
(see Fundamentals of Name Analysis).
This synthesized attribute is set by a module computation to 1.
*EdgeKey
- is a
DefTableKey-valued attribute representing the key of the created
edge.
This attribute is set by a module computation.
A module computation sets the following properties of the value of the
EdgeKey attribute:
FromNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*tailEnv attribute.
ToNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*toEnv attribute.
EdgeLabel
- is an integer-valued property holding the value of the
*label
attribute.
The OutSideInDeps role is used to partition the abstract syntax
tree into subtrees, in order to bind type-qualified names of path edge
tips incrementally.
It is automatically inherited by the root symbol, and can also be
inherited by any symbol that inherits the RangeScope role.
OutSideInDeps defines a subgraph @math{W} of the scope graph
@math{G}.
No edge of @math{G} may have its tail in @math{G-W} and its tip in @math{W}
(see Interaction with type analysis).
The OutsideEdge role can be used to create edges that have their
tails at the OutSideInDeps node and their tips in @math{G-W}.
It would be appropriate if several edges are to be created for one
OutSideInDeps node.
OutsideEdge provides the following attributes:
*tailEnv
- is a
NodeTuplePtr-valued attribute representing the range that is
the tail of the edge.
This attribute must be set by a developer computation.
*toEnv
- is a
NodeTuplePtr-valued attribute representing the range that is
the tip of the edge.
This attribute must be set by a developer computation.
*label
- is an integer-valued attribute that contains the edge label
(see Fundamentals of Name Analysis).
This synthesized attribute is set by a module computation to 1.
*EdgeKey
- is a
DefTableKey-valued attribute representing the key of the created
edge.
This attribute is set by a module computation.
A module computation sets the following properties of the value of the
EdgeKey attribute:
FromNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*tailEnv attribute.
ToNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*toEnv attribute.
EdgeLabel
- is an integer-valued property holding the value of the
*label
attribute.
Both the Pascal with statement and the Java anonymous class
illustrate the common case in which there is a single path edge whose tail
is at the OutSideInDeps node and whose tip is in @math{G-W}.
The *OutSideInEdge role can be used for this special case.
The *OutSideInEdge role must be inherited by a symbol that also
inherits the *OutSideInDeps role.
It uses the *Env attribute of the *OutSideInDeps role and
the following two attributes to define the created edge:
*tipEnv
- is a
NodeTuplePtr-valued attribute representing the tip of the
created edge.
This attribute must be set by a developer computation.
*label
- is an integer-valued attribute that contains the edge label.
This synthesized attribute is set by a module computation to 1.
*OutSideInEdge.*Env specifies the tail of the new edge.
|
