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
|
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
from ../tnf/type.tnf on 12 Febuary 2003 -->
<TITLE>Type analysis tasks - Operator Identification</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>Type analysis tasks</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="type_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="type_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="type_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="SEC8" HREF="type_toc.html#SEC8">Operator Identification</A></H1>
<P>
Operator identification is a subtask of type analysis for any language
that has overloaded operators, i.e. a source operator symbol like
<CODE>+</CODE>
may denote one of several target operations, e.g. integer addition or
floating point addition or boolean disjunction.
The distinction is made using the types of the operands. (The Ada-like
case where the expected result type is also used is not supported here.)
<P>
The <CODE>Operator</CODE> module allows compact descriptions of the
characteristics of each operator.
It is required that types of operands and expressions are
represented by <CODE>DefTableKey</CODE>s which are
PDL known keys.
The module also supports transformation of operators.
Target operators are also represented by PDL known keys which
may have properties associated that describe their translation.
<P>
This module replaces the <CODE>AdaptOil</CODE> module of previous library
versions,
and covers all its functionality. It uses the current version of the
Oil tool which supports operators and types being represented by
<CODE>DefTableKey</CODE>s.
<P>
The <CODE>Operator</CODE> module is instantiated with a <CODE>referto</CODE> parameter
that gives the name of the file containing the operator descriptions
<PRE>
$/Type/Operator.gnrc +referto=(FILENAME):inst
</PRE>
If this instantiation is contained in a <CODE>.specs</CODE> file and
if the description file, say <CODE>Oper.d</CODE> is contained in the
same directory, it may read
<PRE>
$/Type/Operator.gnrc +referto=(Oper.d):inst
</PRE>
If the <CODE>.specs</CODE> and <CODE>Oper.d</CODE> are contained in a <CODE>.fw</CODE>
specification, the same line can be used.
<P>
The file contains a sequence of macro calls that describe source
operators and target operators.
The module provides computational roles for binary and unary operators
(<CODE>BinTgtOpr</CODE> and <CODE>UnTgtOpr</CODE>) which perform operator
identification. Their use is described below.
<P>
The macros that describe the operators have the following forms:
<A NAME="IDX80"></A>
<A NAME="IDX81"></A>
<P>
<DL COMPACT>
<DT><CODE>SrcOpr (Token, ConSymbol, TreeSymbol, SrcKey)</CODE>
<DD>A source operator is described.
<CODE>Token</CODE> is a literal terminal that denotes the operator in the
concrete grammar.
The operator's precedence is specified
by the concrete grammar nonterminal <CODE>ConSymbol</CODE>, that collects
a set of operators having the same precedence.
In the tree grammar the operator (and all others of the <CODE>ConSymbol</CODE>
set) is represented by a <CODE>TreeSymbol</CODE>.
<CODE>SrcKey</CODE> is the name of a <CODE>DefTableKey</CODE> which represents
this operator uniquely. It is automatically introduced as a PDL
known key.
<P>
<DT><CODE>TgtOpr (SrcKey, TgtKey, Signature, KeyInit)</CODE>
<DD>A target operator <CODE>TgtKey</CODE> is described.
It is uniquely represented by the <CODE>DefTableKey</CODE> <CODE>TgtKey</CODE>,
which is automatically introduced as a PDL known key.
The operator is one of
several overloaded meanings for the source operator <CODE>SrcKey</CODE>.
Its signature is specified by <CODE>Signature</CODE>, using the notation
of the Oil tool. The types occurring in the <CODE>Signature</CODE> are
names of <CODE>DefTableKey</CODE>s.
Properties may be associated to <CODE>TgtKey</CODE>
to be used for further analysis and translation
tasks. They can be initialized by <CODE>KeyInit</CODE> which is a
possibly empty <CODE>PropertyValueList</CODE> in PDL notation.
(If more than one property is initialized, the macro name
<CODE>comma</CODE> has to be used as a separator instead of the <CODE>,</CODE>
token.)
</DL>
<P>
The following restrictions must be obeyed:
Every <CODE>SrcKey</CODE> must occur only once in a <CODE>SrcOpr</CODE> description.
Every <CODE>TgtKey</CODE> must occur only once in a <CODE>TgtOpr</CODE> description.
<A NAME="IDX82"></A>
<A NAME="IDX83"></A>
<A NAME="IDX84"></A>
<A NAME="IDX85"></A>
<A NAME="IDX86"></A>
<A NAME="IDX87"></A>
<A NAME="IDX88"></A>
<A NAME="IDX89"></A>
<P>
The computational role <CODE>BinTgtOpr</CODE> is to be inherited by
a grammar symbol that represents a binary operator and that is
mentioned as a <CODE>TreeSymbol</CODE> in a <CODE>SrcOpr</CODE> description.
Two attributes named <CODE>LType</CODE> and <CODE>RType</CODE> have to be set
to the type of the left and of the right operand respectively.
Attributes <CODE>ResType</CODE>, <CODE>LTType</CODE>, and <CODE>RTType</CODE> are
computed representing
the result type of the identified target operator and its operand types.
An attribute <CODE>TgtKey</CODE> is computed representing the
target operator by the key specified in the <CODE>TgtOpr</CODE> description.
<P>
The same holds for the computational role <CODE>UnTgtOpr</CODE>, with the
exception that only the <CODE>RType</CODE> attribute has to be set.
<P>
The computational role <CODE>ChkOpr</CODE> provides a check whether a valid
target operator is identified for the given types, and issues a
message otherwise.
It can be inherited by binary or unary operator symbols.
<P>
The use of this module is demonstrated by adding expressions with
binary and unary operators to the language of our running example.
In the concrete grammar an expression hierarchy defines precedences
and associativity of operator sets:
<PRE>
Expression: Expression AddOpr Factor / Factor.
Factor: Factor MulOpr Operand / Operand.
Operand: MonOpr Operand.
Operand: '(' Expression ')'.
</PRE>
Here <CODE>UnOpr</CODE>s have highest precedence and <CODE>AddOpr</CODE> have lowest.
The operators of the three sets are not specified here.
They are introduced by <CODE>SrcOpr</CODE> descriptions contained in the
file the module is instantiated with, e.g.
<PRE>
SrcOpr ('+', AddOpr, BinOpr, AddKey)
SrcOpr ('*', MulOpr, BinOpr, MulKey)
SrcOpr ('-', MonOpr, UnOpr, NegKey)
</PRE>
<P>
The module adds a production for every source operator to the
concrete grammar, e.g.
<PRE>
AddOpr: '+'.
</PRE>
It states that <CODE>AddOpr</CODE> and <CODE>MulOpr</CODE> are to be represented
by a <CODE>BinOpr</CODE> node in the tree, and it adds an attribute
computations for each operator context to the tree, e.g.
<PRE>
RULE: BinOpr ::= '+' COMPUTE BinOpr.OprSym = AddKey; END;
</PRE>
<P>
The following target operator descriptions (also contained in
the file the module is instantiated with)
overload those operators with operations on integral numbers and
boolean values:
<PRE>
TgtOpr (AddKey, iAddKey, (intType,intType):intType, TgtStr={"+"})
TgtOpr (AddKey, bOrKey, (boolType,boolType):boolType, TgtStr={"||"})
TgtOpr (MulKey, iMulKey, (intType,intType):intType, TgtStr={"*"})
TgtOpr (MulKey, bAndKey, (boolType,boolType):boolType, TgtStr={"&&"})
TgtOpr (NegKey, iNegKey, (intType):intType, TgtStr={"-"})
TgtOpr (NegKey, bNotKey, (boolType):boolType, TgtStr={"!"})
</PRE>
From these descriptions the module generates the necessary .oil
specifications, e.g
<PRE>
INDICATION AddKey: iAddKey;
OPER iAddKey (intType,intType):intType;
</PRE>
and the necessary .pdl specifications, e.g
<PRE>
iAddKey -> TgtStr={"+"};
</PRE>
The properties that are initialized in the target operator description,
here <CODE>TgtStr</CODE> have to be defined in the user's specification.
<P>
We then can use the computational roles <CODE>BinTgtOpr</CODE>,
<CODE>UnTgtOpr</CODE>, and <CODE>ChkOpr</CODE> to solve the overloading resolution
task. We only have to assign the types of the operands to attributes
of the operator symbol, and use the types of the signature of the
identified target operator correspondingly:
<PRE>
SYMBOL Expression: Type, ReqType: DefTableKey;
SYMBOL BinOpr INHERITS BinTgtOpr, ChkOpr END;
RULE: Expression ::= Expression BinOpr Expression COMPUTE
BinOpr.LType = Expression[2].Type;
BinOpr.RType = Expression[3].Type;
Expression[1].Type = BinOpr.ResType;
Expression[2].ReqType = BinOpr.LTType;
Expression[3].ReqType = BinOpr.RTType;
END;
SYMBOL UnOpr INHERITS UnTgtOpr, ChkOpr END;
RULE: Expression ::= UnOpr Expression COMPUTE
UnOpr.RType = Expression[2].Type;
Expression[1].Type = UnOpr.ResType;
Expression[2].ReqType = UnOpr.RTType;
END;
</PRE>
<P>
The operator descriptions of the target operators in our example
associate a property <CODE>TgtStr</CODE> to be used for a translation to C:
<PRE>
RULE: Expression ::= Expression BinOpr Expression COMPUTE
Expression[1].CCode =
PTGBinOpr (Expression[2].CCode,
GetTgtStr (BinOpr.TgtKey, "??"),
Expression[3].CCode);
END;
RULE: Expression ::= UnOpr Expression COMPUTE
Expression[1].CCode =
PTGUnOpr (GetTgtStr (UnOpr.TgtKey, "??"),
Expression[2].CCode);
END;
</PRE>
<P>
To complete the above example we need a .pdl specification of the
<CODE>TgtStr</CODE> property
<PRE>
TgtStr: CharPtr; "Strings.h"
</PRE>
<P>
and suitable <CODE>.ptg</CODE> patterns for the translation of expressions:
<PRE>
BinOpr: "(" $1 ")" $2 string "(" $3 ")"
UnOpr: $1 string "(" $2 ")"
</PRE>
<A NAME="IDX90"></A>
<A NAME="IDX91"></A>
<A NAME="IDX92"></A>
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="type_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="type_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="type_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>
|
