General Information

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

Tutorials

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

Reference Manuals

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

Libraries

	Eli library routines
	Specification Module Library

Translation Tasks

	Lexical analysis specification
	Syntactic Analysis Manual
	Computation in Trees

Tools

	LIGA Control Language
	Debugging Information for LIDO
	Graphical ORder TOol

FunnelWeb User's Manual

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

Generating Unparsing Code

Monitoring a Processor's Execution

Administration

System Administration Guide

LIDO -- Computations in Trees

Early Computations During Tree Construction

In general the execution of specified computations begins when the tree is completely build. However, certain application tasks require that an action is performed immediately when an input construct is read. It may be not acceptable to wait until the input is completely processed. Typical examples are desktop calculators: A formula is evaluated and the result is output before the next formula is read. Another example is a computation which influences the input processing, e.g. switch to another input source.

In such cases, these computations (the output of the expression value or the switch of the input file) can be marked to be executed early using the keyword BOTTOMUP. The Liga system then tries to arrange the computations such that they are executed already when their node is constructed.

   RULE: Program  ::= Sequence END;
   RULE: Sequence ::= Sequence Output NewLine END;
   RULE: Sequence ::= END;

   SYMBOL Expression: Value: int;

   RULE: Output ::= Expression COMPUTE
     printf ("%d\n", Expression.Value) BOTTOMUP;
   END;

   RULE: Expression ::= Number COMPUTE
     Expression.Value = Number;
   END;

   RULE: Expression ::= Expression BinOpr Expression COMPUTE
     Expression[1].Value =
       APPLY (BinOpr.Funct, 
              Expression[2].Value, Expression[3].Value);
   END;

   SYMBOL BinOpr: Funct: BinFunct;
   RULE:  BinOpr ::= '+' COMPUTE BinOpr.Funct = Add;  END;
   RULE:  BinOpr ::= '*' COMPUTE BinOpr.Funct = Mult; END;

Figure 15 shows the LIDO specifications for a simple desktop calculator. The printf operation in the lower context of the Output symbol is marked to be executed early. It prints the value of a complete expression before the next expression is read. The values of subexpressions are not printed.

Many other computations in other contexts may contribute values to the marked one: in this case computations of the Value attribute of subexpressions. Liga tries to arrange their execution early enough to contribute their values to the marked computation. These contributing computations should not be marked BOTTOMUP, in order to give Liga the chance to find a suitable but less restrictive solution.

Arranging computations on which a BOTTOMUP computation depends is determined by the way trees are build: left-to-right bottom-up. The BOTTOMUP computations may not depend on computations that belong to context which are higher or to the right in the tree. Furthermore, at tree construction time values can only be propagated upward out of subtrees, but not to sibling nodes or to uncle nodes.

The following technical detail needs to be considered for tree grammar design in the presence of BOTTOMUP computations: Usually parsers need one token lookahead. That means, a tree node is constructed not before the next token is read which is behind the subtree of that node. In our example the node that has the BOTTOMUP computation is created when the NewLine token is read. If we had chosen to specify the NewLine in the production of Output instead, like

    RULE: Output::= Expression NewLine COMPUTE ...