Week 6

Exercises on symbol tables

  1. 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.

  2. 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;
          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.

  3. (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.

  4. (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.

Maintained by Christopher J. F. Pickett. [HOME]