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
|
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
from ../tnf/tp.tnf on 12 Febuary 2003 -->
<TITLE>Tree Parsing - Summary of the Specification Language</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_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="tp_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="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="IDX38"></A>
<H1><A NAME="SEC13" HREF="tp_toc.html#SEC13">Summary of the Specification Language</A></H1>
<P>
The phrase structure of the specification language is described by the
following ambiguous grammar:
<P>
<PRE>
Source: (Include / Declaration / Rule)+ .
Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .
Rule:
Nonterm '::=' Node (':' / '::') Action ['COST' Integer] ';' /
Nonterm '::=' Nonterm ':' Action ['COST' Integer] ';' /
Nonterm '::=' Fragment ':' Action ['COST' Integer] ';' .
Action: Identifier .
Node:
Terminal /
Terminal '(' Nonterm [',' Nonterm] ')' /
Terminal '(' (Type // ',') ')' /
Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .
Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .
</PRE>
<P>
Declarations and rules are the main components of a specification.
Includes are simply names of files that are needed to define the
identifiers representing types and actions.
<A NAME="IDX39"></A>
<P>
An <CODE>Include</CODE> is a sequence of characters delimited by quotation marks
(<KBD>"</KBD>).
It is used unchanged in an <CODE>#include</CODE> directive output by the
specification language translator.
Only one <CODE>#include</CODE> directive is output for each distinct
<CODE>Include</CODE>, regardless of how many times that <CODE>Include</CODE> appears in
the specification.
<A NAME="IDX40"></A>
<P>
An <CODE>Identifier</CODE> is a sequence of letters and digits, the first of
which is a letter.
As in C, the underscore (<KBD>_</KBD>) is considered a letter.
<P>
<A NAME="IDX41"></A>
<H2><A NAME="SEC14" HREF="tp_toc.html#SEC14">Declarations</A></H2>
<P>
Each nonterminal symbol must be declared, stating the type of the value
associated with it:
<P>
<PRE>
Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .
</PRE>
<P>
Types are always represented by identifiers.
If the type is a C basic type, no further declaration is necessary.
Other types must be defined by a
<A NAME="IDX42"></A>
<CODE>typedef</CODE> construct that appears in
some file named by an <CODE>Include</CODE>
(see <A HREF="tp_4.html#SEC13">Summary of the Specification Language</A>).
<P>
Here is a set of declarations that is appropriate for the examples given
earlier in this document:
<P>
<PRE>
IntLit: int;
IntReg, FltReg: reg; "mydefs.h"
</PRE>
<P>
Because <CODE>int</CODE> is a C basic type, no further information is necessary.
<CODE>reg</CODE>, on the other hand, is declared by a <CODE>typedef</CODE>
construct that appears in file <TT>`mydefs.h'</TT>.
Thus the <CODE>Include</CODE> <SAMP>`"mydefs.h"'</SAMP> is used to provide access to
that information.
<P>
<A NAME="IDX43"></A>
<H2><A NAME="SEC15" HREF="tp_toc.html#SEC15">Rules</A></H2>
<P>
As discussed earlier, there are three kinds of rules:
node rules (see <A HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>),
chain rules (see <A HREF="tp_2.html#SEC7">Chain Rules</A>), and
fragment rules (see <A HREF="tp_2.html#SEC8">Rules Describing Tree Fragments</A>):
<P>
<PRE>
Rule:
Nonterm '::=' Node (':' / '::') Action ['COST' Integer] ';' /
Nonterm '::=' Nonterm ':' Action ['COST' Integer] ';' /
Nonterm '::=' Fragment ':' Action ['COST' Integer] ';' .
Action: Identifier .
</PRE>
<P>
Each rule has an associated
<A NAME="IDX44"></A>
action and an optional
<A NAME="IDX45"></A>
cost (which defaults to 1 if not specified).
The action is defined by an identifier, which must be defined in the
file described by one of the <CODE>Include</CODE> components of the
specification.
That definition might be an <CODE>extern</CODE> statement or a <CODE>#define</CODE>
directive (see <A HREF="tp_3.html#SEC11">Implementing Actions</A>).
The signature of the action is determined by the type of the left-hand-side
<CODE>Nonterm</CODE> and the right-hand side as discussed above
(see <A HREF="tp_3.html#SEC10">Actions and Values</A>).
<A NAME="IDX46"></A>
<P>
A node rule describes a single, possibly decorated, node of the tree being
parsed (see <A HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>):
<P>
<PRE>
Node:
Terminal /
Terminal '(' Nonterm [',' Nonterm] ')' /
Terminal '(' (Type // ',') ')' /
Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .
</PRE>
<A NAME="IDX47"></A>
<P>
<CODE>Terminal</CODE> is the symbol of the
<A NAME="IDX48"></A>
ranked alphabet that is represented by the node.
The <CODE>Node</CODE> must have <VAR>k</VAR> <CODE>Nonterm</CODE> children if
<CODE>Terminal</CODE> has arity <VAR>k</VAR>.
<P>
Each <CODE>Terminal</CODE> is also associated with a specific set
(possibly empty) of
<A NAME="IDX49"></A>
attributes.
There is no limit to the number or types of the attributes decorating a
node.
Each attribute is denoted by a <CODE>Type</CODE>, which must be either a C basic
type or an identifier defined by a <CODE>typedef</CODE> construct that appears in
some file named by an <CODE>Include</CODE>
(see <A HREF="tp_4.html#SEC13">Summary of the Specification Language</A>).
<P>
The <CODE>::</CODE> marker distinguishes a
<A NAME="IDX50"></A>
commutative node (see <A HREF="tp_3.html#SEC12">Commutative Actions</A>).
This node must have two children, and those children must be distinct
nonterminals.
A commutative node rule may have arbitrary decorations.
<P>
A fragment rule describes a fragment consisting of two or more adjacent
nodes:
<P>
<PRE>
Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .
</PRE>
<P>
Nodes participating in fragments may not be decorated.
There is no limit on the size of a fragment.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_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="tp_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="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>
|
