Eli   Documents

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

Abstract Syntax Tree Unparsing

Previous Chapter Next Chapter Table of Contents


Deriving an Unparser

Recall the example of the pretty-printer that was defined by the file following type-`specs' file (see Using an Unparser):

example.fw
example.fw :idem
Add.fw

The first line is the name of a file defining a processor that builds a tree from a sentence in the expression language. The second line is a request to derive a textual unparser from the definition of the expression language. Finally, the third line is the name of a file containing the computation that outputs the unparsed tree. These three lines constitute the complete definition of the pretty-printer, which could be derived from this type-`specs' file in the usual way.

Here we are concerned only with the problem of deriving an unparser, exemplified by the second line above. Such a derivation always yields a FunnelWeb file that defines the desired unparser. Since the derivation occurs as a component of a type-`specs' file, the derived unparser becomes a component of the processor defined by that type-`specs' file.

All of the information needed to construct the unparser must be derivable from its basis (file `example.fw' in this case). Different derivations are applied to the basis to create different kinds of unparsers, to control the representation language of the unparsed text, and to obtain a definition of the output structure.

Establishing a basis

In the simplest case, the only information needed to derive an unparser is the tree grammar rules defining the set of trees to be unparsed.

Since the generated unparser will be a component of some processor, all of the rules defining trees to be unparsed must be valid rules of the tree grammar for that processor. The easiest way to satisfy this requirement is for the basis of the unparser derivation to define a complete tree grammar for the processor. This is the situation in our example; file `example.fw' defines the complete tree grammar for the expression language and therefore for the pretty-printer. (See Deriving structural unparsers, for applications in which unparsers are derived from parts of the tree grammar for a processor.)

Suppose that we were to create a file `evaluate.fw' containing computations that evaluate sentences in the expression language. A "desk calculator" could then be defined by a file `calculator.specs' with the content:

example.fw
evaluate.fw

In this case, `calculator.specs' still defines the complete tree grammar for the expression language. Thus the following type-`specs' file would define a processor that reads sentences in the expression language, evaluates them, and prints them in a standard format:

calculator.specs
calculator.specs :idem
Add.fw

The situation is more complex when some PTG patterns must be overridden to obtain the desired output. Overriding patterns must be specified as part of the basis from which the unparser is derived, and they will be incorporated into the generated unparser definition.

One way to include overriding PTG patterns in the basis of an unparser derivation is to make them a part of the overall processor specification. Thus, for example, they could be included in `example.fw' of the specifications above. Then either of the derivations shown (the one based on `example.fw' or the one based on `calculator.specs') would produce an unparser with the specified patterns overridden. It is important to note that the tree grammar and the PTG patterns are the only things defined by `calculator.specs' (or by `example.fw' in the earlier derivation) that are relevant to deriving an unparser. All other information is ignored. PTG patterns whose names do not match prefixed rule names from the tree grammar are also ignored.

It is often a violation of modularity to combine overriding patterns with the overall processor specification. For example, consider an unparser that outputs a postfix representation of a sentence in the expression language (see Overriding PTG patterns). The overriding patterns are specific to this particular processor, and have nothing to do with the definition of the expression language itself. Including them in `example.fw' would pollute the language specification, tying it to this application.

We can easily avoid this violation of modularity by adding a patterns parameter to `example.fw' to form the basis of the derivation. First, the overriding patterns are defined in a file named (say) `Postfix.ptg':

Idem_PlusExp: $1 $2  "+" [Separator]
Idem_StarExp: $1 $2  "*" [Separator]
Idem_Parens:  $1
Idem_CallExp: $1 $2      [Separator]

This file is then supplied as the value of the patterns parameter (see Parameterization Expressions of Eli User Interface Reference Manual):

example.fw +patterns=(Postfix.ptg)

The unparser derivation would then be:

example.fw +patterns=(Postfix.ptg) :idem

