java_cup

Class production

public class production extends Object

This class represents a production in the grammar. It contains a LHS non terminal, and an array of RHS symbols. As various transformations are done on the RHS of the production, it may shrink. As a result a separate length is always maintained to indicate how much of the RHS array is still valid.

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()).

Version: last updated: 7/3/96

Author: Frank Flannery

See Also: production_part symbol_part action_part

Field Summary
protected static intnext_index
Static counter for assigning unique index numbers.
protected action_part_action
An action_part containing code for the action to be performed when we reduce with this production.
protected static Hashtable_all
Table of all productions.
protected terminal_set_first_set
First set of the production.
protected int_index
Index number of the production.
protected symbol_part_lhs
The left hand side non-terminal.
protected boolean_nullable
Nullability of the production (can it derive the empty string).
protected boolean_nullable_known
Is the nullability of the production known or unknown?
protected int_num_reductions
Count of number of reductions using this production.
protected production_part[]_rhs
A collection of parts for the right hand side.
protected int_rhs_assoc
protected int_rhs_length
How much of the right hand side array we are presently using.
protected int_rhs_prec
The precedence of the rule
Constructor Summary
production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, String action_str)
Full constructor.
production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l)
Constructor with no action string.
production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, String action_str, int prec_num, int prec_side)
production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, int prec_num, int prec_side)
Method Summary
action_partaction()
An action_part containing code for the action to be performed when we reduce with this production.
static Enumerationall()
Access to all productions.
terminal_setcheck_first_set()
Update (and return) the first set based on current NT firsts.
booleancheck_nullable()
Check to see if the production (now) appears to be nullable.
protected Stringdeclare_labels(production_part[] rhs, int rhs_len, String final_action)
Declare label names as valid variables within the action string
booleanequals(production other)
Equality comparison.
booleanequals(Object other)
Generic equality comparison.
static productionfind(int indx)
Lookup a production by index.
terminal_setfirst_set()
First set of the production.
inthashCode()
Produce a hash code.
intindex()
Index number of the production.
protected static booleanis_id_char(char c)
Determine if a character can be in a label id.
protected static booleanis_id_start(char c)
Determine if a given character can be a label id starter.
symbol_partlhs()
The left hand side non-terminal.
protected Stringmake_declaration(String labelname, String stack_type, int offset)
Return label declaration code
protected intmerge_adjacent_actions(production_part[] rhs_parts, int len)
Helper routine to merge adjacent actions in a set of RHS parts
voidnote_reduction_use()
Increment the count of reductions with this non-terminal
booleannullable()
Nullability of the production (can it derive the empty string).
booleannullable_known()
Is the nullability of the production known or unknown?
static intnumber()
Total number of productions.
intnum_reductions()
Count of number of reductions using this production.
intprecedence_num()
Access to the precedence of the rule
intprecedence_side()
protected voidremove_embedded_actions()
Remove all embedded actions from a production by factoring them out into individual action production using new non terminals. if the original production was:
    A ::= B {action1} C {action2} D 
  
then it will be factored into:
    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.
production_partrhs(int indx)
Access to the collection of parts for the right hand side.
intrhs_length()
How much of the right hand side array we are presently using.
voidset_precedence_num(int prec_num)
Setting the precedence of a rule
voidset_precedence_side(int prec_side)
protected action_partstrip_trailing_action(production_part[] rhs_parts, int len)
Helper routine to strip a trailing action off rhs and return it
StringtoString()
Convert to a string.
Stringto_simple_string()
Convert to a simpler string.

Field Detail

next_index

protected static int next_index
Static counter for assigning unique index numbers.

_action

protected action_part _action
An action_part containing code for the action to be performed when we reduce with this production.

_all

protected static Hashtable _all
Table of all productions. Elements are stored using their index as the key.

_first_set

protected terminal_set _first_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.

_index

protected int _index
Index number of the production.

_lhs

protected symbol_part _lhs
The left hand side non-terminal.

