KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > beaver > comp > Configuration


1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2  * This file is part of Beaver Parser Generator. *
3  * Copyright (C) 2003,2004 Alexander Demenchuk <alder@softanvil.com>. *
4  * All rights reserved. *
5  * See the file "LICENSE" for the terms and conditions for copying, *
6  * distribution and modification of Beaver. *
7  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

8
9 package beaver.comp;
10
11 import java.util.Arrays JavaDoc;
12 import java.util.HashMap JavaDoc;
13 import java.util.Map JavaDoc;
14
15 import beaver.comp.util.BitSet;
16 import beaver.spec.Grammar;
17 import beaver.spec.GrammarSymbol;
18 import beaver.spec.NonTerminal;
19 import beaver.spec.Production;
20 import beaver.spec.Terminal;
21
22
23 /**
24  * This class represents an LALR item or a parser configuration. Each configuration consists of a
25  * production, a "dot" that marks a position in a production and a set of lookahead symbols.
26  */

27 class Configuration implements Comparable JavaDoc
28 {
29     static class Set
30     {
31         static class Factory
32         {
33             private Map JavaDoc configurations;
34             private Configuration probe;
35             private Grammar grammar;
36
37             /** Start of a linked list of all configurations in a state */
38             Configuration first_conf;
39
40             /** Last configuration in a list. Place where we add new configurations. */
41             Configuration last_conf;
42
43             /** Number of configurations added so far */
44             int num_conf;
45
46             Factory(Grammar grammar)
47             {
48                 this.configurations = new HashMap JavaDoc(89);
49                 this.probe = new Configuration();
50                 this.grammar = grammar;
51             }
52
53             void reset()
54             {
55                 first_conf = last_conf = null;
56                 num_conf = 0;
57
58                 //configurations.clear();
59
configurations = new HashMap JavaDoc(89);
60             }
61
62             Configuration addConfiguration(Production rule, int mark)
63             {
64                 probe.rule = rule;
65                 probe.dot = mark;
66
67                 Configuration conf = (Configuration) configurations.get(probe);
68                 if (conf == null)
69                 {
70                     conf = new Configuration(probe, grammar);
71                     configurations.put(conf, conf);
72
73                     if (last_conf == null)
74                         last_conf = first_conf = conf;
75                     else
76                         last_conf = last_conf.next = conf;
77                     num_conf++;
78                 }
79                 return conf;
80             }
81
82             Set getCore()
83             {
84                 Configuration[] core = new Configuration[num_conf];
85                 int j = 0;
86                 for (Configuration conf = first_conf; conf != null; conf = conf.next)
87                 {
88                     core[j++] = conf;
89                 }
90                 Arrays.sort(core);
91
92                 Configuration conf = first_conf = core[0];
93                 int core_hash_code = conf.hashCode();
94                 for (j = 1; j < num_conf; j++)
95                 {
96                     conf = conf.next = core[j];
97                     core_hash_code = core_hash_code * 571 + conf.hashCode();
98                 }
99                 last_conf = conf;
100                 conf.next = null;
101
102                 return new Set(this, core_hash_code);
103             }
104         }
105
106         /** Producer of new configurations in this set */
107         Configuration.Set.Factory conf_set_factory;
108
109         /** Start of a linked list of all configurations in a state */
110         Configuration first_conf;
111
112         /** Last core configuration. */
113         Configuration last_core_conf;
114
115         /** Cached core size */
116         int core_size;
117
118         /** Cached core hash code */
119         int core_hash_code;
120
121         private Set(Configuration.Set.Factory conf_set_factory, int hash_code)
122         {
123             this.conf_set_factory = conf_set_factory;
124             this.first_conf = conf_set_factory.first_conf;
125             this.last_core_conf = conf_set_factory.last_conf;
126             this.core_hash_code = hash_code;
127             this.core_size = conf_set_factory.num_conf;
128         }
129
130         void appendReversePropagation(Set conf_set)
131         {
132             Configuration stop = last_core_conf.next;
133             for (Configuration my_conf = first_conf, cp_conf = conf_set.first_conf; my_conf != stop; my_conf = my_conf.next, cp_conf = cp_conf.next)
134             {
135                 my_conf.appendReversePropagation(cp_conf);
136             }
137         }
138
139         void buildClosure()
140         {
141             for (Configuration conf = first_conf; conf != null; conf = conf.next)
142             {
143                 if (conf.isDotAfterLastSymbol())
144                     continue;
145
146                 GrammarSymbol sym = conf.getSymbolAfterDot();
147                 if (sym instanceof NonTerminal)
148                 {
149                     NonTerminal nt = (NonTerminal) sym;
150                     for (Production rule = nt.definitions.start(); rule != null; rule = rule.next_definition)
151                     {
152                         Configuration new_conf = conf_set_factory.addConfiguration(rule, 0);
153                         if (new_conf.addLookaheads(conf))
154                         {
155                             conf.addForwardPropagation(new_conf);
156                         }
157                     }
158                 }
159             }
160         }
161         
162         void reverseReversePropagation()
163         {
164             for (Configuration conf = first_conf; conf != null; conf = conf.next)
165             {
166                 conf.reverseReversePropagation();
167             }
168         }
169
170         void resetContributionFlags()
171         {
172             for (Configuration conf = first_conf; conf != null; conf = conf.next)
173             {
174                 conf.has_contributed = false;
175             }
176         }
177
178         private boolean equals(Set conf_set)
179         {
180             if (conf_set == this)
181                 return true;
182
183             if (conf_set.core_size != this.core_size)
184                 return false;
185
186             Configuration my_conf = first_conf;
187             Configuration cmp_conf = conf_set.first_conf;
188             Configuration stop = last_core_conf.next;
189             while (my_conf != stop && my_conf.equals(cmp_conf))
190             {
191                 my_conf = my_conf.next;
192                 cmp_conf = cmp_conf.next;
193             }
194             return my_conf == stop;
195         }
196
197         public boolean equals(Object JavaDoc obj)
198         {
199             return obj instanceof Set && this.equals((Set) obj);
200         }
201
202         public int hashCode()
203         {
204             return core_hash_code;
205         }
206
207         public String JavaDoc toString()
208         {
209             StringBuffer JavaDoc str = new StringBuffer JavaDoc(1000);
210             Configuration conf = first_conf;
211             for (; conf != last_core_conf.next; conf = conf.next)
212             {
213                 str.append('+').append(conf).append('\n');
214             }
215             for (; conf != null; conf = conf.next)
216             {
217                 str.append(' ').append(conf).append('\n');
218             }
219             return str.toString();
220         }
221     }
222
223     static class PropagationLink
224     {
225         /** Next element in a linked list */
226         PropagationLink next;
227
228         /** A configuration to propagate to/from */
229         Configuration conf;
230
231         PropagationLink(Configuration conf)
232         {
233             this.conf = conf;
234         }
235     }
236
237     /** Next configuration in a linked list of state configurations */
238     Configuration next;
239
240     Production rule;
241     int dot;
242     BitSet lookaheads;
243
244     // Configurations may initially be missing some symbols from their lookahead sets.
245
// Links are maintained from each configuration to the set of configurations that
246
// would need to be updated if symbols are added to the lookahead set.
247
PropagationLink fwd_propagation;
248     PropagationLink bck_propagation, last_bck_propagation;
249
250     /**
251      * A flags that is used by state factory to mark configurations that have already
252      * contributed to a successor state.
253      */

254     boolean has_contributed;
255
256     /**
257      * Constructor for a Configuration.Factory probe
258      */

259     private Configuration()
260     {
261     }
262
263     Configuration(Configuration factory_probe, Grammar grammar)
264     {
265         this.rule = factory_probe.rule;
266         this.dot = factory_probe.dot;
267         this.lookaheads = new BitSet(grammar.terminals.length);
268     }
269
270     GrammarSymbol getSymbolAfterDot()
271     {
272         return rule.rhs.items[dot].symbol;
273     }
274
275     boolean isDotAfterLastSymbol()
276     {
277         return dot == rule.rhs.items.length;
278     }
279
280     void addLookahead(Terminal term)
281     {
282         lookaheads.add(term.id);
283     }
284
285     /**
286      * Adds lookahead symbols from a given configuration.
287      *
288      * @return true if all rhs parts were nullable nonterminals and hence the lookahead set
289      * needs to be expanded by propagating terminals from configurations that contribute
290      * lookaheadds to the current source of terminals.
291      */

292     boolean addLookaheads(Configuration conf)
293     {
294         for (int i = conf.dot + 1; i < conf.rule.rhs.items.length; i++)
295         {
296             GrammarSymbol sym = conf.rule.rhs.items[i].symbol;
297             if (sym instanceof Terminal)
298             {
299                 lookaheads.add(sym.id);
300                 return false;
301             }
302             else
303             {
304                 NonTerminal nt = (NonTerminal) sym;
305                 lookaheads.add(nt.first_set);
306                 if (!nt.is_nullable)
307                     return false;
308             }
309         }
310         return true;
311     }
312
313     void addForwardPropagation(Configuration conf)
314     {
315         PropagationLink link = new PropagationLink(conf);
316         link.next = fwd_propagation;
317         fwd_propagation = link;
318     }
319
320     void addReversePropagation(Configuration conf)
321     {
322         PropagationLink link = new PropagationLink(conf);
323         if (last_bck_propagation == null)
324             last_bck_propagation = bck_propagation = link;
325         else
326             last_bck_propagation = last_bck_propagation.next = link;
327     }
328
329     void appendReversePropagation(Configuration conf)
330     {
331         if (last_bck_propagation == null)
332             bck_propagation = conf.bck_propagation;
333         else
334             last_bck_propagation.next = conf.bck_propagation;
335         last_bck_propagation = conf.last_bck_propagation;
336     }
337
338     void reverseReversePropagation()
339     {
340         PropagationLink link = bck_propagation;
341         while (link != null)
342         {
343             PropagationLink next_link = link.next;
344             Configuration conf = link.conf;
345
346             link.conf = this;
347             link.next = conf.fwd_propagation;
348             conf.fwd_propagation = link;
349
350             link = next_link;
351         }
352         bck_propagation = null;
353     }
354
355     boolean findLookaheads()
356     {
357         boolean more_found = false;
358         for (PropagationLink link = fwd_propagation; link != null; link = link.next)
359         {
360             if (link.conf.lookaheads.add(this.lookaheads))
361             {
362                 more_found = true;
363                 link.conf.has_contributed = false;
364             }
365         }
366         return more_found;
367     }
368
369     boolean equals(Configuration conf)
370     {
371         return this.rule == conf.rule && this.dot == conf.dot;
372     }
373
374     public boolean equals(Object JavaDoc obj)
375     {
376         return obj instanceof Configuration && this.equals((Configuration) obj);
377     }
378
379     public int hashCode()
380     {
381         return rule.id * 37 + dot;
382     }
383
384     /**
385      * Defined ordering of two configurations in a set.
386      * <p/>
387      * Sets are kept ordered, so it's easy to match cores of configuration set
388      *
389      * @param o another Configuration
390      * @return int < 0, 0, or int > 0 if current Configuration <, ==, or > the one provided in the method's argument
391      */

392     public int compareTo(Object JavaDoc o)
393     {
394         if (o == this)
395             return 0;
396
397         Configuration conf = (Configuration) o;
398         int cmp = this.rule.id - conf.rule.id;
399         if (cmp == 0)
400         {
401             cmp = this.dot - conf.dot;
402         }
403         return cmp;
404     }
405
406     public String JavaDoc toString()
407     {
408         StringBuffer JavaDoc str = new StringBuffer JavaDoc(100);
409         str.append(rule.lhs).append(" =");
410         for (int i = 0; i < rule.rhs.items.length; i++)
411         {
412             Production.RHS.Item rhs_item = rule.rhs.items[i];
413             str.append(' ');
414             if (i == dot)
415                 str.append('*');
416             str.append(rhs_item);
417         }
418         if (dot == rule.rhs.items.length)
419             str.append(" *");
420         int line;
421         if ((line = rule.getFirstLine()) > 0)
422         {
423             str.append(" @ ").append(line);
424         }
425         return str.toString();
426     }
427 }
428
Popular Tags