A complete processor accepting a sentence in the expression language and printing its postfix equivalent in standard form would then be defined by the following type-`specs' file:

example.fw
example.fw +patterns=(Postfix.ptg) :idem
Add.fw

A basis may include any number of file-valued patterns parameters. Only the PTG patterns defined by these files are relevant to the unparser generation; all other information is ignored. PTG patterns whose names do not match prefixed rule names from the tree grammar are also ignored.

Any unparser can be derived with a prefix other than Idem for the type-PTGNode attributes and PTG patterns that it creates. The desired prefix forms part of the basis from which the unparser is derived. This feature is useful if an application involves more than one unparser (see Deriving multiple unparsers).

The desired prefix is supplied as the value of the prefix parameter. For example, the basis for an expression language unparser computing the attributes TargetPtg and TargetOrigPtg instead of IdemPtg and IdemOrigPtg would be:

example.fw +prefix=Target

All PTG pattern names in an unparser derived from this basis would begin with Target_. Thus, if we wished to override the generated patterns in order to produce postfix, the overriding pattern names in `Postfix.ptg' would have to reflect the new prefix:

Target_PlusExp: $1 $2  "+" [Separator]
Target_StarExp: $1 $2  "*" [Separator]
Target_Parens:  $1
Target_CallExp: $1 $2      [Separator]

The basis of such an unparser consists of the the specification file for the tree grammar, modified by the two parameters (which may be given in any order see Parameterization Expressions of Eli User Interface Reference Manual):

example.fw +prefix=Target +patterns=(Postfix.ptg)

In the remainder of this document, `Basis' will be used to denote the basis of an unparser derivation. As we have seen in this section, `Basis' consists of a single file defining a tree grammar, possibly parameterized by a set of overriding PTG patterns and/or a prefix to replace the default Idem.

Deriving textual unparsers

A textual unparser is constructed by deriving the :idem product:

Basis :idem

The result of this derivation is a FunnelWeb file defining a textual unparser. That FunnelWeb file contains:

A PostScript version of the unparser definition can also be derived for documentation purposes:

Basis :idem :fwTex :ps

Deriving structural unparsers

A structural unparser is constructed by deriving the :tree product:

Basis :tree

The result of this derivation is a FunnelWeb file defining a structural unparser. That FunnelWeb file contains:

A PostScript version of the unparser definition can also be derived for documentation purposes:

Basis :tree :fwTex :ps

A structural unparser produces a description of the tree in some language. Recall that a generic functional representation is used by default. Any other standard representation language can be specified by supplying an appropriate value of the lang parameter to the derivation. For example, the following derives a structural unparser producing a description of the tree in XML:

Basis +lang=XML :tree

See Languages describing tree structure, for a list of the standard representation languages.

When none of the standard representation languages is appropriate, you can specify your own unparser generator. This unparser generator can be invoked by supplying its executable file to the derivation as the value of the lang parameter.

The most common way to specify a new unparser generator is to modify an existing specification and then use Eli to produce an executable file from that modified specification. We have already given an example of this technique (see Languages describing tree structure). In that example, file `M3.specs' defined a generator producing an unparser that represents a tree by a Modula-3 program. The executable version of that generator could be obtained in the usual way by deriving the exe product from `M3.specs' (see exe -- Executable Version of the Processor of Products and Parameters Reference). Thus the following derivation would create a Modula-3 unparser for the trees defined by `Basis':

Basis +lang=(M3.specs :exe) :tree

Here the executable file supplied as the value of the lang parameter is the one derived from the specification of the Modula-3 unparser generator.

Obtaining the structure definition

Structural unparser generators producing application-language code also deliver a definition of the data structure(s) described by that code. For example, an unparser generator producing tree descriptions in XML also delivers a "document type declaration" (DTD) file defining a grammar for those descriptions. Here's the DTD file for the expression language:

<!ENTITY % Axiom "(rule_000)">
<!ENTITY % Expression
  "(PlusExp | StarExp | Parens | IdnExp | IntExp | CallExp)">
