File: comptrees_2.html

package info (click to toggle)
eli-doc 4.4.0-4
links: PTS
area: main
in suites: sarge
size: 13,256 kB
ctags: 4,583
sloc: makefile: 42
file content (383 lines) | stat: -rw-r--r-- 17,827 bytes
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from ../tnf/comptrees.tnf on 12 Febuary 2003 -->

<TITLE>LIDO -- Computations in Trees - Dependent Computations</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM><IMG SRC="gifs/elilogo.gif" BORDER=0>&nbsp;</TD>
<TD WIDTH="25" VALIGN=BOTTOM><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>
<TD ALIGN=LEFT WIDTH="600" VALIGN=BOTTOM><IMG SRC="gifs/title.gif"></TD>
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_toc.html">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<CENTER>&nbsp;<A HREF="mailto:elibugs@cs.colorado.edu"><IMG SRC="gifs/button_mail.gif" NOSAVE BORDER=0 HEIGHT=32 WIDTH=32></A><A HREF="mailto:elibugs@cs.colorado.edu">Questions, Comments, ....</A></CENTER>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>LIDO -- Computations in Trees</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_1.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_3.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC2" HREF="comptrees_toc.html#SEC2">Dependent Computations</A></H1>
<A NAME="IDX14"></A>
<P>
Language processing requires certain computations to be executed for
each instance of a language construct. Hence the specification
associates computations to rule contexts. Usually a computation depends
on values or effects yielded by other computations. Such dependencies
are specified by <EM>attributes</EM> associated to grammar symbols. It should
be emphasized that only the necessary dependencies are specified, rather
than a complete execution order. A tree walking algorithm that executes
the computations in a suitable order is generated automatically.
<A NAME="IDX15"></A>
<A NAME="IDX16"></A>
<A NAME="IDX17"></A>
<P>
In this section we introduce the basic concepts and notations for
specification of dependent computations in trees. The examples refer to
the tree grammar of the previous section. It will be shown how
expression evaluation and a simple transformation is specified.
<P>
<H2><A NAME="SEC3" HREF="comptrees_toc.html#SEC3">Value Dependencies</A></H2>
<A NAME="IDX18"></A>
<P>
Let us first describe computations that evaluate any given expression
tree and print the result:
<A NAME="IDX19"></A>
<P>
<PRE>
   ATTR value: int;

   RULE: Root ::=  Expr  COMPUTE
      printf ("value is %d\n", Expr.value);
   END;
</PRE>
<P>
<A NAME="IDX20"></A>
<P>
The above <CODE>RULE</CODE> associates the <CODE>printf</CODE> computation to the
rule context. The notation repeats the rule as shown in
the tree grammar and adds any set of computations between <CODE>COMPUTE</CODE>
and <CODE>END</CODE>. Computations are denoted like calls of C functions.
The arguments are C literals, again function calls, or attributes.
(User defined
functions are implemented in specifications files separate from the .lido
specification, See  <A HREF="comptrees_6.html#SEC13">Interactions within Eli</A>.)
<P>
The above computation uses the <CODE>value</CODE> attribute of the
<CODE>Expr</CODE> subtree of this context. In general any attribute of any
symbol that occurs in the rule context may be used in a computation of
that context.
<A NAME="IDX21"></A>
<A NAME="IDX22"></A>
<P>
In this case the <CODE>value</CODE> attribute is the integral value computed
for the expression. The <CODE>ATTR</CODE> construct states that its type is
<CODE>int</CODE>. In fact it specifies that type for any attribute 
named <CODE>value</CODE> that is just used with a symbol.
Any C type name may be specified.
Such a type association is valid throughout the whole specification.
It can be overridden by attribute properties specified in <CODE>SYMBOL</CODE>
constructs.
<P>
The above computation depends on a computation that yields
<CODE>Expr.value</CODE>.  Since the internal structure of the <CODE>Expr</CODE>
subtree determines how its value is to be computed, those computations
are associated with the two lower adjacent contexts that have <CODE>Expr</CODE>
on the left-hand side of their production, as shown in the computations
of Figure 3.
<P>
<PRE>
   TERM Number: int;

   RULE: Expr ::= Number COMPUTE
     Expr.value = Number;
   END;

   RULE: Expr ::= Expr Opr Expr COMPUTE
     Expr[1].value = Opr.value;
     Opr.left  = Expr[2].value;
     Opr.right = Expr[3].value;
   END;

   SYMBOL Opr: left, right: int;

   RULE: Opr ::=  '+'  COMPUTE
     Opr.value  =  ADD(Opr.left, Opr.right);
   END;

   RULE: Opr ::=  '*'  COMPUTE
     Opr.value = MUL(Opr.left, Opr.right);
   END;
