diff options
Diffstat (limited to 'src/syntaxParser/java_cup/lalr_item.java')
| -rw-r--r-- | src/syntaxParser/java_cup/lalr_item.java | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/src/syntaxParser/java_cup/lalr_item.java b/src/syntaxParser/java_cup/lalr_item.java new file mode 100644 index 0000000..fe92054 --- /dev/null +++ b/src/syntaxParser/java_cup/lalr_item.java @@ -0,0 +1,330 @@ +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; + } + /*-----------------------------------------------------------*/ +} |