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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
package subex
import (
"main/walk"
)
// A state of execution for the transducer
type SubexState interface {
// Eat a datum and transition to any number of new states
eat(store Store, char walk.Datum) []SubexBranch
// Find accepting states reachable through epsilon transitions and return their outputs
accepting(store Store) [][]walk.Datum
}
// Try first, if it fails then try second
type SubexGroupState struct {
first, second SubexState
}
func (state SubexGroupState) eat(store Store, char walk.Datum) []SubexBranch {
otherStore := store.clone()
return append(state.first.eat(store, char), state.second.eat(otherStore, char)...)
}
func (state SubexGroupState) accepting(store Store) [][]walk.Datum {
return append(state.first.accepting(store), state.second.accepting(store)...)
}
// Run the match machine and store the output in a slot for later use
// Output nothing
type SubexStoreState struct {
match SubexState
slot rune
next SubexState
toStore []walk.Datum
}
func (state SubexStoreState) eat(store Store, char walk.Datum) (nextStates []SubexBranch) {
acceptedOutputs := state.match.accepting(store)
for _, acceptedOutput := range acceptedOutputs {
nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput))
nextStates = append(nextStates, state.next.eat(nextStore.clone(), char)...)
}
nextMatchStates := state.match.eat(store.clone(), char)
for _, matchState := range nextMatchStates {
nextStates = append(nextStates, SubexBranch {
state: SubexStoreState {
match: matchState.state,
slot: state.slot,
next: state.next,
toStore: walk.ConcatData(state.toStore, matchState.output),
},
output: nil,
store: store.clone(),
})
}
return nextStates
}
func (state SubexStoreState) accepting(store Store) (outputs [][]walk.Datum) {
acceptedOutputs := state.match.accepting(store)
for _, acceptedOutput := range acceptedOutputs {
nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput))
outputs = append(outputs, state.next.accepting(nextStore)...)
}
return outputs
}
// Don't read in anything, just output the series of data and slots specified
type SubexOutputState struct {
content []TransducerOutput
next SubexState
}
// Given a store, return what is outputted by an epsilon transition from this state
func (state SubexOutputState) build(store Store) []walk.Datum {
var result []walk.Datum
for _, part := range state.content {
result = append(result, part.build(store)...)
}
return result
}
func (state SubexOutputState) eat(store Store, char walk.Datum) []SubexBranch {
content := state.build(store)
nextStates := state.next.eat(store, char)
for i := range nextStates {
nextStates[i].output = walk.ConcatData(content, nextStates[i].output)
}
return nextStates
}
func (state SubexOutputState) accepting(store Store) [][]walk.Datum {
content := state.build(store)
outputs := state.next.accepting(store)
for i := range outputs {
outputs[i] = walk.ConcatData(content, outputs[i])
}
return outputs
}
// A final state, transitions to nothing but is accepting
type SubexNoneState struct {}
func (state SubexNoneState) eat(store Store, char walk.Datum) []SubexBranch {
return nil
}
func (state SubexNoneState) accepting(store Store) [][]walk.Datum {
return [][]walk.Datum{nil}
}
// Read in a specific datum and output it
// TODO rename to better reflect datum instead of rune
type SubexCopyRuneState struct {
rune walk.Datum
next SubexState
}
func (state SubexCopyRuneState) eat(store Store, char walk.Datum) []SubexBranch {
// TODO can I compare Datum values with == ?
if char == state.rune {
return []SubexBranch{{
state: state.next,
output: []walk.Datum{char},
store: store,
}}
}
return nil
}
func (state SubexCopyRuneState) accepting(store Store) [][]walk.Datum {
return nil
}
// Read in any datum and output it
type SubexCopyAnyState struct {
next SubexState
}
func (state SubexCopyAnyState) eat(store Store, char walk.Datum) []SubexBranch {
return []SubexBranch{{
state: state.next,
output: []walk.Datum{char},
store: store,
}}
}
func (state SubexCopyAnyState) accepting(store Store) [][]walk.Datum {
return nil
}
// Read in a datum and apply a map to generate a datum to output
// If the input isn't in the map transition to nothing
type SubexRangeState struct {
parts map[walk.Datum]walk.Datum
next SubexState
}
func (state SubexRangeState) eat(store Store, char walk.Datum) []SubexBranch {
out, exists := state.parts[char]
if !exists {
return nil
} else {
return []SubexBranch{{
state: state.next,
output: []walk.Datum{out},
store: store,
}}
}
}
func (state SubexRangeState) accepting(store Store) [][]walk.Datum {
return nil
}
|
