automata

package
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 11, 2022 License: MIT Imports: 15 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var ErrNotImplemented = errors.New("not implemented")
View Source 
var SupportedChars = []byte{}
View Source 
var UnicodeRange = []Interval{
	NewInterval(0, int(unicode.MaxRune)),
}

Functions

This section is empty.

Types

type DFA 

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

func (*DFA) Accept 

func (dfa *DFA) Accept(s string) (RegexID, bool)

func (*DFA) GetFinStates 

func (dfa *DFA) GetFinStates() *collection.Set[StateID]

func (*DFA) GetInitState 

func (dfa *DFA) GetInitState() StateID

func (*DFA) GetRegexID added in v0.4.0 

func (dfa *DFA) GetRegexID(sid StateID) RegexID

func (*DFA) GetStates 

func (dfa *DFA) GetStates() []StateID

func (*DFA) GetTransitionTable 

func (dfa *DFA) GetTransitionTable() *DFATransition

func (*DFA) LexerMinimize 

func (dfa *DFA) LexerMinimize() *DFA

func (DFA) ToDot 

func (dfa DFA) ToDot() (string, error)

type DFATransition 

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

func NewDFATransition 

func NewDFATransition() *DFATransition

func (*DFATransition) GetMap added in v0.4.0 

func (trans *DFATransition) GetMap(sid StateID) (map[Interval]StateID, bool)

func (*DFATransition) Set 

func (trans *DFATransition) Set(from StateID, intv Interval, to StateID)

type EpsilonTransition added in v0.4.0 

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

func NewEpsilonTransition added in v0.4.0 

func NewEpsilonTransition() EpsilonTransition

func (EpsilonTransition) Set added in v0.4.0 

func (t EpsilonTransition) Set(from, to StateID) EpsilonTransition

type ImdDFATransition added in v0.4.0 

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

func NewImdDFATransition added in v0.4.0 

func NewImdDFATransition() *ImdDFATransition

func (*ImdDFATransition) Set added in v0.4.0 

func (trans *ImdDFATransition) Set(from *StateSet, intv Interval, to *StateSet)

type ImdEpsilonTransition added in v0.4.0 

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

func NewImdEpsilonTransition added in v0.4.0 

func NewImdEpsilonTransition(size int, mp map[StateID]*StateSet) ImdEpsilonTransition

type ImdNFA 

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

func (*ImdNFA) Eclosure added in v0.4.0 

func (nfa *ImdNFA) Eclosure(sid StateID) *StateSet

func (*ImdNFA) SubsetConstruction added in v0.4.0 

func (nfa *ImdNFA) SubsetConstruction() (states *StateSetDict[StateID], trans *ImdDFATransition, initState *StateSet, finStates *StateSetDict[Nothing])

func (*ImdNFA) ToDFA 

func (nfa *ImdNFA) ToDFA() *DFA

func (ImdNFA) ToDot 

func (nfa ImdNFA) ToDot() (string, error)

type ImdNFATransition 

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

func NewImdNFATransition added in v0.4.0 

func NewImdNFATransition(mp map[StateID]map[Interval]*StateSet) ImdNFATransition

type Interval added in v0.4.0 

type Interval struct {
	L int
	R int
}

func Disjoin added in v0.4.0 

func Disjoin(intvs []Interval) []Interval

https://stackoverflow.com/a/25832898

func NewInterval added in v0.4.0 

func NewInterval(s, e int) Interval

func (Interval) Difference added in v0.4.0 

func (x Interval) Difference(y Interval) []Interval

func (Interval) Overlap added in v0.4.0 

func (x Interval) Overlap(y Interval) bool

type NFA 

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

func NewNFA 

func NewNFA(states *collection.Set[StateID], etrans EpsilonTransition, trans NFATransition, initStates *collection.Set[StateID], finStates *collection.Set[StateID]) *NFA

func (*NFA) Concat 

func (nfa *NFA) Concat(other *NFA) *NFA

func (*NFA) SetRegexID 

func (nfa *NFA) SetRegexID(rid RegexID) *NFA

func (*NFA) Star 

func (nfa *NFA) Star() *NFA

func (*NFA) Sum 

func (nfa *NFA) Sum(other *NFA) *NFA

func (NFA) ToDot 

func (nfa NFA) ToDot() (string, error)

func (*NFA) ToImdNFA added in v0.4.0 

func (nfa *NFA) ToImdNFA() *ImdNFA

type NFATransition 

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

func NewNFATransition added in v0.4.0 

func NewNFATransition() NFATransition

func (NFATransition) Set added in v0.4.0 

func (trans NFATransition) Set(from StateID, intv Interval, to StateID) NFATransition

type Nothing 

type Nothing struct{}

type RegexID 

type RegexID int

type Sha 

type Sha = [sha256.Size]byte

type State 

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

func NewState 

func NewState(id StateID) State

func (State) GetID 

func (st State) GetID() StateID

type StateID 

type StateID int

func NewStateID added in v0.4.0 

func NewStateID() StateID

type StateIDToRegexID added in v0.4.0 

type StateIDToRegexID map[StateID]RegexID

func NewStateIDToRegexID added in v0.4.0 

func NewStateIDToRegexID() StateIDToRegexID

func (StateIDToRegexID) Get added in v0.4.0 

func (mp StateIDToRegexID) Get(sid StateID) RegexID

func (StateIDToRegexID) Set added in v0.4.0 

func (mp StateIDToRegexID) Set(sid StateID, rid RegexID)

type StateSet 

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

func NewStateSet 

func NewStateSet(n int) *StateSet

func (*StateSet) Contains 

func (ss *StateSet) Contains(x StateID) bool

func (*StateSet) Copy 

func (ss *StateSet) Copy() *StateSet

func (*StateSet) Insert 

func (ss *StateSet) Insert(x StateID) *StateSet

func (*StateSet) Intersection 

func (ss *StateSet) Intersection(other *StateSet) *StateSet

func (*StateSet) IsAny 

func (ss *StateSet) IsAny() bool

func (*StateSet) IsEmpty 

func (ss *StateSet) IsEmpty() bool

func (*StateSet) Union 

func (ss *StateSet) Union(other *StateSet) *StateSet

type StateSetDict 

type StateSetDict[T any] struct {
	// contains filtered or unexported fields
}

func NewStateSetDict 

func NewStateSetDict[T any]() *StateSetDict[T]

func (*StateSetDict[T]) Contains 

func (d *StateSetDict[T]) Contains(ss *StateSet) bool

func (*StateSetDict[T]) Get 

func (d *StateSetDict[T]) Get(ss *StateSet) (T, bool)

func (*StateSetDict[T]) Set 

func (d *StateSetDict[T]) Set(ss *StateSet, v T) *StateSetDict[T]

func (*StateSetDict[T]) Size added in v0.4.0 

func (d *StateSetDict[T]) Size() int

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.