1. package com.sun.java_cup.internal;
  2. import java.util.Hashtable;
  3. import java.util.Enumeration;
  4. /** This class represents a production in the grammar. It contains
  5. * a LHS non terminal, and an array of RHS symbols. As various
  6. * transformations are done on the RHS of the production, it may shrink.
  7. * As a result a separate length is always maintained to indicate how much
  8. * of the RHS array is still valid.<p>
  9. *
  10. * I addition to construction and manipulation operations, productions provide
  11. * methods for factoring out actions (see remove_embedded_actions()), for
  12. * computing the nullability of the production (i.e., can it derive the empty
  13. * string, see check_nullable()), and operations for computing its first
  14. * set (i.e., the set of terminals that could appear at the beginning of some
  15. * string derived from the production, see check_first_set()).
  16. *
  17. * @see com.sun.java_cup.internal.production_part
  18. * @see com.sun.java_cup.internal.symbol_part
  19. * @see com.sun.java_cup.internal.action_part
  20. * @version last updated: 7/3/96
  21. * @author Frank Flannery
  22. */
  23. public class production {
  24. /*-----------------------------------------------------------*/
  25. /*--- Constructor(s) ----------------------------------------*/
  26. /*-----------------------------------------------------------*/
  27. /** Full constructor. This constructor accepts a LHS non terminal,
  28. * an array of RHS parts (including terminals, non terminals, and
  29. * actions), and a string for a final reduce action. It does several
  30. * manipulations in the process of creating a production object.
  31. * After some validity checking it translates labels that appear in
  32. * actions into code for accessing objects on the runtime parse stack.
  33. * It them merges adjacent actions if they appear and moves any trailing
  34. * action into the final reduce actions string. Next it removes any
  35. * embedded actions by factoring them out with new action productions.
  36. * Finally it assigns a unique index to the production.<p>
  37. *
  38. * Factoring out of actions is accomplished by creating new "hidden"
  39. * non terminals. For example if the production was originally: <pre>
  40. * A ::= B {action} C D
  41. * </pre>
  42. * then it is factored into two productions:<pre>
  43. * A ::= B X C D
  44. * X ::= {action}
  45. * </pre>
  46. * (where X is a unique new non terminal). This has the effect of placing
  47. * all actions at the end where they can be handled as part of a reduce by
  48. * the parser.
  49. */
  50. public production(
  51. non_terminal lhs_sym,
  52. production_part rhs_parts[],
  53. int rhs_l,
  54. String action_str)
  55. throws internal_error
  56. {
  57. int i;
  58. action_part tail_action;
  59. String declare_str;
  60. int rightlen = rhs_l;
  61. /* remember the length */
  62. if (rhs_l >= 0)
  63. _rhs_length = rhs_l;
  64. else if (rhs_parts != null)
  65. _rhs_length = rhs_parts.length;
  66. else
  67. _rhs_length = 0;
  68. /* make sure we have a valid left-hand-side */
  69. if (lhs_sym == null)
  70. throw new internal_error(
  71. "Attempt to construct a production with a null LHS");
  72. /* I'm not translating labels anymore, I'm adding code to declare
  73. labels as valid variables. This way, the users code string is
  74. untouched
  75. 6/96 frankf */
  76. /* check if the last part of the right hand side is an action. If
  77. it is, it won't be on the stack, so we don't want to count it
  78. in the rightlen. Then when we search down the stack for a
  79. Symbol, we don't try to search past action */
  80. if (rhs_l > 0) {
  81. if (rhs_parts[rhs_l - 1].is_action()) {
  82. rightlen = rhs_l - 1;
  83. } else {
  84. rightlen = rhs_l;
  85. }
  86. }
  87. /* get the generated declaration code for the necessary labels. */
  88. declare_str = declare_labels(
  89. rhs_parts, rightlen, action_str);
  90. if (action_str == null)
  91. action_str = declare_str;
  92. else
  93. action_str = declare_str + action_str;
  94. /* count use of lhs */
  95. lhs_sym.note_use();
  96. /* create the part for left-hand-side */
  97. _lhs = new symbol_part(lhs_sym);
  98. /* merge adjacent actions (if any) */
  99. _rhs_length = merge_adjacent_actions(rhs_parts, _rhs_length);
  100. /* strip off any trailing action */
  101. tail_action = strip_trailing_action(rhs_parts, _rhs_length);
  102. if (tail_action != null) _rhs_length--;
  103. /* Why does this run through the right hand side happen
  104. over and over? here a quick combination of two
  105. prior runs plus one I wanted of my own
  106. frankf 6/25/96 */
  107. /* allocate and copy over the right-hand-side */
  108. /* count use of each rhs symbol */
  109. _rhs = new production_part[_rhs_length];
  110. for (i=0; i<_rhs_length; i++) {
  111. _rhs[i] = rhs_parts[i];
  112. if (!_rhs[i].is_action()) {
  113. ((symbol_part)_rhs[i]).the_symbol().note_use();
  114. if (((symbol_part)_rhs[i]).the_symbol() instanceof terminal) {
  115. _rhs_prec =
  116. ((terminal)((symbol_part)_rhs[i]).the_symbol()).precedence_num();
  117. _rhs_assoc =
  118. ((terminal)((symbol_part)_rhs[i]).the_symbol()).precedence_side();
  119. }
  120. }
  121. }
  122. /*now action string is really declaration string, so put it in front!
  123. 6/14/96 frankf */
  124. if (action_str == null) action_str = "";
  125. if (tail_action != null && tail_action.code_string() != null)
  126. action_str = action_str + "\t\t" + tail_action.code_string();
  127. /* stash the action */
  128. _action = new action_part(action_str);
  129. /* rewrite production to remove any embedded actions */
  130. remove_embedded_actions();
  131. /* assign an index */
  132. _index = next_index++;
  133. /* put us in the global collection of productions */
  134. _all.put(new Integer(_index),this);
  135. /* put us in the production list of the lhs non terminal */
  136. lhs_sym.add_production(this);
  137. }
  138. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  139. /** Constructor with no action string. */
  140. public production(
  141. non_terminal lhs_sym,
  142. production_part rhs_parts[],
  143. int rhs_l)
  144. throws internal_error
  145. {
  146. this(lhs_sym,rhs_parts,rhs_l,null);
  147. }
  148. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  149. /* Constructor with precedence and associativity of production
  150. contextually define */
  151. public production(
  152. non_terminal lhs_sym,
  153. production_part rhs_parts[],
  154. int rhs_l,
  155. String action_str,
  156. int prec_num,
  157. int prec_side)
  158. throws internal_error
  159. {
  160. this(lhs_sym,rhs_parts,rhs_l,action_str);
  161. /* set the precedence */
  162. set_precedence_num(prec_num);
  163. set_precedence_side(prec_side);
  164. }
  165. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  166. /* Constructor w/ no action string and contextual precedence
  167. defined */
  168. public production(
  169. non_terminal lhs_sym,
  170. production_part rhs_parts[],
  171. int rhs_l,
  172. int prec_num,
  173. int prec_side)
  174. throws internal_error
  175. {
  176. this(lhs_sym,rhs_parts,rhs_l,null);
  177. /* set the precedence */
  178. set_precedence_num(prec_num);
  179. set_precedence_side(prec_side);
  180. }
  181. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  182. /*-----------------------------------------------------------*/
  183. /*--- (Access to) Static (Class) Variables ------------------*/
  184. /*-----------------------------------------------------------*/
  185. /** Table of all productions. Elements are stored using their index as
  186. * the key.
  187. */
  188. protected static Hashtable _all = new Hashtable();
  189. /** Access to all productions. */
  190. public static Enumeration all() {return _all.elements();}
  191. /** Lookup a production by index. */
  192. public static production find(int indx) {
  193. return (production) _all.get(new Integer(indx));
  194. }
  195. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  196. /** Total number of productions. */
  197. public static int number() {return _all.size();}
  198. /** Static counter for assigning unique index numbers. */
  199. protected static int next_index;
  200. /*-----------------------------------------------------------*/
  201. /*--- (Access to) Instance Variables ------------------------*/
  202. /*-----------------------------------------------------------*/
  203. /** The left hand side non-terminal. */
  204. protected symbol_part _lhs;
  205. /** The left hand side non-terminal. */
  206. public symbol_part lhs() {return _lhs;}
  207. /** The precedence of the rule */
  208. protected int _rhs_prec = -1;
  209. protected int _rhs_assoc = -1;
  210. /** Access to the precedence of the rule */
  211. public int precedence_num() { return _rhs_prec; }
  212. public int precedence_side() { return _rhs_assoc; }
  213. /** Setting the precedence of a rule */
  214. public void set_precedence_num(int prec_num) {
  215. _rhs_prec = prec_num;
  216. }
  217. public void set_precedence_side(int prec_side) {
  218. _rhs_assoc = prec_side;
  219. }
  220. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  221. /** A collection of parts for the right hand side. */
  222. protected production_part _rhs[];
  223. /** Access to the collection of parts for the right hand side. */
  224. public production_part rhs(int indx) throws internal_error
  225. {
  226. if (indx >= 0 && indx < _rhs_length)
  227. return _rhs[indx];
  228. else
  229. throw new internal_error(
  230. "Index out of range for right hand side of production");
  231. }
  232. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  233. /** How much of the right hand side array we are presently using. */
  234. protected int _rhs_length;
  235. /** How much of the right hand side array we are presently using. */
  236. public int rhs_length() {return _rhs_length;}
  237. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  238. /** An action_part containing code for the action to be performed when we
  239. * reduce with this production.
  240. */
  241. protected action_part _action;
  242. /** An action_part containing code for the action to be performed when we
  243. * reduce with this production.
  244. */
  245. public action_part action() {return _action;}
  246. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  247. /** Index number of the production. */
  248. protected int _index;
  249. /** Index number of the production. */
  250. public int index() {return _index;}
  251. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  252. /** Count of number of reductions using this production. */
  253. protected int _num_reductions = 0;
  254. /** Count of number of reductions using this production. */
  255. public int num_reductions() {return _num_reductions;}
  256. /** Increment the count of reductions with this non-terminal */
  257. public void note_reduction_use() {_num_reductions++;}
  258. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  259. /** Is the nullability of the production known or unknown? */
  260. protected boolean _nullable_known = false;
  261. /** Is the nullability of the production known or unknown? */
  262. public boolean nullable_known() {return _nullable_known;}
  263. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  264. /** Nullability of the production (can it derive the empty string). */
  265. protected boolean _nullable = false;
  266. /** Nullability of the production (can it derive the empty string). */
  267. public boolean nullable() {return _nullable;}
  268. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  269. /** First set of the production. This is the set of terminals that
  270. * could appear at the front of some string derived from this production.
  271. */
  272. protected terminal_set _first_set = new terminal_set();
  273. /** First set of the production. This is the set of terminals that
  274. * could appear at the front of some string derived from this production.
  275. */
  276. public terminal_set first_set() {return _first_set;}
  277. /*-----------------------------------------------------------*/
  278. /*--- Static Methods ----------------------------------------*/
  279. /*-----------------------------------------------------------*/
  280. /** Determine if a given character can be a label id starter.
  281. * @param c the character in question.
  282. */
  283. protected static boolean is_id_start(char c)
  284. {
  285. return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c == '_');
  286. //later need to handle non-8-bit chars here
  287. }
  288. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  289. /** Determine if a character can be in a label id.
  290. * @param c the character in question.
  291. */
  292. protected static boolean is_id_char(char c)
  293. {
  294. return is_id_start(c) || (c >= '0' && c <= '9');
  295. }
  296. /*-----------------------------------------------------------*/
  297. /*--- General Methods ---------------------------------------*/
  298. /*-----------------------------------------------------------*/
  299. /** Return label declaration code
  300. * @param labelname the label name
  301. * @param stack_type the stack type of label?
  302. * @author frankf
  303. */
  304. protected String make_declaration(
  305. String labelname,
  306. String stack_type,
  307. int offset)
  308. {
  309. String ret;
  310. /* Put in the left/right value labels */
  311. if (emit.lr_values())
  312. ret = "\t\tint " + labelname + "left = ((com.sun.java_cup.internal.runtime.Symbol)" +
  313. emit.pre("stack") + ".elementAt(" + emit.pre("top") +
  314. "-" + offset + ")).left;\n" +
  315. "\t\tint " + labelname + "right = ((com.sun.java_cup.internal.runtime.Symbol)" +
  316. emit.pre("stack") + ".elementAt(" + emit.pre("top") +
  317. "-" + offset + ")).right;\n";
  318. else ret = "";
  319. /* otherwise, just declare label. */
  320. return ret + "\t\t" + stack_type + " " + labelname + " = (" + stack_type +
  321. ")((" + "com.sun.java_cup.internal.runtime.Symbol) " + emit.pre("stack") + ".elementAt(" + emit.pre("top")
  322. + "-" + offset + ")).value;\n";
  323. }
  324. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  325. /** Declare label names as valid variables within the action string
  326. * @param rhs array of RHS parts.
  327. * @param rhs_len how much of rhs to consider valid.
  328. * @param final_action the final action string of the production.
  329. * @param lhs_type the object type associated with the LHS symbol.
  330. */
  331. protected String declare_labels(
  332. production_part rhs[],
  333. int rhs_len,
  334. String final_action)
  335. {
  336. String declaration = "";
  337. symbol_part part;
  338. action_part act_part;
  339. int pos;
  340. /* walk down the parts and extract the labels */
  341. for (pos = 0; pos < rhs_len; pos++)
  342. {
  343. if (!rhs[pos].is_action())
  344. {
  345. part = (symbol_part)rhs[pos];
  346. /* if it has a label, make declaration! */
  347. if (part.label() != null)
  348. {
  349. declaration = declaration +
  350. make_declaration(part.label(), part.the_symbol().stack_type(),
  351. rhs_len-pos-1);
  352. }
  353. }
  354. }
  355. return declaration;
  356. }
  357. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  358. /** Helper routine to merge adjacent actions in a set of RHS parts
  359. * @param rhs_parts array of RHS parts.
  360. * @param len amount of that array that is valid.
  361. * @return remaining valid length.
  362. */
  363. protected int merge_adjacent_actions(production_part rhs_parts[], int len)
  364. {
  365. int from_loc, to_loc, merge_cnt;
  366. /* bail out early if we have no work to do */
  367. if (rhs_parts == null || len == 0) return 0;
  368. merge_cnt = 0;
  369. to_loc = -1;
  370. for (from_loc=0; from_loc<len; from_loc++)
  371. {
  372. /* do we go in the current position or one further */
  373. if (to_loc < 0 || !rhs_parts[to_loc].is_action()
  374. || !rhs_parts[from_loc].is_action())
  375. {
  376. /* next one */
  377. to_loc++;
  378. /* clear the way for it */
  379. if (to_loc != from_loc) rhs_parts[to_loc] = null;
  380. }
  381. /* if this is not trivial? */
  382. if (to_loc != from_loc)
  383. {
  384. /* do we merge or copy? */
  385. if (rhs_parts[to_loc] != null && rhs_parts[to_loc].is_action() &&
  386. rhs_parts[from_loc].is_action())
  387. {
  388. /* merge */
  389. rhs_parts[to_loc] = new action_part(
  390. ((action_part)rhs_parts[to_loc]).code_string() +
  391. ((action_part)rhs_parts[from_loc]).code_string());
  392. merge_cnt++;
  393. }
  394. else
  395. {
  396. /* copy */
  397. rhs_parts[to_loc] = rhs_parts[from_loc];
  398. }
  399. }
  400. }
  401. /* return the used length */
  402. return len - merge_cnt;
  403. }
  404. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  405. /** Helper routine to strip a trailing action off rhs and return it
  406. * @param rhs_parts array of RHS parts.
  407. * @param len how many of those are valid.
  408. * @return the removed action part.
  409. */
  410. protected action_part strip_trailing_action(
  411. production_part rhs_parts[],
  412. int len)
  413. {
  414. action_part result;
  415. /* bail out early if we have nothing to do */
  416. if (rhs_parts == null || len == 0) return null;
  417. /* see if we have a trailing action */
  418. if (rhs_parts[len-1].is_action())
  419. {
  420. /* snip it out and return it */
  421. result = (action_part)rhs_parts[len-1];
  422. rhs_parts[len-1] = null;
  423. return result;
  424. }
  425. else
  426. return null;
  427. }
  428. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  429. /** Remove all embedded actions from a production by factoring them
  430. * out into individual action production using new non terminals.
  431. * if the original production was: <pre>
  432. * A ::= B {action1} C {action2} D
  433. * </pre>
  434. * then it will be factored into: <pre>
  435. * A ::= B NT$1 C NT$2 D
  436. * NT$1 ::= {action1}
  437. * NT$2 ::= {action2}
  438. * </pre>
  439. * where NT$1 and NT$2 are new system created non terminals.
  440. */
  441. /* the declarations added to the parent production are also passed along,
  442. as they should be perfectly valid in this code string, since it
  443. was originally a code string in the parent, not on its own.
  444. frank 6/20/96 */
  445. protected void remove_embedded_actions(
  446. ) throws internal_error
  447. {
  448. non_terminal new_nt;
  449. production new_prod;
  450. String declare_str;
  451. /* walk over the production and process each action */
  452. for (int act_loc = 0; act_loc < rhs_length(); act_loc++)
  453. if (rhs(act_loc).is_action())
  454. {
  455. declare_str = declare_labels(
  456. _rhs, act_loc, "");
  457. /* create a new non terminal for the action production */
  458. new_nt = non_terminal.create_new();
  459. new_nt.is_embedded_action = true; /* 24-Mar-1998, CSA */
  460. /* create a new production with just the action */
  461. new_prod = new action_production(this, new_nt, null, 0,
  462. declare_str + ((action_part)rhs(act_loc)).code_string());
  463. /* replace the action with the generated non terminal */
  464. _rhs[act_loc] = new symbol_part(new_nt);
  465. }
  466. }
  467. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  468. /** Check to see if the production (now) appears to be nullable.
  469. * A production is nullable if its RHS could derive the empty string.
  470. * This results when the RHS is empty or contains only non terminals
  471. * which themselves are nullable.
  472. */
  473. public boolean check_nullable() throws internal_error
  474. {
  475. production_part part;
  476. symbol sym;
  477. int pos;
  478. /* if we already know bail out early */
  479. if (nullable_known()) return nullable();
  480. /* if we have a zero size RHS we are directly nullable */
  481. if (rhs_length() == 0)
  482. {
  483. /* stash and return the result */
  484. return set_nullable(true);
  485. }
  486. /* otherwise we need to test all of our parts */
  487. for (pos=0; pos<rhs_length(); pos++)
  488. {
  489. part = rhs(pos);
  490. /* only look at non-actions */
  491. if (!part.is_action())
  492. {
  493. sym = ((symbol_part)part).the_symbol();
  494. /* if its a terminal we are definitely not nullable */
  495. if (!sym.is_non_term())
  496. return set_nullable(false);
  497. /* its a non-term, is it marked nullable */
  498. else if (!((non_terminal)sym).nullable())
  499. /* this one not (yet) nullable, so we aren't */
  500. return false;
  501. }
  502. }
  503. /* if we make it here all parts are nullable */
  504. return set_nullable(true);
  505. }
  506. /** set (and return) nullability */
  507. boolean set_nullable(boolean v)
  508. {
  509. _nullable_known = true;
  510. _nullable = v;
  511. return v;
  512. }
  513. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  514. /** Update (and return) the first set based on current NT firsts.
  515. * This assumes that nullability has already been computed for all non
  516. * terminals and productions.
  517. */
  518. public terminal_set check_first_set() throws internal_error
  519. {
  520. int part;
  521. symbol sym;
  522. /* walk down the right hand side till we get past all nullables */
  523. for (part=0; part<rhs_length(); part++)
  524. {
  525. /* only look at non-actions */
  526. if (!rhs(part).is_action())
  527. {
  528. sym = ((symbol_part)rhs(part)).the_symbol();
  529. /* is it a non-terminal?*/
  530. if (sym.is_non_term())
  531. {
  532. /* add in current firsts from that NT */
  533. _first_set.add(((non_terminal)sym).first_set());
  534. /* if its not nullable, we are done */
  535. if (!((non_terminal)sym).nullable())
  536. break;
  537. }
  538. else
  539. {
  540. /* its a terminal -- add that to the set */
  541. _first_set.add((terminal)sym);
  542. /* we are done */
  543. break;
  544. }
  545. }
  546. }
  547. /* return our updated first set */
  548. return first_set();
  549. }
  550. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  551. /** Equality comparison. */
  552. public boolean equals(production other)
  553. {
  554. if (other == null) return false;
  555. return other._index == _index;
  556. }
  557. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  558. /** Generic equality comparison. */
  559. public boolean equals(Object other)
  560. {
  561. if (!(other instanceof production))
  562. return false;
  563. else
  564. return equals((production)other);
  565. }
  566. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  567. /** Produce a hash code. */
  568. public int hashCode()
  569. {
  570. /* just use a simple function of the index */
  571. return _index*13;
  572. }
  573. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  574. /** Convert to a string. */
  575. public String toString()
  576. {
  577. String result;
  578. /* catch any internal errors */
  579. try {
  580. result = "production [" + index() + "]: ";
  581. result += ((lhs() != null) ? lhs().toString() : "$$NULL-LHS$$");
  582. result += " :: = ";
  583. for (int i = 0; i<rhs_length(); i++)
  584. result += rhs(i) + " ";
  585. result += ";";
  586. if (action() != null && action().code_string() != null)
  587. result += " {" + action().code_string() + "}";
  588. if (nullable_known())
  589. if (nullable())
  590. result += "[NULLABLE]";
  591. else
  592. result += "[NOT NULLABLE]";
  593. } catch (internal_error e) {
  594. /* crash on internal error since we can't throw it from here (because
  595. superclass does not throw anything. */
  596. e.crash();
  597. result = null;
  598. }
  599. return result;
  600. }
  601. /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  602. /** Convert to a simpler string. */
  603. public String to_simple_string() throws internal_error
  604. {
  605. String result;
  606. result = ((lhs() != null) ? lhs().the_symbol().name() : "NULL_LHS");
  607. result += " ::= ";
  608. for (int i = 0; i < rhs_length(); i++)
  609. if (!rhs(i).is_action())
  610. result += ((symbol_part)rhs(i)).the_symbol().name() + " ";
  611. return result;
  612. }
  613. /*-----------------------------------------------------------*/
  614. }