graph

Documentation

Index

• Constants
• func WriteDotGraph(out io.Writer, start *Node, id string)
• type Asserts
• type Edge
• type Expression
• type Node
  • func BuildDfa(nfa []*Node) []*Node
  • func BuildNfa[E Expression](expressions []E) ([]*Node, error)
  • func (n *Node) GetEdgeKind(kind int) []*Edge

Constants

const (
	KNil = iota
	KRune
	KClass
	KAssert
	KWild
)

Functions

func WriteDotGraph

func WriteDotGraph(out io.Writer, start *Node, id string)

WriteDotGraph Print a graph in DOT format given the start node.

$ dot -Tps input.dot -o output.ps

Types

type Asserts

type Asserts = uint64

const (
	AStartText Asserts = 1 << iota
	AEndText
	AStartLine
	AEndLine
	AWordBoundary
	ANoWordBoundary
)

The following are exact copy of the asserts in lexer.go.

type Edge

type Edge struct {
	Kind int     // Nil/Rune/Class/Assert/Wild.
	Dst  *Node   // Destination node.
	R    rune    // Rune for rune edges.
	A    Asserts // Asserts for assert edges.
	Lim  limits  // Pairs of limits for character class edges.
}

type Expression

type Expression interface {
	GetRegex() string
	GetId() int
}

type Node

type Node struct {
	E      []*Edge // Out-edges.
	Id     int     // Index number. Scoped to a family.
	Accept int     // True if this is an accepting state.
	Set    []int   // The NFA nodes represented by a DFA node.
}

func BuildDfa

func BuildDfa(nfa []*Node) []*Node

BuildDfa NFA -> DFA DFA: Deterministic Finite Automaton

func BuildNfa

func BuildNfa[E Expression](expressions []E) ([]*Node, error)

BuildNfa Regex -> NFA (Nondeterministic Finite Automaton) We cannot have our alphabet be all Unicode characters. Instead, we compute an alphabet for each regex:

1. Singles: we add single runes used in the regex: any rune not in a range. These are held in `singles`.

2. Ranges: entire ranges become elements of the alphabet. If ranges in the same expression overlap, we break them up into non-overlapping ranges. The generated code checks singles before ranges, so there's no need to break up a range if it contains a single. These are maintained in sorted order in `lim`.

3. Wild: we add an element representing all other runes.

e.g. the alphabet of /[0-9]*[Ee][2-5]*/ is singles: { E, e }, lim: { [0-1], [2-5], [6-9] } and the wild element.

func (*Node) GetEdgeKind

func (n *Node) GetEdgeKind(kind int) []*Edge