← 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/non_terminal.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/non_terminal.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 non-terminal symbol in the grammar.  Each
39
 
 *  non terminal has a textual name, an index, and a string which indicates
40
 
 *  the type of object it will be implemented with at runtime (i.e. the class
41
 
 *  of object that will be pushed on the parse stack to represent it). 
42
 
 *
43
 
 * @version last updated: 11/25/95
44
 
 * @author  Scott Hudson
45
 
 */
46
 
 
47
 
public class non_terminal extends symbol {
48
 
 
49
 
  /*-----------------------------------------------------------*/
50
 
  /*--- Constructor(s) ----------------------------------------*/
51
 
  /*-----------------------------------------------------------*/
52
 
 
53
 
  /** Full constructor.
54
 
   * @param nm  the name of the non terminal.
55
 
   * @param tp  the type string for the non terminal.
56
 
   */
57
 
  public non_terminal(String nm, String tp) 
58
 
    {
59
 
      /* super class does most of the work */
60
 
      super(nm, tp);
61
 
 
62
 
      /* add to set of all non terminals and check for duplicates */
63
 
      Object conflict = _all.put(nm,this);
64
 
      if (conflict != null)
65
 
        // can't throw an exception here because these are used in static
66
 
        // initializers, so we crash instead
67
 
        // was: 
68
 
        // throw new internal_error("Duplicate non-terminal ("+nm+") created");
69
 
        (new internal_error("Duplicate non-terminal ("+nm+") created")).crash();
70
 
 
71
 
      /* assign a unique index */
72
 
      _index = next_index++;
73
 
 
74
 
      /* add to by_index set */
75
 
      _all_by_index.put(new Integer(_index), this);
76
 
    }
77
 
 
78
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
79
 
 
80
 
  /** Constructor with default type. 
81
 
   * @param nm  the name of the non terminal.
82
 
   */
83
 
  public non_terminal(String nm) 
84
 
    {
85
 
      this(nm, null);
86
 
    }
87
 
 
88
 
  /*-----------------------------------------------------------*/
89
 
  /*--- (Access to) Static (Class) Variables ------------------*/
90
 
  /*-----------------------------------------------------------*/
91
 
 
92
 
  /** Table of all non-terminals -- elements are stored using name strings 
93
 
   *  as the key 
94
 
   */
95
 
  protected static Hashtable _all = new Hashtable();
96
 
 
97
 
  //Hm Added clear  to clear all static fields
98
 
  public static void clear() {
99
 
      _all.clear();
100
 
      _all_by_index.clear();
101
 
      next_index=0;
102
 
      next_nt=0;
103
 
  }
104
 
 
105
 
  /** Access to all non-terminals. */
106
 
  public static Enumeration all() {return _all.elements();}
107
 
 
108
 
  /** lookup a non terminal by name string */ 
109
 
  public static non_terminal find(String with_name)
110
 
    {
111
 
      if (with_name == null)
112
 
        return null;
113
 
      else 
114
 
        return (non_terminal)_all.get(with_name);
115
 
    }
116
 
 
117
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
118
 
 
119
 
  /** Table of all non terminals indexed by their index number. */
120
 
  protected static Hashtable _all_by_index = new Hashtable();
121
 
 
122
 
  /** Lookup a non terminal by index. */
123
 
  public static non_terminal find(int indx)
124
 
    {
125
 
      Integer the_indx = new Integer(indx);
126
 
 
127
 
      return (non_terminal)_all_by_index.get(the_indx);
128
 
    }
129
 
 
130
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
131
 
 
132
 
  /** Total number of non-terminals. */
133
 
  public static int number() {return _all.size();}
134
 
 
135
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
136
 
 
137
 
  /** Static counter to assign unique indexes. */
138
 
  protected static int next_index = 0;
139
 
 
140
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
141
 
 
142
 
  /** Static counter for creating unique non-terminal names */
143
 
  static protected int next_nt = 0;
144
 
 
145
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
146
 
 
147
 
  /** special non-terminal for start symbol */
148
 
  public static final non_terminal START_nt = new non_terminal("$START");
149
 
 
150
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
151
 
 
152
 
  /** flag non-terminals created to embed action productions */
153
 
  public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
154
 
 
155
 
  /*-----------------------------------------------------------*/
156
 
  /*--- Static Methods ----------------------------------------*/
157
 
  /*-----------------------------------------------------------*/
158
 
         
159
 
  /** Method for creating a new uniquely named hidden non-terminal using 
160
 
   *  the given string as a base for the name (or "NT$" if null is passed).
161
 
   * @param prefix base name to construct unique name from. 
162
 
   */
163
 
  static non_terminal create_new(String prefix) throws internal_error
164
 
    {
165
 
      return create_new(prefix,null); // TUM 20060608 embedded actions patch
166
 
    }
167
 
 
168
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
169
 
 
170
 
  /** static routine for creating a new uniquely named hidden non-terminal */
171
 
  static non_terminal create_new() throws internal_error
172
 
    { 
173
 
      return create_new(null); 
174
 
    }
175
 
    /**
176
 
     * TUM 20060608 bugfix for embedded action codes
177
 
     */
178
 
    static non_terminal create_new(String prefix, String type) throws internal_error{
179
 
        if (prefix==null) prefix = "NT$";
180
 
        return new non_terminal(prefix + next_nt++,type);
181
 
    }
182
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
183
 
 
184
 
  /** Compute nullability of all non-terminals. */
185
 
