CFG derivation tester

main.go

package main

import (
    "fmt"
    "strings"
)

func main() {
    // ! Edit grammar
    cfg := NewGrammar('S', map[byte]Rule{
        'S': {"", "SS", "aSb", "bSa"},
    })

    // ! Edit test cases
    cfg.TestDerivation("aaabbabba")
    cfg.TestDerivation("")
    cfg.TestDerivation("aaabbabb")
}

// ************************** TESTER SOURCE **************************

type Rule = []string
type Grammar struct {
    initialVariable byte
    rules           []*Rule
}

func NewGrammar(initialVariable byte, rules map[byte]Rule) (cfg Grammar) {
    cfg.initialVariable = initialVariable

    cfg.rules = make([]*Rule, 'Z'-'A'+1)
    for variable, rule := range rules {
        cfg.rules[variable-'A'] = &rule
    }

    return
}

func (cfg *Grammar) Get(variable byte) *Rule {
    if variable < 'A' || variable > 'Z' {
        return nil
    }

    return cfg.rules[variable-'A']
}

func (cfg *Grammar) TestDerivation(test string) {
    displayTest := test
    if test == "" {
        displayTest = "<empty string>"
    }

    if cfg.CanDerive(test) {
        fmt.Println("Accept:", displayTest)
    } else {
        fmt.Println("Reject:", displayTest)
    }
}

func (cfg *Grammar) CanDerive(test string) bool {
    derived := make([]byte, len(test))
    toDerive := fmt.Sprintf("%c", cfg.initialVariable)
    return cfg.canDerive(&test, &derived, 0, toDerive, 15)
}

func (cfg *Grammar) canDerive(
    test *string,
    derived *[]byte,
    derivedOffset int,
    toDerive string,
    depth int,
) bool {
    if depth < 0 {
        // Too many recursive calls
        return false
    }

    alreadyDerived := string(*derived)[:derivedOffset]
    if !strings.HasPrefix(*test, alreadyDerived) {
        // The string I'm deriving starts with "alreadyDerived", but "test" doesn't
        return false
    }

    // Copy terminal variables until found
    nonTerminalVarFoundAtIndex := -1
    for i, variable := range toDerive {
        if cfg.Get(byte(variable)) == nil {
            // It's a terminal variable, copy if there is enough space
            if derivedOffset == len(*test) {
                // No more space left and the string has not ended yet
                return false
            }

            (*derived)[derivedOffset] = byte(variable)
            derivedOffset++
        } else {
            // Non terminal variable found!
            nonTerminalVarFoundAtIndex = i
            break
        }
    }

    if nonTerminalVarFoundAtIndex >= 0 {
        // Must derive a non terminal variable
        for _, rule := range *cfg.Get(toDerive[nonTerminalVarFoundAtIndex]) {
            // Apply this rule and keep going
            nextToDerive := rule + toDerive[nonTerminalVarFoundAtIndex+1:]
            if cfg.canDerive(test, derived, derivedOffset, nextToDerive, depth-1) {
                // Propagate acceptance!
                return true
            }
        }

        // No branch accepted, refuse
        return false
    } else {
        // Derivation has ended
        return derivedOffset == len(*test) && string(*derived) == *test
    }
}