Source code: 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 }