![]() |
![]() |
![]() |
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
![]() |
![]() |
LIDO -- Computations in TreesDependent ComputationsLanguage 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.
Value DependenciesLet us first describe computations that evaluate any given expression tree and print the result:
ATTR value: int; RULE: Root ::= Expr COMPUTE printf ("value is %d\n", Expr.value); END;
The above
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[1].value = Opr.value; Opr.left = Expr[2].value; Opr.right = Expr[3].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
The 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
State Dependencies
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[2].print = Expr[1].print; Expr[3].print = Expr[2].printed; Opr.print = Expr[3].printed; Expr[1].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). Computations may also depend on the computation of value carrying attributes without using their value, or computations may yield a value and also depend on some preconditions.
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.
|