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
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Beyond Symbol Tables</TITLE>
<META NAME="description" CONTENT="Beyond Symbol Tables">
<META NAME="keywords" CONTENT="tpman">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="tpman.css">
<LINK REL="previous" HREF="node34.html">
<LINK REL="up" HREF="node28.html">
<LINK REL="next" HREF="node36.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html557"
HREF="node36.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html553"
HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html549"
HREF="node34.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html555"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html556"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html558"
HREF="node36.html">Design Considerations for Kimwitu</A>
<B> Up:</B> <A NAME="tex2html554"
HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html550"
HREF="node34.html">Memo Functions</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION00097000000000000000">
Beyond Symbol Tables</A>
</H2>
<P>
Attributes of uniquely stored terms can be used to implement symbol tables,<A NAME="1185"> </A>
or more exactly, the contents of symbol tables.
Looking up translates to newly creating a term (which is represented uniquely)
and then inspecting its attributes.
One can view this as making the look up function a memo function.
<P>
The nice thing is that entire terms can be used as the key in the `symbol table'.
This is useful for e.g. nested scopes.
A key can then be a term composed of an identifier and a scope indication.
This tuple should be unique.
<P>
As an example, we consider the detection of common subexpressions.
Every subexpression is a key in the symbol table, and one pass over the expression
computes the attribute <I>ocs</I>, which represents the number of occurrences of each subexpression.
<P>
<A NAME="1187"> </A><A NAME="1188"> </A>
<A NAME="1189"> </A><A NAME="1190"> </A>
<PRE><HR><!--lgrindfile: comsub.k 15:30 Jul 19 1996-->
<I>/* A very simple tree structure */</I>
funnytree {<B>uniq</B>}: Str(<B>casestring</B>)
| Cons(funnytree funnytree)
{ <B>int</B> ocs = 0;
funnytree next ;
{ $0->next = alltrees;
alltrees = $0; }
}
;
<BR>
<B>void</B> occurs(funnytree $f) {
Str: { f->ocs++; }
Cons(f1, f2): { f->ocs++; occurs(f1); occurs(f2); }
}
<BR>
%{ KC_TYPES_HEADER
funnytree alltrees;
%}
<BR>
<B>int</B> main() {
funnytree ft, it;
<BR>
alltrees = (funnytree)0;
ft = Str(mkcasestring(<code>"foo"</code>));
ft = Cons(ft, ft);
ft = Cons(ft, Str(mkcasestring(<code>"bar"</code>)));
ft = Cons(ft, ft);
it = alltrees;
occurs(it);
<B>for</B>(; it!= (funnytree)0; it= it->next) {
<B>if</B> (it->ocs>1) {
printf(<code>"occurs %d times:\n"</code>, it->ocs);
print_funnytree(it);
} } }
<HR></PRE>
<P>
The example also illustrates a technique through which all values of a particular
phylum in the symbol table
can be accessed.
The idea is that they are strung together using an attribute (here <I>next</I>)
and a global variable (here <I>alltrees</I>), which are manipulated in the initialisation part
of a term.
The other essential components of this technique are the initialisation of the global variable,
and the inclusion of its definition in all the files through <I>KC_TYPES_HEADER</I>.
This technique also works for non unique phyla.
Unique phyla should not be used when some of the attributes depend on the context of their nodes.
<A NAME="1195"> </A>
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html557"
HREF="node36.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html553"
HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html549"
HREF="node34.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html555"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html556"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html558"
HREF="node36.html">Design Considerations for Kimwitu</A>
<B> Up:</B> <A NAME="tex2html554"
HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html550"
HREF="node34.html">Memo Functions</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>
|