_nullable

protected boolean _nullable
Nullability of the production (can it derive the empty string).

_nullable_known

protected boolean _nullable_known
Is the nullability of the production known or unknown?

_num_reductions

protected int _num_reductions
Count of number of reductions using this production.

_rhs

protected production_part[] _rhs
A collection of parts for the right hand side.

_rhs_assoc

protected int _rhs_assoc

_rhs_length

protected int _rhs_length
How much of the right hand side array we are presently using.

_rhs_prec

protected int _rhs_prec
The precedence of the rule

Constructor Detail

production

public production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, String action_str)
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.

production

public production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l)
Constructor with no action string.

production

public production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, String action_str, int prec_num, int prec_side)

production

public production(non_terminal lhs_sym, production_part[] rhs_parts, int rhs_l, int prec_num, int prec_side)

Method Detail

action

public action_part action()
An action_part containing code for the action to be performed when we reduce with this production.

all

public static Enumeration all()
Access to all productions.

check_first_set

public terminal_set check_first_set()
Update (and return) the first set based on current NT firsts. This assumes that nullability has already been computed for all non terminals and productions.

check_nullable

public boolean check_nullable()
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.

declare_labels

protected String declare_labels(production_part[] rhs, int rhs_len, String final_action)
Declare label names as valid variables within the action string

Parameters: rhs array of RHS parts. rhs_len how much of rhs to consider valid. final_action the final action string of the production. lhs_type the object type associated with the LHS symbol.

equals

public boolean equals(production other)
Equality comparison.

equals

public boolean equals(Object other)
Generic equality comparison.

find

public static production find(int indx)
Lookup a production by index.

first_set

public terminal_set first_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.

hashCode

public int hashCode()
Produce a hash code.

index

public int index()
Index number of the production.

is_id_char

protected static boolean is_id_char(char c)
Determine if a character can be in a label id.

Parameters: c the character in question.

is_id_start

protected static boolean is_id_start(char c)
Determine if a given character can be a label id starter.

Parameters: c the character in question.

lhs

public symbol_part lhs()
The left hand side non-terminal.

make_declaration

protected String make_declaration(String labelname, String stack_type, int offset)
Return label declaration code

Parameters: labelname the label name stack_type the stack type of label?

Author: frankf

merge_adjacent_actions

protected int merge_adjacent_actions(production_part[] rhs_parts, int len)
Helper routine to merge adjacent actions in a set of RHS parts

Parameters: rhs_parts array of RHS parts. len amount of that array that is valid.

Returns: remaining valid length.

note_reduction_use

public void note_reduction_use()
Increment the count of reductions with this non-terminal

nullable

public boolean nullable()
Nullability of the production (can it derive the empty string).

nullable_known

public boolean nullable_known()
Is the nullability of the production known or unknown?

number

public static int number()
Total number of productions.

num_reductions

public int num_reductions()
Count of number of reductions using this production.

precedence_num

public int precedence_num()
Access to the precedence of the rule

precedence_side

public int precedence_side()

remove_embedded_actions

protected void remove_embedded_actions()
Remove all embedded actions from a production by factoring them out into individual action production using new non terminals. if the original production was:
    A ::= B {action1} C {action2} D 
  
then it will be factored into:
    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.

rhs

public production_part rhs(int indx)
Access to the collection of parts for the right hand side.

rhs_length

public int rhs_length()
How much of the right hand side array we are presently using.

set_precedence_num

public void set_precedence_num(int prec_num)
Setting the precedence of a rule

set_precedence_side

public void set_precedence_side(int prec_side)

strip_trailing_action

protected action_part strip_trailing_action(production_part[] rhs_parts, int len)
Helper routine to strip a trailing action off rhs and return it

Parameters: rhs_parts array of RHS parts. len how many of those are valid.

Returns: the removed action part.

toString

public String toString()
Convert to a string.

to_simple_string

public String to_simple_string()
Convert to a simpler string.