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
|
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
from ../tnf/tp.tnf on 12 Febuary 2003 -->
<TITLE>Tree Parsing - Actions Carried Out During Parsing</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>Tree Parsing</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_2.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_4.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_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>
<A NAME="IDX23"></A>
<H1><A NAME="SEC9" HREF="tp_toc.html#SEC9">Actions Carried Out During Parsing</A></H1>
<P>
Each rule has an associated action, written as an
identifier:
<P>
<PRE>
N0 ::= s(Ni,aj) : Action1
N0 ::= N1 : Action2
N0 ::= s(t(Ni),Nj) : Action3
</PRE>
<P>
The action associated with a rule is carried out each time the rule is used
in a derivation.
Each rule may be associated with a distinct action, or a single action may
be associated with several rules.
<P>
<H2><A NAME="SEC10" HREF="tp_toc.html#SEC10">Actions and Values</A></H2>
<P>
The action carried out for each use of a rule in a derivation is a function
application.
<A NAME="IDX25"></A>
<A NAME="IDX24"></A>
The action identifier is the name of the function, and the arguments to
which it is applied are the values of the nonterminals and attributes
appearing on the right-hand side of the pattern.
These values are taken in order from left to right.
The result of the function becomes the value of the nonterminal appearing on
the left-hand side of the pattern.
<P>
For example, consider one of the rules of the specification introduced above
(see <A HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>), augmented by an action called
<CODE>IntR_loadconst</CODE>:
<P>
<PRE>
IntReg ::= IntegerVal(int) : IntR_loadconst
</PRE>
For each use of the rule <CODE>IntReg ::= IntegerVal(int)</CODE> in some
derivation, the function named <CODE>IntR_loadconst</CODE> will be applied to the
integer-valued attribute of the leaf.
The result of this function application will become the value of the
<CODE>IntReg</CODE> nonterminal.
<A NAME="IDX26"></A>
<A NAME="IDX27"></A>
<P>
The types of the attribute values are stated explicitly in the rules.
<A NAME="IDX29"></A>
<A NAME="IDX28"></A>
A type is also associated with each nonterminal by means of a declaration
(see <A HREF="tp_4.html#SEC13">Summary of the Specification Language</A>).
For example, the type associated with the nonterminal <CODE>IntReg</CODE> might
be structure of type <CODE>reg</CODE> defined as follows:
<P>
<PRE>
typedef struct { int register; PTGNode code; } reg;
</PRE>
Here the <CODE>register</CODE> field would be the number of the register holding
the result and the <CODE>code</CODE> field would be a representation of the
assembly language instructions producing the result in that register
(see <A HREF="ptg_1.html#SEC1">Introduction of Pattern-Based Text Generator</A>).
<P>
In this case, execution of <CODE>IntR_loadconst</CODE> would allocate a register
and create a PTG node representing the assembly language instruction
loading the integer constant specified by the integer-valued attribute of
the leaf into that register.
It would return a type-<CODE>reg</CODE> structure containing that information.
This structure would then become the value of the <CODE>IntReg</CODE> nonterminal.
<P>
Here's another example of a rule, this time augmented by an action called
<CODE>IntRR_sub</CODE>:
<P>
<PRE>
IntReg ::= Minus(IntReg,IntReg) : IntRR_sub
</PRE>
The function named <CODE>IntRR_sub</CODE> will be applied to the values returned
by the two children of the <CODE>Minus</CODE> node for each use of
<CODE>IntReg ::= Minus(IntReg,IntReg)</CODE> in some derivation,
and the result will become the value of the <CODE>IntReg</CODE> nonterminal on
the left-hand side of the rule.
The first argument of <CODE>IntRR_sub</CODE> would be the value returned by the
action associated with the left child of the <CODE>Minus</CODE> node, and the
second would be the value returned by the right child.
<P>
Execution of <CODE>IntRR_sub</CODE> might allocate a register to hold the result
of the subtraction and create a PTG node representing the sequence
consisting of the PTG nodes passed to it as operands followed by
the assembly language instruction that computes the difference of two
integer values in registers and leaves the result in a register.
<CODE>IntRR_sub</CODE> would return a type-<CODE>reg</CODE> structure, which would
become the value of the <CODE>IntReg</CODE> nonterminal on the left-hand side of
the rule.
<P>
Each nonterminal is associated with a function whose
name is <CODE>TP_</CODE> followed by the name of the nonterminal.
This function takes as its only argument a tree (of type <CODE>TPNode</CODE>,
see <A HREF="tp_1.html#SEC4">Node Construction Functions</A>), and returns a value of
the type associated with the nonterminal.
Whenever one of these functions is applied to the root of a tree,
it parses that tree.
The parse finds the cheapest derivation of the function's nonterminal
at the root of the tree.
All of the actions implied by the derivation are executed, and the result
of the function is the result delivered by the action executed at the root
of the tree.
The only guarantee one can make about the order in which the actions are
executed is that it respects the data flow constraints implied by the
function applications.
<P>
A specification with all of the rules described so far
has only two nonterminals (<CODE>IntReg</CODE> and <CODE>FltReg</CODE>).
The translator will generate two parsing functions that can be applied
to the root of a tree:
<P>
<A NAME="IDX30"></A>
<U>:</U> reg <B>TP_IntReg</B> <I>(TPNode <VAR>tree</VAR>)</I><P>
A derivation for the tree rooted in <VAR>tree</VAR> in which the root is
interpreted as an <CODE>IntReg</CODE> will be sought.
If such a derivation is possible, the actions associated with the steps for
the cheapest will be executed.
The result of the action associated with the derivation step at the root
will be returned.
Otherwise the program will terminate abnormally.
<P>
<A NAME="IDX31"></A>
<U>:</U> reg <B>TP_FltReg</B> <I>(TPNode <VAR>tree</VAR>)</I><P>
A derivation for the tree rooted in <VAR>tree</VAR> in which the root is
interpreted as a <CODE>FltReg</CODE> will be sought.
If such a derivation is possible, the actions associated with the steps for
the cheapest will be executed.
The result of the action associated with the derivation step at the root
will be returned.
Otherwise the program will terminate abnormally.
<P>
The program will terminate abnormally when a requested derivation is not
possible.
This condition always arises from a design fault; either the patterns are
incomplete, or the tree to be parsed is malformed.
<P>
<A NAME="IDX32"></A>
<H2><A NAME="SEC11" HREF="tp_toc.html#SEC11">Implementing Actions</A></H2>
<P>
An action is a function application, and the name of the action is the
function to be invoked.
The rule with which the action is associated determines the signature of
the function:
Recall that the arguments of the function are the nonterminals and
attributes appearing on the right-hand side of the associated rule, in
order from left to right.
The result of the function becomes the value of the nonterminal appearing
on the left-hand side of the associated rule.
Each nonterminal and attribute has a fixed type.
<P>
Function application can be implemented either by calling a
<A NAME="IDX33"></A>
macro or by invoking a
<A NAME="IDX34"></A>
routine.
If the action requires a routine invocation, and the
<A NAME="IDX36"></A>
<A NAME="IDX35"></A>
signature of the
routine to be invoked matches the signature determined by the rule, then
the routine name can be used directly as the action.
Often, however, there is a mismatch between the signatures.
In that case, the action can be made the name of a macro that rearranges
arguments, inserts constants, or does whatever else is needed to correct
the mismatch.
<P>
<A NAME="IDX37"></A>
<H2><A NAME="SEC12" HREF="tp_toc.html#SEC12">Commutative Actions</A></H2>
<P>
Many computers have instruction sets that are asymmetric in their treatment
of operands.
For example, a machine with two-operand instructions may allow only the
second of these operands to be a literal value.
If two values in registers are being added, the "add register"
instruction is used, but if a literal value were being added to a value in a
register the "add immediate" instruction would be necessary.
One rule characterizing an integer addition operation for such a machine,
with an action to generate the "add immediate" instruction,
might be the following:
<P>
<PRE>
IntReg ::= Plus(IntReg,IntLit) : IntRI_add
</PRE>
(Here the nonterminal <CODE>IntLit</CODE> represents the interpretation
"a literal integer".)
<P>
Notice that the children of the <CODE>Plus</CODE> node in this rule have
different interpretations; this rule cannot be used in a derivation that
interprets the left child of the <CODE>Plus</CODE> node as an <CODE>IntLit</CODE> and
the right child as an <CODE>IntReg</CODE>.
<P>
Because addition is commutative, however, it is possible to interchange
the children of the <CODE>Plus</CODE> node without changing the resulting value.
Therefore if a derivation interprets the left child of the <CODE>Plus</CODE> node
as an <CODE>IntLit</CODE> and the right child as an <CODE>IntReg</CODE>, the tree
parser should be able to simply invoke the <CODE>IntRI_add</CODE> action with the
two operands reversed.
<P>
This possibility is indicated by using <CODE>::</CODE> instead of <CODE>:</CODE>
between the rule and its associated action:
<P>
<PRE>
IntReg ::= Plus(IntReg,IntLit) :: IntRI_add
</PRE>
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_2.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_4.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_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>
|