  public static void compute_nullability() throws internal_error
186
 
    {
187
 
      boolean      change = true;
188
 
      non_terminal nt;
189
 
      Enumeration  e;
190
 
      production   prod;
191
 
 
192
 
      /* repeat this process until there is no change */
193
 
      while (change)
194
 
        {
195
 
          /* look for a new change */
196
 
          change = false;
197
 
 
198
 
          /* consider each non-terminal */
199
 
          for (e=all(); e.hasMoreElements(); )
200
 
            {
201
 
              nt = (non_terminal)e.nextElement();
202
 
 
203
 
              /* only look at things that aren't already marked nullable */
204
 
              if (!nt.nullable())
205
 
                {
206
 
                  if (nt.looks_nullable())
207
 
                    {
208
 
                      nt._nullable = true;
209
 
                      change = true;
210
 
                    }
211
 
                }
212
 
            }
213
 
        }
214
 
      
215
 
      /* do one last pass over the productions to finalize all of them */
216
 
      for (e=production.all(); e.hasMoreElements(); )
217
 
        {
218
 
          prod = (production)e.nextElement();
219
 
          prod.set_nullable(prod.check_nullable());
220
 
        }
221
 
    }
222
 
 
223
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
224
 
 
225
 
  /** Compute first sets for all non-terminals.  This assumes nullability has
226
 
   *  already computed.
227
 
   */
228
 
  public static void compute_first_sets() throws internal_error
229
 
    {
230
 
      boolean      change = true;
231
 
      Enumeration  n;
232
 
      Enumeration  p;
233
 
      non_terminal nt;
234
 
      production   prod;
235
 
      terminal_set prod_first;
236
 
 
237
 
      /* repeat this process until we have no change */
238
 
      while (change)
239
 
        {
240
 
          /* look for a new change */
241
 
          change = false;
242
 
 
243
 
          /* consider each non-terminal */
244
 
          for (n = all(); n.hasMoreElements(); )
245
 
            {
246
 
              nt = (non_terminal)n.nextElement();
247
 
 
248
 
              /* consider every production of that non terminal */
249
 
              for (p = nt.productions(); p.hasMoreElements(); )
250
 
                {
251
 
                  prod = (production)p.nextElement();
252
 
 
253
 
                  /* get the updated first of that production */
254
 
                  prod_first = prod.check_first_set();
255
 
 
256
 
                  /* if this going to add anything, add it */
257
 
                  if (!prod_first.is_subset_of(nt._first_set))
258
 
                    {
259
 
                      change = true;
260
 
                      nt._first_set.add(prod_first);
261
 
                    }
262
 
                }
263
 
            }
264
 
        }
265
 
    }
266
 
 
267
 
  /*-----------------------------------------------------------*/
268
 
  /*--- (Access to) Instance Variables ------------------------*/
269
 
  /*-----------------------------------------------------------*/
270
 
 
271
 
  /** Table of all productions with this non terminal on the LHS. */
272
 
  protected Hashtable _productions = new Hashtable(11);
273
 
 
274
 
  /** Access to productions with this non terminal on the LHS. */
275
 
  public Enumeration productions() {return _productions.elements();}
276
 
 
277
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
278
 
 
279
 
  /** Total number of productions with this non terminal on the LHS. */
280
 
  public int num_productions() {return _productions.size();}
281
 
 
282
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
283
 
 
284
 
  /** Add a production to our set of productions. */
285
 
  public void add_production(production prod) throws internal_error
286
 
    {
287
 
      /* catch improper productions */
288
 
      if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
289
 
        throw new internal_error(
290
 
          "Attempt to add invalid production to non terminal production table");
291
 
 
292
 
      /* add it to the table, keyed with itself */
293
 
      _productions.put(prod,prod);
294
 
    }
295
 
 
296
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
297
 
 
298
 
  /** Nullability of this non terminal. */
299
 
  protected boolean _nullable;
300
 
 
301
 
  /** Nullability of this non terminal. */
302
 
  public boolean nullable() {return _nullable;}
303
 
 
304
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
305
 
 
306
 
  /** First set for this non-terminal. */
307
 
  protected terminal_set _first_set = new terminal_set();
308
 
 
309
 
  /** First set for this non-terminal. */
310
 
  public terminal_set first_set() {return _first_set;}
311
 
 
312
 
  /*-----------------------------------------------------------*/
313
 
  /*--- General Methods ---------------------------------------*/
314
 
  /*-----------------------------------------------------------*/
315
 
 
316
 
  /** Indicate that this symbol is a non-terminal. */
317
 
  public boolean is_non_term() 
318
 
    {
319
 
      return true;
320
 
    }
321
 
 
322
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
323
 
 
324
 
  /** Test to see if this non terminal currently looks nullable. */
325
 
  protected boolean looks_nullable() throws internal_error
326
 
    {
327
 
      /* look and see if any of the productions now look nullable */
328
 
      for (Enumeration e = productions(); e.hasMoreElements(); )
329
 
        /* if the production can go to empty, we are nullable */
330
 
        if (((production)e.nextElement()).check_nullable())
331
 
          return true;
332
 
 
333
 
      /* none of the productions can go to empty, so we are not nullable */
334
 
      return false;
335
 
    }
336
 
 
337
 
  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
338
 
 
339
 
  /** convert to string */
340
 
  public String toString()
341
 
    {
342
 
      return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
343
 
    }
344
 
 
345
 
  /*-----------------------------------------------------------*/
346
 
}