← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/weka/jaunty

« back to all changes in this revision

Viewing changes to weka/core/parser/java_cup/lalr_item_set.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg, Torsten Werner, Soeren Sonnenburg
  • Date: 2008-10-30 06:42:46 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20081030064246-648zj038l155host
Tags: 3.5.8+cup1-1
[ Torsten Werner ]
* Update Section field in doc-base file.
* Add Class-Path attribute to jar file.

[ Soeren Sonnenburg ]
* Update my email address to sonne@debian.org.
* Update copyright.
* Remove build, java cup and jflex from orig.tar.gz.
* Add cup and jflex as build dependency.
* Patch weka source to use cup from debian.
* Patch weka shell wrapper to use java-6-sun or openjdk.
* Obtain documentation from svn.
* Build depend on texlive-latex-extra (required to generate documentation).
* Add javadoc as build target.
* Use java-wrappers to start weka.

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/core/parser/java_cup/lalr_item_set.java
1
 
/*
2
 
 * STANDARD ML OF NEW JERSEY COPYRIGHT NOTICE, LICENSE AND DISCLAIMER.
3
 
 * 
4
 
 * Copyright (c) 1989-1998 by Lucent Technologies
5
 
 * 
6
 
 * Permission to use, copy, modify, and distribute this software and its
7
 
 * documentation for any purpose and without fee is hereby granted, provided
8
 
 * that the above copyright notice appear in all copies and that both the
9
 
 * copyright notice and this permission notice and warranty disclaimer appear
10
 
 * in supporting documentation, and that the name of Lucent Technologies, Bell
11
 
 * Labs or any Lucent entity not be used in advertising or publicity pertaining
12
 
 * to distribution of the software without specific, written prior permission.
13
 
 *
14
 
 * Lucent disclaims all warranties with regard to this software, including all
15
 
 * implied warranties of merchantability and fitness. In no event shall Lucent
16
 
 * be liable for any special, indirect or consequential damages or any damages
17
 
 * whatsoever resulting from loss of use, data or profits, whether in an action
18
 
 * of contract, negligence or other tortious action, arising out of or in
19
 
 * connection with the use or performance of this software. 
20
 
 *
21
 
 * Taken from this URL:
22
 
 * http://www.smlnj.org/license.html
23
 
 * 
24
 
 * This license is compatible with the GNU GPL (see section "Standard ML of New
25
 
 * Jersey Copyright License"):
26
 
 * http://www.gnu.org/licenses/license-list.html#StandardMLofNJ
27
 
 */
28
 
 
29
 
/*
30
 
 * Copyright 1996-1999 by Scott Hudson, Frank Flannery, C. Scott Ananian
31
 
 */
32
 
 
33
 
package weka.core.parser.java_cup;
34
 
 
35
 
import java.util.Hashtable;
36
 
import java.util.Enumeration;
37
 
 
38
 
/** This class represents a set of LALR items.  For purposes of building
39
 
 *  these sets, items are considered unique only if they have unique cores
40
 
 *  (i.e., ignoring differences in their lookahead sets).<p>
41
 
 *
42
 
 *  This class provides fairly conventional set oriented operations (union,
43
 
 *  sub/super-set tests, etc.), as well as an LALR "closure" operation (see 
44
 
 *  compute_closure()).
45
 
 *
46
 
 * @see     weka.core.parser.java_cup.lalr_item
47
 
 * @see     weka.core.parser.java_cup.lalr_state
48
 
 * @version last updated: 3/6/96
49
 
 * @author  Scott Hudson
50
 
 */
51
 
 
52
 
public class lalr_item_set {
53
 
 
54
 
  /*-----------------------------------------------------------*/
55
 
  /*--- Constructor(s) ----------------------------------------*/
56
 
  /*-----------------------------------------------------------*/
57
 
 
58
 
  /** Constructor for an empty set. */
59
 
  public lalr_item_set() { }
60
 
 
61
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
62
 
 
63
 
  /** Constructor for cloning from another set. 
64
 
   * @param other indicates set we should copy from.
65
 
   */
66
 
