001: package java_cup;
002:
003: import java.util.Stack;
004: import java.util.Enumeration;
005:
006: /** This class represents an LALR item. Each LALR item consists of
007: * a production, a "dot" at a position within that production, and
008: * a set of lookahead symbols (terminal). (The first two of these parts
009: * are provide by the super class). An item is designed to represent a
010: * configuration that the parser may be in. For example, an item of the
011: * form: <pre>
012: * [A ::= B * C d E , {a,b,c}]
013: * </pre>
014: * indicates that the parser is in the middle of parsing the production <pre>
015: * A ::= B C d E
016: * </pre>
017: * that B has already been parsed, and that we will expect to see a lookahead
018: * of either a, b, or c once the complete RHS of this production has been
019: * found.<p>
020: *
021: * Items may initially be missing some items from their lookahead sets.
022: * Links are maintained from each item to the set of items that would need
023: * to be updated if symbols are added to its lookahead set. During
024: * "lookahead propagation", we add symbols to various lookahead sets and
025: * propagate these changes across these dependency links as needed.
026: *
027: * @see java_cup.lalr_item_set
028: * @see java_cup.lalr_state
029: * @version last updated: 11/25/95
030: * @author Scott Hudson
031: */
032: public class lalr_item extends lr_item_core {
033:
034: /*-----------------------------------------------------------*/
035: /*--- Constructor(s) ----------------------------------------*/
036: /*-----------------------------------------------------------*/
037:
038: /** Full constructor.
039: * @param prod the production for the item.
040: * @param pos the position of the "dot" within the production.
041: * @param look the set of lookahead symbols.
042: */
043: public lalr_item(production prod, int pos, terminal_set look)
044: throws internal_error {
045: super (prod, pos);
046: _lookahead = look;
047: _propagate_items = new Stack();
048: needs_propagation = true;
049: }
050:
051: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
052:
053: /** Constructor with default position (dot at start).
054: * @param prod the production for the item.
055: * @param look the set of lookahead symbols.
056: */
057: public lalr_item(production prod, terminal_set look)
058: throws internal_error {
059: this (prod, 0, look);
060: }
061:
062: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
063:
064: /** Constructor with default position and empty lookahead set.
065: * @param prod the production for the item.
066: */
067: public lalr_item(production prod) throws internal_error {
068: this (prod, 0, new terminal_set());
069: }
070:
071: /*-----------------------------------------------------------*/
072: /*--- (Access to) Instance Variables ------------------------*/
073: /*-----------------------------------------------------------*/
074:
075: /** The lookahead symbols of the item. */
076: protected terminal_set _lookahead;
077:
078: /** The lookahead symbols of the item. */
079: public terminal_set lookahead() {
080: return _lookahead;
081: }
082:
083: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
084:
085: /** Links to items that the lookahead needs to be propagated to. */
086: protected Stack _propagate_items;
087:
088: /** Links to items that the lookahead needs to be propagated to */
089: public Stack propagate_items() {
090: return _propagate_items;
091: }
092:
093: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
094:
095: /** Flag to indicate that this item needs to propagate its lookahead
096: * (whether it has changed or not).
097: */
098: protected boolean needs_propagation;
099:
100: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
101:
102: /** Add a new item to the set of items we propagate to. */
103: public void add_propagate(lalr_item prop_to) {
104: _propagate_items.push(prop_to);
105: needs_propagation = true;
106: }
107:
108: /*-----------------------------------------------------------*/
109: /*--- General Methods ---------------------------------------*/
110: /*-----------------------------------------------------------*/
111:
112: /** Propagate incoming lookaheads through this item to others need to
113: * be changed.
114: * @params incoming symbols to potentially be added to lookahead of this item.
115: */
116: public void propagate_lookaheads(terminal_set incoming)
117: throws internal_error {
118: boolean change = false;
119:
120: /* if we don't need to propagate, then bail out now */
121: if (!needs_propagation
122: && (incoming == null || incoming.empty()))
123: return;
124:
125: /* if we have null incoming, treat as an empty set */
126: if (incoming != null) {
127: /* add the incoming to the lookahead of this item */
128: change = lookahead().add(incoming);
129: }
130:
131: /* if we changed or need it anyway, propagate across our links */
132: if (change || needs_propagation) {
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: lalr_item result;
150:
151: /* can't shift if we have dot already at the end */
152: if (dot_at_end())
153: throw new internal_error(
154: "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: terminal_set result;
176: int pos;
177: production_part part;
178: symbol sym;
179:
180: /* sanity check */
181: if (dot_at_end())
182: throw new internal_error(
183: "Attempt to calculate a lookahead set with a completed item");
184:
185: /* start with an empty result */
186: result = new terminal_set();
187:
188: /* consider all nullable symbols after the one to the right of the dot */
189: for (pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++) {
190: part = the_production().rhs(pos);
191:
192: /* consider what kind of production part it is -- skip actions */
193: if (!part.is_action()) {
194: sym = ((symbol_part) part).the_symbol();
195:
196: /* if its a terminal add it in and we are done */
197: if (!sym.is_non_term()) {
198: result.add((terminal) sym);
199: return result;
200: } else {
201: /* otherwise add in first set of the non terminal */
202: result.add(((non_terminal) sym).first_set());
203:
204: /* if its nullable we continue adding, if not, we are done */
205: if (!((non_terminal) sym).nullable())
206: return result;
207: }
208: }
209: }
210:
211: /* if we get here everything past the dot was nullable
212: we add in the lookahead for after the production and we are done */
213: result.add(lookahead_after);
214: return result;
215: }
216:
217: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
218:
219: /** Determine if everything from the symbol one beyond the dot all the
220: * way to the end of the right hand side is nullable. This would indicate
221: * that the lookahead of this item must be included in the lookaheads of
222: * all items produced as a closure of this item. Note: this routine should
223: * not be invoked until after first sets and nullability have been
224: * calculated for all non terminals.
225: */
226: public boolean lookahead_visible() throws internal_error {
227: production_part part;
228: symbol sym;
229:
230: /* if the dot is at the end, we have a problem, but the cleanest thing
231: to do is just return true. */
232: if (dot_at_end())
233: return true;
234:
235: /* walk down the rhs and bail if we get a non-nullable symbol */
236: for (int pos = dot_pos() + 1; pos < the_production()
237: .rhs_length(); pos++) {
238: part = the_production().rhs(pos);
239:
240: /* skip actions */
241: if (!part.is_action()) {
242: sym = ((symbol_part) part).the_symbol();
243:
244: /* if its a terminal we fail */
245: if (!sym.is_non_term())
246: return false;
247:
248: /* if its not nullable we fail */
249: if (!((non_terminal) sym).nullable())
250: return false;
251: }
252: }
253:
254: /* if we get here its all nullable */
255: return true;
256: }
257:
258: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
259:
260: /** Equality comparison -- here we only require the cores to be equal since
261: * we need to do sets of items based only on core equality (ignoring
262: * lookahead sets).
263: */
264: public boolean equals(lalr_item other) {
265: if (other == null)
266: return false;
267: return super .equals(other);
268: }
269:
270: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
271:
272: /** Generic equality comparison. */
273: public boolean equals(Object other) {
274: if (!(other instanceof lalr_item))
275: return false;
276: else
277: return equals((lalr_item) other);
278: }
279:
280: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
281:
282: /** Return a hash code -- here we only hash the core since we only test core
283: * matching in LALR items.
284: */
285: public int hashCode() {
286: return super .hashCode();
287: }
288:
289: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
290:
291: /** Convert to string. */
292: public String toString() {
293: String result = "";
294:
295: // additional output for debugging:
296: // result += "(" + obj_hash() + ")";
297: result += "[";
298: result += super .toString();
299: result += ", ";
300: if (lookahead() != null) {
301: result += "{";
302: for (int t = 0; t < terminal.number(); t++)
303: if (lookahead().contains(t))
304: result += terminal.find(t).name() + " ";
305: result += "}";
306: } else
307: result += "NULL LOOKAHEAD!!";
308: result += "]";
309:
310: // additional output for debugging:
311: // result += " -> ";
312: // for (int i = 0; i<propagate_items().size(); i++)
313: // result+=((lalr_item)(propagate_items().elementAt(i))).obj_hash()+" ";
314: //
315: // if (needs_propagation) result += " NP";
316:
317: return result;
318: }
319: /*-----------------------------------------------------------*/
320: }
|