Source code: java_cup/non_terminal.java
1 package java_cup;
2
3 import java.util.Hashtable;
4 import java.util.Enumeration;
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 nm, String 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 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(_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 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 _all = new Hashtable();
64
65 /** Access to all non-terminals. */
66 public static Enumeration all() {return _all.elements();}
67
68 /** lookup a non terminal by name string */
69 public static non_terminal find(String 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 _all_by_index = new Hashtable();
81
82 /** Lookup a non terminal by index. */
83 public static non_terminal find(int indx)
84 {
85 Integer the_indx = new Integer(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 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 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 n;
187 Enumeration 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 _productions = new Hashtable(11);
228
229 /** Access to productions with this non terminal on the LHS. */
230 public Enumeration 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 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 toString()
296 {
297 return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
298 }
299
300 /*-----------------------------------------------------------*/
301 }