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 - Reference Manual

Previous Chapter Next Chapter Table of Contents

Computations

Computations are associated with rules or with symbols. Each computation (that is not overridden) is executed exactly once for every instance of its context in a particular tree. A computation may yield a value denoted as an attribute which may be used by other computations. Computations may also be specified as depending on one another without passing a value in order to specify dependences on side-effects of computations. (see Dependent Expressions).

Syntax

    Computations ::=  [ 'COMPUTE' Computation ]

    Computation  ::=  Computation Computation |
                   | Attribute '=' Expression Terminator
                   | Expression Terminator
                   | Attribute '+=' Expression Terminator

    Terminator   ::= ';'
                   | 'BOTTOMUP' ';'

There are three forms of computations: attribute computations denoted as an assignment to an attribute, plain computations that are simple expressions, and accumulating computations which are a special variant of attribute computations, distinguished by the += token.

Attribute Computations and Plain Computations

The following example shows a sequence of two attribute computations and two plain computations:

Examples

    COMPUTE
      Expr.postType = boolType;
      Stmt[1].code = PTGWhile (Expr.code, Stmt[2].code);
      printf ("while loop in line %d\n", LINE);
      printf ("value = %d\n", Expr.val) BOTTOMUP;
    END;

A computation is executed by evaluating its expression. It depends on every attribute that occurs in the expression regardless whether the attribute is used for the evaluation. We say those attributes are the preconditions of the computation. The attribute on the left-hand side of an attribute computation represents the postcondition of that computation. Plain computations do not establish a postcondition for any other computation. The evaluator is generated such that the computations are executed in an order that obeys these dependencies for any tree of the tree grammar.

If both a symbol computation and a rule computation define the same attribute of a symbol, the rule computation will be executed in that context, overriding the symbol computation.

An expression may occur in value context, where it must yield a value, or it may occur in VOID context, where it may or may not yield a value. If it does yield a value in VOID context, the value is discarded. These terms will be used in sections below where further constructs are introduced which contain expressions.

If the left-hand side attribute of an attribute computation has a type different from VOID the right-hand side expression is in value context; the result of the expression evaluation is assigned to the attribute. If the left-hand side attribute has the type VOID the right-hand side expression is in VOID context. In this case the attribute simply states the postcondition that the computation has been executed.

A plain computation is in VOID context, i. e. it may or may not yield a value.

Computations may be specified to be executed BOTTOMUP, that means while the input is being read and the tree is being built. LIGA then tries to arrange the computations such that those are executed already when their tree node is constructed. This facility is useful for example if the generated language processor is to produce output while its input is supplied (like desktop calculators), or if a computation is used to switch the input file.

Note: A BOTTOMUP computation may depend on other computations. These dependencies should be specified the usual way. Such precondition computations should NOT be specified BOTTOMUP unless they themselves are to be related to input processing. Without such an over-specification LIGA can apply more sophisticated means to correctly schedule the precondition computations automatically.

Note: Due to the parser's lookahead, one token beyond the last token of the context of the BOTTOMUP computation is read before before the computation is executed.

Restrictions

If the attribute in an attribute computation has a non-VOID type the evaluation of the expression must yield a value of that type. This condition is not checked by LIGA. It is checked by the compiler that compiles the generated evaluator.

Multiple symbol computations that define the same attribute are forbidden.

There must be exactly one attribute computation for each synthesized attribute of the left-hand side nonterminal and for each inherited attribute of each nonterminal occurrence on the right-hand side in the production of a rule context, or such a computation is inherited in the rule context. (For accumulating computations a different rule applies.)

There may not be any cyclic dependencies between computations for any tree of the tree grammar.

Contexts that may belong to subtrees which are built by computations (see Computed Subtrees) may not have computations that are marked BOTTOMUP or contribute to BOTTOMUP computations.

LIGA may fail to allocate BOTTOMUP computations as required due to attribute dependencies or due to LIGA's evaluation strategy. In such cases messages are given.

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.

Restrictions

If an attribute has an accumulating computation, it is called an accumulating attribute, and may not have or inherit non-accumulating computations.

An accumulating attribute must have type VOID.

Let X be the left-hand side nonterminal in a rule r and X.s an accumulating synthesized attribute, then there must be at least one accumulating computation for X.s in r or inherited there.

Let X[i] be an occurrence of the nonterminal X on the right-hand side of the rule r and X.s an accumulating inherited attribute, then there must be at least one accumulating computation for X[i].s in r or inherited there.

CHAIN computations and CHAIN attributes may not be accumulating.

Previous Chapter Next Chapter Table of Contents