Write a description file

The description file describes a LR(0) item set and conflicts (if any).

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)
 		}