+++ /dev/null
-package java_cup;
-
-import java.util.Stack;
-import java.util.Enumeration;
-
-/** This class represents an LALR item. Each LALR item consists of
- * a production, a "dot" at a position within that production, and
- * a set of lookahead symbols (terminal). (The first two of these parts
- * are provide by the super class). An item is designed to represent a
- * configuration that the parser may be in. For example, an item of the
- * form: <pre>
- * [A ::= B * C d E , {a,b,c}]
- * </pre>
- * indicates that the parser is in the middle of parsing the production <pre>
- * A ::= B C d E
- * </pre>
- * that B has already been parsed, and that we will expect to see a lookahead
- * of either a, b, or c once the complete RHS of this production has been
- * found.<p>
- *
- * Items may initially be missing some items from their lookahead sets.
- * Links are maintained from each item to the set of items that would need
- * to be updated if symbols are added to its lookahead set. During
- * "lookahead propagation", we add symbols to various lookahead sets and
- * propagate these changes across these dependency links as needed.
- *
- * @see java_cup.lalr_item_set
- * @see java_cup.lalr_state
- * @version last updated: 11/25/95
- * @author Scott Hudson
- */
-public class lalr_item extends lr_item_core {
-
- /*-----------------------------------------------------------*/
- /*--- Constructor(s) ----------------------------------------*/
- /*-----------------------------------------------------------*/
-
- /** Full constructor.
- * @param prod the production for the item.
- * @param pos the position of the "dot" within the production.
- * @param look the set of lookahead symbols.
- */
- public lalr_item(production prod, int pos, terminal_set look)
- throws internal_error
- {
- super(prod, pos);
- _lookahead = look;
- _propagate_items = new Stack();
- needs_propagation = true;
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Constructor with default position (dot at start).
- * @param prod the production for the item.
- * @param look the set of lookahead symbols.
- */
- public lalr_item(production prod, terminal_set look) throws internal_error
- {
- this(prod,0,look);
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Constructor with default position and empty lookahead set.
- * @param prod the production for the item.
- */
- public lalr_item(production prod) throws internal_error
- {
- this(prod,0,new terminal_set());
- }
-
- /*-----------------------------------------------------------*/
- /*--- (Access to) Instance Variables ------------------------*/
- /*-----------------------------------------------------------*/
-
- /** The lookahead symbols of the item. */
- protected terminal_set _lookahead;
-
- /** The lookahead symbols of the item. */
- public terminal_set lookahead() {return _lookahead;}
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Links to items that the lookahead needs to be propagated to. */
- protected Stack _propagate_items;
-
- /** Links to items that the lookahead needs to be propagated to */
- public Stack propagate_items() {return _propagate_items;}
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Flag to indicate that this item needs to propagate its lookahead
- * (whether it has changed or not).
- */
- protected boolean needs_propagation;
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Add a new item to the set of items we propagate to. */
- public void add_propagate(lalr_item prop_to)
- {
- _propagate_items.push(prop_to);
- needs_propagation = true;
- }
-
- /*-----------------------------------------------------------*/
- /*--- General Methods ---------------------------------------*/
- /*-----------------------------------------------------------*/
-
- /** Propagate incoming lookaheads through this item to others need to
- * be changed.
- * @params incoming symbols to potentially be added to lookahead of this item.
- */
- public void propagate_lookaheads(terminal_set incoming) throws internal_error
- {
- boolean change = false;
-
- /* if we don't need to propagate, then bail out now */
- if (!needs_propagation && (incoming == null || incoming.empty()))
- return;
-
- /* if we have null incoming, treat as an empty set */
- if (incoming != null)
- {
- /* add the incoming to the lookahead of this item */
- change = lookahead().add(incoming);
- }
-
- /* if we changed or need it anyway, propagate across our links */
- if (change || needs_propagation)
- {
- /* don't need to propagate again */
- needs_propagation = false;
-
- /* propagate our lookahead into each item we are linked to */
- for (int i = 0; i < propagate_items().size(); i++)
- ((lalr_item)propagate_items().elementAt(i))
- .propagate_lookaheads(lookahead());
- }
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Produce the new lalr_item that results from shifting the dot one position
- * to the right.
- */
- public lalr_item shift() throws internal_error
- {
- lalr_item result;
-
- /* can't shift if we have dot already at the end */
- if (dot_at_end())
- throw new internal_error("Attempt to shift past end of an lalr_item");
-
- /* create the new item w/ the dot shifted by one */
- result = new lalr_item(the_production(), dot_pos()+1,
- new terminal_set(lookahead()));
-
- /* change in our lookahead needs to be propagated to this item */
- add_propagate(result);
-
- return result;
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Calculate lookahead representing symbols that could appear after the
- * symbol that the dot is currently in front of. Note: this routine must
- * not be invoked before first sets and nullability has been calculated
- * for all non terminals.
- */
- public terminal_set calc_lookahead(terminal_set lookahead_after)
- throws internal_error
- {
- terminal_set result;
- int pos;
- production_part part;
- symbol sym;
-
- /* sanity check */
- if (dot_at_end())
- throw new internal_error(
- "Attempt to calculate a lookahead set with a completed item");
-
- /* start with an empty result */
- result = new terminal_set();
-
- /* consider all nullable symbols after the one to the right of the dot */
- for (pos = dot_pos()+1; pos < the_production().rhs_length(); pos++)
- {
- part = the_production().rhs(pos);
-
- /* consider what kind of production part it is -- skip actions */
- if (!part.is_action())
- {
- sym = ((symbol_part)part).the_symbol();
-
- /* if its a terminal add it in and we are done */
- if (!sym.is_non_term())
- {
- result.add((terminal)sym);
- return result;
- }
- else
- {
- /* otherwise add in first set of the non terminal */
- result.add(((non_terminal)sym).first_set());
-
- /* if its nullable we continue adding, if not, we are done */
- if (!((non_terminal)sym).nullable())
- return result;
- }
- }
- }
-
- /* if we get here everything past the dot was nullable
- we add in the lookahead for after the production and we are done */
- result.add(lookahead_after);
- return result;
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Determine if everything from the symbol one beyond the dot all the
- * way to the end of the right hand side is nullable. This would indicate
- * that the lookahead of this item must be included in the lookaheads of
- * all items produced as a closure of this item. Note: this routine should
- * not be invoked until after first sets and nullability have been
- * calculated for all non terminals.
- */
- public boolean lookahead_visible() throws internal_error
- {
- production_part part;
- symbol sym;
-
- /* if the dot is at the end, we have a problem, but the cleanest thing
- to do is just return true. */
- if (dot_at_end()) return true;
-
- /* walk down the rhs and bail if we get a non-nullable symbol */
- for (int pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++)
- {
- part = the_production().rhs(pos);
-
- /* skip actions */
- if (!part.is_action())
- {
- sym = ((symbol_part)part).the_symbol();
-
- /* if its a terminal we fail */
- if (!sym.is_non_term()) return false;
-
- /* if its not nullable we fail */
- if (!((non_terminal)sym).nullable()) return false;
- }
- }
-
- /* if we get here its all nullable */
- return true;
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Equality comparison -- here we only require the cores to be equal since
- * we need to do sets of items based only on core equality (ignoring
- * lookahead sets).
- */
- public boolean equals(lalr_item other)
- {
- if (other == null) return false;
- return super.equals(other);
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Generic equality comparison. */
- public boolean equals(Object other)
- {
- if (!(other instanceof lalr_item))
- return false;
- else
- return equals((lalr_item)other);
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Return a hash code -- here we only hash the core since we only test core
- * matching in LALR items.
- */
- public int hashCode()
- {
- return super.hashCode();
- }
-
- /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
-
- /** Convert to string. */
- public String toString()
- {
- String result = "";
-
- // additional output for debugging:
- // result += "(" + obj_hash() + ")";
- result += "[";
- result += super.toString();
- result += ", ";
- if (lookahead() != null)
- {
- result += "{";
- for (int t = 0; t < terminal.number(); t++)
- if (lookahead().contains(t))
- result += terminal.find(t).name() + " ";
- result += "}";
- }
- else
- result += "NULL LOOKAHEAD!!";
- result += "]";
-
- // additional output for debugging:
- // result += " -> ";
- // for (int i = 0; i<propagate_items().size(); i++)
- // result+=((lalr_item)(propagate_items().elementAt(i))).obj_hash()+" ";
- //
- // if (needs_propagation) result += " NP";
-
- return result;
- }
- /*-----------------------------------------------------------*/
-}
projects / IRC.git / blobdiff