Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DFA ¶
type DFA struct {
Start int // the starting state
Error int // the error state (should be 0)
Accepting machines.DFAAccepting // state-idx to match-id
Trans machines.DFATrans // the transition matrix
Matches [][]int // match-id to list of accepting states
// contains filtered or unexported fields
}
DFA is a Deterministic Finite-state Automaton
func Generate ¶
Generate a DFA from a regular expressions AST. The generated DFA is minimized during the generation process.
type LabeledAST ¶
type LabeledAST struct {
Root frontend.AST // root of the AST
Order []frontend.AST // post-order labeling of the all the nodes
Kids [][]int // a lookup table of location for each of the nodes children
Positions []int // a labeling of all the position nodes (Character/Range) in the AST.
Matches []int // the index (in Positions) of all the EOS nodes
// contains filtered or unexported fields
}
LabeledAST is a post-order labeled version of the AST. The root the node will be Order[len(Order)-1].
func Label ¶
func Label(ast frontend.AST) *LabeledAST
Label a tree and its "positions" (Character/Range nodes) in post-order notation.
func (*LabeledAST) First ¶
func (a *LabeledAST) First() (first [][]int)
First computes a look up table for each node in the tree (in post order, matching the Order member) indicating for the subtree rooted at each node which positions (leaf nodes indexes in the Positions slice) will appear at the beginning of a string matching that subtree.
func (*LabeledAST) Follow ¶
func (a *LabeledAST) Follow() (firstOfTree []int, follow []map[int]bool)
Follow computes look up tables for each Position (leaf node) in the tree which indicates what other Position could follow the current position in a matching string. It also computes what positions appear first in the tree.
func (*LabeledAST) Last ¶
func (a *LabeledAST) Last() (last [][]int)
Last computes a look up table for each node in the tree (in post order, matching the Order member) indicating for the subtree rooted at each node which positions (leaf nodes indexes in the Positions slice) will appear at the end of a string matching that subtree.
func (*LabeledAST) MatchesEmptyString ¶
func (a *LabeledAST) MatchesEmptyString() (nullable []bool)
MatchesEmptyString computes a look up table for each node in the tree (in post order, matching the Order member) on whether or not the subtree rooted in each node matches the empty string.
Source Files