diff options
author | Ryo Nihei <nihei.dev@gmail.com> | 2021-07-22 02:19:11 +0900 |
---|---|---|
committer | Ryo Nihei <nihei.dev@gmail.com> | 2021-07-22 02:19:11 +0900 |
commit | 42cea3ead12d4f64c03aca2892c37e0f6c8c4c90 (patch) | |
tree | 0c9839695aee5fe3b51b0e6e372162682eccd0f3 | |
parent | Print pattern strings of anonymous pattern on conflict messages (diff) | |
download | urubu-42cea3ead12d4f64c03aca2892c37e0f6c8c4c90.tar.gz urubu-42cea3ead12d4f64c03aca2892c37e0f6c8c4c90.tar.xz |
Write a description file
The description file describes a LR(0) item set and conflicts (if any).
-rw-r--r-- | cmd/vartan/compile.go | 15 | ||||
-rw-r--r-- | driver/parser_test.go | 6 | ||||
-rw-r--r-- | grammar/first_test.go | 6 | ||||
-rw-r--r-- | grammar/follow_test.go | 6 | ||||
-rw-r--r-- | grammar/grammar.go | 38 | ||||
-rw-r--r-- | grammar/lr0_item_test.go | 6 | ||||
-rw-r--r-- | grammar/slr.go | 152 | ||||
-rw-r--r-- | grammar/slr_test.go | 6 |
8 files changed, 209 insertions, 26 deletions
diff --git a/cmd/vartan/compile.go b/cmd/vartan/compile.go index 354637b..3753cd0 100644 --- a/cmd/vartan/compile.go +++ b/cmd/vartan/compile.go @@ -6,6 +6,7 @@ import ( "io/ioutil" "os" "path/filepath" + "strings" verr "github.com/nihei9/vartan/error" "github.com/nihei9/vartan/grammar" @@ -94,7 +95,13 @@ func runCompile(cmd *cobra.Command, args []string) (retErr error) { return err } - cgram, err := grammar.Compile(gram) + var descFileName string + { + _, grmFileName := filepath.Split(grmPath) + descFileName = fmt.Sprintf("%v.desc", strings.TrimSuffix(grmFileName, ".vr")) + } + + cgram, err := grammar.Compile(gram, grammar.EnableDescription(descFileName)) if err != nil { return err } @@ -119,8 +126,10 @@ func readGrammar(path string) (grm *grammar.Grammar, retErr error) { return nil, err } - var b grammar.GrammarBuilder - return b.Build(ast) + b := grammar.GrammarBuilder{ + AST: ast, + } + return b.Build() } func writeCompiledGrammar(cgram *spec.CompiledGrammar, path string) error { diff --git a/driver/parser_test.go b/driver/parser_test.go index c352e91..0bf8175 100644 --- a/driver/parser_test.go +++ b/driver/parser_test.go @@ -281,8 +281,10 @@ foo: "foo"; t.Fatal(err) } - var b grammar.GrammarBuilder - g, err := b.Build(ast) + b := grammar.GrammarBuilder{ + AST: ast, + } + g, err := b.Build() if tt.specErr { if err == nil { t.Fatal("an expected error didn't occur") diff --git a/grammar/first_test.go b/grammar/first_test.go index b2118c0..041f411 100644 --- a/grammar/first_test.go +++ b/grammar/first_test.go @@ -155,8 +155,10 @@ func genActualFirst(t *testing.T, src string) (*firstSet, *Grammar) { if err != nil { t.Fatal(err) } - var b GrammarBuilder - gram, err := b.Build(ast) + b := GrammarBuilder{ + AST: ast, + } + gram, err := b.Build() if err != nil { t.Fatal(err) } diff --git a/grammar/follow_test.go b/grammar/follow_test.go index 6ae8a9e..3500d14 100644 --- a/grammar/follow_test.go +++ b/grammar/follow_test.go @@ -136,8 +136,10 @@ func genActualFollow(t *testing.T, src string) (*followSet, *Grammar) { if err != nil { t.Fatal(err) } - var b GrammarBuilder - gram, err := b.Build(ast) + b := GrammarBuilder{ + AST: ast, + } + gram, err := b.Build() if err != nil { t.Fatal(err) } diff --git a/grammar/grammar.go b/grammar/grammar.go index 353beef..7cd2409 100644 --- a/grammar/grammar.go +++ b/grammar/grammar.go @@ -2,6 +2,7 @@ package grammar import ( "fmt" + "os" mlcompiler "github.com/nihei9/maleeni/compiler" mlspec "github.com/nihei9/maleeni/spec" @@ -25,18 +26,18 @@ type Grammar struct { } type GrammarBuilder struct { + AST *spec.RootNode + errs verr.SpecErrors } -func (b *GrammarBuilder) Build(root *spec.RootNode) (*Grammar, error) { - b.errs = nil - - symTabAndLexSpec, err := b.genSymbolTableAndLexSpec(root) +func (b *GrammarBuilder) Build() (*Grammar, error) { + symTabAndLexSpec, err := b.genSymbolTableAndLexSpec(b.AST) if err != nil { return nil, err } - prodsAndActs, err := b.genProductionsAndActions(root, symTabAndLexSpec) + prodsAndActs, err := b.genProductionsAndActions(b.AST, symTabAndLexSpec) if err != nil { return nil, err } @@ -428,7 +429,24 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd }, nil } -func Compile(gram *Grammar) (*spec.CompiledGrammar, error) { +type compileConfig struct { + descriptionFileName string +} + +type compileOption func(config *compileConfig) + +func EnableDescription(fileName string) compileOption { + return func(config *compileConfig) { + config.descriptionFileName = fileName + } +} + +func Compile(gram *Grammar, opts ...compileOption) (*spec.CompiledGrammar, error) { + config := &compileConfig{} + for _, opt := range opts { + opt(config) + } + lexSpec, err := mlcompiler.Compile(gram.lexSpec, mlcompiler.CompressionLevel(mlcompiler.CompressionLevelMax)) if err != nil { return nil, err @@ -503,6 +521,14 @@ func Compile(gram *Grammar) (*spec.CompiledGrammar, error) { sym2AnonPat: gram.sym2AnonPat, } tab, err := slr.build() + if config.descriptionFileName != "" { + f, err := os.OpenFile(config.descriptionFileName, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644) + if err != nil { + return nil, err + } + defer f.Close() + slr.writeDescription(f) + } if err != nil { return nil, err } diff --git a/grammar/lr0_item_test.go b/grammar/lr0_item_test.go index 9a0628a..78e9f3b 100644 --- a/grammar/lr0_item_test.go +++ b/grammar/lr0_item_test.go @@ -33,8 +33,10 @@ id: "[A-Za-z_][0-9A-Za-z_]*"; if err != nil { t.Fatal(err) } - var b GrammarBuilder - gram, err := b.Build(ast) + b := GrammarBuilder{ + AST: ast, + } + gram, err := b.Build() if err != nil { t.Fatal(err) } diff --git a/grammar/slr.go b/grammar/slr.go index 221bf8f..870e84f 100644 --- a/grammar/slr.go +++ b/grammar/slr.go @@ -2,6 +2,7 @@ package grammar import ( "fmt" + "io" "strings" ) @@ -171,6 +172,8 @@ type slrTableBuilder struct { nonTermCount int symTab *symbolTable sym2AnonPat map[symbol]string + + conflicts []conflict } func (b *slrTableBuilder) build() (*ParsingTable, error) { @@ -224,21 +227,156 @@ func (b *slrTableBuilder) build() (*ParsingTable, error) { } } } + + b.conflicts = conflicts + if len(conflicts) > 0 { - var msg strings.Builder - for _, conflict := range conflicts { - fmt.Fprintf(&msg, "\n") + return nil, fmt.Errorf("%v conflicts", len(conflicts)) + } + + return ptab, nil +} + +func (b *slrTableBuilder) writeDescription(w io.Writer) { + conflicts := map[stateNum][]conflict{} + for _, con := range b.conflicts { + switch c := con.(type) { + case *shiftReduceConflict: + conflicts[c.state] = append(conflicts[c.state], c) + case *reduceReduceConflict: + conflicts[c.state] = append(conflicts[c.state], c) + } + } + + fmt.Fprintf(w, "# Conflicts\n\n") + + if len(b.conflicts) > 0 { + fmt.Fprintf(w, "%v conflics:\n\n", len(b.conflicts)) + + for _, conflict := range b.conflicts { switch c := conflict.(type) { case *shiftReduceConflict: - fmt.Fprintf(&msg, "%v: shift/reduce conflict (shift %v, reduce %v) on %v", c.state, c.nextState, c.prodNum, b.symbolToText(c.sym)) + fmt.Fprintf(w, "%v: shift/reduce conflict (shift %v, reduce %v) on %v\n", c.state, c.nextState, c.prodNum, b.symbolToText(c.sym)) case *reduceReduceConflict: - fmt.Fprintf(&msg, "%v: reduce/reduce conflict (reduce %v and %v) on %v", c.state, c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) + fmt.Fprintf(w, "%v: reduce/reduce conflict (reduce %v and %v) on %v\n", c.state, c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) } } - return nil, fmt.Errorf("%v conflicts:%v", len(conflicts), msg.String()) + fmt.Fprintf(w, "\n") + } else { + fmt.Fprintf(w, "no conflicts\n\n") } - return ptab, nil + fmt.Fprintf(w, "# Productions\n\n") + + fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions())) + + for _, prod := range b.prods.getAllProductions() { + fmt.Fprintf(w, "%4v %v\n", prod.num, b.productionToString(prod, -1)) + } + + fmt.Fprintf(w, "\n# States\n\n") + + fmt.Fprintf(w, "%v states:\n\n", len(b.automaton.states)) + + for _, state := range b.automaton.states { + fmt.Fprintf(w, "state %v\n", state.num) + for _, item := range state.items { + prod, ok := b.prods.findByID(item.prod) + if !ok { + fmt.Fprintf(w, "<production not found>\n") + continue + } + fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot)) + } + + fmt.Fprintf(w, "\n") + + var shiftRecs []string + var reduceRecs []string + var gotoRecs []string + var accRec string + { + for sym, kID := range state.next { + nextState := b.automaton.states[kID] + if sym.isTerminal() { + shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, b.symbolToText(sym))) + } else { + gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, b.symbolToText(sym))) + } + } + + for prodID := range state.reducible { + prod, ok := b.prods.findByID(prodID) + if !ok { + reduceRecs = append(reduceRecs, "<production not found>") + continue + } + if prod.lhs.isStart() { + accRec = "accept on <EOF>" + continue + } + flw, err := b.follow.find(prod.lhs) + if err != nil { + reduceRecs = append(reduceRecs, fmt.Sprintf("%v", err)) + continue + } + for sym := range flw.symbols { + reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, b.symbolToText(sym))) + } + if flw.eof { + reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on <EOF>", prod.num)) + } + } + } + + if len(shiftRecs) > 0 || len(reduceRecs) > 0 { + for _, rec := range shiftRecs { + fmt.Fprintf(w, " %v\n", rec) + } + for _, rec := range reduceRecs { + fmt.Fprintf(w, " %v\n", rec) + } + fmt.Fprintf(w, "\n") + } + if len(gotoRecs) > 0 { + for _, rec := range gotoRecs { + fmt.Fprintf(w, " %v\n", rec) + } + fmt.Fprintf(w, "\n") + } + if accRec != "" { + fmt.Fprintf(w, " %v\n\n", accRec) + } + + cons, ok := conflicts[state.num] + if ok { + for _, con := range cons { + switch c := con.(type) { + case *shiftReduceConflict: + fmt.Fprintf(w, " shift/reduce conflict (shift %v, reduce %v) on %v\n", c.nextState, c.prodNum, b.symbolToText(c.sym)) + case *reduceReduceConflict: + fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) + } + } + fmt.Fprintf(w, "\n") + } + } +} + +func (b *slrTableBuilder) productionToString(prod *production, dot int) string { + var w strings.Builder + fmt.Fprintf(&w, "%v →", b.symbolToText(prod.lhs)) + for n, rhs := range prod.rhs { + if n == dot { + fmt.Fprintf(&w, " ・") + } + fmt.Fprintf(&w, " %v", b.symbolToText(rhs)) + } + if dot == len(prod.rhs) { + fmt.Fprintf(&w, " ・") + } + + return w.String() } func (b *slrTableBuilder) symbolToText(sym symbol) string { diff --git a/grammar/slr_test.go b/grammar/slr_test.go index 15f58c1..9723a0d 100644 --- a/grammar/slr_test.go +++ b/grammar/slr_test.go @@ -39,8 +39,10 @@ id: "[A-Za-z_][0-9A-Za-z_]*"; if err != nil { t.Fatal(err) } - var b GrammarBuilder - gram, err = b.Build(ast) + b := GrammarBuilder{ + AST: ast, + } + gram, err = b.Build() if err != nil { t.Fatal(err) } |