KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > java_cup > internal > lalr_item


1 package com.sun.java_cup.internal;
2
3 import java.util.Stack JavaDoc;
4 import java.util.Enumeration JavaDoc;
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 com.sun.java_cup.internal.lalr_item_set
28  * @see com.sun.java_cup.internal.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 JavaDoc();
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 JavaDoc _propagate_items;
87
88   /** Links to items that the lookahead needs to be propagated to */
89   public Stack JavaDoc 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 JavaDoc 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 JavaDoc toString()
300     {
301       String JavaDoc 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 }
331
Popular Tags