From a5a4db8283fda88c5bd42272de0258e5d134c5bd Mon Sep 17 00:00:00 2001 From: Charlie Stanton Date: Sun, 19 Feb 2023 09:13:00 +0000 Subject: Removes obsolete subex code from main/main.go --- main/main.go | 580 ----------------------------------------------------------- 1 file changed, 580 deletions(-) diff --git a/main/main.go b/main/main.go index 3a701ed..46b83e7 100644 --- a/main/main.go +++ b/main/main.go @@ -4,8 +4,6 @@ import ( "os" "bufio" "fmt" - "strings" - "unicode/utf8" "main/subex" ) @@ -40,584 +38,6 @@ type ProgramState struct { program []Command } -//const eof rune = -1 -type RuneReader struct { - input string - pos, width int -} -func (l *RuneReader) next() rune { - if l.pos >= len(l.input) { - l.width = 0 - return eof - } - var r rune - r, l.width = utf8.DecodeRuneInString(l.input[l.pos:]) - l.pos += l.width - return r -} -func (l *RuneReader) accept(chars string) bool { - r := l.next() - for _, char := range chars { - if char == r { - return true - } - } - l.rewind() - return false -} -func (l *RuneReader) rewind() { - l.pos -= l.width -} - -func parseReplacement(l *RuneReader) (output []TransducerOutput) { - loop: for { - r := l.next() - switch r { - case eof: - panic("Missing closing \"") - case '"': - break loop - case '$': - slot := l.next() - if slot == eof { - panic("Missing slot character") - } - output = append(output, TransducerReplacementLoad(slot)) - default: - output = append(output, TransducerReplacementRune(r)) - } - } - return output -} - -func parseRegex(l *RuneReader, minPower int) RegexAST { - var lhs RegexAST - r := l.next() - switch r { - case eof: - return nil - case ')', '*', '-', '|': - l.rewind() - return nil - case '(': - lhs = parseRegex(l, 0) - if !l.accept(")") { - panic("Missing matching )") - } - case '.': - lhs = RegexASTAny{} - default: - lhs = RegexASTRune(r) - } - loop: for { - if minPower <= 0 { - next := parseRegex(l, 1) - if next != nil { - lhs = RegexASTConcat{lhs, next} - continue loop - } - } - r := l.next() - switch { - case r == '*' && minPower <= 4: - lhs = RegexASTMaximise{lhs} - case r == '-' && minPower <= 4: - lhs = RegexASTMinimise{lhs} - case r == '|' && minPower <= 2: - rhs := parseRegex(l, 3) - if rhs == nil { - panic("Missing regex after |") - } - lhs = RegexASTOr{lhs, rhs} - default: - l.rewind() - break loop - } - } - return lhs -} - -func parseSubex(l *RuneReader, minPower int) TransducerAST { - var lhs TransducerAST - r := l.next() - switch r { - case eof: - return nil - case '(': - lhs = parseSubex(l, 0) - if !l.accept(")") { - panic("Missing matching )") - } - case ')', '*', '-', '|': - l.rewind() - return nil - case '$': - slot := l.next() - if slot == eof { - panic("Missing slot character") - } - match := parseRegex(l, 100) - if match == nil { - panic("Missing regex for store") - } - lhs = TransducerASTStore{ - match: match, - slot: slot, - } - case '"': - replacement := parseReplacement(l) - lhs = TransducerASTOutput{replacement} - case '.': - lhs = TransducerASTCopyAny{} - default: - lhs = TransducerASTCopyRune(r) - } - loop: for { - if minPower <= 0 { - next := parseSubex(l, 1) - if next != nil { - lhs = TransducerASTConcat{lhs, next} - continue loop - } - } - r := l.next() - switch { - case r == '*' && minPower <= 4: - lhs = TransducerASTMaximise{lhs} - case r == '-' && minPower <= 4: - lhs = TransducerASTMinimise{lhs} - case r == '|' && minPower <= 2: - rhs := parseSubex(l, 3) - if rhs == nil { - panic("Missing subex after |") - } - lhs = TransducerASTOr{lhs, rhs} - default: - l.rewind() - break loop - } - } - return lhs -} - -func parse(input string) TransducerAST { - l := RuneReader { - input: input, - pos: 0, - width: 0, - } - return parseSubex(&l, 0) -} - -type TransducerOutput interface { - build(Store) string -} - -type TransducerReplacementRune rune -func (replacement TransducerReplacementRune) build(store Store) string { - return string(replacement) -} - -type TransducerReplacementLoad rune -func (replacement TransducerReplacementLoad) build(store Store) string { - return store[rune(replacement)] -} - -type RegexState interface { - eat(char rune) []RegexState - accepting() bool -} - -type RegexNoneState struct {} -func (state RegexNoneState) eat(char rune) []RegexState { - return nil -} -func (state RegexNoneState) accepting() bool { - return true -} - -type RegexAnyState struct { - next RegexState -} -func (state RegexAnyState) eat(char rune) []RegexState { - return []RegexState{state.next} -} -func (state RegexAnyState) accepting() bool { - return false -} - -type RegexRuneState struct { - rune rune - next RegexState -} -func (state RegexRuneState) eat(char rune) []RegexState { - if char == state.rune { - return []RegexState{state.next} - } - return nil -} -func (state RegexRuneState) accepting() bool { - return false -} - -type RegexGroupState struct { - first, second RegexState -} -func (state RegexGroupState) eat(char rune) []RegexState { - return append(state.first.eat(char), state.second.eat(char)...) -} -func (state RegexGroupState) accepting() bool { - return state.first.accepting() || state.second.accepting() -} - -type RegexAST interface { - compileWith(next RegexState) RegexState -} - -type RegexASTRune rune -func (ast RegexASTRune) compileWith(next RegexState) RegexState { - return RegexRuneState{ - rune: rune(ast), - next: next, - } -} -func (ast RegexASTRune) String() string { - return string(rune(ast)) -} - -type RegexASTAny struct {} -func (ast RegexASTAny) compileWith(next RegexState) RegexState { - return RegexAnyState{next} -} -func (ast RegexASTAny) String() string { - return "." -} - -type RegexASTConcat struct { - first, second RegexAST -} -func (ast RegexASTConcat) compileWith(next RegexState) RegexState { - return ast.first.compileWith(ast.second.compileWith(next)) -} -func (ast RegexASTConcat) String() string { - return fmt.Sprintf("Concat{%v, %v}", ast.first, ast.second) -} - -type RegexASTOr struct { - first, second RegexAST -} -func (ast RegexASTOr) compileWith(next RegexState) RegexState { - return RegexGroupState{ - ast.first.compileWith(next), - ast.second.compileWith(next), - } -} - -type RegexASTMaximise struct { - content RegexAST -} -func (ast RegexASTMaximise) compileWith(next RegexState) RegexState { - state := &RegexGroupState{ - nil, - next, - } - state.first = ast.content.compileWith(state) - return state -} - -type RegexASTMinimise struct { - content RegexAST -} -func (ast RegexASTMinimise) compileWith(next RegexState) RegexState { - state := &RegexGroupState{ - next, - nil, - } - state.second = ast.content.compileWith(state) - return state -} - -type Store map[rune]string -func (store Store) clone() Store { - newStore := make(Store) - for key, val := range store { - newStore[key] = val - } - return newStore -} - -type TransducerState interface { - eat(store Store, char rune) []TransducerStatePair - accepting(store Store) []string -} - -type TransducerGroupState struct { - first, second TransducerState -} -func (state TransducerGroupState) eat(store Store, char rune) []TransducerStatePair { - otherStore := store.clone() - return append(state.first.eat(store, char), state.second.eat(otherStore, char)...) -} -func (state TransducerGroupState) accepting(store Store) []string { - return append(state.first.accepting(store), state.second.accepting(store)...) -} - -type TransducerStoreState struct { - match RegexState - slot rune - next TransducerState - input string -} -func (state TransducerStoreState) eat(store Store, char rune) []TransducerStatePair { - var nextStates []TransducerStatePair - if state.match.accepting() { - store[state.slot] = state.input - nextStates = state.next.eat(store, char) - } - nextRegexStates := state.match.eat(char) - for _, regexState := range nextRegexStates { - nextStates = append(nextStates, TransducerStatePair { - state: TransducerStoreState { - match: regexState, - slot: state.slot, - next: state.next, - input: state.input + string(char), - }, - output: "", - store: store.clone(), - }) - } - return nextStates -} -func (state TransducerStoreState) accepting(store Store) []string { - if state.match.accepting() { - return state.next.accepting(store) - } - return nil -} - -type TransducerOutputState struct { - content []TransducerOutput - next TransducerState -} -func (state TransducerOutputState) build(store Store) string { - var builder strings.Builder - for _, part := range state.content { - builder.WriteString(part.build(store)) - } - return builder.String() -} -func (state TransducerOutputState) eat(store Store, char rune) []TransducerStatePair { - content := state.build(store) - nextStates := state.next.eat(store, char) - for i := range nextStates { - nextStates[i].output = content + nextStates[i].output - } - return nextStates -} -func (state TransducerOutputState) accepting(store Store) []string { - content := state.build(store) - outputs := state.next.accepting(store) - for i := range outputs { - outputs[i] = content + outputs[i] - } - return outputs -} - -type TransducerNoneState struct {} -func (state TransducerNoneState) eat(store Store, char rune) []TransducerStatePair { - return nil -} -func (state TransducerNoneState) accepting(store Store) []string { - return []string{""} -} - -type TransducerCopyRuneState struct { - rune rune - next TransducerState -} -func (state TransducerCopyRuneState) eat(store Store, char rune) []TransducerStatePair { - if char == state.rune { - return []TransducerStatePair{{ - state: state.next, - output: string(char), - store: store, - }} - } - return nil -} -func (state TransducerCopyRuneState) accepting(store Store) []string { - return nil -} - -type TransducerCopyAnyState struct { - next TransducerState -} -func (state TransducerCopyAnyState) eat(store Store, char rune) []TransducerStatePair { - return []TransducerStatePair{{ - state: state.next, - output: string(char), - store: store, - }} -} -func (state TransducerCopyAnyState) accepting(store Store) []string { - return nil -} - -type TransducerAST interface { - compileWithNext(next TransducerState) TransducerState -} - -type TransducerASTConcat struct { - first, second TransducerAST -} -func (ast TransducerASTConcat) compileWithNext(next TransducerState) TransducerState { - return ast.first.compileWithNext(ast.second.compileWithNext(next)) -} -func (ast TransducerASTConcat) String() string { - return fmt.Sprintf("(%v)(%v)", ast.first, ast.second) -} - -type TransducerASTStore struct { - match RegexAST - slot rune -} -func (ast TransducerASTStore) compileWithNext(next TransducerState) TransducerState { - return TransducerStoreState { - match: ast.match.compileWith(RegexNoneState{}), - slot: ast.slot, - next: next, - } -} -func (ast TransducerASTStore) String() string { - return fmt.Sprintf("$%c(%v)", ast.slot, ast.match) -} - -type TransducerASTOr struct { - first, second TransducerAST -} -func (ast TransducerASTOr) compileWithNext(next TransducerState) TransducerState { - return TransducerGroupState { - ast.first.compileWithNext(next), - ast.second.compileWithNext(next), - } -} - -type TransducerASTMaximise struct { - content TransducerAST -} -func (ast TransducerASTMaximise) compileWithNext(next TransducerState) TransducerState { - state := &TransducerGroupState { - nil, - next, - } - state.first = ast.content.compileWithNext(state) - return state -} -func (ast TransducerASTMaximise) String() string { - return fmt.Sprintf("(%v)*", ast.content) -} - -type TransducerASTMinimise struct { - content TransducerAST -} -func (ast TransducerASTMinimise) compileWithNext(next TransducerState) TransducerState { - state := &TransducerGroupState { - next, - nil, - } - state.second = ast.content.compileWithNext(state) - return state -} -func (ast TransducerASTMinimise) String() string { - return fmt.Sprintf("(%v)-", ast.content) -} - -type TransducerASTRepeat struct { - content TransducerAST - min, max int -} -func (ast TransducerASTRepeat) compileWithNext(next TransducerState) TransducerState { - for i := ast.min; i < ast.max; i += 1 { - next = TransducerGroupState { - ast.content.compileWithNext(next), - next, - } - } - for i := 0; i < ast.min; i += 1 { - next = ast.content.compileWithNext(next) - } - return next -} - -type TransducerASTCopyRune rune -func (ast TransducerASTCopyRune) compileWithNext(next TransducerState) TransducerState { - return TransducerCopyRuneState{ - rune: rune(ast), - next: next, - } -} - -type TransducerASTCopyAny struct {} -func (ast TransducerASTCopyAny) compileWithNext(next TransducerState) TransducerState { - return TransducerCopyAnyState{next} -} -func (ast TransducerASTCopyAny) String() string { - return "." -} - -type TransducerASTOutput struct { - replacement []TransducerOutput -} -func (ast TransducerASTOutput) compileWithNext(next TransducerState) TransducerState { - return TransducerOutputState{ - content: ast.replacement, - next: next, - } -} - -func compileTransducer(transducerAst TransducerAST) TransducerState { - return transducerAst.compileWithNext(TransducerNoneState{}) -} - -type TransducerStatePair struct { - store Store - state TransducerState - output string -} -func (pair TransducerStatePair) eat(char rune) []TransducerStatePair { - states := pair.state.eat(pair.store, char) - for i := range states { - states[i].output = pair.output + states[i].output - } - return states -} -func (pair TransducerStatePair) accepting() []string { - return pair.state.accepting(pair.store) -} - -func runTransducer(transducer TransducerState, input string) (output string, err bool) { - states := []TransducerStatePair{{ - state: transducer, - output: "", - store: make(Store), - }} - for _, char := range input { - var newStates []TransducerStatePair - for _, state := range states { - newStates = append(newStates, state.eat(char)...) - } - states = newStates - } - for _, state := range states { - outputEnds := state.accepting() - for _, outputEnd := range outputEnds { - return state.output + outputEnd, false - } - } - return "", true -} - func main() { if len(os.Args) != 3 { panic("Expected: stred [input] [subex]") -- cgit v1.2.3