3 import java.util.Hashtable;
4 import java.util.Enumeration;
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).
11 * @version last updated: 11/25/95
12 * @author Scott Hudson
15 public class non_terminal extends symbol {
17 /*-----------------------------------------------------------*/
18 /*--- Constructor(s) ----------------------------------------*/
19 /*-----------------------------------------------------------*/
22 * @param nm the name of the non terminal.
23 * @param tp the type string for the non terminal.
25 public non_terminal(String nm, String tp)
27 /* super class does most of the work */
30 /* add to set of all non terminals and check for duplicates */
31 Object conflict = _all.put(nm,this);
33 // can't throw an exception here because these are used in static
34 // initializers, so we crash instead
36 // throw new internal_error("Duplicate non-terminal ("+nm+") created");
37 (new internal_error("Duplicate non-terminal ("+nm+") created")).crash();
39 /* assign a unique index */
40 _index = next_index++;
42 /* add to by_index set */
43 _all_by_index.put(new Integer(_index), this);
46 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
48 /** Constructor with default type.
49 * @param nm the name of the non terminal.
51 public non_terminal(String nm)
56 /*-----------------------------------------------------------*/
57 /*--- (Access to) Static (Class) Variables ------------------*/
58 /*-----------------------------------------------------------*/
60 /** Table of all non-terminals -- elements are stored using name strings
63 protected static Hashtable _all = new Hashtable();
65 /** Access to all non-terminals. */
66 public static Enumeration all() {return _all.elements();}
68 /** lookup a non terminal by name string */
69 public static non_terminal find(String with_name)
71 if (with_name == null)
74 return (non_terminal)_all.get(with_name);
77 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
79 /** Table of all non terminals indexed by their index number. */
80 protected static Hashtable _all_by_index = new Hashtable();
82 /** Lookup a non terminal by index. */
83 public static non_terminal find(int indx)
85 Integer the_indx = new Integer(indx);
87 return (non_terminal)_all_by_index.get(the_indx);
90 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
92 /** Total number of non-terminals. */
93 public static int number() {return _all.size();}
95 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
97 /** Static counter to assign unique indexes. */
98 protected static int next_index = 0;
100 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
102 /** Static counter for creating unique non-terminal names */
103 static protected int next_nt = 0;
105 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
107 /** special non-terminal for start symbol */
108 public static final non_terminal START_nt = new non_terminal("$START");
110 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
112 /** flag non-terminals created to embed action productions */
113 public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
115 /*-----------------------------------------------------------*/
116 /*--- Static Methods ----------------------------------------*/
117 /*-----------------------------------------------------------*/
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.
123 static non_terminal create_new(String prefix) throws internal_error
125 if (prefix == null) prefix = "NT$";
126 return new non_terminal(prefix + next_nt++);
129 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
131 /** static routine for creating a new uniquely named hidden non-terminal */
132 static non_terminal create_new() throws internal_error
134 return create_new(null);
137 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
139 /** Compute nullability of all non-terminals. */
140 public static void compute_nullability() throws internal_error
142 boolean change = true;
147 /* repeat this process until there is no change */
150 /* look for a new change */
153 /* consider each non-terminal */
154 for (e=all(); e.hasMoreElements(); )
156 nt = (non_terminal)e.nextElement();
158 /* only look at things that aren't already marked nullable */
161 if (nt.looks_nullable())
170 /* do one last pass over the productions to finalize all of them */
171 for (e=production.all(); e.hasMoreElements(); )
173 prod = (production)e.nextElement();
174 prod.set_nullable(prod.check_nullable());
178 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
180 /** Compute first sets for all non-terminals. This assumes nullability has
183 public static void compute_first_sets() throws internal_error
185 boolean change = true;
190 terminal_set prod_first;
192 /* repeat this process until we have no change */
195 /* look for a new change */
198 /* consider each non-terminal */
199 for (n = all(); n.hasMoreElements(); )
201 nt = (non_terminal)n.nextElement();
203 /* consider every production of that non terminal */
204 for (p = nt.productions(); p.hasMoreElements(); )
206 prod = (production)p.nextElement();
208 /* get the updated first of that production */
209 prod_first = prod.check_first_set();
211 /* if this going to add anything, add it */
212 if (!prod_first.is_subset_of(nt._first_set))
215 nt._first_set.add(prod_first);
222 /*-----------------------------------------------------------*/
223 /*--- (Access to) Instance Variables ------------------------*/
224 /*-----------------------------------------------------------*/
226 /** Table of all productions with this non terminal on the LHS. */
227 protected Hashtable _productions = new Hashtable(11);
229 /** Access to productions with this non terminal on the LHS. */
230 public Enumeration productions() {return _productions.elements();}
232 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
234 /** Total number of productions with this non terminal on the LHS. */
235 public int num_productions() {return _productions.size();}
237 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
239 /** Add a production to our set of productions. */
240 public void add_production(production prod) throws internal_error
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");
247 /* add it to the table, keyed with itself */
248 _productions.put(prod,prod);
251 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
253 /** Nullability of this non terminal. */
254 protected boolean _nullable;
256 /** Nullability of this non terminal. */
257 public boolean nullable() {return _nullable;}
259 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
261 /** First set for this non-terminal. */
262 protected terminal_set _first_set = new terminal_set();
264 /** First set for this non-terminal. */
265 public terminal_set first_set() {return _first_set;}
267 /*-----------------------------------------------------------*/
268 /*--- General Methods ---------------------------------------*/
269 /*-----------------------------------------------------------*/
271 /** Indicate that this symbol is a non-terminal. */
272 public boolean is_non_term()
277 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
279 /** Test to see if this non terminal currently looks nullable. */
280 protected boolean looks_nullable() throws internal_error
282 /* look and see if any of the productions now look nullable */
283 for (Enumeration e = productions(); e.hasMoreElements(); )
284 /* if the production can go to empty, we are nullable */
285 if (((production)e.nextElement()).check_nullable())
288 /* none of the productions can go to empty, so we are not nullable */
292 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
294 /** convert to string */
295 public String toString()
297 return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
300 /*-----------------------------------------------------------*/