dfa

README

dfago

A simple implementation of Discrete Finite Automata written in Go. Uses TOML for DFA syntax. See example.dfa.

States in the DFA are listed as:

[state.state_name]
acccept = true | false
transitions [
  ... array of transitions which are...
  ["s:exact_string_match", "destination_state_name"],
  ["r:.*regex_match", "destination_state_name"],
  ["f:lua_function:argument1", "destination_state_name"]
]

The top level [dfa] object will include the name of the starting state and a few optional fields described below. Destination states must be valid names. In a given state, the current input will be matched against each transition until the first match. Matches can be exact strings (prefixed with 's:'), regular expression matches (prefixed with 'r:'), or Lua function calls (prefixed with 'f:' and formatted as 'f:function_name:argument_string). If no match is made, the DFA will remain in the current state by default. When all inputs have been consumed, the accept value of the current state is returned.

Lua functions must match the signature:

function (str1, str2)
  return bool
end

These will be called with the argument embedded in the transition as str1 and the input as str2. The functions are pulled from defaultlib.lua and any files passed to dfa.AddLua(). If the function returns true, the transition is considered matched to the input and will be taken. Otherwise, the DFA will continue searching for transition matches.

[dfa]
start = "start_state_name"
hasNoMatch = false | true
noMatch = "destination_state_if_no_match"
globalPostTransitions = [
  ... array of transitions which are applied in every state 
  if no transitions in the current state are matched...
  ["s:exact_string_match", "destination_state_name"],
  ["r:.*regex_match", "destination_state_name"],
]

The rundfa binary in the rundfa folder can be used to directly run TOML formatted DFA files on the commant line. It is a thin wrapper around the dfago library.

To build:

cd rundfa
go build

To run:

./rundfa <toml_file> <input0> <input1> ... <inputN>

A Note on Building

With the addition of Lua support (via aarzilli's excellent golua), you will need to have the Lua shared library installed to build. See his page for additional details. Once linked, this is not required for running.

Documentation

Index

• type DFA
  • func ParseDFA(dfaToml string) (*DFA, error)
  • func ParseDFAFromFile(path string) (*DFA, error)
  • func (dfa *DFA) AddLua(file string)
  • func (dfa *DFA) ApplyDFA(inputs []string) (bool, error)
  • func (dfa *DFA) ApplyLua(funcname string, inputA string, inputB string) bool
  • func (dfa *DFA) Close()
• type DFAConfig
• type DFAState

Types

type DFA

type DFA struct {
	L      *lua.State
	Config DFAConfig           `toml:"dfa"`
	States map[string]DFAState `toml:"state"`
}

func ParseDFA

func ParseDFA(dfaToml string) (*DFA, error)

func ParseDFAFromFile

func ParseDFAFromFile(path string) (*DFA, error)

func (*DFA) AddLua

func (dfa *DFA) AddLua(file string)

func (*DFA) ApplyDFA

func (dfa *DFA) ApplyDFA(inputs []string) (bool, error)

func (*DFA) ApplyLua

func (dfa *DFA) ApplyLua(funcname string, inputA string, inputB string) bool

func (*DFA) Close

func (dfa *DFA) Close()

type DFAConfig

type DFAConfig struct {
	Start                 string      `toml:"start"`
	HasNoMatchState       bool        `toml:"hasNoMatch"`
	NoMatchState          string      `toml:"noMatch"`
	GlobalPostTransitions [][2]string `toml:"globalPostTransitions"`
}

type DFAState

type DFAState struct {
	Accept      bool        `toml:"accept"`
	Transitions [][2]string `toml:"transitions"`
}