LIDO - Reference Manual
Remote access constructs are used to relate computations
that belong to distant contexts
in the tree, rather than those of adjacent contexts. The
INCLUDING construct accesses attributes of symbols that are further up
in the tree (i. e. closer to the root). The CONSTITUENT(S) construct
accesses attributes of symbols that are further down in the tree (i. e. closer
to the leaves). The CHAIN construct relates computations in a
left-to-right depth-first order within subtrees.
These constructs may propagate values or simply specify
dependencies between computations.
Remote access constructs are used to abstract from the particular tree structure
between related computations. Computational patterns can be specified
independent of the particular grammar using remote access in
combination with symbol computations and CLASS symbols. Reusable specification
modules are based on that technique.
The INCLUDING -construct accesses an attribute of a symbol that is on the
path towards the tree root. Hence, several computations in a subtree may depend
on an attribute at the subtree root.
Syntax
RemoteAccess ::= 'INCLUDING' RemAttrList
RemAttrList ::= RemAttr | '(' RemAttrs ')'
RemAttrs ::= RemAttr ',' RemAttrs '|' RemAttr
RemAttr ::= SymbName '.' AttrName
Examples
INCLUDING Range.Env
INCLUDING (Block.Scope, Root.Env)
The RemAttrList specifies the set of attributes referred to by the
INCLUDING construct, called the referred set. On evaluation it accesses an
attribute of the first symbol on the
path to the root which is in that set.
An INCLUDING in a rule computation accesses an attribute of a symbol
above the current context, even if the left-hand side symbol is in the
RemAttrList .
An INCLUDING in a symbol computation accesses an attribute of a symbol
above the current one, even if the current one is in the RemAttrList .
An attribute of a CLASS symbol C.a in the RemAttrList contributes
attributes X.a to the referred set for all TREE
symbols X by which C is inherited.
An INCLUDING in a VOID context does not cause a value to be
propagated; it just states a dependency.
Restrictions
The referred set may not be empty, unless the computation which contains it
is not part of or inherited by any rule context.
The tree grammar must guarantee that in every tree there is at least one of the
symbols of the referred set above the context of the INCLUDING .
The referred set must not contain different attributes of the same symbol.
The types of the attributes in the referred set must be equal, unless
INCLUDING is in a VOID context.
The CONSTITUENTS -construct accesses attributes of symbols that are in
the subtree of the current context. Hence, it may depend on several
computations in the subtree. If values are to be propagated they are combined
by user defined functions.
The CONSTITUENT -construct accesses a single attribute instance of a
symbol that is in the subtree of the current context.
Syntax
RemoteAccess ::= [ SymbolRef ] 'CONSTITUENT'
RemAttrList [ ShieldClause ]
| [ SymbolRef ] 'CONSTITUENTS'
RemAttrList [ ShieldClause ] [ WithClause ]
ShieldClause ::= 'SHIELD' SymbNameList
SymbNameList ::= SymbName | '(' SymbNames ')' | '(' ')'
WithClause ::= 'WITH' '(' TypeName ',' CombFctName ','
SingleFctName ',' NullFctName ')'
Examples
CONSTITUENT Declarator.type
Declarations CONSTITUENTS DefIdent.GotType
CONSTITUENTS Range.GotLocKeys SHIELD Range
CONSTITUENTS Stmt.code SHIELD Stmt
WITH (PTGNode, PTGSeq, IDENTICAL, PTGNull)
The RemAttrList specifies the set of attributes referred to
by the CONSTITUENT(S) construct, called the referred set.
On evaluation it accesses all
instances of attributes of that set which are in a certain range of the subtree
of the current context. That range is determined by its root node, which itself
does not belong to the range, and by the set of shield symbols. The tree nodes
below a shield symbol are excluded from that range.
In a rule computation the root of the tree range is the node corresponding to
the left-hand side of the production. The optional SymbolRef may
restrict the root of the tree range to a node corresponding to a symbol of the
right-hand side of the production.
In a (lower or upper) symbol computation the root of the tree range is the node
corresponding to that symbol.
If the optional ShieldClause is given it specifies the set of shielded
symbols. If an empty ShieldClause is given,
no symbols are shielded from the tree range.
If the ShieldClause is omitted then the root symbol of the tree range
(as described above) is shielded from the range.
An attribute of a CLASS symbol C.a in the RemAttrList contributes
attributes X.a to the referred set for all TREE symbols X
to which C is inherited.
A CLASS symbol C in the ShieldClause contributes symbols X
to the set of shielded symbols for all TREE symbols X to which
C is inherited.
A CONSTITUENT(S) in a VOID context simply states a dependency
and does not cause a value to be propagated.
For a CONSTITUENTS that is not in VOID context a
WithClause specifies how the values of the accessed attribute instances
are combined into one value.
The given TypeName specifies the type of the result and of
intermediate values.
The CombFctName specifies a function (or macro) that is
applied to two values of the given type and
yields one value of that type.
The SingleFctName specifies a function (or macro) that is
applied to each accessed attribute instance and yields a value
of the given type.
The NullFctName specifies a function (or macro) that has no
argument and yields an intermediate value. It is called for every node in the
tree range that could have referred attribute instances below it according to the
tree grammar, but for the particular tree it has none. Hence, the result of
this function should be neutral with respect to the combine function.
It is guaranteed that the combine function is applied to
intermediate values
according to a post-order projection of the accessed tree nodes.
It is left
open in which associative order that function combines intermediate
values.
The referred set of a CONSTITUENTS
may be empty if no attributes of the RemAttrList
are reachable in the subtree or if CLASS symbols in the
RemAttrList are not inherited to any TREE symbol.
In that case a VOID CONSTITUENTS is ignored,
and a value CONSTITUENTS results in a call of
the NullFctName .
Restrictions
A SymbolRef must denote a right-hand side symbol of the production. It
must not be specified in symbol computations.
A CONSTITUENTS in a value context must have a WithClause .
For a CONSTITUENT the tree grammar must guarantee that the accessed
attribute instance is uniquely determined for every tree.
The RemAttrs must have the same type if the CONSTITUENT(S) is in
value context.
Chains relate computations in left-to-right depth-first order within certain
subtrees. A chain may propagate values or just specify dependencies in that
order. Only effective computations, that compute a new chain value or a new
post-condition need to be specified. They are automatically linked in the
described order.
The basic idea is captured by the following diagram representing the
way of a chain through the tree context of a rule graphically:
RULE: LhsSym ::= RhsSym1 RhsSym2 END;
| ^
v |
u LhsSym d
/ ^
/ \
/ _____ \
/ | | \
v | v \
d RhsSym1 u d RhsSym2 u
| ^ | ^
| | | |
------------ --------------
The arcs represent the path of the chain through this context,
coming in from the upper context of LhsSym , going through the
two subtrees, and leaving to the upper context.
That chain propagation is established automatically if the chain is not
used in this context.
Usually, some of the three arcs inside the the context may be specified
by explicit computations that
use and define the chain at a certain symbol occurrence.
The u and d in the graphic stand for usable and definable
chain accesses respectively.
Chain accesses are denoted like attribute accesses with a ChainName
instead of an attribute name.
Syntax
ChainSpec ::= 'CHAIN' ChainNames ':' TypeName
Computation ::= 'CHAINSTART' Attribute '=' Expression Terminator
Attribute ::= SymbolRef '.' ChainName
Examples
CHAIN cnt : int
RULE: Block ::= '{' Decls Stmts '}' COMPUTE
CHAINSTART Stmts.cnt = 0;
printf ("Block has %d statements\n", Stmts.cnt);
END;
RULE: Stmt ::= Var '=' Expr ';' COMPUTE
Stmt.cnt = ADD (Stmt.cnt, 1);
END;
CHAIN codeseq: PTGNode;
SYMBOL Block COMPUTE
CHAINSTART HEAD.codeseq = PTGNULL;
SYNT.transl = TAIL.codeseq;
END;
SYMBOL Stmt COMPUTE
THIS.codeseq = PTGSeq (THIS.codeseq, THIS.transl);
END;
A CHAIN specification introduces the name and the type of a chain. Any
attribute notation using a ChainName denotes a chain access.
A chain states a precondition and a postcondition for each symbol node on the
chain. The precondition is set by the upper context of the symbol,
the postcondition by its lower context.
They can be understood as an implicitly introduced pair of attributes, an
inherited one for the precondition and a synthesized one
for the postcondition.
A computation is allocated on the chain if it
depends on the chain and its result contributes to the chain.
Such computations are automatically linked in left-to-right depth-first
order.
A computation is only linked in chain order if it defines the chain and depends
directly or indirectly on it. A computation that only accesses the chain
without defining it is not necessarily executed in chain order.
A computation that defines a chain without directly or indirectly accessing it
breaks the chain, i. e. the execution order of subsequent chain computations is
independent of those prior to this computation.
There may be several instances of a chain that have the same name
and type. Each instance is identified by a context
that contains a CHAINSTART computation for that chain.
Chain references in subtrees of such a CHAINSTART context
belong to that instance, unless they belong to a nested instance
of CHAINSTART context deeper in the tree.
Different instances of a chain are not related to
each other, regardless of whether they are nested or separate.
However, they may be explicitly connected by computations.
The structure of the tree grammar must ensure that there is a
CHAINSTART context above any computation that
refers to the chain.
A CHAINSTART computation defines the initial value of a chain.
The chain is started at the symbol specified as the destination of
the CHAINSTART computation. It must be the leftmost of the
right-hand side symbols which the chain is to be passed through.
HEAD.c may be used for a chain c
to denote the leftmost symbol of the right-hand side, in symbol computations
as well as in rule computations.
A computation may refer to a chain c by one of the following
notations: X.c in rule computations,
THIS.c , SYNT.c , INH.c in symbol computations,
HEAD.c , and TAIL.c in both rule and symbol computations.
The notations X.c and THIS.c have different meanings
depending on their occurrence in a defining position of an attribute
computation or in an applied position within an expression:
In rule computations the following holds:
If X is the left-hand side symbol of the production,
then an applied occurrence X.c denotes
the chain's precondition at X ;
a defining occurrence X.c denotes
the chain's postcondition at X .
If X is a right-hand side symbol of the production,
then a defining occurrence X.c denotes
the chain's precondition at X ;
an applied occurrence X.c denotes
the chain's postcondition at X .
In symbol contexts only lower computations may access or define a chain.
An applied occurrence of THIS.c
denotes the chain's precondition of that symbol;
INH.c may be used instead.
A defining occurrence of THIS.c
denotes the chain's postcondition of that symbol;
SYNT.c may be used instead.
The notation HEAD.c can be used to define the chain's
precondition of the leftmost subtree.
The notation TAIL.c can be used to access the chain's
postcondition of the rightmost subtree.
These notations can be used in symbol computations
and in rule computations. If used in a rule computation that
rule must have at least one subtree.
If HEAD.c , TAIL.c , or CHAINSTART is used in a
symbol computation that is inherited by a rule which has no subtree,
they have the same effect as if there was a subtree which passes
the chain dependency and the chain value, if any, unchanged.
In the following example a chain c is used in symbol computations.
They state that the functions Prefix and Suffix
are called on the chain for every Expression context.
The Prefix call is applied to the incoming chain and
specifies the chain precondition for the leftmost
subtree of Expression .
The Suffix call is applied to the result of the
rightmost subtree and specifies the chain postcondition of
this Expression :
SYMBOL Expression COMPUTE
HEAD.c = Prefix (THIS.c);
THIS.c = Suffix (TAIL.c);
END;
Restrictions
Every ChainName must be different from any attribute name and any
AttrName .
The tree grammar must guarantee that each access of a chain is in a subtree of
a CHAINSTART context for that chain.
Furthermore that subtree may not be to the left of the symbol where
the CHAINSTART initiates the chain.
None of THIS.c , SYNT.c , INH.c , TAIL.c
may be used in upper symbol computations.
HEAD.c must not be used in applied positions.
TAIL.c must not be used in defining positions.
Chains can not be accessed in INCLUDING or
CONSTITUENT(S) constructs.
|