class

Kleene::NFA

Inherits Reference < Object

Constructors

new(start_state : Kleene::State, alphabet : Set(Char) = DEFAULT_ALPHABET, transitions : Hash(Kleene::State, Hash(Char, Set(Kleene::NFATransition))) = Hash(State, Hash(Char, Set(NFATransition))).new, initial_states = nil)
Source

Instance methods

accept?
Source
add_state(new_state)
Source
add_states(states)
Source
add_transition(token : Char, from_state, to_state)
Source
all_transitions
Source
alphabet
Source
alphabet=(alphabet : Set(Char))
Source
current_states
Source
current_states=(current_states : Set(State))
Source
deep_clone
Source
epsilon_closure(state_set : Set(State)) : Set(State)
Source
epsilon_closure(state : State) : Set(State)

Determine the epsilon closure of the given state set That is, determine what states are reachable on an epsilon transition from the current state set (@current_states). Returns a Set of State objects.

Source
error_states
Source
final_states
Source
final_states=(final_states : Set(State))
Source
graphviz
Source
handle_token!(input_token : Char)

process another input token

Source
match?(input : String) : MatchRef | Nil
Source
matches(input)

Returns an array of matches found anywhere in the input string

Source
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

Source
next_states(state_set, input_token)
Source
reachable_states(start_state)

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

Source
regex_pattern
Source
remove_state(state)
Source
reset_current_states
Source
set_regex_pattern(pattern : Nil | String)
Source
start_state
Source
start_state=(start_state : State)
Source
states
Source
states=(states : Set(State))
Source
to_dfa

This implements the subset construction algorithm presented on page 118 of the first edition of the dragon book. I found a similar explanation at: http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3.pdf

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

Source
transitions
Source
transitions=(transitions : Hash(State, Hash(Char, Set(NFATransition))))
Source
transitions_from(state_set : Set(State)) : Set(NFATransition)
Source
transitions_from(state : State) : Set(NFATransition)
Source
update_final_states
Source