-
Notifications
You must be signed in to change notification settings - Fork 0
/
sequitur.go
112 lines (98 loc) · 2.1 KB
/
sequitur.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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
package fuzzgun
import (
"fmt"
"reflect"
"strings"
)
type sequitur struct {
allRules []string
finalRules []string
idx int
}
type symbol struct {
s string
typ int
}
func (s symbol) String() string {
if s.typ > 0 {
return fmt.Sprintf("nonterm[%s]", s.s)
}
return fmt.Sprintf("term[%s]", s.s)
}
type digram [2]symbol
func stringToCorpus(corpus ...string) (out [][]symbol) {
for _, c := range corpus {
var symbols []symbol
for _, a := range c {
symbols = append(symbols, symbol{s: string(a), typ: 1})
}
out = append(out, symbols)
}
return
}
func (seq *sequitur) parse(corpus [][]symbol) (out []symbol) {
rules := extractRules(corpus)
if len(rules) < 1 {
for _, symbols := range corpus {
out = append(out, compressTerminals(symbols)...)
}
return out
}
var newCorpus [][]symbol
for _, symbols := range corpus {
newSymbols := replaceWithRules(symbols, rules)
newCorpus = append(newCorpus, compressTerminals(newSymbols))
}
return seq.parse(newCorpus)
}
func replaceWithRules(symbols []symbol, rules map[digram]struct{}) (out []symbol) {
for i := 0; i < len(symbols); {
if i < len(symbols)-1 {
slice := symbols[i : i+2]
var d digram
copy(d[:], slice)
if _, ok := rules[d]; ok {
var s []string
s = append(s, d[0].s, d[1].s)
term := symbol{typ: 0, s: strings.Join(s, "")}
out = append(out, term)
i = i + 2
} else {
out = append(out, symbols[i])
i++
}
} else {
out = append(out, symbols[i])
i++
}
}
return
}
func extractRules(corpus [][]symbol) map[digram]struct{} {
digrams := make(map[digram]int)
rules := make(map[digram]struct{})
for _, symbols := range corpus {
for i := 0; i <= len(symbols)-2; i++ {
var d digram
copy(d[:], symbols[i:i+2])
digrams[d]++
}
for digram, count := range digrams {
if count > 1 {
rules[digram] = struct{}{}
}
}
}
return rules
}
func compressTerminals(arr []symbol) []symbol {
out := make([]symbol, 0)
for _, s := range arr {
if s.typ < 1 && len(out) > 0 && reflect.DeepEqual(s, out[len(out)-1]) {
continue
} else {
out = append(out, s)
}
}
return out
}