home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / users / Harry / compilers / p8 / SymbolTable.java < prev    next >
Text File  |  2006-01-29  |  10KB  |  307 lines
  1. // -------------------------------- SymbolTable --------------------------------
  2. //
  3. // This class implements the symbol table, which maintains a mapping from Strings
  4. // to Ast.Nodes.  There will be no instances of this class; all methods are
  5. // static.  The primary methods are:
  6. //
  7. //     enter (string, node)
  8. //     find (string)  -->  node
  9. //     alreadyDefined (string)  -->  boolean
  10. //
  11. // The symbol table also supports a notion of "scope".  The following routines
  12. // control the scope:
  13. //
  14. //     openScope ()
  15. //     closeScope ()
  16. //
  17. // Calling "closeScope" will delete all mappigns added since the last call to
  18. // "openScope".  There is a globally accessible variable called
  19. //
  20. //     SymbolTable.level
  21. //
  22. // which may be accessed to find the current scope level.  It begins at zero.
  23. // "Level" is incremented whenever "openScope" is called, and decremented whenever
  24. // "closeScope" is called.  You do not need to call "openScope" before adding
  25. // entries.
  26. //
  27. // Finally, the following method may be used in debugging, if desired:
  28. //
  29. //     printTable ()
  30. //
  31. // The symbol table is stored using a hash-table.  There is an array of
  32. // pointers to linked lists.  Each element on the linked list is an
  33. // instance of class "Bucket", so the linked list is called a "bucket list".
  34. // For each key-value pair, there is a Bucket which contains both the key
  35. // (a String) and the value (a ptr to an Ast.Node).  Each string "s" is hashed
  36. // to an integer, which is used as an index into the array.  The entry for "s"
  37. // will be stored on the corresponding bucket list.  The bucket list is linked
  38. // on a field called "next".  If there are several entries for "s", then they
  39. // will all be stored on the bucket list, with the most recent entries nearer
  40. // the beginning of the list.  Each bucket also contains the scope level (an
  41. // integer) at the time it was created.
  42. //
  43. // When "closeScope" is called, we may have to delete a number of Buckets.
  44. // The buckets to be deleted will all be at the front of their bucket lists.
  45. // To avoid going through the entire array, we maintain a linked list for each
  46. // scope.  When a new Bucket is created, it is placed on this list, which is
  47. // called the "scope list".  Each Bucket has a field called "slink" which is
  48. // used as a next pointer for this list.
  49. //
  50. // Harry Porter -- 02/12/03
  51. //
  52.  
  53. import java.util.*;
  54.  
  55. class SymbolTable {
  56.  
  57.     //
  58.     // There is one "Bucket" object for each key-value mapping.  This object
  59.     // is on 2 linked lists: the "bucket list" (linked on "next") and the
  60.     // "scope list" (linked on "slink").  In addition, we keep the scope at
  61.     // which the mapping was created (field "scope") and the hash-value of
  62.     // the key (field "hashVal").  The hashVal makes deletions faster.
  63.     //
  64.     static class Bucket {
  65.         String   id;          // Key: The symbol
  66.         Ast.Node def;         // Value: The definition of this symbol
  67.         int      hashVal;     // What this id hashed to
  68.         int      scope;       // Scope level at which this symbol entered
  69.         Bucket   next;        // Ptr to next Bucket in this bucket list
  70.         Bucket   slink;       // Ptr to next Bucket in this scope list
  71.     }
  72.  
  73.     //
  74.     // There is one "Scope" object for each active scope level; they are
  75.     // linked together in decreasing scope-level order by field "next".
  76.     // All symbols at a given level are linked into a list (the "scope
  77.     // list"), which is pointed to by the "slink" field.
  78.     //
  79.     static class Scope {
  80.         Bucket slink;         // Ptr to latest Bucket for this scope
  81.         Scope next;           // Ptr to next Scope record
  82.     }
  83.  
  84.     //
  85.     // Class Variables
  86.     //
  87.     static final int HASH_TABLE_SIZE = 211;
  88.     static Bucket [] symbolTable = new Bucket [HASH_TABLE_SIZE];
  89.     static int level = 0;
  90.     static Scope scopeList = new Scope ();
  91.  
  92.  
  93.  
  94.     //
  95.     //  Constructor -- There are no instances.
  96.     //
  97.     private SymbolTable () { }
  98.  
  99.  
  100.  
  101.     //
  102.     // enter (str, def)
  103.     //
  104.     // This method adds an entry to the symbol table mapping this
  105.     // string to the given definition.  If there is already an entry
  106.     // at this scope level, the new entry will override it.
  107.     //
  108.     static void enter (String str, Ast.Node def) {
  109.         Bucket buck;
  110.         int i = hash (str);
  111.  
  112.         // System.out.println ("enter          called with '" + str + "'");
  113.      
  114.         // Allocate a new Bucket...
  115.         buck = new Bucket ();
  116.         buck.id = str;
  117.         buck.scope = level;
  118.         buck.def = def;
  119.         buck.hashVal = i;
  120.  
  121.         // Add the new Bucket into the hash table bucket list...
  122.         buck.next = symbolTable [i];
  123.         symbolTable [i] = buck;
  124.  
  125.         // Add this Bucket into the slink list for the current scope level...
  126.         buck.slink = scopeList.slink;
  127.         scopeList.slink = buck;
  128.  
  129.     }
  130.  
  131.  
  132.  
  133.     //
  134.     // find (string)
  135.     //
  136.     // This routine searches the symbol table for the entry for "string".
  137.     // If found, it returns a ptr to its definition; otherwise it returns NULL.
  138.     //
  139.     static Ast.Node find (String str) {
  140.         int i = hash (str);
  141.         Bucket buck = symbolTable [i];
  142.  
  143.         // System.out.println ("find           called with '" + str + "'");
  144.  
  145.         while (buck != null) {
  146.             if (buck.id == str) {
  147.                 return buck.def;
  148.             }
  149.             buck = buck.next;
  150.         }
  151.         return null;
  152.     }
  153.  
  154.  
  155.  
  156.     //
  157.     // alreadyDefined (str)  -->  boolean
  158.     //
  159.     // This routine looks 'str' up in the current scope and returns TRUE
  160.     // if found and FALSE otherwise.  It searches only the current scope.
  161.     //
  162.     static boolean alreadyDefined (String str) {
  163.         int i = hash (str);
  164.         Bucket buck = symbolTable [i];
  165.  
  166.         // System.out.println ("alreadyDefined called with '" + str + "'");
  167.  
  168.         while (buck != null) {
  169.             if (buck.id == str) {
  170.                 return (buck.scope == level);
  171.             }
  172.             buck = buck.next;
  173.         }
  174.         return false;
  175.     }
  176.  
  177.  
  178.  
  179.     //
  180.     // openScope()
  181.     //
  182.     // This routine opens a new scope and increments the static variable "level."
  183.     //
  184.     static void openScope () {
  185.             Scope sc = new Scope ();
  186.             sc.slink = null;
  187.             sc.next = scopeList;
  188.             scopeList = sc;
  189.             level++;
  190.      
  191.             // System.out.println ("openScope      called: new level=" + level);
  192.     }
  193.  
  194.  
  195.  
  196.     //
  197.     // closeScope ()
  198.     //
  199.     // This method closes the highest scope and removes all entries in that
  200.     // scope.  It decrements "level".
  201.     //
  202.     static void closeScope ()
  203.         throws FatalError
  204.     {
  205.         Bucket buck, temp;
  206.         Scope sc;
  207.         if (level <= 0) {
  208.             throw new LogicError ("Compiler logic error in closeScope");
  209.         }
  210.         buck = scopeList.slink;
  211.         while (buck != null) {
  212.             symbolTable [buck.hashVal] = buck.next;
  213.             temp = buck.slink;
  214.             buck.def = null;
  215.             buck.next = null;
  216.             buck.slink = null;
  217.             buck = temp;
  218.         }
  219.         sc = scopeList;
  220.         scopeList = scopeList.next;
  221.         sc.slink = null;
  222.         sc.next = null;
  223.         level--;
  224.  
  225.         // System.out.println ("closeScope     called: new level=" + level);
  226.     }
  227.  
  228.  
  229.  
  230.     //
  231.     // hash (p)  -->  int
  232.     //
  233.     // This routine computes a hash value for the string pointed to by p.
  234.     // It then transforms it into a range making it suitable as an index
  235.     // into the hash table.
  236.     //
  237.     static int hash (String p) {
  238.         int i = p.hashCode ();         // May return a negative number.
  239.         if (i == 0x80000000) {
  240.             i = 123;
  241.         } else if (i < 0) {
  242.             i = -i;
  243.         }
  244.         return i % HASH_TABLE_SIZE;
  245.     }
  246.  
  247.  
  248.  
  249.     //
  250.     // printTable ()
  251.     //
  252.     // Print the entire symbol table, starting with the current level
  253.     // and working down.
  254.     //
  255.     static void printTable () {
  256.         Bucket buck;
  257.         System.out.println ("==========  The Symbol Table  ==========");
  258.         for (int lev = level; 0 <= lev; lev--) {
  259.             System.out.println ("  ==========  Scope Level=" + lev +"  ==========");
  260.             for (int i = 0; i < HASH_TABLE_SIZE; i++) {
  261.                 buck = symbolTable [i];
  262.                 if (buck != null && buck.scope == lev) {
  263.                   System.out.println ("      ==========  Bucket List # " + i +
  264.                                           "  ==========");
  265.                   while (buck != null) {
  266.                       if (buck.scope == lev) {
  267.                           System.out.println ("        " + buck.id +
  268.                                               "  [level=" + buck.scope +
  269.                                               ", hashVal=" + buck.hashVal + "]");
  270.                           printDef (buck.def);
  271.                       }
  272.                       buck = buck.next;
  273.                   }
  274.                }
  275.             }
  276. //             System.out.println ("  ===============================");
  277.         }
  278.         System.out.println ("===============================");
  279.     }
  280.  
  281.  
  282.  
  283.     //
  284.     // printDef (p)
  285.     //
  286.     // This method is passed a pointer to a VarDecl, TypeDecl, ProcDecl, or NULL.
  287.     // It prints it.
  288.     //
  289.     static void printDef (Ast.Node p) {
  290.         if (p == null) {
  291.             System.out.println ("            NULL");
  292.         } else if (p instanceof Ast.VarDecl) {
  293.             System.out.println ("            VarDecl...");
  294.         } else if (p instanceof Ast.TypeDecl) {
  295.             System.out.println ("            TypeDecl...");
  296.         } else if (p instanceof Ast.ProcDecl) {
  297.             System.out.println ("            ProcDecl... ");
  298.         } else if (p instanceof Ast.Formal) {
  299.             System.out.println ("            Formal... ");
  300.         } else {
  301.             System.out.println ("            *****  Not a VAR_DECL, PROC_DECL, TYPE_DECL, or FORMAL  *****");
  302.         }
  303.     }
  304.  
  305.  
  306. }
  307.