Last active
January 7, 2023 09:51
-
-
Save simonesestito/96b0abd49486bb5028cb038334cef6f1 to your computer and use it in GitHub Desktop.
CFG derivation tester
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment