1 package java_cup;
2 
3 import java.util.Enumeration;
4 import java.util.Hashtable;
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    */
non_terminal(String nm, String tp)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 
43   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
44 
45   /** Constructor with default type.
46    * @param nm  the name of the non terminal.
47    */
non_terminal(String nm)48   public non_terminal(String nm)
49     {
50       this(nm, null);
51     }
52 
53   /*-----------------------------------------------------------*/
54   /*--- (Access to) Static (Class) Variables ------------------*/
55   /*-----------------------------------------------------------*/
56 
57   /** Table of all non-terminals -- elements are stored using name strings
58    *  as the key
59    */
60   protected static Hashtable _all = new Hashtable();
61 
62   /** Access to all non-terminals. */
all()63   public static Enumeration all() {return _all.elements();};
64 
65   /** lookup a non terminal by name string */
find(String with_name)66   public static non_terminal find(String with_name)
67     {
68       if (with_name == null)
69         return null;
70       else
71         return (non_terminal)_all.get(with_name);
72     }
73 
74   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
75 
76   /** Total number of non-terminals. */
number()77   public static int number() {return _all.size();};
78 
79   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
80 
81   /** Static counter to assign unique indexes. */
82   protected static int next_index = 0;
83 
84   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
85 
86   /** Static counter for creating unique non-terminal names */
87   static protected int next_nt = 0;
88 
89   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
90 
91   /** special non-terminal for start symbol */
92   public static final non_terminal START_nt = new non_terminal("$START");
93 
94   /*-----------------------------------------------------------*/
95   /*--- Static Methods ----------------------------------------*/
96   /*-----------------------------------------------------------*/
97 
98   /** Method for creating a new uniquely named hidden non-terminal using
99    *  the given string as a base for the name (or "NT$" if null is passed).
100    * @param prefix base name to construct unique name from.
101    */
create_new(String prefix)102   static non_terminal create_new(String prefix) throws internal_error
103     {
104       if (prefix == null) prefix = "NT$";
105       return new non_terminal(prefix + next_nt++);
106     }
107 
108   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
109 
110   /** static routine for creating a new uniquely named hidden non-terminal */
create_new()111   static non_terminal create_new() throws internal_error
112     {
113       return create_new(null);
114     }
115 
116   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
117 
118   /** Compute nullability of all non-terminals. */
compute_nullability()119   public static void compute_nullability() throws internal_error
120     {
121       boolean      change = true;
122       non_terminal nt;
123       Enumeration  e;
124       production   prod;
125 
126       /* repeat this process until there is no change */
127       while (change)
128     {
129       /* look for a new change */
130       change = false;
131 
132       /* consider each non-terminal */
133       for (e=all(); e.hasMoreElements(); )
134         {
135           nt = (non_terminal)e.nextElement();
136 
137           /* only look at things that aren't already marked nullable */
138           if (!nt.nullable())
139         {
140           if (nt.looks_nullable())
141             {
142               nt._nullable = true;
143               change = true;
144             }
145         }
146         }
147     }
148 
149       /* do one last pass over the productions to finalize all of them */
150       for (e=production.all(); e.hasMoreElements(); )
151     {
152       prod = (production)e.nextElement();
153       prod.set_nullable(prod.check_nullable());
154     }
155     }
156 
157   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
158 
159   /** Compute first sets for all non-terminals.  This assumes nullability has
160    *  already computed.
161    */
compute_first_sets()162   public static void compute_first_sets() throws internal_error
163     {
164       boolean      change = true;
165       Enumeration  n;
166       Enumeration  p;
167       non_terminal nt;
168       production   prod;
169       terminal_set prod_first;
170 
171       /* repeat this process until we have no change */
172       while (change)
173     {
174       /* look for a new change */
175       change = false;
176 
177       /* consider each non-terminal */
178       for (n = all(); n.hasMoreElements(); )
179         {
180           nt = (non_terminal)n.nextElement();
181 
182           /* consider every production of that non terminal */
183           for (p = nt.productions(); p.hasMoreElements(); )
184         {
185           prod = (production)p.nextElement();
186 
187           /* get the updated first of that production */
188           prod_first = prod.check_first_set();
189 
190           /* if this going to add anything, add it */
191           if (!prod_first.is_subset_of(nt._first_set))
192             {
193               change = true;
194               nt._first_set.add(prod_first);
195             }
196         }
197         }
198     }
199     }
200 
201   /*-----------------------------------------------------------*/
202   /*--- (Access to) Instance Variables ------------------------*/
203   /*-----------------------------------------------------------*/
204 
205   /** Table of all productions with this non terminal on the LHS. */
206   protected Hashtable _productions = new Hashtable(11);
207 
208   /** Access to productions with this non terminal on the LHS. */
productions()209   public Enumeration productions() {return _productions.elements();};
210 
211   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
212 
213   /** Total number of productions with this non terminal on the LHS. */
num_productions()214   public int num_productions() {return _productions.size();};
215 
216   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
217 
218   /** Add a production to our set of productions. */
add_production(production prod)219   public void add_production(production prod) throws internal_error
220     {
221       /* catch improper productions */
222       if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
223     throw new internal_error(
224       "Attempt to add invalid production to non terminal production table");
225 
226       /* add it to the table, keyed with itself */
227       _productions.put(prod,prod);
228     }
229 
230   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
231 
232   /** Nullability of this non terminal. */
233   protected boolean _nullable;
234 
235   /** Nullability of this non terminal. */
nullable()236   public boolean nullable() {return _nullable;}
237 
238   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
239 
240   /** First set for this non-terminal. */
241   protected terminal_set _first_set = new terminal_set();
242 
243   /** First set for this non-terminal. */
first_set()244   public terminal_set first_set() {return _first_set;}
245 
246   /*-----------------------------------------------------------*/
247   /*--- General Methods ---------------------------------------*/
248   /*-----------------------------------------------------------*/
249 
250   /** Indicate that this symbol is a non-terminal. */
is_non_term()251   public boolean is_non_term()
252     {
253       return true;
254     }
255 
256   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
257 
258   /** Test to see if this non terminal currently looks nullable. */
looks_nullable()259   protected boolean looks_nullable() throws internal_error
260     {
261       /* look and see if any of the productions now look nullable */
262       for (Enumeration e = productions(); e.hasMoreElements(); )
263     /* if the production can go to empty, we are nullable */
264     if (((production)e.nextElement()).check_nullable())
265       return true;
266 
267       /* none of the productions can go to empty, so we are not nullable */
268       return false;
269     }
270 
271   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
272 
273   /** convert to string */
toString()274   public String toString()
275     {
276       return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
277     }
278 
279   /*-----------------------------------------------------------*/
280 };
281