Package java_cup

Class lalr_item_set


  • public class lalr_item_set
    extends java.lang.Object
    This class represents a set of LALR items. For purposes of building these sets, items are considered unique only if they have unique cores (i.e., ignoring differences in their lookahead sets).

    This class provides fairly conventional set oriented operations (union, sub/super-set tests, etc.), as well as an LALR "closure" operation (see compute_closure()).

    See Also:
    lalr_item, lalr_state
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.Hashtable _all
      A hash table to implement the set.
      protected java.lang.Integer hashcode_cache
      Cached hashcode for this set.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      lalr_item add​(lalr_item itm)
      Add a singleton item, merging lookahead sets if the item is already part of the set.
      void add​(lalr_item_set other)
      Add a complete set, merging lookaheads where items are already in the set
      java.util.Enumeration all()
      Access to all elements of the set.
      void compute_closure()
      Compute the closure of the set using the LALR closure rules.
      boolean contains​(lalr_item itm)
      Does the set contain a particular item?
      boolean equals​(lalr_item_set other)
      Equality comparison.
      boolean equals​(java.lang.Object other)
      Generic equality comparison.
      lalr_item find​(lalr_item itm)
      Return the item in the set matching a particular item (or null if not found)
      lalr_item get_one()
      Remove and return one item from the set (done in hash order).
      int hashCode()
      Return hash code.
      boolean is_subset_of​(lalr_item_set other)
      Is this set an (improper) subset of another?
      boolean is_superset_of​(lalr_item_set other)
      Is this set an (improper) superset of another?
      protected void not_null​(java.lang.Object obj)
      Helper function for null test.
      void remove​(lalr_item itm)
      Remove a single item if it is in the set.
      void remove​(lalr_item_set other)
      Remove (set subtract) a complete set.
      int size()
      Size of the set
      java.lang.String toString()
      Convert to string.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • _all

        protected java.util.Hashtable _all
        A hash table to implement the set. We store the items using themselves as keys.
      • hashcode_cache

        protected java.lang.Integer hashcode_cache
        Cached hashcode for this set.
    • Constructor Detail

      • lalr_item_set

        public lalr_item_set()
        Constructor for an empty set.
    • Method Detail

      • all

        public java.util.Enumeration all()
        Access to all elements of the set.
      • size

        public int size()
        Size of the set
      • contains

        public boolean contains​(lalr_item itm)
        Does the set contain a particular item?
        Parameters:
        itm - the item in question.
      • find

        public lalr_item find​(lalr_item itm)
        Return the item in the set matching a particular item (or null if not found)
        Parameters:
        itm - the item we are looking for.
      • is_subset_of

        public boolean is_subset_of​(lalr_item_set other)
                             throws internal_error
        Is this set an (improper) subset of another?
        Parameters:
        other - the other set in question.
        Throws:
        internal_error
      • is_superset_of

        public boolean is_superset_of​(lalr_item_set other)
                               throws internal_error
        Is this set an (improper) superset of another?
        Parameters:
        other - the other set in question.
        Throws:
        internal_error
      • add

        public lalr_item add​(lalr_item itm)
                      throws internal_error
        Add a singleton item, merging lookahead sets if the item is already part of the set. returns the element of the set that was added or merged into.
        Parameters:
        itm - the item being added.
        Throws:
        internal_error
      • add

        public void add​(lalr_item_set other)
                 throws internal_error
        Add a complete set, merging lookaheads where items are already in the set
        Parameters:
        other - the set to be added.
        Throws:
        internal_error
      • not_null

        protected void not_null​(java.lang.Object obj)
                         throws internal_error
        Helper function for null test. Throws an interal_error exception if its parameter is null.
        Parameters:
        obj - the object we are testing.
        Throws:
        internal_error
      • compute_closure

        public void compute_closure()
                             throws internal_error
        Compute the closure of the set using the LALR closure rules. Basically for every item of the form:
            [L ::= a *N alpha, l] 
          
        (where N is a a non terminal and alpha is a string of symbols) make sure there are also items of the form:
            [N ::= *beta, first(alpha l)] 
          
        corresponding to each production of N. Items with identical cores but differing lookahead sets are merged by creating a new item with the same core and the union of the lookahead sets (the LA in LALR stands for "lookahead merged" and this is where the merger is). This routine assumes that nullability and first sets have been computed for all productions before it is called.
        Throws:
        internal_error
      • equals

        public boolean equals​(lalr_item_set other)
        Equality comparison.
      • equals

        public boolean equals​(java.lang.Object other)
        Generic equality comparison.
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Return hash code.
        Overrides:
        hashCode in class java.lang.Object
      • toString

        public java.lang.String toString()
        Convert to string.
        Overrides:
        toString in class java.lang.Object