class Kleene::DFA

• Kleene::DFA
• Reference
• Object

Defined in:

dfa.cr

Constructors

• .new(start_state : Kleene::State, alphabet : Set(Char) = DEFAULT_ALPHABET, transitions : Hash(Kleene::State, Hash(Char, Kleene::DFATransition)) = Hash(State, Hash(Char, DFATransition)).new, dfa_state_to_nfa_state_sets : Hash(Kleene::State, Set(Kleene::State)) = Hash(State, Set(State)).new, transition_callbacks = nil, origin_nfa : Nil | Kleene::NFA = nil)

Instance Method Summary

• #accept?
• #add_transition(token, from_state, to_state)
• #all_transitions : Array(DFATransition)
• #alphabet : Set(Char)
• #alphabet=(alphabet : Set(Char))
• #clear_error_states
• #current_state : State
• #current_state=(current_state : State)
• #deep_clone

  transition callbacks are not copied beacuse it is assumed that the state transition callbacks may be stateful and reference structures or states that only exist in self, but not the cloned copy.

• #dfa_state_to_nfa_state_sets : Hash(State, Set(State))
• #dfa_state_to_nfa_state_sets=(dfa_state_to_nfa_state_sets : Hash(State, Set(State)))
• #error?
• #error_states
• #final_states : Set(State)
• #final_states=(final_states : Set(State))
• #handle_token!(input_token, token_index)

  accept an input token and transition to the next state in the state machine

• #match?(input : String)
• #matches(input)

  Returns an array of matches found anywhere in the input string

• #matches_at_offset(input, input_start_offset)

  Returns an array of matches found in the input string, each of which begins at the offset input_start_offset

• #minimize!

  This is an implementation of the "Reducing a DFA to a Minimal DFA" algorithm presented here: http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart4.pdf This implements Hopcroft's algorithm as presented on page 142 of the first edition of the dragon book.

• #next_state(from_state, input_token, token_index)

  if the DFA is currently in a final state, then we look up the associated NFA states that were also final, and return them def accepting_nfa_states : Set(State) if accept? dfa_state_to_nfa_state_sets[@current_state].select(&.final?).to_set else Set(State).new end end this function transitions from state to state on an input token

• #nfa_state_to_dfa_state_sets : Hash(State, Set(State))
• #nfa_state_to_dfa_state_sets=(nfa_state_to_dfa_state_sets : Hash(State, Set(State)))
• #on_transition(transition, &blk : DFATransitionCallback)
• #on_transition_to(state, &blk : DFATransitionCallback)
• #origin_nfa
• #reachable_states(start_state)

  Returns a set of State objects which are reachable through any transition path from the DFA's start_state.

• #regex_pattern
• #reset_current_state
• #set_regex_pattern(pattern : Nil | String)
• #shallow_clone
• #start_state : State
• #start_state=(start_state : State)
• #states : Set(State)
• #states=(states : Set(State))
• #to_s(verbose = false)

  Returns a nicely readable and concise string representation of this object, typically intended for users.

• #transition_callbacks : Hash(DFATransition, DFATransitionCallback)
• #transition_callbacks=(transition_callbacks : Hash(DFATransition, DFATransitionCallback))
• #transition_callbacks_per_destination_state : Hash(State, DFATransitionCallback)
• #transition_callbacks_per_destination_state=(transition_callbacks_per_destination_state : Hash(State, DFATransitionCallback))
• #transitions : Hash(State, Hash(Char, DFATransition))
• #transitions=(transitions : Hash(State, Hash(Char, DFATransition)))
• #update_final_states

Constructor Detail

Instance Method Detail