Repair/RepairCompiler/java_cup/lalr_item.java

   1 package java_cup;
   2
   3 import java.util.Stack;
   4 import java.util.Enumeration;
   5
   6 /** This class represents an LALR item. Each LALR item consists of
   7  *  a production, a "dot" at a position within that production, and
   8  *  a set of lookahead symbols (terminal).  (The first two of these parts
   9  *  are provide by the super class).  An item is designed to represent a
  10  *  configuration that the parser may be in.  For example, an item of the
  11  *  form: <pre>
  12  *    [A ::= B * C d E  , {a,b,c}]
  13  *  </pre>
  14  *  indicates that the parser is in the middle of parsing the production <pre>
  15  *    A ::= B C d E
  16  *  </pre>
  17  *  that B has already been parsed, and that we will expect to see a lookahead
  18  *  of either a, b, or c once the complete RHS of this production has been
  19  *  found.<p>
  20  *
  21  *  Items may initially be missing some items from their lookahead sets.
  22  *  Links are maintained from each item to the set of items that would need
  23  *  to be updated if symbols are added to its lookahead set.  During
  24  *  "lookahead propagation", we add symbols to various lookahead sets and
  25  *  propagate these changes across these dependency links as needed.
  26  *
  27  * @see     java_cup.lalr_item_set
  28  * @see     java_cup.lalr_state
  29  * @version last updated: 11/25/95
  30  * @author  Scott Hudson
  31  */
  32 public class lalr_item extends lr_item_core {
  33
  34   /*-----------------------------------------------------------*/
  35   /*--- Constructor(s) ----------------------------------------*/
  36   /*-----------------------------------------------------------*/
  37
  38   /** Full constructor.
  39    * @param prod the production for the item.
  40    * @param pos  the position of the "dot" within the production.
  41    * @param look the set of lookahead symbols.
  42    */
  43   public lalr_item(production prod, int pos, terminal_set look)
  44     throws internal_error
  45     {
  46       super(prod, pos);
  47       _lookahead = look;
  48       _propagate_items = new Stack();
  49       needs_propagation = true;
  50     }
  51
  52   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  53
  54   /** Constructor with default position (dot at start).
  55    * @param prod the production for the item.
  56    * @param look the set of lookahead symbols.
  57    */
  58   public lalr_item(production prod, terminal_set look) throws internal_error
  59     {
  60       this(prod,0,look);
  61     }
  62
  63   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  64
  65   /** Constructor with default position and empty lookahead set.
  66    * @param prod the production for the item.
  67    */
  68   public lalr_item(production prod) throws internal_error
  69     {
  70       this(prod,0,new terminal_set());
  71     }
  72
  73   /*-----------------------------------------------------------*/
  74   /*--- (Access to) Instance Variables ------------------------*/
  75   /*-----------------------------------------------------------*/
  76
  77   /** The lookahead symbols of the item. */
  78   protected terminal_set _lookahead;
  79
  80   /** The lookahead symbols of the item. */
  81   public terminal_set lookahead() {return _lookahead;}
  82
  83   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  84
  85   /** Links to items that the lookahead needs to be propagated to. */
  86   protected Stack _propagate_items;
  87
  88   /** Links to items that the lookahead needs to be propagated to */
  89   public Stack propagate_items() {return _propagate_items;}
  90
  91   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  92
  93   /** Flag to indicate that this item needs to propagate its lookahead
  94    *  (whether it has changed or not).
  95    */
  96   protected boolean needs_propagation;
  97
  98   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  99
 100   /** Add a new item to the set of items we propagate to. */
 101   public void add_propagate(lalr_item prop_to)
 102     {
 103       _propagate_items.push(prop_to);
 104       needs_propagation = true;
 105     }
 106
 107   /*-----------------------------------------------------------*/
 108   /*--- General Methods ---------------------------------------*/
 109   /*-----------------------------------------------------------*/
 110
 111   /** Propagate incoming lookaheads through this item to others need to
 112    *  be changed.
 113    * @params incoming symbols to potentially be added to lookahead of this item.
 114    */
 115   public void propagate_lookaheads(terminal_set incoming) throws internal_error
 116     {
 117       boolean change = false;
 118
 119       /* if we don't need to propagate, then bail out now */
 120       if (!needs_propagation && (incoming == null || incoming.empty()))
 121         return;
 122
 123       /* if we have null incoming, treat as an empty set */
 124       if (incoming != null)
 125         {
 126           /* add the incoming to the lookahead of this item */
 127           change = lookahead().add(incoming);
 128         }
 129
 130       /* if we changed or need it anyway, propagate across our links */
 131       if (change || needs_propagation)
 132         {
 133           /* don't need to propagate again */
 134           needs_propagation = false;
 135
 136           /* propagate our lookahead into each item we are linked to */
 137           for (int i = 0; i < propagate_items().size(); i++)
 138             ((lalr_item)propagate_items().elementAt(i))
 139                                           .propagate_lookaheads(lookahead());
 140         }
 141     }
 142
 143   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 144
 145   /** Produce the new lalr_item that results from shifting the dot one position
 146    *  to the right.
 147    */
 148   public lalr_item shift() throws internal_error
 149     {
 150       lalr_item result;
 151
 152       /* can't shift if we have dot already at the end */
 153       if (dot_at_end())
 154         throw new internal_error("Attempt to shift past end of an lalr_item");
 155
 156       /* create the new item w/ the dot shifted by one */
 157       result = new lalr_item(the_production(), dot_pos()+1,
 158                                             new terminal_set(lookahead()));
 159
 160       /* change in our lookahead needs to be propagated to this item */
 161       add_propagate(result);
 162
 163       return result;
 164     }
 165
 166   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 167
 168   /** Calculate lookahead representing symbols that could appear after the
 169    *   symbol that the dot is currently in front of.  Note: this routine must
 170    *   not be invoked before first sets and nullability has been calculated
 171    *   for all non terminals.
 172    */
 173   public terminal_set calc_lookahead(terminal_set lookahead_after)
 174     throws internal_error
 175     {
 176       terminal_set    result;
 177       int             pos;
 178       production_part part;
 179       symbol          sym;
 180
 181       /* sanity check */
 182       if (dot_at_end())
 183         throw new internal_error(
 184           "Attempt to calculate a lookahead set with a completed item");
 185
 186       /* start with an empty result */
 187       result = new terminal_set();
 188
 189       /* consider all nullable symbols after the one to the right of the dot */
 190       for (pos = dot_pos()+1; pos < the_production().rhs_length(); pos++)
 191         {
 192            part = the_production().rhs(pos);
 193
 194            /* consider what kind of production part it is -- skip actions */
 195            if (!part.is_action())
 196              {
 197                sym = ((symbol_part)part).the_symbol();
 198
 199                /* if its a terminal add it in and we are done */
 200                if (!sym.is_non_term())
 201                  {
 202                    result.add((terminal)sym);
 203                    return result;
 204                  }
 205                else
 206                  {
 207                    /* otherwise add in first set of the non terminal */
 208                    result.add(((non_terminal)sym).first_set());
 209
 210                    /* if its nullable we continue adding, if not, we are done */
 211                    if (!((non_terminal)sym).nullable())
 212                      return result;
 213                  }
 214              }
 215         }
 216
 217       /* if we get here everything past the dot was nullable
 218          we add in the lookahead for after the production and we are done */
 219       result.add(lookahead_after);
 220       return result;
 221     }
 222
 223   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 224
 225   /** Determine if everything from the symbol one beyond the dot all the
 226    *  way to the  end of the right hand side is nullable.  This would indicate
 227    *  that the lookahead of this item must be included in the lookaheads of
 228    *  all items produced as a closure of this item.  Note: this routine should
 229    *  not be invoked until after first sets and nullability have been
 230    *  calculated for all non terminals.
 231    */
 232   public boolean lookahead_visible() throws internal_error
 233     {
 234       production_part part;
 235       symbol          sym;
 236
 237       /* if the dot is at the end, we have a problem, but the cleanest thing
 238          to do is just return true. */
 239       if (dot_at_end()) return true;
 240
 241       /* walk down the rhs and bail if we get a non-nullable symbol */
 242       for (int pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++)
 243         {
 244           part = the_production().rhs(pos);
 245
 246           /* skip actions */
 247           if (!part.is_action())
 248             {
 249               sym = ((symbol_part)part).the_symbol();
 250
 251               /* if its a terminal we fail */
 252               if (!sym.is_non_term()) return false;
 253
 254               /* if its not nullable we fail */
 255               if (!((non_terminal)sym).nullable()) return false;
 256             }
 257         }
 258
 259       /* if we get here its all nullable */
 260       return true;
 261     }
 262
 263   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 264
 265   /** Equality comparison -- here we only require the cores to be equal since
 266    *   we need to do sets of items based only on core equality (ignoring
 267    *   lookahead sets).
 268    */
 269   public boolean equals(lalr_item other)
 270     {
 271       if (other == null) return false;
 272       return super.equals(other);
 273     }
 274
 275   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 276
 277   /** Generic equality comparison. */
 278   public boolean equals(Object other)
 279     {
 280       if (!(other instanceof lalr_item))
 281         return false;
 282       else
 283         return equals((lalr_item)other);
 284     }
 285
 286   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 287
 288   /** Return a hash code -- here we only hash the core since we only test core
 289    *  matching in LALR items.
 290    */
 291   public int hashCode()
 292     {
 293       return super.hashCode();
 294     }
 295
 296   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 297
 298   /** Convert to string. */
 299   public String toString()
 300     {
 301       String result = "";
 302
 303       // additional output for debugging:
 304       // result += "(" + obj_hash() + ")";
 305       result += "[";
 306       result += super.toString();
 307       result += ", ";
 308       if (lookahead() != null)
 309         {
 310           result += "{";
 311           for (int t = 0; t < terminal.number(); t++)
 312             if (lookahead().contains(t))
 313               result += terminal.find(t).name() + " ";
 314           result += "}";
 315         }
 316       else
 317         result += "NULL LOOKAHEAD!!";
 318       result += "]";
 319
 320       // additional output for debugging:
 321       // result += " -> ";
 322       // for (int i = 0; i<propagate_items().size(); i++)
 323       //   result+=((lalr_item)(propagate_items().elementAt(i))).obj_hash()+" ";
 324       //
 325       // if (needs_propagation) result += " NP";
 326
 327       return result;
 328     }
 329     /*-----------------------------------------------------------*/
 330 }