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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
package subex
import (
"main/walk"
)
// A state of execution for the transducer
type SubexState interface {
// Eat a Atom and transition to any number of new states
eat(store Store, char walk.Atom) []SubexBranch
// Find accepting states reachable through epsilon transitions and return their outputs
accepting(store Store) [][]walk.Atom
}
// Try first, if it fails then try second
type SubexGroupState struct {
first, second SubexState
}
func (state SubexGroupState) eat(store Store, char walk.Atom) []SubexBranch {
otherStore := store.clone()
return append(state.first.eat(store, char), state.second.eat(otherStore, char)...)
}
func (state SubexGroupState) accepting(store Store) [][]walk.Atom {
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.Atom
}
func (state SubexStoreState) eat(store Store, char walk.Atom) (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.Atom) {
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
}
// A part of an output literal, either an Atom or a slot from which to load
type OutputContent interface {
// Given the current store, return the []Atom produced by the TransducerOutput
build(Store) []walk.Atom
}
// An OutputContent which is just an Atom literal
type OutputAtomLiteral struct {
atom walk.Atom
}
func (replacement OutputAtomLiteral) build(store Store) []walk.Atom {
return []walk.Atom{replacement.atom}
}
// An OutputContent which is a slot that is loaded from
type OutputLoad struct {
slot rune
}
func (replacement OutputLoad) build(store Store) []walk.Atom {
return store[replacement.slot]
}
// Don't read in anything, just output the series of data and slots specified
type SubexOutputState struct {
content []OutputContent
next SubexState
}
// Given a store, return what is outputted by an epsilon transition from this state
func (state SubexOutputState) build(store Store) []walk.Atom {
var result []walk.Atom
for _, part := range state.content {
result = append(result, part.build(store)...)
}
return result
}
func (state SubexOutputState) eat(store Store, char walk.Atom) []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.Atom {
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.Atom) []SubexBranch {
return nil
}
func (state SubexNoneState) accepting(store Store) [][]walk.Atom {
return [][]walk.Atom{nil}
}
// Read in a specific Atom and output it
type SubexCopyAtomState struct {
atom walk.Atom
next SubexState
}
func (state SubexCopyAtomState) eat(store Store, char walk.Atom) []SubexBranch {
// TODO can I compare Atom values with == ?
if char == state.atom {
return []SubexBranch{{
state: state.next,
output: []walk.Atom{char},
store: store,
}}
}
return nil
}
func (state SubexCopyAtomState) accepting(store Store) [][]walk.Atom {
return nil
}
// Read in any Atom and output it
type SubexCopyAnyState struct {
next SubexState
}
func (state SubexCopyAnyState) eat(store Store, char walk.Atom) []SubexBranch {
return []SubexBranch{{
state: state.next,
output: []walk.Atom{char},
store: store,
}}
}
func (state SubexCopyAnyState) accepting(store Store) [][]walk.Atom {
return nil
}
// Read in an Atom and apply a map to generate an Atom to output
// If the input isn't in the map transition to nothing
type SubexRangeState struct {
parts map[walk.Atom]walk.Atom
next SubexState
}
func (state SubexRangeState) eat(store Store, char walk.Atom) []SubexBranch {
out, exists := state.parts[char]
if !exists {
return nil
} else {
return []SubexBranch{{
state: state.next,
output: []walk.Atom{out},
store: store,
}}
}
}
func (state SubexRangeState) accepting(store Store) [][]walk.Atom {
return nil
}
|
