KickJava   Java API By Example, From Geeks To Geeks.

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


1 package com.sun.java_cup.internal;
2
3 import java.util.Hashtable JavaDoc;
4 import java.util.Enumeration JavaDoc;
5
6 /** This class represents a non-terminal symbol in the grammar. Each
7  * non terminal has a textual name, an index, and a string which indicates
8  * the type of object it will be implemented with at runtime (i.e. the class
9  * of object that will be pushed on the parse stack to represent it).
10  *
11  * @version last updated: 11/25/95
12  * @author Scott Hudson
13  */

14
15 public class non_terminal extends symbol {
16
17   /*-----------------------------------------------------------*/
18   /*--- Constructor(s) ----------------------------------------*/
19   /*-----------------------------------------------------------*/
20
21   /** Full constructor.
22    * @param nm the name of the non terminal.
23    * @param tp the type string for the non terminal.
24    */

25   public non_terminal(String JavaDoc nm, String JavaDoc tp)
26     {
27       /* super class does most of the work */
28       super(nm, tp);
29
30       /* add to set of all non terminals and check for duplicates */
31       Object JavaDoc conflict = _all.put(nm,this);
32       if (conflict != null)
33     // can't throw an exception here because these are used in static
34
// initializers, so we crash instead
35
// was:
36
// throw new internal_error("Duplicate non-terminal ("+nm+") created");
37
(new internal_error("Duplicate non-terminal ("+nm+") created")).crash();
38
39       /* assign a unique index */
40       _index = next_index++;
41
42       /* add to by_index set */
43       _all_by_index.put(new Integer JavaDoc(_index), this);
44     }
45
46   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
47
48   /** Constructor with default type.
49    * @param nm the name of the non terminal.
50    */

51   public non_terminal(String JavaDoc nm)
52     {
53       this(nm, null);
54     }
55
56   /*-----------------------------------------------------------*/
57   /*--- (Access to) Static (Class) Variables ------------------*/
58   /*-----------------------------------------------------------*/
59
60   /** Table of all non-terminals -- elements are stored using name strings
61    * as the key
62    */

63   protected static Hashtable JavaDoc _all = new Hashtable JavaDoc();
64
65   /** Access to all non-terminals. */
66   public static Enumeration JavaDoc all() {return _all.elements();}
67
68   /** lookup a non terminal by name string */
69   public static non_terminal find(String JavaDoc with_name)
70     {
71       if (with_name == null)
72         return null;
73       else
74         return (non_terminal)_all.get(with_name);
75     }
76
77   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
78
79   /** Table of all non terminals indexed by their index number. */
80   protected static Hashtable JavaDoc _all_by_index = new Hashtable JavaDoc();
81
82   /** Lookup a non terminal by index. */
83   public static non_terminal find(int indx)
84     {
85       Integer JavaDoc the_indx = new Integer JavaDoc(indx);
86
87       return (non_terminal)_all_by_index.get(the_indx);
88     }
89
90   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
91
92   /** Total number of non-terminals. */
93   public static int number() {return _all.size();}
94
95   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
96
97   /** Static counter to assign unique indexes. */
98   protected static int next_index = 0;
99
100   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
101
102   /** Static counter for creating unique non-terminal names */
103   static protected int next_nt = 0;
104
105   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
106
107   /** special non-terminal for start symbol */
108   public static final non_terminal START_nt = new non_terminal("$START");
109
110   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
111
112   /** flag non-terminals created to embed action productions */
113   public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
114
115   /*-----------------------------------------------------------*/
116   /*--- Static Methods ----------------------------------------*/
117   /*-----------------------------------------------------------*/
118      
119   /** Method for creating a new uniquely named hidden non-terminal using
120    * the given string as a base for the name (or "NT$" if null is passed).
121    * @param prefix base name to construct unique name from.
122    */

123   static non_terminal create_new(String JavaDoc prefix) throws internal_error
124     {
125       if (prefix == null) prefix = "NT$";
126       return new non_terminal(prefix + next_nt++);
127     }
128
129   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
130
131   /** static routine for creating a new uniquely named hidden non-terminal */
132   static non_terminal create_new() throws internal_error
133     {
134       return create_new(null);
135     }
136
137   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
138
139   /** Compute nullability of all non-terminals. */
140   public static void compute_nullability() throws internal_error
141     {
142       boolean change = true;
143       non_terminal nt;
144       Enumeration JavaDoc e;
145       production prod;
146
147       /* repeat this process until there is no change */
148       while (change)
149     {
150       /* look for a new change */
151       change = false;
152
153       /* consider each non-terminal */
154       for (e=all(); e.hasMoreElements(); )
155         {
156           nt = (non_terminal)e.nextElement();
157
158           /* only look at things that aren't already marked nullable */
159           if (!nt.nullable())
160         {
161           if (nt.looks_nullable())
162             {
163               nt._nullable = true;
164               change = true;
165             }
166         }
167         }
168     }
169       
170       /* do one last pass over the productions to finalize all of them */
171       for (e=production.all(); e.hasMoreElements(); )
172     {
173       prod = (production)e.nextElement();
174       prod.set_nullable(prod.check_nullable());
175     }
176     }
177
178   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
179
180   /** Compute first sets for all non-terminals. This assumes nullability has
181    * already computed.
182    */

183   public static void compute_first_sets() throws internal_error
184     {
185       boolean change = true;
186       Enumeration JavaDoc n;
187       Enumeration JavaDoc p;
188       non_terminal nt;
189       production prod;
190       terminal_set prod_first;
191
192       /* repeat this process until we have no change */
193       while (change)
194     {
195       /* look for a new change */
196       change = false;
197
198       /* consider each non-terminal */
199       for (n = all(); n.hasMoreElements(); )
200         {
201           nt = (non_terminal)n.nextElement();
202
203           /* consider every production of that non terminal */
204           for (p = nt.productions(); p.hasMoreElements(); )
205         {
206           prod = (production)p.nextElement();
207
208           /* get the updated first of that production */
209           prod_first = prod.check_first_set();
210
211           /* if this going to add anything, add it */
212           if (!prod_first.is_subset_of(nt._first_set))
213             {
214               change = true;
215               nt._first_set.add(prod_first);
216             }
217         }
218         }
219     }
220     }
221
222   /*-----------------------------------------------------------*/
223   /*--- (Access to) Instance Variables ------------------------*/
224   /*-----------------------------------------------------------*/
225
226   /** Table of all productions with this non terminal on the LHS. */
227   protected Hashtable JavaDoc _productions = new Hashtable JavaDoc(11);
228
229   /** Access to productions with this non terminal on the LHS. */
230   public Enumeration JavaDoc productions() {return _productions.elements();}
231
232   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
233
234   /** Total number of productions with this non terminal on the LHS. */
235   public int num_productions() {return _productions.size();}
236
237   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
238
239   /** Add a production to our set of productions. */
240   public void add_production(production prod) throws internal_error
241     {
242       /* catch improper productions */
243       if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
244     throw new internal_error(
245       "Attempt to add invalid production to non terminal production table");
246
247       /* add it to the table, keyed with itself */
248       _productions.put(prod,prod);
249     }
250
251   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
252
253   /** Nullability of this non terminal. */
254   protected boolean _nullable;
255
256   /** Nullability of this non terminal. */
257   public boolean nullable() {return _nullable;}
258
259   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
260
261   /** First set for this non-terminal. */
262   protected terminal_set _first_set = new terminal_set();
263
264   /** First set for this non-terminal. */
265   public terminal_set first_set() {return _first_set;}
266
267   /*-----------------------------------------------------------*/
268   /*--- General Methods ---------------------------------------*/
269   /*-----------------------------------------------------------*/
270
271   /** Indicate that this symbol is a non-terminal. */
272   public boolean is_non_term()
273     {
274       return true;
275     }
276
277   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
278
279   /** Test to see if this non terminal currently looks nullable. */
280   protected boolean looks_nullable() throws internal_error
281     {
282       /* look and see if any of the productions now look nullable */
283       for (Enumeration JavaDoc e = productions(); e.hasMoreElements(); )
284     /* if the production can go to empty, we are nullable */
285     if (((production)e.nextElement()).check_nullable())
286       return true;
287
288       /* none of the productions can go to empty, so we are not nullable */
289       return false;
290     }
291
292   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
293
294   /** convert to string */
295   public String JavaDoc toString()
296     {
297       return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
298     }
299
300   /*-----------------------------------------------------------*/
301 }
302
Popular Tags