Logo Search packages:      
Sourcecode: jasmin-sable version File versions  Download package

java_cup::lalr_state Class Reference

List of all members.

Detailed Description

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.

See also:



last updated: 7/3/96
Frank Flannery

Definition at line 52 of file lalr_state.java.

Public Member Functions

void add_transition (symbol on_sym, lalr_state to_st) throws internal_error
void build_table_entries (parse_action_table act_table, parse_reduce_table reduce_table) throws internal_error
boolean equals (Object other)
boolean equals (lalr_state other)
int hashCode ()
int index ()
lalr_item_set items ()
 lalr_state (lalr_item_set itms) throws internal_error
String toString ()
lalr_transition transitions ()

Static Public Member Functions

static Enumeration all ()
static lalr_state build_machine (production start_prod) throws internal_error
static lalr_state find_state (lalr_item_set itms)
static int number ()

Protected Member Functions

boolean fix_with_precedence (production p, int term_index, parse_action_row table_row, parse_action act) throws internal_error
parse_action insert_action (parse_action a1, parse_action a2, int act_type) throws internal_error
parse_action insert_reduce (parse_action a1, parse_action a2) throws internal_error
parse_action insert_shift (parse_action a1, parse_action a2) throws internal_error
void propagate_lookaheads () throws internal_error
void report_conflicts (terminal_set conflict_set) throws internal_error
void report_reduce_reduce (lalr_item itm1, lalr_item itm2) throws internal_error
void report_shift_reduce (lalr_item red_itm, int conflict_sym) throws internal_error

Static Protected Member Functions

static void dump_state (lalr_state st) throws internal_error
static void propagate_all_lookaheads () throws internal_error

Protected Attributes

int _index
lalr_item_set _items
lalr_transition _transitions = null

Static Protected Attributes

static Hashtable _all = new Hashtable()
static Hashtable _all_kernels = new Hashtable()
static int next_index = 0

The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index