package java_cup;
|
|
import java.util.Stack;
|
|
/** 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 += "(" + hashCode() + ")";
|
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 += propagate_items().elementAt(i).hashCode() + " ";
|
//
|
// if (needs_propagation) result += " NP";
|
|
return result;
|
}
|
/*-----------------------------------------------------------*/
|
};
|