  public lalr_item_set(lalr_item_set other) 
67
 
    throws internal_error
68
 
    {
69
 
      not_null(other);
70
 
      _all = (Hashtable)other._all.clone();
71
 
    }
72
 
 
73
 
  /*-----------------------------------------------------------*/
74
 
  /*--- (Access to) Instance Variables ------------------------*/
75
 
  /*-----------------------------------------------------------*/
76
 
 
77
 
  /** A hash table to implement the set.  We store the items using themselves
78
 
   *  as keys. 
79
 
   */
80
 
  protected Hashtable _all = new Hashtable(11);
81
 
 
82
 
  /** Access to all elements of the set. */
83
 
  public Enumeration all() {return _all.elements();}
84
 
 
85
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
86
 
 
87
 
  /** Cached hashcode for this set. */
88
 
  protected Integer hashcode_cache = null;
89
 
 
90
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
91
 
 
92
 
  /** Size of the set */
93
 
  public int size() {return _all.size();}
94
 
 
95
 
  /*-----------------------------------------------------------*/
96
 
  /*--- Set Operation Methods ---------------------------------*/
97
 
  /*-----------------------------------------------------------*/
98
 
 
99
 
  /** Does the set contain a particular item? 
100
 
   * @param itm the item in question.
101
 
   */
102
 
  public boolean contains(lalr_item itm) {return _all.containsKey(itm);}
103
 
 
104
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
105
 
 
106
 
  /** Return the item in the set matching a particular item (or null if not 
107
 
   *  found) 
108
 
   *  @param itm the item we are looking for.
109
 
   */
110
 
  public lalr_item find(lalr_item itm) {return (lalr_item)_all.get(itm);}
111
 
 
112
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
113
 
 
114
 
  /** Is this set an (improper) subset of another? 
115
 
   * @param other the other set in question.
116
 
   */
117
 
  public boolean is_subset_of(lalr_item_set other) throws internal_error
118
 
    {
119
 
      not_null(other);
120
 
 
121
 
      /* walk down our set and make sure every element is in the other */
122
 
      for (Enumeration e = all(); e.hasMoreElements(); )
123
 
        if (!other.contains((lalr_item)e.nextElement()))
124
 
          return false;
125
 
 
126
 
      /* they were all there */
127
 
      return true;
128
 
    }
129
 
 
130
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
131
 
 
132
 
  /** Is this set an (improper) superset of another? 
133
 
   * @param other the other set in question.
134
 
   */
135
 
  public boolean is_superset_of(lalr_item_set other) throws internal_error
136
 
    {
137
 
      not_null(other);
138
 
      return other.is_subset_of(this);
139
 
    }
140
 
 
141
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
142
 
 
143
 
  /** Add a singleton item, merging lookahead sets if the item is already 
144
 
   *  part of the set.  returns the element of the set that was added or 
145
 
   *  merged into.
146
 
   * @param itm the item being added.
147
 
   */
148
 
  public lalr_item add(lalr_item itm) throws internal_error
149
 
    {
150
 
      lalr_item other;
151
 
 
152
 
      not_null(itm); 
153
 
 
154
 
      /* see if an item with a matching core is already there */
155
 
      other = (lalr_item)_all.get(itm);
156
 
 
157
 
      /* if so, merge this lookahead into the original and leave it */
158
 
      if (other != null)
159
 
        {
160
 
          other.lookahead().add(itm.lookahead());
161
 
          return other;
162
 
        }
163
 
      /* otherwise we just go in the set */
164
 
      else
165
 
        {
166
 
          /* invalidate cached hashcode */
167
 
          hashcode_cache = null;
168
 
 
169
 
          _all.put(itm,itm);
170
 
          return itm;
171
 
        }
172
 
    }
173
 
 
174
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
175
 
 
176
 
  /** Remove a single item if it is in the set. 
177
 
   * @param itm the item to remove.
178
 
   */
179
 
  public void remove(lalr_item itm) throws internal_error
180
 
