001: package java_cup;
002:
003: import java.util.Hashtable;
004: import java.util.Enumeration;
005:
006: /** This class represents a non-terminal symbol in the grammar. Each
007: * non terminal has a textual name, an index, and a string which indicates
008: * the type of object it will be implemented with at runtime (i.e. the class
009: * of object that will be pushed on the parse stack to represent it).
010: *
011: * @version last updated: 11/25/95
012: * @author Scott Hudson
013: */
014:
015: public class non_terminal extends symbol {
016:
017: /*-----------------------------------------------------------*/
018: /*--- Constructor(s) ----------------------------------------*/
019: /*-----------------------------------------------------------*/
020:
021: /** Full constructor.
022: * @param nm the name of the non terminal.
023: * @param tp the type string for the non terminal.
024: */
025: public non_terminal(String nm, String tp) {
026: /* super class does most of the work */
027: super (nm, tp);
028:
029: /* add to set of all non terminals and check for duplicates */
030: Object conflict = _all.put(nm, this );
031: if (conflict != null)
032: // can't throw an exception here because these are used in static
033: // initializers, so we crash instead
034: // was:
035: // throw new internal_error("Duplicate non-terminal ("+nm+") created");
036: (new internal_error("Duplicate non-terminal (" + nm
037: + ") created")).crash();
038:
039: /* assign a unique index */
040: _index = next_index++;
041:
042: /* add to by_index set */
043: _all_by_index.put(new Integer(_index), this );
044: }
045:
046: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
047:
048: /** Constructor with default type.
049: * @param nm the name of the non terminal.
050: */
051: public non_terminal(String nm) {
052: this (nm, null);
053: }
054:
055: /*-----------------------------------------------------------*/
056: /*--- (Access to) Static (Class) Variables ------------------*/
057: /*-----------------------------------------------------------*/
058:
059: /** Table of all non-terminals -- elements are stored using name strings
060: * as the key
061: */
062: protected static Hashtable _all = new Hashtable();
063:
064: //Hm Added clear to clear all static fields
065: public static void clear() {
066: _all.clear();
067: _all_by_index.clear();
068: next_index = 0;
069: next_nt = 0;
070: }
071:
072: /** Access to all non-terminals. */
073: public static Enumeration all() {
074: return _all.elements();
075: }
076:
077: /** lookup a non terminal by name string */
078: public static non_terminal find(String with_name) {
079: if (with_name == null)
080: return null;
081: else
082: return (non_terminal) _all.get(with_name);
083: }
084:
085: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
086:
087: /** Table of all non terminals indexed by their index number. */
088: protected static Hashtable _all_by_index = new Hashtable();
089:
090: /** Lookup a non terminal by index. */
091: public static non_terminal find(int indx) {
092: Integer the_indx = new Integer(indx);
093:
094: return (non_terminal) _all_by_index.get(the_indx);
095: }
096:
097: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
098:
099: /** Total number of non-terminals. */
100: public static int number() {
101: return _all.size();
102: }
103:
104: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
105:
106: /** Static counter to assign unique indexes. */
107: protected static int next_index = 0;
108:
109: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
110:
111: /** Static counter for creating unique non-terminal names */
112: static protected int next_nt = 0;
113:
114: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
115:
116: /** special non-terminal for start symbol */
117: public static final non_terminal START_nt = new non_terminal(
118: "$START");
119:
120: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
121:
122: /** flag non-terminals created to embed action productions */
123: public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
124:
125: /*-----------------------------------------------------------*/
126: /*--- Static Methods ----------------------------------------*/
127: /*-----------------------------------------------------------*/
128:
129: /** Method for creating a new uniquely named hidden non-terminal using
130: * the given string as a base for the name (or "NT$" if null is passed).
131: * @param prefix base name to construct unique name from.
132: */
133: static non_terminal create_new(String prefix) throws internal_error {
134: return create_new(prefix, null); // TUM 20060608 embedded actions patch
135: }
136:
137: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
138:
139: /** static routine for creating a new uniquely named hidden non-terminal */
140: static non_terminal create_new() throws internal_error {
141: return create_new(null);
142: }
143:
144: /**
145: * TUM 20060608 bugfix for embedded action codes
146: */
147: static non_terminal create_new(String prefix, String type)
148: throws internal_error {
149: if (prefix == null)
150: prefix = "NT$";
151: return new non_terminal(prefix + next_nt++, type);
152: }
153:
154: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
155:
156: /** Compute nullability of all non-terminals. */
157: public static void compute_nullability() throws internal_error {
158: boolean change = true;
159: non_terminal nt;
160: Enumeration e;
161: production prod;
162:
163: /* repeat this process until there is no change */
164: while (change) {
165: /* look for a new change */
166: change = false;
167:
168: /* consider each non-terminal */
169: for (e = all(); e.hasMoreElements();) {
170: nt = (non_terminal) e.nextElement();
171:
172: /* only look at things that aren't already marked nullable */
173: if (!nt.nullable()) {
174: if (nt.looks_nullable()) {
175: nt._nullable = true;
176: change = true;
177: }
178: }
179: }
180: }
181:
182: /* do one last pass over the productions to finalize all of them */
183: for (e = production.all(); e.hasMoreElements();) {
184: prod = (production) e.nextElement();
185: prod.set_nullable(prod.check_nullable());
186: }
187: }
188:
189: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
190:
191: /** Compute first sets for all non-terminals. This assumes nullability has
192: * already computed.
193: */
194: public static void compute_first_sets() throws internal_error {
195: boolean change = true;
196: Enumeration n;
197: Enumeration p;
198: non_terminal nt;
199: production prod;
200: terminal_set prod_first;
201:
202: /* repeat this process until we have no change */
203: while (change) {
204: /* look for a new change */
205: change = false;
206:
207: /* consider each non-terminal */
208: for (n = all(); n.hasMoreElements();) {
209: nt = (non_terminal) n.nextElement();
210:
211: /* consider every production of that non terminal */
212: for (p = nt.productions(); p.hasMoreElements();) {
213: prod = (production) p.nextElement();
214:
215: /* get the updated first of that production */
216: prod_first = prod.check_first_set();
217:
218: /* if this going to add anything, add it */
219: if (!prod_first.is_subset_of(nt._first_set)) {
220: change = true;
221: nt._first_set.add(prod_first);
222: }
223: }
224: }
225: }
226: }
227:
228: /*-----------------------------------------------------------*/
229: /*--- (Access to) Instance Variables ------------------------*/
230: /*-----------------------------------------------------------*/
231:
232: /** Table of all productions with this non terminal on the LHS. */
233: protected Hashtable _productions = new Hashtable(11);
234:
235: /** Access to productions with this non terminal on the LHS. */
236: public Enumeration productions() {
237: return _productions.elements();
238: }
239:
240: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
241:
242: /** Total number of productions with this non terminal on the LHS. */
243: public int num_productions() {
244: return _productions.size();
245: }
246:
247: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
248:
249: /** Add a production to our set of productions. */
250: public void add_production(production prod) throws internal_error {
251: /* catch improper productions */
252: if (prod == null || prod.lhs() == null
253: || prod.lhs().the_symbol() != this )
254: throw new internal_error(
255: "Attempt to add invalid production to non terminal production table");
256:
257: /* add it to the table, keyed with itself */
258: _productions.put(prod, prod);
259: }
260:
261: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
262:
263: /** Nullability of this non terminal. */
264: protected boolean _nullable;
265:
266: /** Nullability of this non terminal. */
267: public boolean nullable() {
268: return _nullable;
269: }
270:
271: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
272:
273: /** First set for this non-terminal. */
274: protected terminal_set _first_set = new terminal_set();
275:
276: /** First set for this non-terminal. */
277: public terminal_set first_set() {
278: return _first_set;
279: }
280:
281: /*-----------------------------------------------------------*/
282: /*--- General Methods ---------------------------------------*/
283: /*-----------------------------------------------------------*/
284:
285: /** Indicate that this symbol is a non-terminal. */
286: public boolean is_non_term() {
287: return true;
288: }
289:
290: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
291:
292: /** Test to see if this non terminal currently looks nullable. */
293: protected boolean looks_nullable() throws internal_error {
294: /* look and see if any of the productions now look nullable */
295: for (Enumeration e = productions(); e.hasMoreElements();)
296: /* if the production can go to empty, we are nullable */
297: if (((production) e.nextElement()).check_nullable())
298: return true;
299:
300: /* none of the productions can go to empty, so we are not nullable */
301: return false;
302: }
303:
304: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
305:
306: /** convert to string */
307: public String toString() {
308: return super .toString() + "[" + index() + "]"
309: + (nullable() ? "*" : "");
310: }
311:
312: /*-----------------------------------------------------------*/
313: }
|