fsa

README

* Fsa
Go-package for final state automata (FSA). FSA are represented using a
sparse table. Final states can hold string values and map input
strings to values.

Documentation

Index

• type Builder
  • func NewBuilder() *Builder
  • func (b *Builder) Add(wf, v string) error
  • func (b *Builder) AddToAlphabet(chars string)
  • func (b *Builder) Build() (*FSA, error)
  • func (b *Builder) Statistics() Statistics
• type DFANode
  • func Determinize(initial NDFANode, b DFANodeBuilder) DFANode
• type DFANodeBuilder
• type FSA
  • func NewFSAFromNodes(initial DFANode) *FSA
  • func (a *FSA) Data(s uint32) uint32
  • func (a *FSA) Delta(s uint32, c byte) uint32
  • func (a *FSA) GobDecode(buf []byte) error
  • func (a *FSA) GobEncode() ([]byte, error)
  • func (a *FSA) Info(d uint32) string
  • func (a *FSA) Initial() uint32
• type NDFANode
• type Statistics

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

func NewBuilder

func NewBuilder() *Builder

NewBuilder creates a new builder.

func (*Builder) Add

func (b *Builder) Add(wf, v string) error

Add adds a key-value pair to the builder. The resulting automaton then associates key wf with value v.

func (*Builder) AddToAlphabet

func (b *Builder) AddToAlphabet(chars string)

AddToAlphabet adds all characters (bytes) in str to the builder's internal alphabet.

All characters of keys added to the builder must be added to the alphabet before being added to the builder. The zero character \0 has special meaning and cannot be added to the builder's alphabet.

func (*Builder) Build

func (b *Builder) Build() (*FSA, error)

Build finishes the building process and returns the CFSA.

func (*Builder) Statistics

func (b *Builder) Statistics() Statistics

Statistics returns a Statistics struct.

type DFANode

type DFANode interface {
	Final() string         // Return the empty string to denote non-final nodes.
	Target(c byte) DFANode // Target for the given transition
}

Node represents a state in a DFA. They can be used to construct an FSA instance.

Final states should return a non-empty string in their implementation of the Final() method. If a node has no target transition, nil should be returned.

func Determinize

func Determinize(initial NDFANode, b DFANodeBuilder) DFANode

Determinize determinizes a non-deterministic FSA.

type DFANodeBuilder

type DFANodeBuilder interface {
	NewNode(string) DFANode           // Return a new DFANode instance.
	LinkNodes(DFANode, byte, DFANode) // Link the two nodes together with a specific byte.
}

DFANodeBuilder is used to build and link DFANodes by fsa.Determinize.

type FSA

type FSA struct {
	// contains filtered or unexported fields
}

func NewFSAFromNodes

func NewFSAFromNodes(initial DFANode) *FSA

NewFSAFromNodes creates a new fsa from the given initial state. The function panics if the nodes do not represent a dfa.

func (*FSA) Data

func (a *FSA) Data(s uint32) uint32

Data returns the data of a cell if it is a data state.

func (*FSA) Delta

func (a *FSA) Delta(s uint32, c byte) uint32

Delta executes a transition from s using c and returns the target state. If no transition can be executed, 0 is returned.

func (*FSA) GobDecode

func (a *FSA) GobDecode(buf []byte) error

func (*FSA) GobEncode

func (a *FSA) GobEncode() ([]byte, error)

func (*FSA) Info

func (a *FSA) Info(d uint32) string

Info returns the stored info string for the given data pointer.

func (*FSA) Initial

func (a *FSA) Initial() uint32

Initial returns the inital state for this CFSA.

type NDFANode

type NDFANode interface {
	Final() string             // Holds a non-empty string for final nodes.
	Targets(c byte) []NDFANode // Targets for the given transitions.
	ID() uint64                // The unique id for the node.
}

Node represents a state in a NDFA. They can be used to construct an deterministic automaton and from there be converted into a FSA instance.

Final states should return a non-empty string in their implementation of the Final() method. If a node has no target transition, nil should be returned.

type Statistics

type Statistics struct {
	Words    int // Number of words.
	FreeCell int // Position of the first free cell.
	Cells    int // Number of cells.
	States   int // Number of state cells.
	Empty    int // Number of empty cells.
}

Statistics holds various metrics of the builder.