<!ENTITY % Arguments "(ArgList)">
<!ELEMENT rule_000 (%Expression;)>
<!ELEMENT PlusExp (%Expression;, %Expression;)>
<!ELEMENT StarExp (%Expression;, %Expression;)>
<!ELEMENT Parens (%Expression;)>
<!ELEMENT IdnExp (#PCDATA)>
<!ELEMENT IntExp (#PCDATA)>
<!ELEMENT CallExp (#PCDATA, %Arguments;)>
<!ELEMENT ArgList ((%Expression;)*)>

This definition depends only on the tree grammar, not on any particular tree defined by that grammar. Thus it is built separately:

Basis +lang=XML :treeStruc

The treeStruc product is a set of files. Both the number of files in that set and their types depend on the particular structural unparser being generated. For example, the set is empty for the generic functional representation. The XML unparser generator produces a single DTD file, and the Java unparser generator produces one type-`java' file for every class in the representation.

You can list the files in the set with the following request:

Basis +lang=XML :treeStruc :ls >

To obtain copies of the definition files, make a copy of the set itself (see Extracting and Editing Objects of Eli User Interface Reference Manual):

Basis +lang=XML :treeStruc > Structure

(This request copies the generated files into a sub-directory named `Structure' of the current directory; the destination name `Structure' could be replaced by any directory name. The directory must exist before the request is made.)

Deriving multiple unparsers

Consider a translator that builds a target program tree corresponding to the source program presented to it. Perhaps we would like to make that translator output a listing of the source text formatted according to standard rules and also an XML file that defined the target program tree. This can be done by including two unparsers, one textual and the other structural.

To make the discussion concrete, let `Source_i.specs' define a processor that reads a sentence in language `i' and builds a corresponding decorated tree. `Translator.fw' specifies computations over such a source program tree that build a target program tree according to the structure defined by file `Target_j.specs'. File `Translator.specs', consisting of the following three lines, would then define a translator that would build a target program tree corresponding to a sentence in language `i':

Source_i.specs
Target_j.specs
Translate.fw

If the root of the tree grammar defined in `Source_i.specs' is Source, and the root of the tree grammar defined in `Target_j.specs' is Target, then `Translate.fw' might contain the following LIDO computation:

RULE Axiom: Root ::= Source $ Target
COMPUTE
  Target.GENTREE=Source.Code;
END;

This computation takes the target program tree that has been built as the value of attribute Source.Code, and makes it the second child of the root node (see Computed Subtrees of LIDO - Reference Manual).

Given `Translator.specs', one way to define a processor producing a listing of the source text formatted according to standard rules and also an XML file defining the target program tree would be to write the following type-`specs' file:

Translator.specs
Translator.specs                          :idem
Translator.specs +prefix=Target +lang=XML :tree
Add.fw

The first line of this file defines the translator itself, and the second line defines a textual unparser computing IdemPtg attributes. A structural unparser computing TargetPtg attributes that hold XML representations of their nodes is defined by the third line. Two of the additional computations defined by the last line of this file might be:

SYMBOL Source COMPUTE Sep_Out   (      THIS.IdemPtg);   END;
SYMBOL Target COMPUTE BP_OutFile("xml",THIS.TargetPtg); END;

These computations will write the pretty-printed source program to the standard output, and the XML representation of the target program tree to file `xml'.

Deriving unparsers from sub-grammars

Suppose that the tree grammars defined by `Source_i.specs' and `Target_j.specs' in the example of the previous section are disjoint. In that case, the processor defined there will compute unnecessary IdemPtg attributes for target tree nodes and unnecessary TargetPtg attributes for source tree nodes. These unnecessary computations can be avoided by simply changing the type-`specs' file to derive each unparser from the tree grammar to which it applies:

Translator.specs
Source_i.specs                          :idem
Target_j.specs +prefix=Target +lang=XML :tree
Add.fw

Note that no other changes are needed in any of the files.

Each of the two tree grammars on which the unparsers are based defines a complete, rooted sub-tree of the complete tree. Moreover, because the tree grammar defined by `Target_j.specs' describes a tree created by attribution, each of its rules has been given an explicit name (see Tree Construction Functions of LIDO - Reference Manual).

The fact that no more than one of the tree grammars contains unnamed rules is crucial to the success of the complete processor derivation. Recall that an unparser definition contains the definition of the tree grammar on which it is based, and every rule in that tree grammar is named. If the names were not explicit in the unparser's basis, the names in the unparser definition will have been created as part of the unparser generation. The same name creation process is applied during every unparser generation, and therefore if two unparsers generated from disjoint tree grammars with unnamed rules are combined there will be name clashes.


Previous Chapter Next Chapter Table of Contents