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
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
|
<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 - Interactions within Eli</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_5.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_7.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="SEC13" HREF="comptrees_toc.html#SEC13">Interactions within Eli</A></H1>
<A NAME="IDX66"></A>
<P>
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.
<P>
<H2><A NAME="SEC14" HREF="comptrees_toc.html#SEC14">Supplying Tree Computation Specifications to Eli</A></H2>
<A NAME="IDX67"></A>
<P>
Specifications as described in this document are written in files named
<CODE>x.lido</CODE> where <CODE>x</CODE> is an arbitrary name. The specification of
larger tasks should be decomposed into single subtasks
specified in separate files each.
<P>
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 <CODE>.specs</CODE> file or by generating them from a
<CODE>.fw</CODE> file. <A HREF="comptrees_6.html#SEC15">Tree Construction</A> describes another
contribution to the set
of <CODE>.lido</CODE> files for tree grammar specification.
<P>
It should be pointed out that <CODE>RULE</CODE>, <CODE>SYMBOL</CODE>, <CODE>ATTR</CODE>,
and <CODE>CHAIN</CODE> 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 <CODE>RULE</CODE> or
<CODE>SYMBOL</CODE> name are accumulated. The LIGA system processes the
concatenation of all <CODE>.lido</CODE> files. Hence the reference manual for
the language LIDO (see <A HREF="lidoref_toc.html">LIDO - Reference Manual</A>)
refers to that compound specification disregarding the composition of
single files.
<A NAME="IDX68"></A>
<A NAME="IDX69"></A>
<P>
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
<A HREF="modlib_toc.html">Specification Module Library</A>.
The inheritance mechanism as
introduced in section <A HREF="comptrees_4.html#SEC11">Reuse of Symbol Computations</A> is applied, and the
use of the module
is stated in a <CODE>.specs</CODE> or a <CODE>.fw</CODE> file as described in that document.
<P>
<H2><A NAME="SEC15" HREF="comptrees_toc.html#SEC15">Tree Construction</A></H2>
<A NAME="IDX70"></A>
<A NAME="IDX71"></A>
<P>
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.
<A NAME="IDX72"></A>
<A NAME="IDX73"></A>
<P>
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 (<CODE>.con</CODE> and
<CODE>.sym</CODE> files) for those parts of the language which are known
and fixed, specify tree grammar rules (in <CODE>.lido</CODE> 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.
<A NAME="IDX74"></A>
<A NAME="IDX75"></A>
<P>
An Eli tool
(Maptool, see <A HREF="syntax_toc.html">Syntactic Analysis Manual</A>)
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 precendences
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.
<A NAME="IDX76"></A>
<A NAME="IDX77"></A>
<A NAME="IDX78"></A>
<A NAME="IDX79"></A>
<P>
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 <CODE>'begin'</CODE> or <CODE>':='</CODE>.
For each named terminal,
like <CODE>Name</CODE> or <CODE>Number</CODE>, a <CODE>.gla</CODE> 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 <CODE>TERM</CODE> construct, e. g.
<P>
<PRE>
TERM Name: int;
</PRE>
<P>
Since GLA generated scanners pass such token information by
values of type <CODE>int</CODE>, LIGA assumes that type if the <CODE>TERM</CODE>
construct is omitted for a named terminal. Hence, the above
<CODE>TERM</CODE> construct is redundant for terminals created by GLA.
It is needed for terminal created by other scanners or by
computed tree extension.
<P>
<H2><A NAME="SEC16" HREF="comptrees_toc.html#SEC16">Implementing Tree Computations</A></H2>
<A NAME="IDX80"></A>
<A NAME="IDX81"></A>
<P>
The implementation of functions, types, constants, and variables
used in tree computations is
not specified within the <CODE>.lido</CODE> 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 <CODE>stdio.h</CODE> (like <CODE>printf</CODE>), or if they are
predefined in LIDO (like <CODE>ADD</CODE>,
see <A HREF="lidoref_12.html#SEC21">Predefined Entities of LIDO -- Reference Manual</A>,
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.
<A NAME="IDX82"></A>
<A NAME="IDX83"></A>
<A NAME="IDX84"></A>
<A NAME="IDX85"></A>
<A NAME="IDX86"></A>
<A NAME="IDX87"></A>
<P>
It is recommended to apply a modular style for those implementations:
Supply C modules consisting of a <CODE>m.c</CODE> and a <CODE>m.h</CODE> file each,
where the latter describes the objects exported by the module. (It is
also possible to implement computations by CPP-macros.)
<P>
The file names <CODE>m.h</CODE> and <CODE>m.c</CODE> of all such user supplied
C-modules have to be mentioned in some <CODE>.specs</CODE> file. Furthermore
one or several <CODE>.head</CODE> files or <CODE>.HEAD.phi</CODE> files have to be
provided. They have to contain a line
<P>
<PRE>
#include "m.h"
</PRE>
<P>
for each module <CODE>m</CODE>, making it available to the generated
evaluator. It is recommended to protect each <CODE>m.h</CODE> file against
multiple inclusion by suitable CPP-commands.
<A NAME="IDX88"></A>
<A NAME="IDX89"></A>
<A NAME="IDX90"></A>
<A NAME="IDX91"></A>
<P>
If a module needs some operations for initialization or finalization
they can be written (as function calls) into files <CODE>m.init</CODE> or
<CODE>m.finl</CODE> (or into <CODE>.INIT.phi</CODE> or <CODE>.FINL.phi</CODE> files).
<P>
<H2><A NAME="SEC17" HREF="comptrees_toc.html#SEC17">Specification Errors</A></H2>
<A NAME="IDX92"></A>
<A NAME="IDX93"></A>
<P>
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
<P>
<PRE>
x.specs:exe:warning
</PRE>
<A NAME="IDX94"></A>
<P>
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
<P>
<PRE>
x.specs:exe:help
</PRE>
<P>
Violations of the LIDO specification language definition are reported
with references to the <CODE>.lido</CODE> 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:
<P>
A report saying
<P>
<PRE>
VOID attribute not allowed here
</PRE>
<A NAME="IDX95"></A>
<P>
in most cases indicates that an attribute is used without specifying its
type, <CODE>VOID</CODE> is assumed then. The reason of such an error often is a
misspelled attribute name.
<P>
It may be helpful to derive
<P>
<PRE>
x.specs:showFe
</PRE>
<A NAME="IDX96"></A>
<P>
and look at the file <CODE>attr.info</CODE>. It gives an overview on all
attributes the system found so far in the <CODE>.lido</CODE> files. (Attributes
that stem from inheritance are not yet found in this phase.)
<P>
A report saying
<P>
<PRE>
attribute class in conflict
</PRE>
<A NAME="IDX97"></A>
<P>
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.
<P>
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
<A NAME="IDX98"></A>
<A NAME="IDX99"></A>
<P>
<PRE>
x.specs:ExpInfo
</PRE>
<P>
That file describes how each remote access construct can be replaced by
a set of equivalent computations propagating the accessed values through
adjacent contexts.
<P>
<A NAME="IDX100"></A>
<P>
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
<P>
<PRE>
x.specs:OrdInfo
</PRE>
<P>
or by using the tool <CODE>gorto</CODE> (see <A HREF="gorto_toc.html">GORTO - Graphical Dependency Analyzer</A>)
for tracing dependencies graphically.
<P>
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 <CODE>gorto</CODE>. It is
highly recommended NOT to try to avoid such situations before they are
reported, since they occur rather seldom.
<P>
<A NAME="IDX101"></A>
<A NAME="IDX102"></A>
<P>
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
<CODE>visitprocs.c</CODE>. 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.
<P>
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.
<P>
If functions are used in a <CODE>.lido</CODE> file but are not made available
for the evaluator, the error might not be reported before the whole
program is linked.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_5.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_7.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>
|
