+ * + * I addition to construction and manipulation operations, productions provide + * methods for factoring out actions (see remove_embedded_actions()), for + * computing the nullability of the production (i.e., can it derive the empty + * string, see check_nullable()), and operations for computing its first + * set (i.e., the set of terminals that could appear at the beginning of some + * string derived from the production, see check_first_set()). + * + * @see java_cup.production_part + * @see java_cup.symbol_part + * @see java_cup.action_part + * @version last updated: 7/3/96 + * @author Frank Flannery + */ + +public class production { + + /*-----------------------------------------------------------*/ + /*--- Constructor(s) ----------------------------------------*/ + /*-----------------------------------------------------------*/ + + /** Full constructor. This constructor accepts a LHS non terminal, + * an array of RHS parts (including terminals, non terminals, and + * actions), and a string for a final reduce action. It does several + * manipulations in the process of creating a production object. + * After some validity checking it translates labels that appear in + * actions into code for accessing objects on the runtime parse stack. + * It them merges adjacent actions if they appear and moves any trailing + * action into the final reduce actions string. Next it removes any + * embedded actions by factoring them out with new action productions. + * Finally it assigns a unique index to the production.
+ * + * Factoring out of actions is accomplished by creating new "hidden" + * non terminals. For example if the production was originally:
+ * A ::= B {action} C D
+ *
+ * then it is factored into two productions:
+ * A ::= B X C D
+ * X ::= {action}
+ *
+ * (where X is a unique new non terminal). This has the effect of placing
+ * all actions at the end where they can be handled as part of a reduce by
+ * the parser.
+ */
+ public production(
+ non_terminal lhs_sym,
+ production_part rhs_parts[],
+ int rhs_l,
+ String action_str)
+ throws internal_error
+ {
+ int i;
+ action_part tail_action;
+ String declare_str;
+ int rightlen = rhs_l;
+
+ /* remember the length */
+ if (rhs_l >= 0)
+ _rhs_length = rhs_l;
+ else if (rhs_parts != null)
+ _rhs_length = rhs_parts.length;
+ else
+ _rhs_length = 0;
+
+ /* make sure we have a valid left-hand-side */
+ if (lhs_sym == null)
+ throw new internal_error(
+ "Attempt to construct a production with a null LHS");
+
+ /* I'm not translating labels anymore, I'm adding code to declare
+ labels as valid variables. This way, the users code string is
+ untouched
+ 6/96 frankf */
+
+ /* check if the last part of the right hand side is an action. If
+ it is, it won't be on the stack, so we don't want to count it
+ in the rightlen. Then when we search down the stack for a
+ Symbol, we don't try to search past action */
+
+ if (rhs_l > 0) {
+ if (rhs_parts[rhs_l - 1].is_action()) {
+ rightlen = rhs_l - 1;
+ } else {
+ rightlen = rhs_l;
+ }
+ }
+
+ /* get the generated declaration code for the necessary labels. */
+ declare_str = declare_labels(
+ rhs_parts, rightlen, action_str);
+
+ if (action_str == null)
+ action_str = declare_str;
+ else
+ action_str = declare_str + action_str;
+
+ /* count use of lhs */
+ lhs_sym.note_use();
+
+ /* create the part for left-hand-side */
+ _lhs = new symbol_part(lhs_sym);
+
+ /* merge adjacent actions (if any) */
+ _rhs_length = merge_adjacent_actions(rhs_parts, _rhs_length);
+
+ /* strip off any trailing action */
+ tail_action = strip_trailing_action(rhs_parts, _rhs_length);
+ if (tail_action != null) _rhs_length--;
+
+ /* Why does this run through the right hand side happen
+ over and over? here a quick combination of two
+ prior runs plus one I wanted of my own
+ frankf 6/25/96 */
+ /* allocate and copy over the right-hand-side */
+ /* count use of each rhs symbol */
+ _rhs = new production_part[_rhs_length];
+ for (i=0; i<_rhs_length; i++) {
+ _rhs[i] = rhs_parts[i];
+ if (!_rhs[i].is_action()) {
+ ((symbol_part)_rhs[i]).the_symbol().note_use();
+ if (((symbol_part)_rhs[i]).the_symbol() instanceof terminal) {
+ _rhs_prec =
+ ((terminal)((symbol_part)_rhs[i]).the_symbol()).precedence_num();
+ _rhs_assoc =
+ ((terminal)((symbol_part)_rhs[i]).the_symbol()).precedence_side();
+ }
+ }
+ }
+
+ /*now action string is really declaration string, so put it in front!
+ 6/14/96 frankf */
+ if (action_str == null) action_str = "";
+ if (tail_action != null && tail_action.code_string() != null)
+ action_str = action_str + "\t\t" + tail_action.code_string();
+
+ /* stash the action */
+ _action = new action_part(action_str);
+
+ /* rewrite production to remove any embedded actions */
+ remove_embedded_actions();
+
+ /* assign an index */
+ _index = next_index++;
+
+ /* put us in the global collection of productions */
+ _all.put(new Integer(_index),this);
+
+ /* put us in the production list of the lhs non terminal */
+ lhs_sym.add_production(this);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Constructor with no action string. */
+ public production(
+ non_terminal lhs_sym,
+ production_part rhs_parts[],
+ int rhs_l)
+ throws internal_error
+ {
+ this(lhs_sym,rhs_parts,rhs_l,null);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /* Constructor with precedence and associativity of production
+ contextually define */
+ public production(
+ non_terminal lhs_sym,
+ production_part rhs_parts[],
+ int rhs_l,
+ String action_str,
+ int prec_num,
+ int prec_side)
+ throws internal_error
+ {
+ this(lhs_sym,rhs_parts,rhs_l,action_str);
+
+ /* set the precedence */
+ set_precedence_num(prec_num);
+ set_precedence_side(prec_side);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /* Constructor w/ no action string and contextual precedence
+ defined */
+ public production(
+ non_terminal lhs_sym,
+ production_part rhs_parts[],
+ int rhs_l,
+ int prec_num,
+ int prec_side)
+ throws internal_error
+ {
+ this(lhs_sym,rhs_parts,rhs_l,null);
+ /* set the precedence */
+ set_precedence_num(prec_num);
+ set_precedence_side(prec_side);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /*-----------------------------------------------------------*/
+ /*--- (Access to) Static (Class) Variables ------------------*/
+ /*-----------------------------------------------------------*/
+
+
+ /** Table of all productions. Elements are stored using their index as
+ * the key.
+ */
+ protected static Hashtable _all = new Hashtable();
+
+ /** Access to all productions. */
+ public static Enumeration all() {return _all.elements();}
+
+ /** Lookup a production by index. */
+ public static production find(int indx) {
+ return (production) _all.get(new Integer(indx));
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Total number of productions. */
+ public static int number() {return _all.size();}
+
+ /** Static counter for assigning unique index numbers. */
+ protected static int next_index;
+
+ /*-----------------------------------------------------------*/
+ /*--- (Access to) Instance Variables ------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** The left hand side non-terminal. */
+ protected symbol_part _lhs;
+
+ /** The left hand side non-terminal. */
+ public symbol_part lhs() {return _lhs;}
+
+
+ /** The precedence of the rule */
+ protected int _rhs_prec = -1;
+ protected int _rhs_assoc = -1;
+
+ /** Access to the precedence of the rule */
+ public int precedence_num() { return _rhs_prec; }
+ public int precedence_side() { return _rhs_assoc; }
+
+ /** Setting the precedence of a rule */
+ public void set_precedence_num(int prec_num) {
+ _rhs_prec = prec_num;
+ }
+ public void set_precedence_side(int prec_side) {
+ _rhs_assoc = prec_side;
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** A collection of parts for the right hand side. */
+ protected production_part _rhs[];
+
+ /** Access to the collection of parts for the right hand side. */
+ public production_part rhs(int indx) throws internal_error
+ {
+ if (indx >= 0 && indx < _rhs_length)
+ return _rhs[indx];
+ else
+ throw new internal_error(
+ "Index out of range for right hand side of production");
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** How much of the right hand side array we are presently using. */
+ protected int _rhs_length;
+
+ /** How much of the right hand side array we are presently using. */
+ public int rhs_length() {return _rhs_length;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** An action_part containing code for the action to be performed when we
+ * reduce with this production.
+ */
+ protected action_part _action;
+
+ /** An action_part containing code for the action to be performed when we
+ * reduce with this production.
+ */
+ public action_part action() {return _action;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Index number of the production. */
+ protected int _index;
+
+ /** Index number of the production. */
+ public int index() {return _index;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Count of number of reductions using this production. */
+ protected int _num_reductions = 0;
+
+ /** Count of number of reductions using this production. */
+ public int num_reductions() {return _num_reductions;}
+
+ /** Increment the count of reductions with this non-terminal */
+ public void note_reduction_use() {_num_reductions++;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Is the nullability of the production known or unknown? */
+ protected boolean _nullable_known = false;
+
+ /** Is the nullability of the production known or unknown? */
+ public boolean nullable_known() {return _nullable_known;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Nullability of the production (can it derive the empty string). */
+ protected boolean _nullable = false;
+
+ /** Nullability of the production (can it derive the empty string). */
+ public boolean nullable() {return _nullable;}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** First set of the production. This is the set of terminals that
+ * could appear at the front of some string derived from this production.
+ */
+ protected terminal_set _first_set = new terminal_set();
+
+ /** First set of the production. This is the set of terminals that
+ * could appear at the front of some string derived from this production.
+ */
+ public terminal_set first_set() {return _first_set;}
+
+ /*-----------------------------------------------------------*/
+ /*--- Static Methods ----------------------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** Determine if a given character can be a label id starter.
+ * @param c the character in question.
+ */
+ protected static boolean is_id_start(char c)
+ {
+ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c == '_');
+
+ //later need to handle non-8-bit chars here
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Determine if a character can be in a label id.
+ * @param c the character in question.
+ */
+ protected static boolean is_id_char(char c)
+ {
+ return is_id_start(c) || (c >= '0' && c <= '9');
+ }
+
+ /*-----------------------------------------------------------*/
+ /*--- General Methods ---------------------------------------*/
+ /*-----------------------------------------------------------*/
+
+
+ /** Return label declaration code
+ * @param labelname the label name
+ * @param stack_type the stack type of label?
+ * @author frankf
+ */
+ protected String make_declaration(
+ String labelname,
+ String stack_type,
+ int offset)
+ {
+ String ret;
+
+ /* Put in the left/right value labels */
+ if (emit.lr_values())
+ ret = "\t\tint " + labelname + "left = ((java_cup.runtime.Symbol)" +
+ emit.pre("stack") + ".elementAt(" + emit.pre("top") +
+ "-" + offset + ")).left;\n" +
+ "\t\tint " + labelname + "right = ((java_cup.runtime.Symbol)" +
+ emit.pre("stack") + ".elementAt(" + emit.pre("top") +
+ "-" + offset + ")).right;\n";
+ else ret = "";
+
+ /* otherwise, just declare label. */
+ return ret + "\t\t" + stack_type + " " + labelname + " = (" + stack_type +
+ ")((" + "java_cup.runtime.Symbol) " + emit.pre("stack") + ".elementAt(" + emit.pre("top")
+ + "-" + offset + ")).value;\n";
+
+ }
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Declare label names as valid variables within the action string
+ * @param rhs array of RHS parts.
+ * @param rhs_len how much of rhs to consider valid.
+ * @param final_action the final action string of the production.
+ * @param lhs_type the object type associated with the LHS symbol.
+ */
+ protected String declare_labels(
+ production_part rhs[],
+ int rhs_len,
+ String final_action)
+ {
+ String declaration = "";
+
+ symbol_part part;
+ action_part act_part;
+ int pos;
+
+ /* walk down the parts and extract the labels */
+ for (pos = 0; pos < rhs_len; pos++)
+ {
+ if (!rhs[pos].is_action())
+ {
+ part = (symbol_part)rhs[pos];
+
+ /* if it has a label, make declaration! */
+ if (part.label() != null)
+ {
+ declaration = declaration +
+ make_declaration(part.label(), part.the_symbol().stack_type(),
+ rhs_len-pos-1);
+ }
+ }
+ }
+ return declaration;
+ }
+
+
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Helper routine to merge adjacent actions in a set of RHS parts
+ * @param rhs_parts array of RHS parts.
+ * @param len amount of that array that is valid.
+ * @return remaining valid length.
+ */
+ protected int merge_adjacent_actions(production_part rhs_parts[], int len)
+ {
+ int from_loc, to_loc, merge_cnt;
+
+ /* bail out early if we have no work to do */
+ if (rhs_parts == null || len == 0) return 0;
+
+ merge_cnt = 0;
+ to_loc = -1;
+ for (from_loc=0; from_loc
+ * A ::= B NT$1 C NT$2 D
+ * NT$1 ::= {action1}
+ * NT$2 ::= {action2}
+ *
+ * where NT$1 and NT$2 are new system created non terminals.
+ */
+
+ /* the declarations added to the parent production are also passed along,
+ as they should be perfectly valid in this code string, since it
+ was originally a code string in the parent, not on its own.
+ frank 6/20/96 */
+ protected void remove_embedded_actions(
+
+ ) throws internal_error
+ {
+ non_terminal new_nt;
+ production new_prod;
+ String declare_str;
+
+ /* walk over the production and process each action */
+ for (int act_loc = 0; act_loc < rhs_length(); act_loc++)
+ if (rhs(act_loc).is_action())
+ {
+
+
+ declare_str = declare_labels(
+ _rhs, act_loc, "");
+ /* create a new non terminal for the action production */
+ new_nt = non_terminal.create_new();
+ new_nt.is_embedded_action = true; /* 24-Mar-1998, CSA */
+
+ /* create a new production with just the action */
+ new_prod = new action_production(this, new_nt, null, 0,
+ declare_str + ((action_part)rhs(act_loc)).code_string());
+
+ /* replace the action with the generated non terminal */
+ _rhs[act_loc] = new symbol_part(new_nt);
+ }
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Check to see if the production (now) appears to be nullable.
+ * A production is nullable if its RHS could derive the empty string.
+ * This results when the RHS is empty or contains only non terminals
+ * which themselves are nullable.
+ */
+ public boolean check_nullable() throws internal_error
+ {
+ production_part part;
+ symbol sym;
+ int pos;
+
+ /* if we already know bail out early */
+ if (nullable_known()) return nullable();
+
+ /* if we have a zero size RHS we are directly nullable */
+ if (rhs_length() == 0)
+ {
+ /* stash and return the result */
+ return set_nullable(true);
+ }
+
+ /* otherwise we need to test all of our parts */
+ for (pos=0; pos