dfa

Documentation

Index

• type DFA
  • func NewDFA(name string) *DFA
  • func (m *DFA) GetStart() string
  • func (m *DFA) GetState(name string) *State
  • func (m *DFA) GetSymbols() []string
  • func (m *DFA) Index()
  • func (m *DFA) InspectStates(from, to string) []string
  • func (m *DFA) InspectSymbols(symbol string) []*Edge
  • func (m *DFA) Run(tokens []string) ([]string, bool)
  • func (m *DFA) SetStart(state string)
  • func (m *DFA) SetState(state *State)
  • func (m *DFA) SetStates(states []*State)
  • func (m *DFA) StateExists(name string) bool
  • func (m *DFA) Step(state, symbol string) (string, bool, error)
• type Edge
• type State
  • func NewState(name string) *State
  • func (s *State) AddTransition(state *State, symbol string)
  • func (s *State) AddTransitions(state *State, symbols []string)
  • func (s *State) GetTransitions() map[string]string
  • func (s *State) IsFinal() bool
  • func (s *State) SetFinal(final bool)
  • func (s *State) Via(symbol string) (string, bool)

Types

type DFA

type DFA struct {
	Name string
	// States holds the state name as well as the state structure
	States map[string]*State
	// StateLookup holds key: symbol->symbol and all the states that
	// are in between of this symbol->state->symbol constellation.
	StateLookup map[string][]string
	// EdgeLookup holds key: symbol and as value all state pairs that
	// are connected by this symbol.
	EdgeLookup map[string][]*Edge
	Indexed    bool
	Start      string
}

DFA holds everything that is needed in order to execute the automaton.

func NewDFA

func NewDFA(name string) *DFA

NewDFA creates a new DFA

func (*DFA) GetStart

func (m *DFA) GetStart() string

GetStart returns the starting point of the DFA.

func (*DFA) GetState

func (m *DFA) GetState(name string) *State

GetState returns the specific state with a given name

func (*DFA) GetSymbols

func (m *DFA) GetSymbols() []string

GetSymbols returns distinct symbols used in this DFA

func (*DFA) Index

func (m *DFA) Index()

Index indexes all symbol to symbol transitions with the states that are in between. And also indexes a symbol with all the state pairs where it is in between.

func (*DFA) InspectStates

func (m *DFA) InspectStates(from, to string) []string

InspectStates returns (if indexed) all states that have a connection from a symbol to a symbol. It answers the questions which state is in between these two symbols.

func (*DFA) InspectSymbols

func (m *DFA) InspectSymbols(symbol string) []*Edge

InspectSymbols returns (if indexed) all states that have a connection from a symbol to a symbol. It answers the questions which state is in between these two symbols.

func (*DFA) Run

func (m *DFA) Run(tokens []string) ([]string, bool)

Run runs the DFA from the starting point with the given events and returns the states that the events have taken

func (*DFA) SetStart

func (m *DFA) SetStart(state string)

SetStart sets the starting point of the DFA.

func (*DFA) SetState

func (m *DFA) SetState(state *State)

SetSetate sets one state

func (*DFA) SetStates

func (m *DFA) SetStates(states []*State)

SetStates is able to set multiple states at once

func (*DFA) StateExists

func (m *DFA) StateExists(name string) bool

StateExists tests if the state exists

func (*DFA) Step

func (m *DFA) Step(state, symbol string) (string, bool, error)

Step executes one step in the DFA and determines if this step is possible within this automaton.

type Edge

type Edge struct {
	From string
	To   string
}

Edge represents a connection from a state to a state

type State

type State struct {
	// Name represents the name of the state
	Name string
	// Transitions represents the transitions of the state.
	// The map is structured map[Symbol]State
	Transitions map[string]string
	Final       bool
}

func NewState

func NewState(name string) *State

NewState creates a new state

func (*State) AddTransition

func (s *State) AddTransition(state *State, symbol string)

AddTransitions adds a symbol that leads to a state - meaning a transition

func (*State) AddTransitions

func (s *State) AddTransitions(state *State, symbols []string)

AddTransitions adds a bulk of symbols to the state that all end up in the same state

func (*State) GetTransitions

func (s *State) GetTransitions() map[string]string

GetTransitions returns the symbols that would lead to a transition

func (*State) IsFinal

func (s *State) IsFinal() bool

IsFinal tests if this state is a final state

func (*State) SetFinal

func (s *State) SetFinal(final bool)

SetFinal sets this state to a final state

func (*State) Via

func (s *State) Via(symbol string) (string, bool)

Via is used by the DFA to find a transition using a symbol