Abstract data types to be used in specifications
 
Several language implementation tasks are solved using linear lists
constructed of data elements which are computed at certain tree nodes,
e.g. a the list of parameter types that is part of the type of a function.
Such lists reflect a left-to-right depth-first order of the
corresponding tree nodes. Similarly such lists are decomposed in
other contexts, e.g. to check the types of the arguments of a function
call. This module provides .lido specifications for such
patterns of linear list usage. The module uses functions of
the linear list module List. Any assignable C type may be chosen
as type of the list elements.
This module is instantiated by
$/Adt/LidoList.gnrc+instance=TYPE +referto=HDR :inst
where TYPE is the name of the element type and HDR.h
is a file that defines the element type, e.g.
$/Adt/LidoList.gnrc+instance=DefTableKey +referto=deftbl :inst
If the element type is predefined in C the referto parameter
is omitted, e.g.
$/Adt/LidoList.gnrc+instance=int :inst
The module provides two groups of computational roles,
TYPEListRoot, PreTYPEListElem, PostTYPEListElem,
TYPEListElem, for construction of a list from attribute values
at tree nodes, and
TYPEDeListRoot, PreTYPEDeListElem, PostTYPEDeListElem,
TYPEDeListElem for distribution of a list over attributes of tree
nodes. For each of the two cases there is one role that characterizes the
root of the subtree where the list construction or distribution
is applied, and three roles for nodes that are related to list elements.
These three roles affect the order of list elements differently in cases
where the related tree nodes may occur recursively (see below).
For construction of a list
TYPEListRoot is associated to a grammar symbol that contains
all occurrences of the roles for its list elements in its
subtree. If TYPEListRoot occurs recursively in the tree,
its lists are collected separately.
The resulting list of type TYPEList is obtained by the
attribute TYPEListRoot.TYPEList.
A user's computation has to provide the list element values
of type TYPE by attributes named TYPEElem at the
symbols which have one of the three element roles.
One of the three roles should be chosen depending on the
desired order of the elements in cases where the list element
symbol occurs recursively in the tree:
If the role PreTYPEListElem is used the elements are taken
in pre-order;
i.e. the attribute value of a node occurs in the list prior to those
of nodes in its subtrees.
If the role PostTYPEListElem is used the elements are taken
in post-order;
i.e. the attribute value of a node occurs in the list after those
of nodes in its subtrees.
If the role TYPEListElem is used no elements are taken
from subtrees of an element node.
There are situations where not all tree nodes that have the role
TYPEListElem shall contribute an element to the list.
A condition attribute TYPEListElem.TYPETakeIt of type
int can be computed such that it is false (0)
if this tree node shall not contribute to the list.
The value of the attribute TYPEListElem.TYPEElem
is irrelevant in that case.
If the condition attribute TYPEListElem.TYPETakeIt
is true the value of the attribute TYPEListElem.TYPEElem
is taken as an element of the list.
A default computation sets TakeIt to true (1).
It becomes effective if it is not overridden as described above.
TYPEFilterListElem is outdated. Its task should be achieved
using the attribute TYPETakeIt.
TYPEFilterListElem may be used instead of TYPEListElem.
Then the value TYPEFilterListElem.TYPEElem will only be inserted into
the list if a call of the function TYPEFilter yields non-null
when given TYPEFilterListElem.TYPEElem as argument.
The function TYPEFilter has to be defined if the role
TYPEFilterListElem is used.
For decomposition of a list
TYPEDeListRoot is associated to a grammar symbol,
and a computation has to be provided such that the attribute
TYPEDeListRoot.TYPEList gets a list value.
That list value is decomposed such that each
occurrence of grammar symbols having one of the element roles
for decomposition (see below)
get a list element value. The list element values are obtained
by attributes named TYPEElem.
If the list is shorter than the number of the element nodes
in the subtree the attributes of the remaining nodes
get the value NoTYPE.
TYPEDeListRoot.TYPEListTail is the
list of remaining elements which are not associated to
element nodes in the subtree, if any.
One of the three element roles for list decomposition should be
chosen depending on the
desired order of the elements in cases where the list element
symbol occurs recursively in the tree:
If the role PreTYPEDeListElem is used the list elements
are associated to TYPEElem attributes of nodes in pre-order,
i.e. the attribute of a node gets an element of the list which
occurs before those elements in the list that are
distributed at the subtrees of the node.
If the role PostTYPEDeListElem is used the list elements
are associated to TYPEElem attributes of nodes in post-order,
i.e. the attribute of a node gets an element of the list which
occurs after those elements in the list that are
distributed at the subtrees of the node.
If the role TYPEDeListElem is used no elements are distributed
to subtrees of an element node.
A condition attribute TYPETakeIt of type
int is computed to true (1) by default.
It determines whether an
element of the list is taken at this node. That computation may be
overridden by a nontrivial computation if such a condition
is desired.
If list decomposition is used the name NoTYPE has to be
defined suitably in a user's specification,
e.g. in HDR.h.
Both TYPEListRoot and TYPEDeListRoot may be
recursively nested without affecting each other.
An example for the use of this module in type analysis is given in
(see Function Types of Functions as typed entities):
In the context of a function declaration
the list of parameter types is composed and associated as a
property of the function type. In the context of a function
call that property is accessed, the list is decomposed, and
its elements - the formal parameter types - are compared with
the types of the arguments.
|