    {
181
 
      not_null(itm); 
182
 
 
183
 
      /* invalidate cached hashcode */
184
 
      hashcode_cache = null;
185
 
 
186
 
      /* remove it from hash table implementing set */
187
 
      _all.remove(itm);
188
 
    }
189
 
 
190
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
191
 
 
192
 
  /** Add a complete set, merging lookaheads where items are already in 
193
 
   *  the set 
194
 
   * @param other the set to be added.
195
 
   */
196
 
  public void add(lalr_item_set other) throws internal_error
197
 
    {
198
 
      not_null(other);
199
 
 
200
 
      /* walk down the other set and do the adds individually */
201
 
      for (Enumeration e = other.all(); e.hasMoreElements(); )
202
 
        add((lalr_item)e.nextElement());
203
 
    }
204
 
 
205
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
206
 
 
207
 
  /** Remove (set subtract) a complete set. 
208
 
   * @param other the set to remove.
209
 
   */
210
 
  public void remove(lalr_item_set other) throws internal_error
211
 
    {
212
 
      not_null(other);
213
 
 
214
 
      /* walk down the other set and do the removes individually */
215
 
      for (Enumeration e = other.all(); e.hasMoreElements(); )
216
 
        remove((lalr_item)e.nextElement());
217
 
    }
218
 
 
219
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
220
 
 
221
 
  /** Remove and return one item from the set (done in hash order). */
222
 
  public lalr_item get_one() throws internal_error
223
 
    {
224
 
      Enumeration the_set;
225
 
      lalr_item result;
226
 
 
227
 
      the_set = all();
228
 
      if (the_set.hasMoreElements())
229
 
        {
230
 
          result = (lalr_item)the_set.nextElement();
231
 
          remove(result);
232
 
          return result;
233
 
        }
234
 
      else
235
 
        return null;
236
 
    }
237
 
 
238
 
  /*-----------------------------------------------------------*/
239
 
  /*--- General Methods ---------------------------------------*/
240
 
  /*-----------------------------------------------------------*/
241
 
 
242
 
  /** Helper function for null test.  Throws an interal_error exception if its
243
 
   *  parameter is null.
244
 
   *  @param obj the object we are testing.
245
 
   */
246
 
  protected void not_null(Object obj) throws internal_error
247
 
    {
248
 
      if (obj == null) 
249
 
        throw new internal_error("Null object used in set operation");
250
 
    }
251
 
 
252
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
253
 
 
254
 
  /** Compute the closure of the set using the LALR closure rules.  Basically
255
 
   *  for every item of the form: <pre>
256
 
   *    [L ::= a *N alpha, l] 
257
 
   *  </pre>
258
 
   *  (where N is a a non terminal and alpha is a string of symbols) make 
259
 
   *  sure there are also items of the form:  <pre>
260
 
   *    [N ::= *beta, first(alpha l)] 
261
 
   *  </pre>
262
 
   *  corresponding to each production of N.  Items with identical cores but 
263
 
   *  differing lookahead sets are merged by creating a new item with the same 
264
 
   *  core and the union of the lookahead sets (the LA in LALR stands for 
265
 
   *  "lookahead merged" and this is where the merger is).  This routine 
266
 
   *  assumes that nullability and first sets have been computed for all 
267
 
   *  productions before it is called.
268
 
   */
269
 
  public void compute_closure()
270
 
    throws internal_error
271
 
