1. package com.sun.java_cup.internal;
  2. import java.util.Hashtable;
  3. import java.util.Enumeration;
  4. /** This class represents a non-terminal symbol in the grammar. Each
  5. * non terminal has a textual name, an index, and a string which indicates
  6. * the type of object it will be implemented with at runtime (i.e. the class
  7. * of object that will be pushed on the parse stack to represent it).
  8. *
  9. * @version last updated: 11/25/95
  10. * @author Scott Hudson
  11. */
  12. public class non_terminal extends symbol {
  13. /*-----------------------------------------------------------*/
  14. /*--- Constructor(s) ----------------------------------------*/
  15. /*-----------------------------------------------------------*/
  16. /** Full constructor.
  17. * @param nm the name of the non terminal.
  18. * @param tp the type string for the non terminal.
  19. */
  20. public non_terminal(String nm, String tp)
  21. {
  22. /* super class does most of the work */
  23. super(nm, tp);
  24. /* add to set of all non terminals and check for duplicates */
  25. Object conflict = _all.put(nm,this);
  26. if (conflict != null)
  27. // can't throw an exception here because these are used in static
  28. // initializers, so we crash instead
  29. // was:
  30. // throw new internal_error("Duplicate non-terminal ("+nm+") created");
  31. (new internal_error("Duplicate non-terminal ("+nm+") created")).crash();
  32. /* assign a unique index */
  33. _index = next_index++;
  34. /* add to by_index set */
  35. _all_by_index.put(new Integer(_index), this);
  36. }
  37. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  38. /** Constructor with default type.
  39. * @param nm the name of the non terminal.
  40. */
  41. public non_terminal(String nm)
  42. {
  43. this(nm, null);
  44. }
  45. /*-----------------------------------------------------------*/
  46. /*--- (Access to) Static (Class) Variables ------------------*/
  47. /*-----------------------------------------------------------*/
  48. /** Table of all non-terminals -- elements are stored using name strings
  49. * as the key
  50. */
  51. protected static Hashtable _all = new Hashtable();
  52. /** Access to all non-terminals. */
  53. public static Enumeration all() {return _all.elements();}
  54. /** lookup a non terminal by name string */
  55. public static non_terminal find(String with_name)
  56. {
  57. if (with_name == null)
  58. return null;
  59. else
  60. return (non_terminal)_all.get(with_name);
  61. }
  62. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  63. /** Table of all non terminals indexed by their index number. */
  64. protected static Hashtable _all_by_index = new Hashtable();
  65. /** Lookup a non terminal by index. */
  66. public static non_terminal find(int indx)
  67. {
  68. Integer the_indx = new Integer(indx);
  69. return (non_terminal)_all_by_index.get(the_indx);
  70. }
  71. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  72. /** Total number of non-terminals. */
  73. public static int number() {return _all.size();}
  74. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  75. /** Static counter to assign unique indexes. */
  76. protected static int next_index = 0;
  77. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  78. /** Static counter for creating unique non-terminal names */
  79. static protected int next_nt = 0;
  80. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  81. /** special non-terminal for start symbol */
  82. public static final non_terminal START_nt = new non_terminal("$START");
  83. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  84. /** flag non-terminals created to embed action productions */
  85. public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
  86. /*-----------------------------------------------------------*/
  87. /*--- Static Methods ----------------------------------------*/
  88. /*-----------------------------------------------------------*/
  89. /** Method for creating a new uniquely named hidden non-terminal using
  90. * the given string as a base for the name (or "NT$" if null is passed).
  91. * @param prefix base name to construct unique name from.
  92. */
  93. static non_terminal create_new(String prefix) throws internal_error
  94. {
  95. if (prefix == null) prefix = "NT$";
  96. return new non_terminal(prefix + next_nt++);
  97. }
  98. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  99. /** static routine for creating a new uniquely named hidden non-terminal */
  100. static non_terminal create_new() throws internal_error
  101. {
  102. return create_new(null);
  103. }
  104. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  105. /** Compute nullability of all non-terminals. */
  106. public static void compute_nullability() throws internal_error
  107. {
  108. boolean change = true;
  109. non_terminal nt;
  110. Enumeration e;
  111. production prod;
  112. /* repeat this process until there is no change */
  113. while (change)
  114. {
  115. /* look for a new change */
  116. change = false;
  117. /* consider each non-terminal */
  118. for (e=all(); e.hasMoreElements(); )
  119. {
  120. nt = (non_terminal)e.nextElement();
  121. /* only look at things that aren't already marked nullable */
  122. if (!nt.nullable())
  123. {
  124. if (nt.looks_nullable())
  125. {
  126. nt._nullable = true;
  127. change = true;
  128. }
  129. }
  130. }
  131. }
  132. /* do one last pass over the productions to finalize all of them */
  133. for (e=production.all(); e.hasMoreElements(); )
  134. {
  135. prod = (production)e.nextElement();
  136. prod.set_nullable(prod.check_nullable());
  137. }
  138. }
  139. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  140. /** Compute first sets for all non-terminals. This assumes nullability has
  141. * already computed.
  142. */
  143. public static void compute_first_sets() throws internal_error
  144. {
  145. boolean change = true;
  146. Enumeration n;
  147. Enumeration p;
  148. non_terminal nt;
  149. production prod;
  150. terminal_set prod_first;
  151. /* repeat this process until we have no change */
  152. while (change)
  153. {
  154. /* look for a new change */
  155. change = false;
  156. /* consider each non-terminal */
  157. for (n = all(); n.hasMoreElements(); )
  158. {
  159. nt = (non_terminal)n.nextElement();
  160. /* consider every production of that non terminal */
  161. for (p = nt.productions(); p.hasMoreElements(); )
  162. {
  163. prod = (production)p.nextElement();
  164. /* get the updated first of that production */
  165. prod_first = prod.check_first_set();
  166. /* if this going to add anything, add it */
  167. if (!prod_first.is_subset_of(nt._first_set))
  168. {
  169. change = true;
  170. nt._first_set.add(prod_first);
  171. }
  172. }
  173. }
  174. }
  175. }
  176. /*-----------------------------------------------------------*/
  177. /*--- (Access to) Instance Variables ------------------------*/
  178. /*-----------------------------------------------------------*/
  179. /** Table of all productions with this non terminal on the LHS. */
  180. protected Hashtable _productions = new Hashtable(11);
  181. /** Access to productions with this non terminal on the LHS. */
  182. public Enumeration productions() {return _productions.elements();}
  183. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  184. /** Total number of productions with this non terminal on the LHS. */
  185. public int num_productions() {return _productions.size();}
  186. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  187. /** Add a production to our set of productions. */
  188. public void add_production(production prod) throws internal_error
  189. {
  190. /* catch improper productions */
  191. if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
  192. throw new internal_error(
  193. "Attempt to add invalid production to non terminal production table");
  194. /* add it to the table, keyed with itself */
  195. _productions.put(prod,prod);
  196. }
  197. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  198. /** Nullability of this non terminal. */
  199. protected boolean _nullable;
  200. /** Nullability of this non terminal. */
  201. public boolean nullable() {return _nullable;}
  202. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  203. /** First set for this non-terminal. */
  204. protected terminal_set _first_set = new terminal_set();
  205. /** First set for this non-terminal. */
  206. public terminal_set first_set() {return _first_set;}
  207. /*-----------------------------------------------------------*/
  208. /*--- General Methods ---------------------------------------*/
  209. /*-----------------------------------------------------------*/
  210. /** Indicate that this symbol is a non-terminal. */
  211. public boolean is_non_term()
  212. {
  213. return true;
  214. }
  215. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  216. /** Test to see if this non terminal currently looks nullable. */
  217. protected boolean looks_nullable() throws internal_error
  218. {
  219. /* look and see if any of the productions now look nullable */
  220. for (Enumeration e = productions(); e.hasMoreElements(); )
  221. /* if the production can go to empty, we are nullable */
  222. if (((production)e.nextElement()).check_nullable())
  223. return true;
  224. /* none of the productions can go to empty, so we are not nullable */
  225. return false;
  226. }
  227. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  228. /** convert to string */
  229. public String toString()
  230. {
  231. return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
  232. }
  233. /*-----------------------------------------------------------*/
  234. }