LIDO -- Computations in Trees
Language processing requires certain computations to be executed for each instance of a language construct. Hence the specification associates computations to rule contexts. Usually a computation depends on values or effects yielded by other computations. Such dependencies are specified by attributes associated to grammar symbols. It should be emphasized that only the necessary dependencies are specified, rather than a complete execution order. A tree walking algorithm that executes the computations in a suitable order is generated automatically.
In this section we introduce the basic concepts and notations for specification of dependent computations in trees. The examples refer to the tree grammar of the previous section. It will be shown how expression evaluation and a simple transformation is specified.
ATTR value: int; RULE: Root ::= Expr COMPUTE printf ("value is %d\n", Expr.value); END;
The above computation uses the
In this case the
The above computation depends on a computation that yields
TERM Number: int; RULE: Expr ::= Number COMPUTE Expr.value = Number; END; RULE: Expr ::= Expr Opr Expr COMPUTE Expr.value = Opr.value; Opr.left = Expr.value; Opr.right = Expr.value; END; SYMBOL Opr: left, right: int; RULE: Opr ::= '+' COMPUTE Opr.value = ADD(Opr.left, Opr.right); END; RULE: Opr ::= '*' COMPUTE Opr.value = MUL(Opr.left, Opr.right); END;Figure 3: Computation of Expression Values
Computations that yield a value to be used in other computations are denoted like an assignment to an attribute. But it must be emphasized that they have to obey the single assignment rule: There must be exactly one computation for each attribute instance in every tree.
The values of binary expressions are computed in each of the two
The three attributes belong to two
conceptually different classes:
There are three (in this case trivial) computations specified in the context
for binary expressions. It should be pointed out that their textual order
is irrelevant: The execution order is determined by their dependencies.
In this case the computation of
Our second example specifies how to print expressions in postfix
notation, e. g.
We may start from a specification that just outputs each number and operator, given in Figure 4. It causes each instance of numbers and operators in the tree being printed. Since no dependencies are specified yet, they may occur in arbitrary order in the output.
RULE: Root ::= Expr COMPUTE printf ("\n"); END; RULE: Expr ::= Number COMPUTE printf ("%d " , Number) END; RULE: Opr ::= '+' COMPUTE printf ("+ "); END; RULE: Opr ::= '*' COMPUTE printf ("* "); END;Figure 4: Output of Expression Components
In order to achieve the desired effect we have to specify that a
computation is not executed before certain preconditions hold which are
established by a postcondition of some other computations. We specify
such conditions by attributes that do not have values, but describe a
computational state. In Figure 5 we associate attributes
RULE: Root ::= Expr COMPUTE Expr.print = "yes"; printf ("\n") <- Expr.printed; END; RULE: Expr ::= Number COMPUTE Expr.printed = printf ("%d ", Number) <- Expr.print; END; RULE: Opr ::= '+' COMPUTE Opr.printed = printf ("+ ") <- Opr.print; END; RULE: Opr ::= '*' COMPUTE Opr.printed = printf ("* ") <- Opr.print; END; RULE: Expr ::= Expr Opr Expr COMPUTE Expr.print = Expr.print; Expr.print = Expr.printed; Opr.print = Expr.printed; Expr.printed = Opr.printed; END;Figure 5: Dependencies for Producing Postfix Expressions
The general form of dependent computations as used in Figure 5 is
postcondition = computation
If the postcondition is not used elsewhere, it (and the =) is omitted.
If the postcondition is directly established by another condition, the
computation and the
<- (X.a, Y.b).
State attributes which do not carry a value have the type
It should be noted that the specifications of several tasks,
e. g. computing expression values and producing postfix output may be
combined in one specification for a language processor that solves all
of them. It is a good style to keep the specifications of
different tasks separate, rather than to merge the
computations for each single context. You may specify several sets of
computations at different places. They are accumulated for each rule
context. LIDO specifications may reside in any number of
See Left-to-Right Dependencies, for an example of expressing the above example using left-to-right depencencies.
There are situations where a
A computation is marked to be accumulating by the
RULE: Program ::= Statements COMPUTE Program.AnalysisDone += DoThis ( ); END; .... RULE: Program ::= Statements COMPUTE Program.AnalysisDone += DoThat ( ) <- Statements.checked; END;Two accumulating computations contribute both to the attribute
RULE: Program ::= Statements COMPUTE Program.AnalysisDone = ORDER (DoThis ( ), DoThat ( )) <- Statements.checked; END;The order in which
Only VOID attributes may have accumulating computations. If an attribute has an accumulating computation, it is called an accumulating attribute, and all its computations must be accumulating. Attributes are not explicitly defined to be accumulating. If an attribute is not defined explicitly, it has the type VOID by default. Hence, accumulating attributes need not be defined explicitly, at all.
The set of accumulating computations of an attribute is combined into a single computation, containing all dependences and function calls of the contributing accumulating computations, as shown above.
Accumulating computations may be inherited from CLASS symbols. In contrast to non-accumulating computations, there is no hiding for accumulating computations: All accumulating computations that lie on an inheritance path to an accumulating attribute in a rule context are combined. For example, add the following specifications to the above example:
SYMBOL Program INHERITS AddOn COMPUTE SYNT. AnalysisDone += AllWaysDo ( ); END; CLASS SYMBOL AddOn COMPUTE SYNT. AnalysisDone += AndAlsoDo (); END;Then all four computations for
Another typical use of accumulating attributes occurs in the context of specification modules: Assume that in a library of specification modules or in a modularly decomposed LIDO specification a computational role like the following is provided:
CLASS SYMBOL FindPath COMPUTE SYNT.Path = SearchPath (SYNT.Graph) <- SYNT.UserDependence; SYNT.UserDependence += "yes"; END;The provider of this computational role allows the user to add a dependence as a user defined pre-condition for the execution of the call of
SYMBOL EdgeList INHERITS FindPath COMPUTE SYNT.UserDependence += SYNT.GotAllEdges; END;