[A ::= B * C d E , {a,b,c}]
this indicates that when the parser is in this state it is currently
looking for an A of the given form, has already seen the B, and would
expect to see an a, b, or c after this sequence is complete. Note that
the parser is normally looking for several things at once (represented
by several items). In our example above, the state would also include
items such as:
[C ::= * X e Z, {d}]
[X ::= * f, {e}]
to indicate that it was currently looking for a C followed by a d (which
would be reduced into a C, matching the first symbol in our production
above), and the terminal f followed by e.At runtime, the parser uses a viable prefix recognition machine made up of these states to parse. The parser has two operations, shift and reduce. In a shift, it consumes one Symbol and makes a transition to a new state. This corresponds to "moving the dot past" a terminal in one or more items in the state (these new shifted items will then be found in the state at the end of the transition). For a reduce operation, the parser is signifying that it is recognizing the RHS of some production. To do this it first "backs up" by popping a stack of previously saved states. It pops off the same number of states as are found in the RHS of the production. This leaves the machine in the same state is was in when the parser first attempted to find the RHS. From this state it makes a transition based on the non-terminal on the LHS of the production. This corresponds to placing the parse in a configuration equivalent to having replaced all the symbols from the the input corresponding to the RHS with the symbol on the LHS.
java_cup.lalr_item , java_cup.lalr_item_set , java_cup.lalr_transition
| Modifier and Type | Field and Description |
|---|---|
| protected static Hashtable | _all
Collection of all states. |
| protected static Hashtable | _all_kernels
Hash table to find states by their kernels (i.e, the original, unclosed, set of items -- which uniquely define the state). |
| protected int | _index
Index of this state in the parse tables |
| protected lalr_item_set | _items
The item set for this state. |
| protected lalr_transition | _transitions
List of transitions out of this state. |
| protected static int | next_index
Static counter for assigning unique state indexes. |
| Access | Constructor and Description |
|---|---|
| public | lalr_state(lalr_item_set
the set of items that makes up this state. itms)Constructor for building a state from a set of items. |
| Modifier and Type | Method and Description |
|---|---|
| public void | add_transition(symbol
the symbol the transition is under. on_sym, lalr_state the state the transition goes to. to_st)Add a transition out of this state to another. |
| public static Enumeration | |
| public static lalr_state | build_machine(production
the start production of the grammar start_prod)Build an LALR viable prefix recognition machine given a start production. |
| public void | build_table_entries(parse_action_table
the action table to put entries in. act_table, parse_reduce_table the reduce-goto table to put entries in. reduce_table)Fill in the parse table entries for this state. |
| protected static void | dump_state(lalr_state st)
Helper routine for debugging -- produces a dump of the given state onto System.out. |
| public boolean | |
| public boolean | equals(Object
the reference object with which to compare. other)Overrides java. |
| public static lalr_state | find_state(lalr_item_set
the kernel set of the state we are looking for. itms)Find and return state with a given a kernel item set (or null if not found). |
| protected boolean | fix_with_precedence(production
the production p, int the index of the lokahead terminal term_index, parse_action_row a row of the action table table_row, parse_action the rule in conflict with the table entry act)Procedure that attempts to fix a shift/reduce error by using precedences. |
| public int | |
| public int | |
| protected parse_action | |
| protected parse_action | |
| protected parse_action | |
| public lalr_item_set | |
| public static int | |
| protected static void | propagate_all_lookaheads()
Propagate lookahead sets through the constructed viable prefix recognizer. |
| protected void | |
| protected void | report_conflicts(terminal_set conflict_set)
Produce warning messages for all conflicts found in this state. |
| protected void | report_reduce_reduce(lalr_item
first item in conflict. itm1, lalr_item second item in conflict. itm2)Produce a warning message for one reduce/reduce conflict. |
| protected void | report_shift_reduce(lalr_item
the item with the reduce. red_itm, int the index of the symbol conflict occurs under. conflict_sym)Produce a warning message for one shift/reduce conflict. |
| public String | |
| public lalr_transition |
| _all | back to summary |
|---|---|
| protected static Hashtable<K, V> _all Collection of all states. | |
| _all_kernels | back to summary |
|---|---|
| protected static Hashtable<K, V> _all_kernels Hash table to find states by their kernels (i.e, the original, unclosed, set of items -- which uniquely define the state). This table stores state objects using (a copy of) their kernel item sets as keys. | |
| _index | back to summary |
|---|---|
| protected int _index Index of this state in the parse tables | |
| _items | back to summary |
|---|---|
| protected lalr_item_set _items The item set for this state. | |
| _transitions | back to summary |
|---|---|
| protected lalr_transition _transitions List of transitions out of this state. | |
| next_index | back to summary |
|---|---|
| protected static int next_index Static counter for assigning unique state indexes. | |
| lalr_state | back to summary |
|---|---|
| public lalr_state(lalr_item_set itms) throws internal_error Constructor for building a state from a set of items.
| |
| add_transition | back to summary |
|---|---|
| public void add_transition(symbol on_sym, lalr_state to_st) throws internal_error Add a transition out of this state to another.
| |
| all | back to summary |
|---|---|
| public static Enumeration Collection of all states. | |
| build_machine | back to summary |
|---|---|
| public static lalr_state build_machine(production start_prod) throws internal_error Build an LALR viable prefix recognition machine given a start production. This method operates by first building a start state from the start production (based on a single item with the dot at the beginning and EOF as expected lookahead). Then for each state it attempts to extend the machine by creating transitions out of the state to new or existing states. When considering extension from a state we make a transition on each symbol that appears before the dot in some item. For example, if we have the items:
[A ::= a b * X c, {d,e}]
[B ::= a b * X d, {a,b}]
in some state, then we would be making a transition under X to a new
state. This new state would be formed by a "kernel" of items
corresponding to moving the dot past the X. In this case:
[A ::= a b X * c, {d,e}]
[B ::= a b X * Y, {a,b}]
The full state would then be formed by "closing" this kernel set of
items so that it included items that represented productions of things
the parser was now looking for. In this case we would items
corresponding to productions of Y, since various forms of Y are expected
next when in this state (see lalr_item_set.compute_closure() for details
on closure). The process of building the viable prefix recognizer terminates when no new states can be added. However, in order to build a smaller number of states (i.e., corresponding to LALR rather than canonical LR) the state building process does not maintain full loookaheads in all items. Consequently, after the machine is built, we go back and propagate lookaheads through the constructed machine using a call to propagate_all_lookaheads(). This makes use of propagation links constructed during the closure and transition process.
| |
| build_table_entries | back to summary |
|---|---|
| public void build_table_entries(parse_action_table act_table, parse_reduce_table reduce_table) throws internal_error Fill in the parse table entries for this state. There are two parse tables that encode the viable prefix recognition machine, an action table and a reduce-goto table. The rows in each table correspond to states of the machine. The columns of the action table are indexed by terminal symbols and correspond to either transitions out of the state (shift entries) or reductions from the state to some previous state saved on the stack (reduce entries). All entries in the action table that are not shifts or reduces, represent errors. The reduce-goto table is indexed by non terminals and represents transitions out of a state on that non-terminal. Conflicts occur if more than one action needs to go in one entry of the action table (this cannot happen with the reduce-goto table). Conflicts are resolved by always shifting for shift/reduce conflicts and choosing the lowest numbered production (hence the one that appeared first in the specification) in reduce/reduce conflicts. All conflicts are reported and if more conflicts are detected than were declared by the user, code generation is aborted.
| |
| dump_state | back to summary |
|---|---|
| protected static void dump_state(lalr_state st) throws internal_error Helper routine for debugging -- produces a dump of the given state onto System.out. | |
| equals | back to summary |
|---|---|
| public boolean equals(lalr_state other) Equality comparison. | |
| equals | back to summary |
|---|---|
| public boolean equals(Object other) Overrides java. Generic equality comparison.
| |
| find_state | back to summary |
|---|---|
| public static lalr_state find_state(lalr_item_set itms) Find and return state with a given a kernel item set (or null if not found). The kernel item set is the subset of items that were used to originally create the state. These items are formed by "shifting the dot" within items of other states that have a transition to this one. The remaining elements of this state's item set are added during closure.
| |
| fix_with_precedence | back to summary |
|---|---|
| protected boolean fix_with_precedence(production p, int term_index, parse_action_row table_row, parse_action act) throws internal_error Procedure that attempts to fix a shift/reduce error by using precedences. --frankf 6/26/96 if a production (also called rule) or the lookahead terminal has a precedence, then the table can be fixed. if the rule has greater precedence than the terminal, a reduce by that rule in inserted in the table. If the terminal has a higher precedence, it is shifted. if they have equal precedence, then the associativity of the precedence is used to determine what to put in the table: if the precedence is left associative, the action is to reduce. if the precedence is right associative, the action is to shift. if the precedence is non associative, then it is a syntax error.
| |
| hashCode | back to summary |
|---|---|
| public int hashCode() Overrides java. Produce a hash code.
| |
| index | back to summary |
|---|---|
| public int index() Index of this state in the parse tables | |
| insert_action | back to summary |
|---|---|
| protected parse_action insert_action(parse_action a1, parse_action a2, int act_type) throws internal_error | |
| insert_reduce | back to summary |
|---|---|
| protected parse_action insert_reduce(parse_action a1, parse_action a2) throws internal_error | |
| insert_shift | back to summary |
|---|---|
| protected parse_action insert_shift(parse_action a1, parse_action a2) throws internal_error | |
| items | back to summary |
|---|---|
| public lalr_item_set items() The item set for this state. | |
| number | back to summary |
|---|---|
| public static int number() Indicate total number of states there are. | |
| propagate_all_lookaheads | back to summary |
|---|---|
| protected static void propagate_all_lookaheads() throws internal_error Propagate lookahead sets through the constructed viable prefix recognizer. When the machine is constructed, each item that results in the creation of another such that its lookahead is included in the other's will have a propagate link set up for it. This allows additions to the lookahead of one item to be included in other items that it was used to directly or indirectly create. | |
| propagate_lookaheads | back to summary |
|---|---|
| protected void propagate_lookaheads() throws internal_error Propagate lookahead sets out of this state. This recursively propagates to all items that have propagation links from some item in this state. | |
| report_conflicts | back to summary |
|---|---|
| protected void report_conflicts(terminal_set conflict_set) throws internal_error Produce warning messages for all conflicts found in this state. | |
| report_reduce_reduce | back to summary |
|---|---|
| protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2) throws internal_error Produce a warning message for one reduce/reduce conflict. | |
| report_shift_reduce | back to summary |
|---|---|
| protected void report_shift_reduce(lalr_item red_itm, int conflict_sym) throws internal_error Produce a warning message for one shift/reduce conflict.
| |
| toString | back to summary |
|---|---|
| public String toString() Overrides java. Convert to a string.
| |
| transitions | back to summary |
|---|---|
| public lalr_transition transitions() List of transitions out of this state. | |