<- Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
path: root/main
diff options
context:
space:
mode:
Diffstat (limited to 'main')
-rw-r--r--main/main.go580
1 files changed, 0 insertions, 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]")