1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
|
<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 - Symbol 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> </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> <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_3.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_5.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="SEC9" HREF="comptrees_toc.html#SEC9">Symbol Computations</A></H1>
<A NAME="IDX53"></A>
<P>
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.
<P>
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.
<P>
In the following we demonstrate the use of symbol computations, and
introduce a construct for their reuse.
<P>
<H2><A NAME="SEC10" HREF="comptrees_toc.html#SEC10">Basic Symbol Computations</A></H2>
<P>
Consider the expression grammar given in the example of <A HREF="comptrees_2.html#SEC3">Value Dependencies</A>.
For the purpose of this
example assume that we want to trace the computation of expression
values, and print
<CODE>Expr.value</CODE> for each <CODE>Expr</CODE> node. We could associate that
computation to both lower <CODE>Expr</CODE> context.
But this computation does not refer to those
particular contexts, it only depends on one <CODE>Expr</CODE> attribute. Hence
we better associate it to the <CODE>Expr</CODE> symbol:
<P>
<PRE>
SYMBOL Expr COMPUTE
printf ("expression value %d in line %d\n", THIS.value, LINE);
END;
</PRE>
<A NAME="IDX54"></A>
<A NAME="IDX55"></A>
<P>
Symbol computations may use attributes of the symbol by the notation
<CODE>THIS.AttributeName</CODE>.
<P>
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.
<P>
<PRE>
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;
</PRE>
Figure 12: Symbol Computations for Usage Count
<A NAME="IDX56"></A>
<A NAME="IDX57"></A>
<P>
An attribute that is defined by a symbol computation has to be
classified <CODE>SYNT</CODE> or <CODE>INH</CODE>, like <CODE>SYNT.Count</CODE> above (instead
of <CODE>THIS.Count</CODE> if the attribute were used in the computation). It
determines whether the computation is intended for the lower <CODE>SYNT</CODE>
or the upper <CODE>INH</CODE> contexts of the symbol.
<A NAME="IDX58"></A>
<A NAME="IDX59"></A>
<A NAME="IDX60"></A>
<P>
The symbol computation of <CODE>Block</CODE> above shows that
<CODE>CONSTITUENTS</CODE> constructs may be used in symbol computations as
well as in rule contexts. The same applies to <CODE>INCLUDING</CODE> and
<CODE>CHAIN</CODE> as shown below.
<P>
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
<CODE>Usage</CODE> and <CODE>Block</CODE> occur. The productions for <CODE>Block</CODE>
and for <CODE>Usage</CODE> may be modified without affecting these symbol
computations.
<P>
Now consider the computation of nesting depth of blocks in Figure 6. The
computation of <CODE>Block.depth</CODE> can also be
specified as a symbol computation:
<P>
<PRE>
SYMBOL Block COMPUTE
INH.depth = ADD (INCLUDING Block.depth, 1);
END;
</PRE>
<P>
In this case the computation is intended to go to the upper contexts of <CODE>Block</CODE>, indicated by <CODE>INH.depth</CODE>. That is correct for any context where <CODE>Block</CODE> is a descendant of a <CODE>Statement</CODE>. But in the <CODE>Program</CODE> context
the <CODE>depth</CODE> of the root <CODE>Block</CODE> must be computed to 0, rather than by
the above symbol computation. So we keep the computation of Figure 6:
<P>
<PRE>
RULE: Root ::= Block COMPUTE
Block.depth = 0;
END;
</PRE>
<P>
It overrides the above symbol computation: A rule computation overrides
a symbol computation for the same attribute.
<P>
The example demonstrates a design rule:
<BLOCKQUOTE>
General context independent computations are specified by symbol
computations. They may be overridden in special cases by computations
in rule contexts.
</BLOCKQUOTE>
<A NAME="IDX61"></A>
<P>
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.
<P>
Finally we demonstrate how <CODE>CHAINS</CODE> 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 <CODE>THIS.RelAdr</CODE> occurs twice with different manings: it
refers to the incoming <CODE>CHAIN</CODE> value in the call of <CODE>ADD</CODE>,
whereas the outgoing <CODE>CHAIN</CODE> value is defined on the
lefthand-side of the computation. <CODE>CHAIN</CODE> accesses are distinguished
by their use or definition, rather than by <CODE>SYNT</CODE> and <CODE>INH</CODE> as
in case of attributes.
<P>
<PRE>
CHAIN RelAdr: int;
SYMBOL Block COMPUTE
CHAINSTART HEAD.RelAdr = 0;
END;
SYMBOL Definition COMPUTE
THIS.RelAdr = ADD (THIS.RelAdr, VariableSize);
END;
</PRE>
Figure 13: Symbol Computations for Addresses of Variables
<P>
<H2><A NAME="SEC11" HREF="comptrees_toc.html#SEC11">Reuse of Symbol Computations</A></H2>
<A NAME="IDX62"></A>
<A NAME="IDX63"></A>
<P>
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.)
<A NAME="IDX64"></A>
<P>
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 <CODE>CLASS</CODE> symbols that do not occur in the
tree grammar. In Figure 14 use a <CODE>CHAIN</CODE> as in the examples of
<A HREF="comptrees_3.html#SEC8">Left-to-Right Dependencies</A>.
<P>
<PRE>
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;
</PRE>
Figure 14: Computationel Concept Occurrence Count
<P>
The above computations correspond to those for computing addresses in
Figure 11. They are extended by computations of attributes
<CODE>TotalOccs</CODE> (for the total number of enumerated constructs) and
<CODE>OccNo</CODE> (for the current number of the enumerated element). Further
computations may use these attributes, instead of referring to the
<CODE>CHAIN</CODE>, which can be considered as an implementation mechanism of the
enumeration computation.
<P>
The <CODE>CLASS</CODE> symbols <CODE>OccRoot</CODE> and <CODE>OccElem</CODE> 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 <CODE>CLASS</CODE> <CODE>SYMBOL</CODE>.
<P>
We now apply this count specification to symbols of our tree grammar:
<P>
<PRE>
SYMBOL Block INHERITS OccRoot END;
SYMBOL Definition INHERITS OccElem END;
</PRE>
<P>
<CODE>Block</CODE> inherits the role <CODE>OccRoot</CODE> and <CODE>Definition</CODE>
inherits the role <CODE>OccElem</CODE>. Those constructs yield the same effect
as if the computations for <CODE>OccRoot</CODE> (<CODE>OccElem</CODE>) were
associated to <CODE>Block</CODE> (<CODE>Definition</CODE>).
As a consequence further computations may use the attributes
<CODE>Definition.OccNo</CODE> (the number of a definition in a block), and
<CODE>Block.TotalOccs</CODE> (the total number of definitions in that block).
<P>
The second enumeration application is specified in the same way:
<P>
<PRE>
SYMBOL Statement INHERITS OccRoot END;
SYMBOL Usage INHERITS OccElem END;
</PRE>
<P>
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.
<P>
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 <CODE>CLASS</CODE> symbol for this computation:
<P>
<PRE>
CLASS SYMBOL PrintTotalOccs COMPUTE
printf ("construct in line %d has %d elements\n",
LINE, THIS.TotalOccs);
END;
</PRE>
<P>
This computation is applied by adding
<P>
<PRE>
SYMBOL Block INHERITS PrintTotalOccs END;
</PRE>
<P>
to the specification and correspondingly for <CODE>Definition</CODE>. The two
<CODE>INHERITS</CODE> constructs can also be combined to one:
<P>
<PRE>
SYMBOL Block INHERITS OccRoot, PrintTotalOccs END;
</PRE>
<P>
We alternatively could extend the role of the enumeration root
<CODE>OccRoot</CODE> such that the total number is always printed by
<P>
<PRE>
CLASS SYMBOL OccRoot INHERITS PrintTotalOccs END;
</PRE>
<P>
In this case each symbol that inherits the computation of <CODE>OccRoot</CODE>
also inherits the computation of <CODE>PrintTotalOccs</CODE>.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_3.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_5.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>
|
