Week 6
Exercises on symbol tables
- Experiment with the following hash functions on
this collection of identifiers:
hash = *str;
while (*str) hash = hash + *str++;
while (*str) hash = hash * *str++;
while (*str) hash = (hash << 1) + *str++;
while (*str) hash = (hash << 2) + *str++;
while (*str) hash = (hash << 3) + *str++;
while (*str) hash = (hash * 65599) + *str++;
- An attempt by you at an even better hash function.
This question requires that you produce a series of 8 graphs that are
like the 3 graphs in the Week 6 slides. Assume a hashtable size of
317. You can use whatever tools and languages you like; once you have
a system to generate one graph, the rest should be trivial.
This question is not hard (estimate of one hour, at which point you
should email if you are not making progress), but it is possible to go
about it the wrong way and spend a long time on it, so keep elegance
and simplicity in mind and remember the value of one-shot programs.
If you want scriptable graphing tools that accept plain text input
then gnuplot and GNU R work well. You may
alternatively want to copy the format of the graphs out of symbol.tex, just be sure to include
the bar package.
Motivation: This is actually a very good question that
illustrates the use of the scientific method in computer science, and
for the most part the rest of this course is either math or
engineering. We have hypotheses about these hash functions being good
or bad, and we will test them empirically using a collection of
identifiers taken from a real-world program. Conducting experiments
such as these and producing graphs from them is an important part of
systems research. If you are interested more generally in the
importance of experimental computer science then you might want to
read this
paper.
- Using a diagram like the one on slide 17 (or better yet, using
a cactus stack representation of the symbol table, as discussed in
class on Friday), show the connection between the abstract syntax
tree and symbol table for the following JOOS class:
public class Cons {
protected Object first;
protected Cons rest;
public Cons(Object f, Cons r)
{ super();
first = f;
rest = r;
}
public void setFirst(Object newfirst)
{ first = newfirst; }
public boolean member(Object item)
{ if (first.equals(item))
return true;
else if (rest == null)
return false;
else
return rest.member(item);
}
}
Motivation: understanding the relationship between abstract
syntax trees and symbol tables is important. If you want to draw this
by hand that is definitely acceptable. If you want to use a computer
then Inkscape is an excellent
tool, just be sure to draw the arrows last. If this question is
taking you too long then simplify the Cons class first.
- (Optional.) Formalize the argument that the collection of correct
JOOS programs is not a context-free language. If you do not know
where to start, refer to slide 2 and this
Wikipedia page.
Motivation: sometimes it's nice to be reminded that back in the
beginning the theory people really invented everything.
- (Optional.) Study the code for symbol checking JOOS programs.
Report on anything unclear.
Motivation: the C and Java JOOS compilers are an excellent
reference for your own WIG compiler, and there are wrong (where
"wrong" expands to "unnecessarily painful") ways to implement symbol
tables.
WIG project status
- Discuss how to build a scanner, a parser, a weeder, and abstract
syntax trees for your version of the WIG language. Outline your
strategy for the remaining work. If you have not met with your group
for your upcoming
milestone then this is an excellent opportunity to brainstorm. If
you have already met with your group then summarize your meeting.
|