Eli   Documents
Eli: Translator Construction Made Easy

General Information

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

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

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
Mail Home

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 dependencies.

Accumulating Computations

There are situations where a VOID attribute, say Program.AnalysisDone, represents a computational state which is reached when several computations are executed, which conceptually belong to different sections of the LIDO text. Instead of moving all these computations to the only place where Program.AnalysisDone is computed, several accumulating computations may stay in their conceptual context and contribute dependences to that attribute.

A computation is marked to be accumulating by the += token. The following example demonstrates the above mentioned use of accumulating computations: 

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 pre-condition 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 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 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 pre-condition 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;

Previous Chapter Next Chapter Table of Contents