package java_cup; import java.util.Enumeration; import java.util.Hashtable; /** This class represents a non-terminal symbol in the grammar. Each * non terminal has a textual name, an index, and a string which indicates * the type of object it will be implemented with at runtime (i.e. the class * of object that will be pushed on the parse stack to represent it). * * @version last updated: 11/25/95 * @author Scott Hudson */ public class non_terminal extends symbol { /*-----------------------------------------------------------*/ /*--- Constructor(s) ----------------------------------------*/ /*-----------------------------------------------------------*/ /** Full constructor. * @param nm the name of the non terminal. * @param tp the type string for the non terminal. */ public non_terminal(String nm, String tp) { /* super class does most of the work */ super(nm, tp); /* add to set of all non terminals and check for duplicates */ Object conflict = _all.put(nm,this); if (conflict != null) // can't throw an exception here because these are used in static // initializers, so we crash instead // was: // throw new internal_error("Duplicate non-terminal ("+nm+") created"); (new internal_error("Duplicate non-terminal ("+nm+") created")).crash(); /* assign a unique index */ _index = next_index++; } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Constructor with default type. * @param nm the name of the non terminal. */ public non_terminal(String nm) { this(nm, null); } /*-----------------------------------------------------------*/ /*--- (Access to) Static (Class) Variables ------------------*/ /*-----------------------------------------------------------*/ /** Table of all non-terminals -- elements are stored using name strings * as the key */ protected static Hashtable _all = new Hashtable(); /** Access to all non-terminals. */ public static Enumeration all() {return _all.elements();}; /** lookup a non terminal by name string */ public static non_terminal find(String with_name) { if (with_name == null) return null; else return (non_terminal)_all.get(with_name); } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Total number of non-terminals. */ public static int number() {return _all.size();}; /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Static counter to assign unique indexes. */ protected static int next_index = 0; /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Static counter for creating unique non-terminal names */ static protected int next_nt = 0; /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** special non-terminal for start symbol */ public static final non_terminal START_nt = new non_terminal("$START"); /*-----------------------------------------------------------*/ /*--- Static Methods ----------------------------------------*/ /*-----------------------------------------------------------*/ /** Method for creating a new uniquely named hidden non-terminal using * the given string as a base for the name (or "NT$" if null is passed). * @param prefix base name to construct unique name from. */ static non_terminal create_new(String prefix) throws internal_error { if (prefix == null) prefix = "NT$"; return new non_terminal(prefix + next_nt++); } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** static routine for creating a new uniquely named hidden non-terminal */ static non_terminal create_new() throws internal_error { return create_new(null); } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Compute nullability of all non-terminals. */ public static void compute_nullability() throws internal_error { boolean change = true; non_terminal nt; Enumeration e; production prod; /* repeat this process until there is no change */ while (change) { /* look for a new change */ change = false; /* consider each non-terminal */ for (e=all(); e.hasMoreElements(); ) { nt = (non_terminal)e.nextElement(); /* only look at things that aren't already marked nullable */ if (!nt.nullable()) { if (nt.looks_nullable()) { nt._nullable = true; change = true; } } } } /* do one last pass over the productions to finalize all of them */ for (e=production.all(); e.hasMoreElements(); ) { prod = (production)e.nextElement(); prod.set_nullable(prod.check_nullable()); } } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Compute first sets for all non-terminals. This assumes nullability has * already computed. */ public static void compute_first_sets() throws internal_error { boolean change = true; Enumeration n; Enumeration p; non_terminal nt; production prod; terminal_set prod_first; /* repeat this process until we have no change */ while (change) { /* look for a new change */ change = false; /* consider each non-terminal */ for (n = all(); n.hasMoreElements(); ) { nt = (non_terminal)n.nextElement(); /* consider every production of that non terminal */ for (p = nt.productions(); p.hasMoreElements(); ) { prod = (production)p.nextElement(); /* get the updated first of that production */ prod_first = prod.check_first_set(); /* if this going to add anything, add it */ if (!prod_first.is_subset_of(nt._first_set)) { change = true; nt._first_set.add(prod_first); } } } } } /*-----------------------------------------------------------*/ /*--- (Access to) Instance Variables ------------------------*/ /*-----------------------------------------------------------*/ /** Table of all productions with this non terminal on the LHS. */ protected Hashtable _productions = new Hashtable(11); /** Access to productions with this non terminal on the LHS. */ public Enumeration productions() {return _productions.elements();}; /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Total number of productions with this non terminal on the LHS. */ public int num_productions() {return _productions.size();}; /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Add a production to our set of productions. */ public void add_production(production prod) throws internal_error { /* catch improper productions */ if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this) throw new internal_error( "Attempt to add invalid production to non terminal production table"); /* add it to the table, keyed with itself */ _productions.put(prod,prod); } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Nullability of this non terminal. */ protected boolean _nullable; /** Nullability of this non terminal. */ public boolean nullable() {return _nullable;} /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** First set for this non-terminal. */ protected terminal_set _first_set = new terminal_set(); /** First set for this non-terminal. */ public terminal_set first_set() {return _first_set;} /*-----------------------------------------------------------*/ /*--- General Methods ---------------------------------------*/ /*-----------------------------------------------------------*/ /** Indicate that this symbol is a non-terminal. */ public boolean is_non_term() { return true; } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** Test to see if this non terminal currently looks nullable. */ protected boolean looks_nullable() throws internal_error { /* look and see if any of the productions now look nullable */ for (Enumeration e = productions(); e.hasMoreElements(); ) /* if the production can go to empty, we are nullable */ if (((production)e.nextElement()).check_nullable()) return true; /* none of the productions can go to empty, so we are not nullable */ return false; } /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ /** convert to string */ public String toString() { return super.toString() + "[" + index() + "]" + (nullable() ? "*" : ""); } /*-----------------------------------------------------------*/ };