General Information

 o Eli: Translator Construction Made Easy
 o Global Index
 o Frequently Asked Questions

Tutorials

 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Type Analysis

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual

Libraries

 o Eli library routines
 o Specification Module Library

Translation Tasks

 o Lexical analysis specification
 o Syntactic Analysis Manual
 o Computation in Trees

Tools

 o LIGA Control Language
 o Debugging Information for LIDO
 o Graphical ORder TOol

 o FunnelWeb User's Manual

 o Pattern-based Text Generator
 o Property Definition Language
 o Operator Identification Language
 o Tree Grammar Specification Language
 o Command Line Processing
 o COLA Options Reference Manual

 o Generating Unparsing Code

 o Monitoring a Processor's Execution

Administration

 o System Administration Guide

 Questions, Comments, ....

LIDO -- Computations in Trees

Previous Chapter Next Chapter Table of Contents


Dependent Computations

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.

Value Dependencies

Let 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 RULE associates the printf computation to the rule context. The notation repeats the rule as shown in the tree grammar and adds any set of computations between COMPUTE and END. Computations are denoted like calls of C functions. The arguments are C literals, again function calls, or attributes. (User defined functions are implemented in specifications files separate from the .lido specification, See Interactions within Eli.)

The above computation uses the value attribute of the Expr subtree of this context. In general any attribute of any symbol that occurs in the rule context may be used in a computation of that context.

In this case the value attribute is the integral value computed for the expression. The ATTR construct states that its type is int. In fact it specifies that type for any attribute named value that is just used with a symbol. Any C type name may be specified. Such a type association is valid throughout the whole specification. It can be overridden by attribute properties specified in SYMBOL constructs.

The above computation depends on a computation that yields Expr.value. Since the internal structure of the Expr subtree determines how its value is to be computed, those computations are associated with the two lower adjacent contexts that have Expr on the left-hand side of their production, as shown in the computations of Figure 3.

   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 TERM construct states that the terminal symbol Number carries a value of type int to be used in computations like that of the first rule.

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 Opr contexts and passed to the root of the binary subtree. The ADD and MUL operations are predefined macros in LIDO. Opr has three attributes, the values of the left and right operands and the result of the operation. The attributes left and right are associated to Opr by the SYMBOL construct which states their type to be int. As only the Opr symbol has attributes of these names thy are not introduced by an ATTR construct. The attribute value is associated to Opr by just using it in a computation. Its type is specified by the ATTR construct explained above.

The three attributes belong to two conceptually different classes: Opr.value is computed in the lower context, as Expr.value (called synthesized or SYNT attribute), whereas Opr.left and Opr.right are computed in the upper context (called inherited or INH attributes). Any attribute must belong to either of the classes in order to obey the single assignment rule.

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 Expr[1].value will be executed last. The attribute notation requires indexing of symbol names, if a symbol occurs more than once in a production, like Expr. The indices enumerate the occurrences of a symbol in the production from left to right beginning with 1.

State Dependencies

Our second example specifies how to print expressions in postfix notation, e. g. 1 2 3 * + for the given expression 1 + 2 * 3. It demonstrates how computations that yield an effect rather than a value are specified to depend on each other.

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 print and printed to Expr and Opr. Expr.print describes the state where the output is produced so far such that the text of the Expr subtree can be appended. Expr.printed describes the state where the text of this subtree is appended (correspondingly for Opr.print and Opr.printed).

   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 <- precondition

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 <- are omitted. If a condition initially holds it is denoted by some literal, like "yes" in the Root context. A computation may depend on several preconditions:

 <- (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 VOID. They need not be introduced by a SYMBOL or an ATTR construct. They may be just used in a computation. But the same consistency and completeness requirements apply for them as for value carrying attributes.

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 .lido files or output fragments of .fw files. Hence, modular decomposition and combining related specifications of different types is encouraged.

See Left-to-Right Dependencies, for an example of expressing the above example using left-to-right depencencies.


Previous Chapter Next Chapter Table of Contents