Detect multiple conflicts

3 files changed, 124 insertions, 29 deletions

diff --git a/grammar/grammar.go b/grammar/grammar.go
index 00c894c..a43b133 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -487,7 +487,15 @@ func Compile(gram *Grammar) (*spec.CompiledGrammar, error) {
 		return nil, err
 	}
 
-	tab, err := genSLRParsingTable(lr0, gram.productionSet, followSet, len(terms), len(nonTerms))
+	slr := &slrTableBuilder{
+		automaton:    lr0,
+		prods:        gram.productionSet,
+		follow:       followSet,
+		termCount:    len(terms),
+		nonTermCount: len(nonTerms),
+		symTab:       gram.symbolTable,
+	}
+	tab, err := slr.build()
 	if err != nil {
 		return nil, err
 	}
diff --git a/grammar/slr.go b/grammar/slr.go
index a3ce803..3794ab7 100644
--- a/grammar/slr.go
+++ b/grammar/slr.go
@@ -2,6 +2,7 @@ package grammar
 
 import (
 	"fmt"
+	"strings"
 )
 
 type ActionType string
@@ -64,6 +65,35 @@ func (e goToEntry) describe() (GoToType, stateNum) {
 	return GoToTypeRegistered, stateNum(e)
 }
 
+type conflict interface {
+	conflict()
+}
+
+type shiftReduceConflict struct {
+	state     stateNum
+	sym       symbol
+	nextState stateNum
+	prodNum   productionNum
+}
+
+func (c *shiftReduceConflict) conflict() {
+}
+
+type reduceReduceConflict struct {
+	state    stateNum
+	sym      symbol
+	prodNum1 productionNum
+	prodNum2 productionNum
+}
+
+func (c *reduceReduceConflict) conflict() {
+}
+
+var (
+	_ conflict = &shiftReduceConflict{}
+	_ conflict = &reduceReduceConflict{}
+)
+
 type ParsingTable struct {
 	actionTable      []actionEntry
 	goToTable        []goToEntry
@@ -84,13 +114,18 @@ func (t *ParsingTable) getGoTo(state stateNum, sym symbolNum) (GoToType, stateNu
 	return t.goToTable[pos].describe()
 }
 
-func (t *ParsingTable) writeShiftAction(state stateNum, sym symbol, nextState stateNum) error {
+func (t *ParsingTable) writeShiftAction(state stateNum, sym symbol, nextState stateNum) conflict {
 	pos := state.Int()*t.terminalCount + sym.num().Int()
 	act := t.actionTable[pos]
 	if !act.isEmpty() {
-		ty, _, _ := act.describe()
+		ty, _, p := act.describe()
 		if ty == ActionTypeReduce {
-			return fmt.Errorf("shift/reduce conflict")
+			return &shiftReduceConflict{
+				state:     state,
+				sym:       sym,
+				nextState: nextState,
+				prodNum:   p,
+			}
 		}
 	}
 	t.actionTable[pos] = newShiftActionEntry(nextState)
@@ -98,15 +133,25 @@ func (t *ParsingTable) writeShiftAction(state stateNum, sym symbol, nextState st
 	return nil
 }
 
-func (t *ParsingTable) writeReduceAction(state stateNum, sym symbol, prod productionNum) error {
+func (t *ParsingTable) writeReduceAction(state stateNum, sym symbol, prod productionNum) conflict {
 	pos := state.Int()*t.terminalCount + sym.num().Int()
 	act := t.actionTable[pos]
 	if !act.isEmpty() {
-		ty, _, p := act.describe()
+		ty, s, p := act.describe()
 		if ty == ActionTypeReduce && p != prod {
-			return fmt.Errorf("reduce/reduce conflict")
+			return &reduceReduceConflict{
+				state:    state,
+				sym:      sym,
+				prodNum1: p,
+				prodNum2: prod,
+			}
+		}
+		return &shiftReduceConflict{
+			state:     state,
+			sym:       sym,
+			nextState: s,
+			prodNum:   prod,
 		}
-		return fmt.Errorf("shift/reduce conflict")
 	}
 	t.actionTable[pos] = newReduceActionEntry(prod)
 
@@ -118,27 +163,38 @@ func (t *ParsingTable) writeGoTo(state stateNum, sym symbol, nextState stateNum)
 	t.goToTable[pos] = newGoToEntry(nextState)
 }
 
-func genSLRParsingTable(automaton *lr0Automaton, prods *productionSet, follow *followSet, termCount, nonTermCount int) (*ParsingTable, error) {
+type slrTableBuilder struct {
+	automaton    *lr0Automaton
+	prods        *productionSet
+	follow       *followSet
+	termCount    int
+	nonTermCount int
+	symTab       *symbolTable
+}
+
+func (b *slrTableBuilder) build() (*ParsingTable, error) {
 	var ptab *ParsingTable
 	{
-		initialState := automaton.states[automaton.initialState]
+		initialState := b.automaton.states[b.automaton.initialState]
 		ptab = &ParsingTable{
-			actionTable:      make([]actionEntry, len(automaton.states)*termCount),
-			goToTable:        make([]goToEntry, len(automaton.states)*nonTermCount),
-			stateCount:       len(automaton.states),
-			terminalCount:    termCount,
-			nonTerminalCount: nonTermCount,
+			actionTable:      make([]actionEntry, len(b.automaton.states)*b.termCount),
+			goToTable:        make([]goToEntry, len(b.automaton.states)*b.nonTermCount),
+			stateCount:       len(b.automaton.states),
+			terminalCount:    b.termCount,
+			nonTerminalCount: b.nonTermCount,
 			InitialState:     initialState.num,
 		}
 	}
 
-	for _, state := range automaton.states {
+	var conflicts []conflict
+	for _, state := range b.automaton.states {
 		for sym, kID := range state.next {
-			nextState := automaton.states[kID]
+			nextState := b.automaton.states[kID]
 			if sym.isTerminal() {
-				err := ptab.writeShiftAction(state.num, sym, nextState.num)
-				if err != nil {
-					return nil, err
+				c := ptab.writeShiftAction(state.num, sym, nextState.num)
+				if c != nil {
+					conflicts = append(conflicts, c)
+					continue
 				}
 			} else {
 				ptab.writeGoTo(state.num, sym, nextState.num)
@@ -146,24 +202,47 @@ func genSLRParsingTable(automaton *lr0Automaton, prods *productionSet, follow *f
 		}
 
 		for prodID := range state.reducible {
-			prod, _ := prods.findByID(prodID)
-			flw, err := follow.find(prod.lhs)
+			prod, _ := b.prods.findByID(prodID)
+			flw, err := b.follow.find(prod.lhs)
 			if err != nil {
 				return nil, err
 			}
 			for sym := range flw.symbols {
-				err := ptab.writeReduceAction(state.num, sym, prod.num)
-				if err != nil {
-					return nil, err
+				c := ptab.writeReduceAction(state.num, sym, prod.num)
+				if c != nil {
+					conflicts = append(conflicts, c)
+					continue
 				}
 			}
 			if flw.eof {
-				err := ptab.writeReduceAction(state.num, symbolEOF, prod.num)
-				if err != nil {
-					return nil, err
+				c := ptab.writeReduceAction(state.num, symbolEOF, prod.num)
+				if c != nil {
+					conflicts = append(conflicts, c)
+					continue
+				}
+			}
+		}
+	}
+	if len(conflicts) > 0 {
+		var msg strings.Builder
+		for _, conflict := range conflicts {
+			fmt.Fprintf(&msg, "\n")
+			switch c := conflict.(type) {
+			case *shiftReduceConflict:
+				sym, ok := b.symTab.toText(c.sym)
+				if !ok {
+					sym = fmt.Sprintf("<not found: %v>", c.sym)
+				}
+				fmt.Fprintf(&msg, "%v: shift/reduce conflict (shift %v, reduce %v) on %v", c.state, c.nextState, c.prodNum, sym)
+			case *reduceReduceConflict:
+				sym, ok := b.symTab.toText(c.sym)
+				if !ok {
+					sym = fmt.Sprintf("<not found: %v>", c.sym)
 				}
+				fmt.Fprintf(&msg, "%v: reduce/reduce conflict (reduce %v and %v) on %v", c.state, c.prodNum1, c.prodNum2, sym)
 			}
 		}
+		return nil, fmt.Errorf("%v conflicts:%v", len(conflicts), msg.String())
 	}
 
 	return ptab, nil
diff --git a/grammar/slr_test.go b/grammar/slr_test.go
index 1ebb02d..15f58c1 100644
--- a/grammar/slr_test.go
+++ b/grammar/slr_test.go
@@ -68,7 +68,15 @@ id: "[A-Za-z_][0-9A-Za-z_]*";
 		nonTermCount = len(nonTermTexts)
 		termCount = len(termTexts)
 
-		ptab, err = genSLRParsingTable(automaton, gram.productionSet, follow, termCount, nonTermCount)
+		slr := &slrTableBuilder{
+			automaton:    automaton,
+			prods:        gram.productionSet,
+			follow:       follow,
+			termCount:    termCount,
+			nonTermCount: nonTermCount,
+			symTab:       gram.symbolTable,
+		}
+		ptab, err = slr.build()
 		if err != nil {
 			t.Fatalf("failed to create a SLR parsing table: %v", err)
 		}