class

Kleene::DFA

Inherits Reference < Object

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 methods

accept?

add_transition(token, from_state, to_state)

all_transitions

alphabet

alphabet=(alphabet : Set(Char))

clear_error_states

current_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

dfa_state_to_nfa_state_sets=(dfa_state_to_nfa_state_sets : Hash(State, Set(State)))

error?

error_states

final_states

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

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

start_state=(start_state : State)

states

states=(states : Set(State))

to_s(verbose = false)

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

This method should usually not be overridden. It delegates to #to_s(IO) which can be overridden for custom implementations.

Also see #inspect.

transition_callbacks

transition_callbacks=(transition_callbacks : Hash(DFATransition, DFATransitionCallback))

transition_callbacks_per_destination_state

transition_callbacks_per_destination_state=(transition_callbacks_per_destination_state : Hash(State, DFATransitionCallback))

transitions

transitions=(transitions : Hash(State, Hash(Char, DFATransition)))

update_final_states