Week 6/41

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++;

   Can you invent an even better hash function?

2. Show, in analogy with slide 17, the connection between the parse 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);
     }
   }
   

3. Formalize the argument that the collection of correct JOOS programs is not a context-free language.
4. Study the code for symbol checking JOOS programs.

WIG project status

• Discuss how to build a scanner, a parser, and abstract syntax trees for your version of the WIG language. Outline your strategy for the remaining work.