lalr_item


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 }
331
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags