-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.go
92 lines (80 loc) · 1.68 KB
/
graph.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package regex
import (
"strings"
"github.com/liyue201/gostl/ds/set"
)
// NFAGraph nfa graph
type NFAGraph struct {
start,
end *NFAState
}
// NewNFAGraph create nfa graph
func NewNFAGraph(start, end *NFAState) *NFAGraph {
return &NFAGraph{
start: start,
end: end,
}
}
// |
func (g *NFAGraph) addParallelGraph(graph *NFAGraph) {
start := NewNFAState()
end := NewNFAState()
start.AddNext(EPSILON, g.start)
start.AddNext(EPSILON, graph.start)
g.end.AddNext(EPSILON, end)
graph.end.AddNext(EPSILON, end)
g.start = start
g.end = end
}
//
func (g *NFAGraph) addSeriesGraph(graph *NFAGraph) {
g.end.AddNext(EPSILON, graph.start)
g.end = graph.end
}
// * 重复0-n次
func (g *NFAGraph) repeatStar() {
g.repeatPlus()
g.addSToE()
}
// ? 重复0次
func (g *NFAGraph) addSToE() {
g.start.AddNext(EPSILON, g.end)
}
// + 重复1-n次
func (g *NFAGraph) repeatPlus() {
start := NewNFAState()
end := NewNFAState()
start.AddNext(EPSILON, g.start)
g.end.AddNext(EPSILON, end)
g.end.AddNext(EPSILON, g.start)
g.start = start
g.end = end
}
// DFAGraph dfa graph
type DFAGraph struct {
start *DFAState
stateMap map[string]*DFAState
}
// NewDFAGraph create dfa graph
func NewDFAGraph(start *DFAState) *DFAGraph {
return &DFAGraph{
start: start,
stateMap: map[string]*DFAState{},
}
}
// Get state
func (g *DFAGraph) Get(states *set.Set) *DFAState {
var builder strings.Builder
for iter := states.Begin(); iter.IsValid(); iter.Next() {
builder.WriteByte('#')
builder.WriteRune(rune(iter.Value().(*NFAState).Id))
}
key := builder.String()
state, ok := g.stateMap[key]
if ok {
return state
}
dfaState := NewDFAState(key, states)
g.stateMap[key] = dfaState
return dfaState
}