    {
272
 
      lalr_item_set consider;
273
 
      lalr_item     itm, new_itm, add_itm;
274
 
      non_terminal  nt;
275
 
      terminal_set  new_lookaheads;
276
 
      Enumeration   p;
277
 
      production    prod;
278
 
      boolean       need_prop;
279
 
 
280
 
 
281
 
 
282
 
      /* invalidate cached hashcode */
283
 
      hashcode_cache = null;
284
 
 
285
 
      /* each current element needs to be considered */
286
 
      consider = new lalr_item_set(this);
287
 
 
288
 
      /* repeat this until there is nothing else to consider */
289
 
      while (consider.size() > 0)
290
 
        {
291
 
          /* get one item to consider */
292
 
          itm = consider.get_one(); 
293
 
 
294
 
          /* do we have a dot before a non terminal */
295
 
          nt = itm.dot_before_nt();
296
 
          if (nt != null)
297
 
            {
298
 
              /* create the lookahead set based on first after dot */
299
 
              new_lookaheads = itm.calc_lookahead(itm.lookahead());
300
 
 
301
 
              /* are we going to need to propagate our lookahead to new item */
302
 
              need_prop = itm.lookahead_visible();
303
 
 
304
 
              /* create items for each production of that non term */
305
 
              for (p = nt.productions(); p.hasMoreElements(); )
306
 
                {
307
 
                  prod = (production)p.nextElement();
308
 
 
309
 
                  /* create new item with dot at start and that lookahead */
310
 
                  new_itm = new lalr_item(prod, 
311
 
                                             new terminal_set(new_lookaheads));
312
 
 
313
 
                  /* add/merge item into the set */
314
 
                  add_itm = add(new_itm);
315
 
                  /* if propagation is needed link to that item */
316
 
                  if (need_prop)
317
 
                    itm.add_propagate(add_itm);
318
 
 
319
 
                  /* was this was a new item*/
320
 
                  if (add_itm == new_itm)
321
 
                    {
322
 
                      /* that may need further closure, consider it also */ 
323
 
                      consider.add(new_itm);
324
 
                    } 
325
 
                } 
326
 
            } 
327
 
        } 
328
 
    }
329
 
 
330
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
331
 
 
332
 
  /** Equality comparison. */
333
 
  public boolean equals(lalr_item_set other)
334
 
    {
335
 
      if (other == null || other.size() != size()) return false;
336
 
 
337
 
      /* once we know they are the same size, then improper subset does test */
338
 
      try {
339
 
        return is_subset_of(other);
340
 
      } catch (internal_error e) {
341
 
        /* can't throw error from here (because superclass doesn't) so crash */
342
 
        e.crash();
343
 
        return false;
344
 
      }
345
 
 
346
 
    }
347
 
 
348
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
349
 
 
350
 
  /** Generic equality comparison. */
351
 
  public boolean equals(Object other)
352
 
    {
353
 
      if (!(other instanceof lalr_item_set))
354
 
        return false;
355
 
      else
356
 
        return equals((lalr_item_set)other);
357
 
    }
358
 
 
359
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
360
 
 
361
 
  /** Return hash code. */
362
 
  public int hashCode()
363
 
    {
364
 
      int result = 0;
365
 
      Enumeration e;
366
 
      int cnt;
367
 
 
368
 
      /* only compute a new one if we don't have it cached */
369
 
      if (hashcode_cache == null)
370
 
        {
371
 
          /* hash together codes from at most first 5 elements */
372
 
          //   CSA fix! we'd *like* to hash just a few elements, but
373
 
          //   that means equal sets will have inequal hashcodes, which
374
 
          //   we're not allowed (by contract) to do.  So hash them all.
375
 
          for (e = all(), cnt=0 ; e.hasMoreElements() /*&& cnt<5*/; cnt++)
376
 
            result ^= ((lalr_item)e.nextElement()).hashCode();
377
 
 
378
 
          hashcode_cache = new Integer(result);
379
 
        }
380
 
 
381
 
      return hashcode_cache.intValue();
382
 
    }
383
 
 
384
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
385
 
 
386
 
  /** Convert to string. */
387
 
  public String toString()
388
 
    {
389
 
      StringBuffer result = new StringBuffer();
390
 
 
391
 
      result.append("{\n");
392
 
      for (Enumeration e=all(); e.hasMoreElements(); ) 
393
 
        {
394
 
          result.append("  " + (lalr_item)e.nextElement() + "\n");
395
 
        }
396
 
       result.append("}");
397
 
 
398
 
       return result.toString();
399
 
    }
400
 
    /*-----------------------------------------------------------*/
401
 
}
402