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

Symbol Computations

In this section we introduce constructs that associate computations to tree grammar symbols rather than to rule contexts. They can be used for computations which are conceptually connected with symbols, i. e. they have to be executed once for each such symbol node and they are not distinguished for the contexts in which the symbol occurs.

The use of symbol computations makes specifications even more independent of the particular tree grammar, and hence reduces the chance to be invalidated by grammar changes. Well designed symbol computations may be reused at different places in one specification, and even in specifications of different language processors.

In the following we demonstrate the use of symbol computations, and introduce a construct for their reuse.

Basic Symbol Computations

Consider the expression grammar given in the example of Value Dependencies. For the purpose of this example assume that we want to trace the computation of expression values, and print Expr.value for each Expr node. We could associate that computation to both lower Expr context. But this computation does not refer to those particular contexts, it only depends on one Expr attribute. Hence we better associate it to the Expr symbol: 

   SYMBOL Expr COMPUTE
      printf ("expression value %d in line %d\n", THIS.value, LINE);
   END;

Symbol computations may use attributes of the symbol by the notation THIS.AttributeName.

The next example in Figure 12 shows how attributes are computed by symbol computations. It rewrites the usage count example of Figure 8. Both of its computations are in fact independent of the particular rule context. 

   ATTR Count: int;

   SYMBOL Usage COMPUTE
     SYNT.Count = 1;
   END;

   SYMBOL Block COMPUTE
      printf ("%d uses occurred\n",
              CONSTITUENTS Usage.Count SHIELD Block
              WITH (int, ADD, IDENTICAL, ZERO));
   END;
Figure 12: Symbol Computations for Usage Count

An attribute that is defined by a symbol computation has to be classified SYNT or INH, like SYNT.Count above (instead of THIS.Count if the attribute were used in the computation). It determines whether the computation is intended for the lower SYNT or the upper INH contexts of the symbol.

The symbol computation of Block above shows that CONSTITUENTS constructs may be used in symbol computations as well as in rule contexts. The same applies to INCLUDING and CHAIN as shown below.

The above example reduces the amount of key strokes only slightly compared with that of Figure 8. But it makes this part of the specification invariant to modifications of the contexts where Usage and Block occur. The productions for Block and for Usage may be modified without affecting these symbol computations.

Now consider the computation of nesting depth of blocks in Figure 6. The computation of Block.depth can also be specified as a symbol computation: 

   SYMBOL Block COMPUTE
     INH.depth = ADD (INCLUDING Block.depth, 1);
   END;

In this case the computation is intended to go to the upper contexts of Block, indicated by INH.depth. That is correct for any context where Block is a descendant of a Statement. But in the Program context the depth of the root Block must be computed to 0, rather than by the above symbol computation. So we keep the computation of Figure 6: 

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

It overrides the above symbol computation: A rule computation overrides a symbol computation for the same attribute.

The example demonstrates a design rule:

General context independent computations are specified by symbol computations. They may be overridden in special cases by computations in rule contexts.

The technique of overriding can also be used to specify default computations: A symbol computation specifies an attribute value for most occurrences of the symbol. In some contexts it is overridden by rule specific computations.

Finally we demonstrate how CHAINS are used in symbol computations. In Figure 11 addresses are computed for variable definitions. It is rewritten, as shown in Figure 13. In the second computation THIS.RelAdr occurs twice with different meanings: it refers to the incoming CHAIN value in the call of ADD, whereas the outgoing CHAIN value is defined on the lefthand-side of the computation. CHAIN accesses are distinguished by their use or definition, rather than by SYNT and INH as in case of attributes. 

   CHAIN RelAdr: int;

   SYMBOL Block COMPUTE
     CHAINSTART HEAD.RelAdr = 0;
   END;

   SYMBOL Definition COMPUTE
     THIS.RelAdr = ADD (THIS.RelAdr, VariableSize);
   END;
Figure 13: Symbol Computations for Addresses of Variables

Reuse of Symbol Computations

Symbol computations are a well suited base for reuse of specifications: A computational concept is specified by a set of symbol computations. Then it is applied by inheriting it to grammar symbols. (Here the term inheritance is used in the sense of object oriented programming; it must not be confused with the class of inherited attributes.)

Assume we want to enumerate occurrences of non-recursive language constructs, e. g. definitions in a block and variable uses in each single statement. We first describe this computational concept by computations associated to new CLASS symbols that do not occur in the tree grammar. In Figure 14 use a CHAIN as in the examples of Left-to-Right Dependencies. 

   CHAIN Occurrence: int;
   ATTR OccNo, TotalOccs: int;

   CLASS SYMBOL OccRoot COMPUTE
     CHAINSTART HEAD.Occurrence = 0;
     THIS.TotalOccs = TAIL.Occurrence;
   END;

   CLASS SYMBOL OccElem COMPUTE
     SYNT.OccNo = THIS.Occurrence;
     THIS.Occurrence = ADD (SYNT.OccNo, 1);
   END;
Figure 14: Computational Concept Occurrence Count

The above computations correspond to those for computing addresses in Figure 11. They are extended by computations of attributes TotalOccs (for the total number of enumerated constructs) and OccNo (for the current number of the enumerated element). Further computations may use these attributes, instead of referring to the CHAIN, which can be considered as an implementation mechanism of the enumeration computation.

The CLASS symbols OccRoot and OccElem represent two roles of this computational concept: The root of a subtree where elements are counted, and the elements to be counted. They are distinguished from symbols of the tree grammar by specifying them CLASS SYMBOL.

We now apply this count specification to symbols of our tree grammar: 

   SYMBOL Block INHERITS OccRoot END;
   SYMBOL Definition INHERITS OccElem END;

Block inherits the role OccRoot and Definition inherits the role OccElem. Those constructs yield the same effect as if the computations for OccRoot (OccElem) were associated to Block (Definition). As a consequence further computations may use the attributes Definition.OccNo (the number of a definition in a block), and Block.TotalOccs (the total number of definitions in that block).

The second enumeration application is specified in the same way: 

   SYMBOL Statement INHERITS OccRoot END;
   SYMBOL Usage INHERITS OccElem END;

Of course we have to make sure that different applications do not interact. For example a third application enumerating the variable assignments would collide with the definition enumeration. This computational concept is not applicable to the enumeration of blocks which are recursive constructs. The specification module library of Eli provides more general applicable modules, and a mechanism that avoids such collisions. The application of those library modules is based on the technique of inheritance of computational roles as described here.

We finally show how several computational concepts may be combined: Assume that we want to print the total number of enumerated constructs. We again introduce a CLASS symbol for this computation: 

   CLASS SYMBOL PrintTotalOccs COMPUTE
      printf ("construct in line %d has %d elements\n",
              LINE, THIS.TotalOccs);
   END;

This computation is applied by adding 

   SYMBOL Block INHERITS PrintTotalOccs END;

to the specification and correspondingly for Definition. The two INHERITS constructs can also be combined to one: 

   SYMBOL Block INHERITS OccRoot, PrintTotalOccs END;

We alternatively could extend the role of the enumeration root OccRoot such that the total number is always printed by 

   CLASS SYMBOL OccRoot INHERITS PrintTotalOccs END;

In this case each symbol that inherits the computation of OccRoot also inherits the computation of PrintTotalOccs.

Previous Chapter Next Chapter Table of Contents