Eli   Documents Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads

General Information

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


 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
 o Typical Eli Usage Errors

Reference Manuals

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


 o Eli library routines
 o Specification Module Library

Translation Tasks

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


 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


 o System Administration Guide

Mail Home

LIDO - Reference Manual

Previous Chapter Next Chapter Table of Contents

Computed Subtrees

In general the tree represents the abstract structure of the input text and is built by scanning and parsing the input. That initial tree may be augmented by subtrees which result from certain computations. This feature can be used for translation into target trees which also contain computations that are executed in the usual way.

The tree construction functions generated by LIGA are used to build such subtrees. They are inserted into the initial tree at certain positions specified in productions.


    Symbols ::= '$' SymbName


    RULE: Block ::= '{' Decl Stmts '}' $ Target COMPUTE
      Target.GENTREE =
           MkTBlock (COORDREF, Dels.tcode, Stmt.tcode);
    RULE TBlock: Target ::= TSeq TSeq COMPUTE ... END;

Trees may be the result of computations using LIGA's tree construction functions as described below (see Tree Construction Functions).

Tree values may be propagated between computations using attributes of the predefined type NODEPTR (see Predefined Entities).

Tree values are inserted into the tree in contexts where the right-hand side of the production specifies insertion points of the form $ X where X is a nonterminal name.

The insertion is specified by a computation of the attribute X.GENTREE where X is the insertion point symbol and GENTREE is a predefined attribute name for inherited attributes of insertion symbols (see Predefined Entities). The computation must yield a value of type NODEPTR that is a legal tree with respect to the tree grammar for X: LIGA guarantees that the computations in the inserted tree are not executed before the tree is inserted.

The tree grammar productions for computed trees may be disjoint from or may overlap with the productions for the initial tree.

Computed trees may again have insertion points in their productions.


There must be exactly one insertion computation for each insertion point of a rule context.

There may not be an insertion computation for a symbol that is not an insertion point.

Inserted trees must be legal with respect to the tree grammar. This property is checked at runtime of the evaluator.

No computation that establishes a precondition for a tree insertion may depended on a computation within the inserted tree.

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

Tree Construction Functions

LIGA generates a set of tree construction functions, one for each rule context. They may be used in computations to build trees which are then inserted at insertion points. Their names and signatures reflect the rule name and the right-hand side of the production.

For a rule

    RULE pBlock: Block::= '{' Decls Stmts '}' END

there is a function


The function name is the rule name prefixed by Mk. Hence, it is recommended not to omit the rule name when its construction function is to be used.

LIGA's tree construction functions are ready to be used in attribute computations. If they are to be applied in user-supplied C-code an include directive

   #include "treecon.h"

has to be used to make the function definitions available.

The first parameter of every function is a pointer to a source coordinate. That argument may be obtained from the coordinate of the context where the function is called. It is used for error reporting, see Predefined Entities.

The following parameters correspond to the sequence of non-literal symbols of the right-hand side of the production. For each nonterminal in the production there is a parameter of type NODEPTR. Its argument must be a pointer to the root node of a suitable subtree, built by node construction functions. For each insertion point in the production there is a parameter of type NODEPTR. Its argument should be NULLNODEPTR, since that subtree is inserted later by a computation. For each named terminal in the production there is a parameter of the type of the terminal. Its argument is the value that is to be passed to terminal uses in computations.

Functions for chain productions, the right-hand side of which consists of exactly one nonterminal, need not be called explicitly. The nodes for those contexts are inserted implicitly when the upper context is built.

LISTOF productions have a specific set of tree construction functions: For a rule like

    RULE pDecls: Decls LISTOF Var | Proc | END;
the functions

are provided, where Mk2pDecls constructs internal list context nodes and MkpDecls builds the root context of the list.

The arguments for each of the parameters l, ll, and lr can be NULLNODEPTR representing an empty list, a pointer to a list element node, a node that can be made a list element subtree by implicit insertion of chain contexts, or the result of a Mk2-function call representing a sublist.

The Mk2-functions concatenate two intermediate list representations into one retaining the order of their elements.

Mk0-macros are generated. They take only the POSITION but no tree as argument, and return NULLNODEPTR representing an empty list. These macros usually need not be used.

The LISTOF subtree must be finally built by a call of the root context function.

Previous Chapter Next Chapter Table of Contents