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
|
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
from ../tnf/tp.tnf on 12 Febuary 2003 -->
<TITLE>Tree Parsing - Table of Contents</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">
<A HREF="tp.ps"><IMG SRC="gifs/print.gif" ALT="Open Postscript File" BORDER="0" ALIGN=RIGHT></A>
<H1>Tree Parsing</H1>
<P>
This document describes a language for defining tree parsers.
Tree parsers can be used to transform, interpret and print tree-structured
data.
They are particularly useful for problems in which the action at a node
depends strongly on the context in which that node appears.
Code selection is a common example of this kind of problem:
The code selected for an operation is largely determined by that
operation's context.
<P>
Consider the problem of selecting an instruction to implement an integer
addition operation on a typical RISC machine.
The machine has two integer add instructions, one taking two register
operands and the other taking a register and a constant operand.
Both of these instructions leave their result in a register.
Load and store instructions also take a register and a constant operand,
which are integers added to obtain the memory address.
Integer addition is a commutative operation, so the instructions involving
constant operands can be used regardless of <EM>which</EM> operand is
constant.
The code selector must perform a distinct action in each of the five
possible situations resulting from these conditions.
<P>
The language described in this document allows the user to specify the
possible situations and required actions in an intuitive way as a set of
pattern/action rules:
<P>
<PRE>
IntReg ::= Plus(IntReg,IntReg) : IntRR_add
IntReg ::= Plus(IntReg,IntLit) :: IntRI_add
MemAdr ::= Plus(IntReg,IntLit) :: RI_address
</PRE>
<P>
Here the first rule specifies that one possible situation is to compute
a value into an integer register by adding the contents of two integer
registers.
The required action in that situation is the <CODE>IntRR_add</CODE> action.
Two situations are specified by the second rule.
In one the left operand is in an integer register and the right operand is
an integer constant, and in the other the operands are reversed.
Both situations can be handled by the <CODE>IntRI_add</CODE> action,
provided that the operands are always presented to it in the order stated
(first the register operand, then the constant operand).
<P>
In addition to supplying the set of rules as a type-<TT>`tp'</TT> file,
a user must make certain that implementations of the actions
(like <CODE>IntRR_add</CODE>, <CODE>IntRI_add</CODE> and <CODE>RI_address</CODE>
in the above example) are available.
The actions might be written by the user or produced by other components of
the system like PTG
(see <A HREF="ptg_toc.html">Top of Pattern-Based Text Generator</A>).
<P>
Actions are arbitrary functions.
They may or may not have results, and may or may not have side effects.
The effect of the whole process is nothing more than the sum total of the
effects of the actions.
<P>
To get the specified actions executed,
the user must first call functions that are generated from the set of rules.
These functions create a tree embodying the contextual relationships
among the operators (like <CODE>Plus</CODE> above).
Once the complete tree has been established, another generated function
is called to parse it (e.g. to determine whether a given node is
an <CODE>IntReg</CODE> or <CODE>IntLit</CODE> in the example above).
Action routines are invoked as a side effect of the parse.
<P>
<P>
<UL>
<LI><A NAME="SEC1" HREF="tp_1.html#SEC1">The Tree To Be Parsed</A>
<UL>
<LI><A NAME="SEC2" HREF="tp_1.html#SEC2">Tree Structure</A>
<LI><A NAME="SEC3" HREF="tp_1.html#SEC3">Decorating Nodes</A>
<LI><A NAME="SEC4" HREF="tp_1.html#SEC4">Node Construction Functions</A>
</UL>
<LI><A NAME="SEC5" HREF="tp_2.html#SEC5">The Tree Patterns</A>
<UL>
<LI><A NAME="SEC6" HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>
<LI><A NAME="SEC7" HREF="tp_2.html#SEC7">Chain Rules</A>
<LI><A NAME="SEC8" HREF="tp_2.html#SEC8">Rules Describing Tree Fragments</A>
</UL>
<LI><A NAME="SEC9" HREF="tp_3.html#SEC9">Actions Carried Out During Parsing</A>
<UL>
<LI><A NAME="SEC10" HREF="tp_3.html#SEC10">Actions and Values</A>
<LI><A NAME="SEC11" HREF="tp_3.html#SEC11">Implementing Actions</A>
<LI><A NAME="SEC12" HREF="tp_3.html#SEC12">Commutative Actions</A>
</UL>
<LI><A NAME="SEC13" HREF="tp_4.html#SEC13">Summary of the Specification Language</A>
<UL>
<LI><A NAME="SEC14" HREF="tp_4.html#SEC14">Declarations</A>
<LI><A NAME="SEC15" HREF="tp_4.html#SEC15">Rules</A>
</UL>
<LI><A NAME="SEC16" HREF="tp_5.html#SEC16">Predefined Entities</A>
<LI><A NAME="SEC17" HREF="tp_6.html#SEC17">Index</A>
</UL>
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>
</BODY></HTML>
|
