lalr_state

Overview | Package | Class | Tree | Deprecated | Index | Help | Weka's home

PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## weka.core.parser.java_cup
Class lalr_state

    java.lang.Object
      weka.core.parser.java_cup.lalr_state

    public class lalr_state

extends java.lang.Object

This class represents a state in the LALR viable prefix recognition machine. A state consists of an LALR item set and a set of transitions to other states under terminal and non-terminal symbols. Each state represents a potential configuration of the parser. If the item set of a state includes an item such as:

        [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.

Version:
  last updated: 7/3/96
Author:
  Frank Flannery
See Also:
  `lalr_item`, `lalr_item_set`, `lalr_transition`

Constructor Summary
`lalr_state(lalr_item_set itms)` Constructor for building a state from a set of items.

Method Summary
`void` | `add_transition(symbol on_sym, lalr_state to_st)` Add a transition out of this state to another.
`static java.util.Enumeration` | `all()` Collection of all states.
`static lalr_state` | `build_machine(production start_prod)` Build an LALR viable prefix recognition machine given a start production.
`void` | `build_table_entries(parse_action_table act_table, parse_reduce_table reduce_table)` Fill in the parse table entries for this state.
`static void` | `clear()`
`boolean` | `equals(lalr_state other)` Equality comparison.
`boolean` | `equals(java.lang.Object other)` Generic equality comparison.
`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).
`int` | `hashCode()` Produce a hash code.
`int` | `index()` Index of this state in the parse tables
`lalr_item_set` | `items()` The item set for this state.
`static int` | `number()` Indicate total number of states there are.
`java.lang.String` | `toString()` Convert to a string.
`lalr_transition` | `transitions()` List of transitions out of this state.

Methods inherited from class java.lang.Object
`getClass, notify, notifyAll, wait, wait, wait`

Constructor Detail

### lalr_state

    public lalr_state(lalr_item_set itms)
               throws internal_error

  Constructor for building a state from a set of items.

  Parameters:
    `itms` - the set of items that makes up this state.
  Throws:
    `internal_error`

Method Detail

### all

    public static java.util.Enumeration all()

  Collection of all states.

### clear

    public static void clear()

### number

    public static int number()

  Indicate total number of states there are.

### find_state

    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.

  Parameters:
    `itms` - the kernel set of the state we are looking for.

### items

    public lalr_item_set items()

  The item set for this state.

### transitions

    public lalr_transition transitions()

  List of transitions out of this state.

### index

    public int index()

  Index of this state in the parse tables

### add_transition

    public void add_transition(symbol on_sym,
                               lalr_state to_st)
                        throws internal_error

  Add a transition out of this state to another.

  Parameters:
    `on_sym` - the symbol the transition is under.
    `to_st` - the state the transition goes to.
  Throws:
    `internal_error`

### build_machine

    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.

  Parameters:
    `start_prod` - the start production of the grammar
  Throws:
    `internal_error`
  See Also:
    `lalr_item_set.compute_closure()`, `propagate_all_lookaheads()`

### build_table_entries

    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.

  Parameters:
    `act_table` - the action table to put entries in.
    `reduce_table` - the reduce-goto table to put entries in.
  Throws:
    `internal_error`

### equals

    public boolean equals(lalr_state other)

  Equality comparison.

### equals

    public boolean equals(java.lang.Object other)

  Generic equality comparison.

  Overrides:
    `equals` in class `java.lang.Object`

### hashCode

    public int hashCode()

  Produce a hash code.

  Overrides:
    `hashCode` in class `java.lang.Object`

### toString

    public java.lang.String toString()

  Convert to a string.

  Overrides:
    `toString` in class `java.lang.Object`

Overview | Package | Class | Tree | Deprecated | Index | Help | Weka's home

PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD