Suppress a report about conflicts resolved explicitly

5 files changed, 151 insertions, 48 deletions

diff --git a/README.md b/README.md
index 8027113..f73d2a6 100644
--- a/README.md
+++ b/README.md
@@ -75,7 +75,6 @@ Next, generate a parsing table using `vartan compile` command.
 
 ```sh
 $ vartan compile expr.vr -o expr.json
-16 conflicts
 ```
 
 ### 3. Debug
diff --git a/cmd/vartan/show.go b/cmd/vartan/show.go
index 04fc4e2..f6203f1 100644
--- a/cmd/vartan/show.go
+++ b/cmd/vartan/show.go
@@ -10,6 +10,7 @@ import (
 	"strings"
 	"text/template"
 
+	"github.com/nihei9/vartan/grammar"
 	"github.com/nihei9/vartan/spec"
 	"github.com/spf13/cobra"
 )
@@ -138,20 +139,64 @@ func writeDescription(w io.Writer, desc *spec.Description) error {
 		return desc.NonTerminals[sym].Name
 	}
 
+	termAssoc := func(sym int) string {
+		switch desc.Terminals[sym].Associativity {
+		case "l":
+			return "left"
+		case "r":
+			return "right"
+		default:
+			return "no"
+		}
+	}
+
+	prodAssoc := func(prod int) string {
+		switch desc.Productions[prod].Associativity {
+		case "l":
+			return "left"
+		case "r":
+			return "right"
+		default:
+			return "no"
+		}
+	}
+
 	fns := template.FuncMap{
 		"printConflictSummary": func(desc *spec.Description) string {
-			count := 0
+			var implicitlyResolvedCount int
+			var explicitlyResolvedCount int
 			for _, s := range desc.States {
-				count += len(s.SRConflict)
-				count += len(s.RRConflict)
+				for _, c := range s.SRConflict {
+					if c.ResolvedBy == grammar.ResolvedByShift.Int() {
+						implicitlyResolvedCount++
+					} else {
+						explicitlyResolvedCount++
+					}
+				}
+				for _, c := range s.RRConflict {
+					if c.ResolvedBy == grammar.ResolvedByProdOrder.Int() {
+						implicitlyResolvedCount++
+					} else {
+						explicitlyResolvedCount++
+					}
+				}
 			}
 
-			if count == 1 {
-				return "1 conflict was detected."
-			} else if count > 1 {
-				return fmt.Sprintf("%v conflicts were detected.", count)
+			var b strings.Builder
+			if implicitlyResolvedCount == 1 {
+				fmt.Fprintf(&b, "%v conflict occurred and resolved implicitly.\n", implicitlyResolvedCount)
+			} else if implicitlyResolvedCount > 1 {
+				fmt.Fprintf(&b, "%v conflicts occurred and resolved implicitly.\n", implicitlyResolvedCount)
+			}
+			if explicitlyResolvedCount == 1 {
+				fmt.Fprintf(&b, "%v conflict occurred and resolved explicitly.\n", explicitlyResolvedCount)
+			} else if explicitlyResolvedCount > 1 {
+				fmt.Fprintf(&b, "%v conflicts occurred and resolved explicitly.\n", explicitlyResolvedCount)
 			}
-			return "No conflict was detected."
+			if implicitlyResolvedCount == 0 && explicitlyResolvedCount == 0 {
+				fmt.Fprintf(&b, "No conflict")
+			}
+			return b.String()
 		},
 		"printTerminal": func(term spec.Terminal) string {
 			var prec string
@@ -249,10 +294,36 @@ func writeDescription(w io.Writer, desc *spec.Description) error {
 			case sr.AdoptedProduction != nil:
 				adopted = fmt.Sprintf("reduce %v", *sr.AdoptedProduction)
 			}
-			return fmt.Sprintf("shift/reduce conflict (shift %v, reduce %v) on %v: %v adopted", sr.State, sr.Production, termName(sr.Symbol), adopted)
+			var resolvedBy string
+			switch sr.ResolvedBy {
+			case grammar.ResolvedByPrec.Int():
+				if sr.AdoptedState != nil {
+					resolvedBy = fmt.Sprintf("symbol %v has higher precedence than production %v", termName(sr.Symbol), sr.Production)
+				} else {
+					resolvedBy = fmt.Sprintf("production %v has higher precedence than symbol %v", sr.Production, termName(sr.Symbol))
+				}
+			case grammar.ResolvedByAssoc.Int():
+				if sr.AdoptedState != nil {
+					resolvedBy = fmt.Sprintf("symbol %v and production %v has the same precedence, and symbol %v has %v associativity", termName(sr.Symbol), sr.Production, termName(sr.Symbol), termAssoc(sr.Symbol))
+				} else {
+					resolvedBy = fmt.Sprintf("production %v and symbol %v has the same precedence, and production %v has %v associativity", sr.Production, termName(sr.Symbol), sr.Production, prodAssoc(sr.Production))
+				}
+			case grammar.ResolvedByShift.Int():
+				resolvedBy = fmt.Sprintf("symbol %v and production %v don't define a precedence comparison (default rule)", sr.Symbol, sr.Production)
+			default:
+				resolvedBy = "?" // This is a bug.
+			}
+			return fmt.Sprintf("shift/reduce conflict (shift %v, reduce %v) on %v: %v adopted because %v", sr.State, sr.Production, termName(sr.Symbol), adopted, resolvedBy)
 		},
 		"printRRConflict": func(rr spec.RRConflict) string {
-			return fmt.Sprintf("reduce/reduce conflict (%v, %v) on %v: reduce %v adopted", rr.Production1, rr.Production2, termName(rr.Symbol), rr.AdoptedProduction)
+			var resolvedBy string
+			switch rr.ResolvedBy {
+			case grammar.ResolvedByProdOrder.Int():
+				resolvedBy = fmt.Sprintf("production %v and %v don't define a precedence comparison (default rule)", rr.Production1, rr.Production2)
+			default:
+				resolvedBy = "?" // This is a bug.
+			}
+			return fmt.Sprintf("reduce/reduce conflict (%v, %v) on %v: reduce %v adopted because %v", rr.Production1, rr.Production2, termName(rr.Symbol), rr.AdoptedProduction, resolvedBy)
 		},
 	}
 
diff --git a/grammar/grammar.go b/grammar/grammar.go
index 4e5b3b2..c996e36 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -1287,8 +1287,21 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
 			}
 		}
 
-		if len(b.conflicts) > 0 {
-			fmt.Fprintf(os.Stderr, "%v conflicts\n", len(b.conflicts))
+		var implicitlyResolvedCount int
+		for _, s := range desc.States {
+			for _, c := range s.SRConflict {
+				if c.ResolvedBy == ResolvedByShift.Int() {
+					implicitlyResolvedCount++
+				}
+			}
+			for _, c := range s.RRConflict {
+				if c.ResolvedBy == ResolvedByProdOrder.Int() {
+					implicitlyResolvedCount++
+				}
+			}
+		}
+		if implicitlyResolvedCount > 0 {
+			fmt.Fprintf(os.Stderr, "%v conflicts\n", implicitlyResolvedCount)
 		}
 	}
 
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index a908001..1e3930b 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -63,25 +63,40 @@ func (e goToEntry) describe() (GoToType, stateNum) {
 	return GoToTypeRegistered, stateNum(e)
 }
 
+type conflictResolutionMethod int
+
+func (m conflictResolutionMethod) Int() int {
+	return int(m)
+}
+
+const (
+	ResolvedByPrec      conflictResolutionMethod = 1
+	ResolvedByAssoc     conflictResolutionMethod = 2
+	ResolvedByShift     conflictResolutionMethod = 3
+	ResolvedByProdOrder conflictResolutionMethod = 4
+)
+
 type conflict interface {
 	conflict()
 }
 
 type shiftReduceConflict struct {
-	state     stateNum
-	sym       symbol
-	nextState stateNum
-	prodNum   productionNum
+	state      stateNum
+	sym        symbol
+	nextState  stateNum
+	prodNum    productionNum
+	resolvedBy conflictResolutionMethod
 }
 
 func (c *shiftReduceConflict) conflict() {
 }
 
 type reduceReduceConflict struct {
-	state    stateNum
-	sym      symbol
-	prodNum1 productionNum
-	prodNum2 productionNum
+	state      stateNum
+	sym        symbol
+	prodNum1   productionNum
+	prodNum2   productionNum
+	resolvedBy conflictResolutionMethod
 }
 
 func (c *reduceReduceConflict) conflict() {
@@ -218,21 +233,20 @@ func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym
 	if !act.isEmpty() {
 		ty, _, p := act.describe()
 		if ty == ActionTypeReduce {
+			act, method := b.resolveSRConflict(sym.num(), p)
 			b.conflicts = append(b.conflicts, &shiftReduceConflict{
-				state:     state,
-				sym:       sym,
-				nextState: nextState,
-				prodNum:   p,
+				state:      state,
+				sym:        sym,
+				nextState:  nextState,
+				prodNum:    p,
+				resolvedBy: method,
 			})
-
-			if b.resolveConflict(sym.num(), p) == ActionTypeShift {
+			if act == ActionTypeShift {
 				tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState))
 			}
-
 			return
 		}
 	}
-
 	tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState))
 }
 
@@ -250,50 +264,52 @@ func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sy
 			}
 
 			b.conflicts = append(b.conflicts, &reduceReduceConflict{
-				state:    state,
-				sym:      sym,
-				prodNum1: p,
-				prodNum2: prod,
+				state:      state,
+				sym:        sym,
+				prodNum1:   p,
+				prodNum2:   prod,
+				resolvedBy: ResolvedByProdOrder,
 			})
-
 			if p < prod {
 				tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(p))
 			} else {
 				tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod))
 			}
 		case ActionTypeShift:
+			act, method := b.resolveSRConflict(sym.num(), prod)
 			b.conflicts = append(b.conflicts, &shiftReduceConflict{
-				state:     state,
-				sym:       sym,
-				nextState: s,
-				prodNum:   prod,
+				state:      state,
+				sym:        sym,
+				nextState:  s,
+				prodNum:    prod,
+				resolvedBy: method,
 			})
-
-			if b.resolveConflict(sym.num(), prod) == ActionTypeReduce {
+			if act == ActionTypeReduce {
 				tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod))
 			}
 		}
-
 		return
 	}
-
 	tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod))
 }
 
-func (b *lrTableBuilder) resolveConflict(sym symbolNum, prod productionNum) ActionType {
+func (b *lrTableBuilder) resolveSRConflict(sym symbolNum, prod productionNum) (ActionType, conflictResolutionMethod) {
 	symPrec := b.precAndAssoc.terminalPrecedence(sym)
 	prodPrec := b.precAndAssoc.productionPredence(prod)
-	if symPrec < prodPrec {
-		return ActionTypeShift
+	if symPrec == 0 || prodPrec == 0 {
+		return ActionTypeShift, ResolvedByShift
 	}
 	if symPrec == prodPrec {
 		assoc := b.precAndAssoc.productionAssociativity(prod)
 		if assoc != assocTypeLeft {
-			return ActionTypeShift
+			return ActionTypeShift, ResolvedByAssoc
 		}
+		return ActionTypeReduce, ResolvedByAssoc
 	}
-
-	return ActionTypeReduce
+	if symPrec < prodPrec {
+		return ActionTypeShift, ResolvedByPrec
+	}
+	return ActionTypeReduce, ResolvedByPrec
 }
 
 func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec.Description, error) {
@@ -485,6 +501,7 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
 						Symbol:     c.sym.num().Int(),
 						State:      c.nextState.Int(),
 						Production: c.prodNum.Int(),
+						ResolvedBy: c.resolvedBy.Int(),
 					}
 
 					ty, s, p := tab.getAction(s.num, c.sym.num())
@@ -509,6 +526,7 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
 						Symbol:      c.sym.num().Int(),
 						Production1: c.prodNum1.Int(),
 						Production2: c.prodNum2.Int(),
+						ResolvedBy:  c.resolvedBy.Int(),
 					}
 
 					_, _, p := tab.getAction(s.num, c.sym.num())
diff --git a/spec/description.go b/spec/description.go
index ae56814..e82c509 100644
--- a/spec/description.go
+++ b/spec/description.go
@@ -44,6 +44,7 @@ type SRConflict struct {
 	Production        int  `json:"production"`
 	AdoptedState      *int `json:"adopted_state"`
 	AdoptedProduction *int `json:"adopted_production"`
+	ResolvedBy        int  `json:"resolved_by"`
 }
 
 type RRConflict struct {
@@ -51,6 +52,7 @@ type RRConflict struct {
 	Production1       int `json:"production_1"`
 	Production2       int `json:"production_2"`
 	AdoptedProduction int `json:"adopted_production"`
+	ResolvedBy        int `json:"resolved_by"`
 }
 
 type State struct {