Symbol Tables

Exercises

1. Hash functions are essential in implementing efficient symbol tables and the effectiveness of different hashing schemes
   can vary widely across different sets of words. Consider this collection of identifiers and evaluate the following
   has functions to see how evenly they distribute the words.
   • hash = *str;
   • while (*str) hash = hash + *str++;
   • while (*str) hash = hash * *str++;
   • while (*str) hash = (hash << 1) + *str++;
   • while (*str) hash = (hash * 65599) + *str++;

   Can you invent an even better hash function?

2. Argue that the collection of correct ESJ programs does not define a context-free language.
3. Study the code for symbol table construction in the SJC compiler. Consider a simple program and draw both the AST
   and symbol table illustrating the cross-referencing between the structures.

Reading

• Dragon, Chapter 2.7 (not much in the book on this)

Materials

Symbol Processsing