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

Remote Dependencies in Trees

In the previous section we considered dependencies between computations within one rule context and computations that are associated to pairs of adjacent contexts. It is often necessary to specify that a precondition of a computation is established rather far away in the tree, e. g. a value computed in the root context is used in several computations down in the tree. Instead of propagating it explicitly through all intermediate contexts it may be accessed directly by notations for remote dependencies.

In the following we introduce three constructs for remote dependency specification:

  • access to a subtree root from contexts within the subtree (INCLUDING construct),
  • access to contexts within a subtree from its root context (CONSTITUENTS construct),
  • computations at certain subtree contexts that depend in depth-first left-to-right order on each other (CHAIN construct).

These constructs can be used for value dependencies as well as for state dependencies. Since these constructs avoid specifications in the contexts between the remote computations, they abstract from the particular tree structure in between: It may be designed according to other aspects or be altered without invalidating those remote dependencies.

Access to a Subtree Root

Assume that we have a language where Blocks are arbitrarily nested. We want to compute the nesting depth of each Block, and mark each Definition with the nesting depth of the smallest enclosing Block. 

   ATTR depth: int;

   RULE: Root ::= Block COMPUTE
     Block.depth = 0;
   END;

   RULE: Block ::= '{' Sequence '}' END;
   RULE: Sequence ::= Sequence Statement END;
   RULE: Sequence ::= Sequence Definition END;
   RULE: Sequence ::= END;

   RULE: Statement ::= Block COMPUTE
     Block.depth = ADD (INCLUDING Block.depth, 1);
   END;

   RULE: Statement ::= Usage END;
   RULE: Usage ::= 'use' Ident END;

   TERM Ident: int;

   RULE: Definition ::= `define' Ident  COMPUTE
     printf ("%s defined on depth %d\n",
              StringTable (Ident), INCLUDING Block.depth);
   END;
Figure 6: Nesting Depth of Blocks

The specification of Figure 6 solves the stated problem by remote dependencies (INCLUDING). The tree contexts between Block and Statement or Definition do not need any computations. They are only mentioned here to show a complete example. The expression 

   INCLUDING Block.depth

used in two computations accesses the depth value of the next enclosing Block.

In general, alternative subtree root symbols may be specified, e. g. 

   INCLUDING (Block.depth, Procedure.depth, Module.depth)

Then the root of the smallest enclosing subtree is accessed which represents one of the given symbols. The tree grammar must guarantee that such a subtree root can always be found. Such an alternative has to be used especially in an INCLUDING that refers to a recursive construct like Block.

INCLUDING constructs may also be used as preconditions in <- constructs, and they may refer to state attributes.

Access to Contexts within a Subtree

Assume that we have a language for sequences of definitions and uses of names in arbitrary order. We want to produce an output text for each definition and each use, such that definition texts precede the use texts in the output. No specific order is required within the two text blocks. 

   RULE: Block ::= '{' Sequence '}' COMPUTE
     Block.DefDone = CONSTITUENTS Definition.DefDone;
   END;

   RULE: Definition ::= 'Define' Ident COMPUTE
      Definition.DefDone =
        printf ("%s defined in line %d\n",
                StringTable(Ident), LINE);
   END;

   RULE: Usage ::= 'use' Ident COMPUTE
       printf ("%s used in line %d\n",
               StringTable(Ident), LINE),
       <- INCLUDING BLOCK.DefDone;
   END;
Figure 7: Sequencing Classes of Computations in a Subtree

The solution of the problem given in Figure 7 uses a state attribute Block.DefDone. It describes the state where all definition texts are printed. Hence in that state the condition Definition.DefDone must hold at each Definition in the subtree below the Block context, as stated by the CONSTITUENTS construct. The state Block.DefDone in turn is the precondition for the print computation in the Usage context. Such a pair of CONSTITUENTS and INCLUDING uses is a common dependency pattern.

The following example demonstrates the remote access to values within a subtree. We simply want to compute the number of Usage constructs in a program of the above language. 

   ATTR Count: int;

   RULE: Block ::= '{' Sequence '}' COMPUTE
     printf  ("%d uses occurred\n",
              CONSTITUENTS Usage.Count
              WITH (int, ADD, IDENTICAL, ZERO));
   END;

   RULE: Usage ::= 'use' Ident COMPUTE
     Usage.Count = 1;
   END;
Figure 8: Adding Values of Subtree Components

The CONSTITUENTS construct in Figure 8 combines the values Usage.Count of each Usage node within the Block subtree. The WITH clause specifies how the values are combined, in this case they are added yielding an int-value.

The WITH clause is a scheme to combine an arbitrary number of values by a binary function. The general form is 

   WITH (t, combine, single, none)

where single is a function that yields a value of type t applied to an attribute accessed by the CONSTITUENTS. The function combine yields a t value applied to two t values. none is a constant function yielding a t value applied to no argument. (It is applied at subtrees that do not contain the accessed symbol, although the tree grammar would allow them to contain it). Typical examples for WITH clauses are given in Figure 9. 

      WITH (int, ADD, IDENTICAL, ZERO)
      WITH (int, Maximum, IDENTICAL, ZERO)
      WITH (int, OR, IDENTICAL, ZERO)
      WITH (int, AND, IDENTICAL, ONE)
      WITH (listtype, Append, SingleList, NullList)
Figure 9: Typical WITH Clauses

The applications of the combine functions obey the left-to-right order of the tree nodes where their arguments stem from. The combine function should be associative, the none function should not affect the resulting value. The calls of the three functions may occur in any suitable order; hence one should not rely upon side-effects. Suitable implementations of the functions and the type must be made available for the evaluator. (see Implementing Tree Computations)

We must be aware that in our example the CONSTITUENTS is applied in a recursive tree structure, i. e. blocks are nested in our language. In fact the above specification causes that Usage constructs in inner blocks do not contribute to the CONSTITUENTS in outer Block context: Inner Block subtrees are shielded from it. We better make that explicit by 

   CONSTITUENTS Usage.Count SHIELD Block WITH (...)

In general we may shield any class of subtrees from the CONSTITUENTS-access, e. g. by 

   SHIELD (Block, Procedure, Module) ...

If no subtree should be shielded an empty SHIELD clause is used: 

   ... SHIELD () ...

In this case our example would count the Usage constructs of all inner blocks too.

In general several attributes may be specified for being accessed by a CONSTITUENTS: 

   CONSTITUENTS (X.a, Y.b)

Left-to-Right Dependencies

As an example for a simple left-to-right dependent computation we rewrite the translation of expressions into postfix form of Figure 4.

In Figure 10 the CHAIN print specifies a sequence of computations that depends on each other in left-to-right depth-first order throughout the tree. It takes over the role of the pair of state attributes print and printed in Figure 5. Hence the CHAIN is introduced with type VOID. 

   CHAIN print: VOID;

   RULE: Root ::= Expr COMPUTE
     CHAINSTART HEAD.print = "yes";
     printf ("\n") <- TAIL.print;
   END;

   RULE: Expr ::= Number COMPUTE
     Expr.print = printf ("%d ", Number. Sym)
                 <- Expr.print;
   END;

   RULE: Opr ::= '+' COMPUTE
     Opr.post = printf ("+") <- Opr.pre;
   END;

   RULE: Expr ::= Expr Opr Expr COMPUTE
     Opr.pre = Expr[3].print;
     Expr[1].print = Opr.post;
   END;
Figure 10: CHAIN for Producing Postfix Expressions

The CHAIN computations are initiated in the Root context; HEAD.print refers to the CHAIN at the leftmost subtree, Expr in this case. TAIL.print refers to the end of the CHAIN at the rightmost subtree, again Expr. It is the precondition for printing the final newline.

In the second context the printf computation is specified to lie on the CHAIN by stating Expr.print to be a precondition (incoming CHAIN) as well as to be a postcondition (outgoing CHAIN).

The Opr context together with the binary operation context specifies that operators are not printed in CHAIN order, but are appended after the right operand is printed. For that purpose two state attributes Opr.pre and Opr.post are used, as in Figure 5.

If it is necessary to locally deviate from CHAIN order, like here in case of the binary operation context, it has to be made sure, that the chain is not cut into separate pieces which are not linked by dependencies: If by some reason we would add another computation to the Opr context of our example, e. g. 

     Opr.print = printf("Operator encountered\n")
                 <- Opr.print;

it looks like being integrated into the print CHAIN. But the two computations of the binary Expression context shortcut the CHAIN across the Opr symbol. Hence, this computation may be executed later than intended.

The above example specifies a single CHAIN of computations through the tree. In general there may be several instances of a CHAIN in several subtrees, which may be nested, too. For example, we may allocate variable definitions to storage addresses relative to their smallest enclosing Block, as shown in Figure 11. Here the CHAIN computations propagate values in depth-first left-to-right order. 

   CHAIN RelAdr: int;

   RULE: Block ::= '{' Sequence '}' COMPUTE
     CHAINSTART HEAD.RelAdr = 0;
   END;

   RULE: Definition ::= 'define' Ident COMPUTE
     Definition.RelAdr = ADD (Definition.RelAdr, VariableSize);
   END;
Figure 11: Computing Addresses of Variables

An individual CHAIN is started for each Block. In the computation of the Definition context the two occurrences of Definition.RelAdr refer to different values on the CHAIN: The access in the ADD computation is the incoming current CHAIN value (the address of this variable), the result left to the = symbol denotes the outgoing next CHAIN value.

Previous Chapter Next Chapter Table of Contents