LIDO -- Computations in Trees
In this section we introduce constructs that associate computations to tree grammar symbols rather than to rule contexts. They can be used for computations which are conceptually connected with symbols, i. e. they have to be executed once for each such symbol node and they are not distinguished for the contexts in which the symbol occurs.
The use of symbol computations makes specifications even more independent of the particular tree grammar, and hence reduces the chance to be invalidated by grammar changes. Well designed symbol computations may be reused at different places in one specification, and even in specifications of different language processors.
In the following we demonstrate the use of symbol computations, and introduce a construct for their reuse.
Consider the expression grammar given in the example of Value Dependencies.
For the purpose of this
example assume that we want to trace the computation of expression
values, and print
SYMBOL Expr COMPUTE printf ("expression value %d in line %d\n", THIS.value, LINE); END;
Symbol computations may use attributes of the symbol by the notation
The next example in Figure 12 shows how attributes are computed by symbol computations. It rewrites the usage count example of Figure 8. Both of its computations are in fact independent of the particular rule context.
ATTR Count: int; SYMBOL Usage COMPUTE SYNT.Count = 1; END; SYMBOL Block COMPUTE printf ("%d uses occurred\n", CONSTITUENTS Usage.Count SHIELD Block WITH (int, ADD, IDENTICAL, ZERO)); END;Figure 12: Symbol Computations for Usage Count
An attribute that is defined by a symbol computation has to be
The symbol computation of
The above example reduces the amount of key strokes only slightly
compared with that of Figure 8. But it makes this part of the
specification invariant to modifications of the contexts where
Now consider the computation of nesting depth of blocks in Figure 6. The
SYMBOL Block COMPUTE INH.depth = ADD (INCLUDING Block.depth, 1); END;
In this case the computation is intended to go to the upper contexts of
RULE: Root ::= Block COMPUTE Block.depth = 0; END;
It overrides the above symbol computation: A rule computation overrides a symbol computation for the same attribute.
The example demonstrates a design rule:
General context independent computations are specified by symbol computations. They may be overridden in special cases by computations in rule contexts.
The technique of overriding can also be used to specify default computations: A symbol computation specifies an attribute value for most occurrences of the symbol. In some contexts it is overridden by rule specific computations.
Finally we demonstrate how
CHAIN RelAdr: int; SYMBOL Block COMPUTE CHAINSTART HEAD.RelAdr = 0; END; SYMBOL Definition COMPUTE THIS.RelAdr = ADD (THIS.RelAdr, VariableSize); END;Figure 13: Symbol Computations for Addresses of Variables
Symbol computations are a well suited base for reuse of specifications: A computational concept is specified by a set of symbol computations. Then it is applied by inheriting it to grammar symbols. (Here the term inheritance is used in the sense of object oriented programming; it must not be confused with the class of inherited attributes.)
Assume we want to enumerate occurrences of non-recursive language
constructs, e. g. definitions in a block and variable uses in each
single statement. We first describe this computational concept by
computations associated to new
CHAIN Occurrence: int; ATTR OccNo, TotalOccs: int; CLASS SYMBOL OccRoot COMPUTE CHAINSTART HEAD.Occurrence = 0; THIS.TotalOccs = TAIL.Occurrence; END; CLASS SYMBOL OccElem COMPUTE SYNT.OccNo = THIS.Occurrence; THIS.Occurrence = ADD (SYNT.OccNo, 1); END;Figure 14: Computationel Concept Occurrence Count
The above computations correspond to those for computing addresses in
Figure 11. They are extended by computations of attributes
We now apply this count specification to symbols of our tree grammar:
SYMBOL Block INHERITS OccRoot END; SYMBOL Definition INHERITS OccElem END;
The second enumeration application is specified in the same way:
SYMBOL Statement INHERITS OccRoot END; SYMBOL Usage INHERITS OccElem END;
Of course we have to make sure that different applications do not interact. For example a third application enumerating the variable assignments would collide with the definition enumeration. This computational concept is not applicable to the enumeration of blocks which are recursive constructs. The specification module library of Eli provides more general applicable modules, and a mechanism that avoids such collisions. The application of those library modules is based on the technique of inheritance of computational roles as described here.
We finally show how several computational concepts may be combined:
Assume that we want to print the total number of enumerated constructs.
We again introduce a
CLASS SYMBOL PrintTotalOccs COMPUTE printf ("construct in line %d has %d elements\n", LINE, THIS.TotalOccs); END;
This computation is applied by adding
SYMBOL Block INHERITS PrintTotalOccs END;
to the specification and correspondingly for
SYMBOL Block INHERITS OccRoot, PrintTotalOccs END;
We alternatively could extend the role of the enumeration root
CLASS SYMBOL OccRoot INHERITS PrintTotalOccs END;
In this case each symbol that inherits the computation of