</PRE>
Figure 3: Computation of Expression Values
<A NAME="IDX23"></A>
<A NAME="IDX24"></A>
<P>
The <CODE>TERM</CODE> construct states that the terminal symbol <CODE>Number</CODE> carries
a value of type <CODE>int</CODE> to be used in computations like that of 
the first rule.
<A NAME="IDX25"></A>
<A NAME="IDX26"></A>
<P>
Computations that yield a value to be used in other computations are
denoted like an assignment to an attribute. But it must be emphasized
that they have to obey the single assignment rule: There must be exactly
one computation for each attribute instance in every tree.
<A NAME="IDX27"></A>
<P>
The values of binary expressions are computed in each of the two 
<CODE>Opr</CODE> contexts and passed to the root of the binary subtree. The
<CODE>ADD</CODE> and <CODE>MUL</CODE> operations are predefined macros in LIDO.
<CODE>Opr</CODE> has three attributes, the values of the left and right
operands and the result of the operation. 
The attributes <CODE>left</CODE>
<A NAME="IDX28"></A>
and <CODE>right</CODE> are associated to <CODE>Opr</CODE> by the <CODE>SYMBOL</CODE> construct
which states their type to be <CODE>int</CODE>. As only the <CODE>Opr</CODE> symbol
has attributes of these names thy are not introduced by an <CODE>ATTR</CODE>
construct.
The attribute <CODE>value</CODE> is
associated to <CODE>Opr</CODE> by just using it in a computation. Its type
is specified by the <CODE>ATTR</CODE> construct explained above.
<A NAME="IDX29"></A>
<A NAME="IDX30"></A>
<A NAME="IDX31"></A>
<A NAME="IDX32"></A>
<A NAME="IDX33"></A>
<A NAME="IDX34"></A>
<P>
The three attributes belong to two
conceptually different classes: <CODE>Opr.value</CODE> is computed in the
lower context, as <CODE>Expr.value</CODE> (called synthesized or <CODE>SYNT</CODE>
attribute), whereas <CODE>Opr.left</CODE> and <CODE>Opr.right</CODE> are computed in
the upper context (called inherited or <CODE>INH</CODE> attributes). Any
attribute must belong to either of the classes in order to obey
the single assignment rule.
<P>
There are three (in this case trivial) computations specified in the context
for binary expressions. It should be pointed out that their textual order
is irrelevant: The execution order is determined by their dependencies.
In this case the computation of <CODE>Expr[1].value</CODE> will be executed
last. The attribute notation requires indexing of symbol names, if a symbol
occurs more than once in a production, like <CODE>Expr</CODE>. The indices
enumerate the occurrences of a symbol in the production from left to right
beginning with 1.
<P>
<H2><A NAME="SEC4" HREF="comptrees_toc.html#SEC4">State Dependencies</A></H2>
<A NAME="IDX35"></A>
<P>
Our second example specifies how to print expressions in postfix
notation, e. g. <CODE>1 2 3 * +</CODE> for the given expression
<CODE>1 + 2 * 3</CODE>. It demonstrates how computations that yield an
effect rather than a value are specified to depend on each other.
<P>
We may start from a specification that just outputs each number and
operator, given in Figure 4. It causes each instance of numbers and
operators in the tree being printed.  Since no dependencies are
specified yet, they may occur in arbitrary order in the output.
<P>
<PRE>
   RULE: Root  ::= Expr  COMPUTE
     printf ("\n");
   END;

   RULE: Expr ::= Number COMPUTE
     printf ("%d " , Number)
   END;

   RULE: Opr   ::=  '+' COMPUTE
     printf ("+ ");
   END;

   RULE: Opr   ::= '*' COMPUTE
     printf ("* ");
   END;
