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

Interactions within Eli

This section gives initial information how specifications of computations in trees interact with other Eli facilities. It should be sufficient for getting started. Other documents have to be consulted for a deeper understanding of those facilities and the interaction.

Supplying Tree Computation Specifications to Eli

Specifications as described in this document are written in files named x.lido where x is an arbitrary name. The specification of larger tasks should be decomposed into single subtasks specified in separate files each.

Further contributions to LIDO specifications are obtained from instantiation of library modules. The components of a LIDO specification are comprised by enumerating their names in a .specs file or by generating them from a .fw file. Tree Construction describes another contribution to the set of .lido files for tree grammar specification.

It should be pointed out that RULE, SYMBOL, ATTR, and CHAIN constructs for the same names may occur arbitrary often in several or one single file as long as they do not specify contradicting properties. Computations specified for one RULE or SYMBOL name are accumulated. The LIGA system processes the concatenation of all .lido files. Hence the reference manual for the language LIDO (see LIDO - Reference Manual) refers to that compound specification disregarding the composition of single files.

It is highly recommended to simplify the development of specifications by the use of precoined solutions provided by the library of specification modules. For that purpose applicable tasks can be identified in the module library, see Specification Module Library. The inheritance mechanism as introduced in section Reuse of Symbol Computations is applied, and the use of the module is stated in a .specs or a .fw file as described in that document.

Tree Construction

The specification of computations in trees assume that a tree according to the tree grammar exists. Usually it is constructed by the structuring phase (scanner and parser) of the language processor. There are two different starting points for the design of the tree structure specifications: the tree grammar or the concrete grammar for the input language.

In general there may be parts of the language that need more attention to the concrete grammar and others where the computations in the tree grammar should be considered first. That may give rise to a mixed strategy: Supply the concrete grammar specification (.con and .sym files) for those parts of the language which are known and fixed, specify tree grammar rules (in .lido files) where computations are already known to be associated to, and take care that the whole grammar is covered by either of them. During the refinement of the computations further tree grammar rules may be added without updating the concrete grammar specification.

An Eli tool (Maptool, see Syntactic Analysis Manual) combines both grammar specification fragments, completes each of them, and relates concrete productions to tree grammar rules such that the parser builds the required tree. That relation is usually not a 1:1 mapping: Some concrete chain productions are left out in the tree grammar, e. g. those which describe operators precedences in expressions. The tree grammar may have chain context which have no correspondence in the concrete grammar, e. g. those which distinguish different classes of identifier occurrences. The latter may even be introduced to the tree grammar when they are needed during the refinement of the computations without updating the concrete grammar specification.

Both the concrete and the tree grammar distinguish literal terminals and named terminals. If the scanner is generated by Eli no further specification is needed for literal terminals, like 'begin' or ':='. For each named terminal, like Name or Number, a .gla specification has to describe its notation. The named terminals usually carry token specific information to be used in tree computations, e. g. the encoding of an identifier token or the value of a number. The LIDO specification should state the type of that information using a TERM construct, e. g. 

  TERM Name: int;

Since GLA generated scanners pass such token information by values of type int, LIGA assumes that type if the TERM construct is omitted for a named terminal. Hence, the above TERM construct is redundant for terminals created by GLA. It is needed for terminal created by other scanners or by computed tree extension.

Implementing Tree Computations

The implementation of functions, types, constants, and variables used in tree computations is not specified within the .lido specification. They have to be made available to the generated evaluator. No further user action is necessary if they are defined in C (like the basic C types) or in the standard I/O library stdio.h (like printf), or if they are predefined in LIDO (like ADD, see Predefined Entities of LIDO -- Reference Manual, or if they are provided by Eli tools (e. g. PDL, PTG). Otherwise the user has to supply implementations of the used entities by C definition.

It is recommended to apply a modular style for those implementations: Supply C modules consisting of a m.c and a m.h file each, where the latter describes the objects exported by the module. (It is also possible to implement computations by CPP-macros.)

The file names m.h and m.c of all such user supplied C-modules have to be mentioned in some .specs file. Furthermore one or several .head files or .HEAD.phi files have to be provided. They have to contain a line 

   #include "m.h"

for each module m, making it available to the generated evaluator. It is recommended to protect each m.h file against multiple inclusion by suitable CPP-commands.

If a module needs some operations for initialization or finalization they can be written (as function calls) into files m.init or m.finl (or into .INIT.phi or .FINL.phi files).

Specification Errors

Eli checks the whole set of specifications extensively. It generates a language processor only if no errors are found. Error reports and warnings are obtained by a derivation like 

   x.specs:exe:warning

The error reports are related to the specification file (and line and column coordinates in it) where Eli found the error symptom, if that is possible. In the following we give hints how to react on the most common classes of errors. As a general rule one can obtain more information about an error symptom by applying the derivation 

   x.specs:exe:help

Violations of the LIDO specification language definition are reported with references to the .lido files. In most cases one should be able to deduce the correction from the report text, consulting the LIDO reference manual if necessary. Additionally the following information might be helpful:

A report saying 

   VOID attribute not allowed here

in most cases indicates that an attribute is used without specifying its type, VOID is assumed then. The reason of such an error often is a misspelled attribute name.

It may be helpful to derive 

   x.specs:showFe

and look at the file attr.info. It gives an overview on all attributes the system found so far in the .lido files. (Attributes that stem from inheritance are not yet found in this phase.)

A report saying 

   attribute class in conflict

indicates that computations in lower contexts and in upper contexts define that attribute. One has to rewrite them such that only one class is used.

If problems are reported with remote dependencies one should check the use of those constructs within the tree grammar structure. In special difficult cases more information can be obtained by deriving 

   x.specs:ExpInfo

That file describes how each remote access construct can be replaced by a set of equivalent computations propagating the accessed values through adjacent contexts.

LIGA also checks whether the dependencies between the computations are acyclic for any tree, and reports if they are cyclic. In that case more information can be obtained by deriving 

   x.specs:OrdInfo

or by using the tool gorto (see GORTO - Graphical Dependency Analyzer) for tracing dependencies graphically.

In rather seldom cases LIGA may report that it could not find an evaluation order, although the dependencies are acyclic. If such a situation occurs it is usually caused by several sets of far ranging dependencies where the computations in one set are independent of those of the other sets. Adding additional dependencies that specify some computation sets to depend on others often solves the problem. More information on the problem is obtained by using gorto. It is highly recommended NOT to try to avoid such situations before they are reported, since they occur rather seldom.

LIGA can not perform type checking on user functions that are called in LIDO expressions. Hence, typing errors and errors on undefined names may be reported when the generated evaluator is compiled. Those reports originally refer to C file named visitprocs.c. Eli traces them back to the line of the computation in the LIDO text where they originate from. In most cases that will be sufficient to identify the problem. But, one has to keep in mind that the report text is in terms of C rather than of LIDO, and that the line number only identifies a computation, rather than the exact line of the problem spot within multiple line computations. In doubtful cases it may be necessary to look at the C code directly.

In case of undefined type names often avalanche errors are reported by the C compiler with respect to several product files. They can not be traced back to some specification file.

If functions are used in a .lido file but are not made available for the evaluator, the error might not be reported before the whole program is linked.

Previous Chapter Next Chapter Table of Contents