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 LefttoRight Dependencies, for an example of expressing the above example using lefttoright depencencies.
Accumulating Computations
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 Program.AnalysisDone , such that it represents the state when
the calls DoThis ( ) and DoThat ( ) are executed after the
precondition Statements.checked has been reached.
The two accumulating computations above have the same effect as if there
was a single computation, as in
RULE: Program ::= Statements COMPUTE Program.AnalysisDone = ORDER (DoThis ( ), DoThat ( )) < Statements.checked; END;The order in which DoThis ( ) and DoThat ( ) are executed
is arbitrarily decided by the Liga system.
Accumulating computations may be formulated in rule context or in the context of TREE or CLASS symbols. Rule attributes may also be computed by accumulating computations. 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 nonaccumulating 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 Program.AnalysisDone
(two in the RULE context above, one in the TREE symbol context Program , and one
inherited from the CLASS symbol AddOn )
will be combined into one. It characterizes the state after execution of the
four function calls and the computation of Statements.checked .
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 precondition for the execution of the call of SearchPath , if necessary. It is demonstrated in the following use of the role:
SYMBOL EdgeList INHERITS FindPath COMPUTE SYNT.UserDependence += SYNT.GotAllEdges; END;