</PRE>
Figure 4: Output of Expression Components
<A NAME="IDX36"></A>
<A NAME="IDX37"></A>
<A NAME="IDX38"></A>
<P>
In order to achieve the desired effect we have to specify that a
computation is not executed before certain preconditions hold which are
established by a postcondition of some other computations. We specify
such conditions by attributes that do not have values, but describe a
computational state. In Figure 5 we associate attributes <CODE>print</CODE>
and <CODE>printed</CODE> to <CODE>Expr</CODE> and <CODE>Opr</CODE>.  <CODE>Expr.print</CODE>
describes the state where the output is produced so far such that the
text of the <CODE>Expr</CODE> subtree can be appended. <CODE>Expr.printed</CODE>
describes the state where the text of this subtree is appended
(correspondingly for <CODE>Opr.print</CODE> and <CODE>Opr.printed</CODE>).
<P>
<PRE>
   RULE: Root ::= Expr COMPUTE
     Expr.print = "yes";
     printf ("\n") &#60;- Expr.printed;
   END;

   RULE: Expr ::= Number COMPUTE
     Expr.printed = printf ("%d ", Number) &#60;- Expr.print;
   END;

   RULE: Opr  ::= '+' COMPUTE
     Opr.printed = printf ("+ ") &#60;- Opr.print;
   END;

   RULE: Opr  ::= '*' COMPUTE
     Opr.printed = printf ("* ") &#60;- Opr.print;
   END;

   RULE: Expr  ::= Expr Opr Expr COMPUTE
     Expr[2].print = Expr[1].print;
     Expr[3].print = Expr[2].printed;
     Opr.print = Expr[3].printed;
     Expr[1].printed = Opr.printed;
   END;
</PRE>
Figure 5: Dependencies for Producing Postfix Expressions
<P>
The general form of dependent computations as used in Figure 5 is
<P>
<PRE>
 <I>postcondition</I> = <I>computation</I> <CODE>&#60;-</CODE> <I>precondition</I>
</PRE>
<P>
If the postcondition is not used elsewhere, it (and the =) is omitted.
If the postcondition is directly established by another condition, the
computation and the <CODE>&#60;-</CODE> are omitted. If a condition
initially holds it is denoted by some literal, like "yes" in
the <CODE>Root</CODE> context.
A computation may depend on several preconditions:
<P>
<PRE>
 &#60;- (X.a, Y.b).
</PRE>
<P>
Computations may also depend on the computation of value carrying
attributes without using their value, or computations may yield a value
and also depend on some preconditions.
<A NAME="IDX39"></A>
<P>
State attributes which do not carry a value have the type <CODE>VOID</CODE>. They
need not be introduced by a <CODE>SYMBOL</CODE> or an <CODE>ATTR</CODE> construct.
They may be just used in a computation. But the same consistency and
completeness requirements apply for them as for value carrying attributes.
<P>
It should be noted that the specifications of several tasks,
e. g. computing expression values and producing postfix output may be
combined in one specification for a language processor that solves all
of them. It is a good style to keep the specifications of
different tasks separate, rather than to merge the
computations for each single context.  You may specify several sets of
computations at different places. They are accumulated for each rule
context. LIDO specifications may reside in any number of <CODE>.lido</CODE>
files or output fragments of <CODE>.fw</CODE> files. Hence, modular
decomposition and combining related specifications of different
types is encouraged.
<P>
See  <A HREF="comptrees_3.html#SEC8">Left-to-Right Dependencies</A>, for an example of expressing the
above example using left-to-right depencencies.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_1.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_3.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>