Make #prec directive change only precedence and not associativity

5 files changed, 275 insertions, 30 deletions

diff --git a/README.md b/README.md
index f73d2a6..b7f6206 100644
--- a/README.md
+++ b/README.md
@@ -384,7 +384,7 @@ Labels are intended to identify elements in directives. An AST doesn't contain l
 
 #### `#prec <symbol: Identifier>`
 
-A `#prec` directive gives alternatives the same precedence and associativety as `symbol`. To be precise, precedence and associativity are given to the right-most symbol in an alternative, not to an alternative.
+A `#prec` directive gives alternatives the same precedence as `symbol`.
 
 See [Operator precedence and associativity](#operator-precedence-and-associativity) section for more details on the `#prec` directive.
 
@@ -499,7 +499,9 @@ foobar
 
 `%left` and `%right` allow you to define precedence and associativiry of symbols. `%left`/`%right` each assign the left/right associativity to symbols.
 
-`#prec` directive assigns the same precedence and associativity as a specified symbol to an alternative.
+When the right-most terminal symbol of an alternative has precedence or associativity defined explicitly, the alternative inherits its precedence and associativity.
+
+`#prec` directive assigns the same precedence as a specified symbol to an alternative.
 
 The grammar for simple four arithmetic operations and assignment expression can be defined as follows:
 
diff --git a/driver/parser_test.go b/driver/parser_test.go
index 4795e29..c717205 100644
--- a/driver/parser_test.go
+++ b/driver/parser_test.go
@@ -496,7 +496,52 @@ foo
 				termNode("foo", "foo"),
 			),
 		},
-		// The 'prec' directive can set precedence and associativity of a production.
+		// A production has the same precedence and associativity as the right-most terminal symbol.
+		{
+			specSrc: `
+%name test
+
+%left add
+
+expr
+    : expr add expr // This alternative has the same precedence and associativiry as 'add'.
+    | int
+    ;
+
+ws #skip
+    : "[\u{0009}\u{0020}]+";
+int
+    : "0|[1-9][0-9]*";
+add
+    : '+';
+`,
+			// This source is recognized as the following structure because the production `expr → expr add expr` has the same
+			// precedence and associativity as the symbol 'add'.
+			//
+			// ((1+2)+3)
+			//
+			// If the symbol doesn't have the precedence and left associativity, the production also doesn't have the precedence
+			// and associativity and this source will be recognized as the following structure.
+			//
+			// (1+(2+3))
+			src: `1+2+3`,
+			ast: nonTermNode("expr",
+				nonTermNode("expr",
+					nonTermNode("expr",
+						termNode("int", "1"),
+					),
+					termNode("add", "+"),
+					nonTermNode("expr",
+						termNode("int", "2"),
+					),
+				),
+				termNode("add", "+"),
+				nonTermNode("expr",
+					termNode("int", "3"),
+				),
+			),
+		},
+		// The 'prec' directive can set precedence of a production.
 		{
 			specSrc: `
 %name test
@@ -527,7 +572,7 @@ div
     : '/';
 `,
 			// This source is recognized as the following structure because the production `expr → sub expr`
-			// has the `#prec mul` directive and has the same precedence and associativity of the symbol `mul`.
+			// has the `#prec mul` directive and has the same precedence of the symbol `mul`.
 			//
 			// (((-1) * 20) / 5)
 			//
diff --git a/grammar/grammar.go b/grammar/grammar.go
index c996e36..d46d70e 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -39,7 +39,7 @@ type precAndAssoc struct {
 	termAssoc map[symbolNum]assocType
 
 	// prodPrec and prodAssoc represent the precedence and the associativities of the production.
-	// These values are inherited from the right-most symbols in the RHS of the productions.
+	// These values are inherited from the right-most terminal symbols in the RHS of the productions.
 	prodPrec  map[productionNum]int
 	prodAssoc map[productionNum]assocType
 }
@@ -150,7 +150,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
 		return nil, b.errs
 	}
 
-	pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods, prodsAndActs.prodPrecs)
+	pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods, prodsAndActs.prodPrecs, prodsAndActs.prodPrecPoss)
 	if err != nil {
 		return nil, err
 	}
@@ -601,6 +601,7 @@ type productionsAndActions struct {
 	augStartSym  symbol
 	astActs      map[productionID][]*astActionEntry
 	prodPrecs    map[productionID]symbol
+	prodPrecPoss map[productionID]*spec.Position
 	recoverProds map[productionID]struct{}
 }
 
@@ -620,6 +621,7 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
 	var augStartSym symbol
 	astActs := map[productionID][]*astActionEntry{}
 	prodPrecs := map[productionID]symbol{}
+	prodPrecPoss := map[productionID]*spec.Position{}
 	recoverProds := map[productionID]struct{}{}
 
 	startProd := root.Productions[0]
@@ -945,6 +947,7 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
 						continue LOOP_RHS
 					}
 					prodPrecs[p.id] = sym
+					prodPrecPoss[p.id] = &dir.Parameters[0].Pos
 				case "recover":
 					if len(dir.Parameters) > 0 {
 						b.errs = append(b.errs, &verr.SpecError{
@@ -974,11 +977,12 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
 		augStartSym:  augStartSym,
 		astActs:      astActs,
 		prodPrecs:    prodPrecs,
+		prodPrecPoss: prodPrecPoss,
 		recoverProds: recoverProds,
 	}, nil
 }
 
-func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet, prodPrecs map[productionID]symbol) (*precAndAssoc, error) {
+func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet, prodPrecs map[productionID]symbol, prodPrecPoss map[productionID]*spec.Position) (*precAndAssoc, error) {
 	termPrec := map[symbolNum]int{}
 	termAssoc := map[symbolNum]assocType{}
 	{
@@ -1082,34 +1086,39 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS
 	prodPrec := map[productionNum]int{}
 	prodAssoc := map[productionNum]assocType{}
 	for _, prod := range prods.getAllProductions() {
-		term, ok := prodPrecs[prod.id]
-		if !ok {
-			mostrightTerm := symbolNil
-			for _, sym := range prod.rhs {
-				if !sym.isTerminal() {
-					continue
-				}
-				mostrightTerm = sym
+		mostrightTerm := symbolNil
+		for _, sym := range prod.rhs {
+			if !sym.isTerminal() {
+				continue
 			}
-
-			term = mostrightTerm
+			mostrightTerm = sym
 		}
-		if term.isNil() {
-			continue
-		}
-
-		prec, ok := termPrec[term.num()]
-		if !ok {
-			continue
+		if !mostrightTerm.isNil() {
+			if prec, ok := termPrec[mostrightTerm.num()]; ok {
+				prodPrec[prod.num] = prec
+			}
+			if assoc, ok := termAssoc[mostrightTerm.num()]; ok {
+				prodAssoc[prod.num] = assoc
+			}
 		}
 
-		assoc, ok := termAssoc[term.num()]
-		if !ok {
-			continue
+		// #prec directive changes only precedence, not associativity.
+		if term, ok := prodPrecs[prod.id]; ok {
+			if prec, ok := termPrec[term.num()]; ok {
+				prodPrec[prod.num] = prec
+			} else {
+				text, _ := symTab.toText(term)
+				b.errs = append(b.errs, &verr.SpecError{
+					Cause:  semErrUndefinedPrec,
+					Detail: text,
+					Row:    prodPrecPoss[prod.id].Row,
+					Col:    prodPrecPoss[prod.id].Col,
+				})
+			}
 		}
-
-		prodPrec[prod.num] = prec
-		prodAssoc[prod.num] = assoc
+	}
+	if len(b.errs) > 0 {
+		return nil, nil
 	}
 
 	return &precAndAssoc{
diff --git a/grammar/grammar_test.go b/grammar/grammar_test.go
index 0295798..46458b0 100644
--- a/grammar/grammar_test.go
+++ b/grammar/grammar_test.go
@@ -193,6 +193,178 @@ fragment f
 				t.Fatalf("symbol having expected mode was not found: want: %v #mode %v", kind, expectedMode)
 			},
 		},
+		{
+			caption: "a production has the same precedence and associativity as the right-most terminal symbol",
+			specSrc: `
+%name test
+
+%left foo
+
+s
+    : foo bar // This alternative has the same precedence and associativity as the right-most terminal symbol 'bar', not 'foo'.
+    ;
+
+foo
+    : 'foo';
+bar
+    : 'bar';
+`,
+			validate: func(t *testing.T, g *Grammar) {
+				var barPrec int
+				var barAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("bar")
+					barPrec = g.precAndAssoc.terminalPrecedence(s.num())
+					barAssoc = g.precAndAssoc.terminalAssociativity(s.num())
+				}
+				var sPrec int
+				var sAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("s")
+					ps, _ := g.productionSet.findByLHS(s)
+					sPrec = g.precAndAssoc.productionPredence(ps[0].num)
+					sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num)
+				}
+				if barPrec != precNil || barAssoc != assocTypeNil {
+					t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, barPrec, barAssoc)
+				}
+				if sPrec != barPrec || sAssoc != barAssoc {
+					t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, sPrec, sAssoc)
+				}
+			},
+		},
+		{
+			caption: "a production has the same precedence and associativity as the right-most terminal symbol",
+			specSrc: `
+%name test
+
+%left foo
+%right bar
+
+s
+    : foo bar // This alternative has the same precedence and associativity as the right-most terminal symbol 'bar'.
+    ;
+
+foo
+    : 'foo';
+bar
+    : 'bar';
+`,
+			validate: func(t *testing.T, g *Grammar) {
+				var barPrec int
+				var barAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("bar")
+					barPrec = g.precAndAssoc.terminalPrecedence(s.num())
+					barAssoc = g.precAndAssoc.terminalAssociativity(s.num())
+				}
+				var sPrec int
+				var sAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("s")
+					ps, _ := g.productionSet.findByLHS(s)
+					sPrec = g.precAndAssoc.productionPredence(ps[0].num)
+					sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num)
+				}
+				if barPrec != 2 || barAssoc != assocTypeRight {
+					t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc)
+				}
+				if sPrec != barPrec || sAssoc != barAssoc {
+					t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, sPrec, sAssoc)
+				}
+			},
+		},
+		{
+			caption: "the `#prec` directive changes only precedence, not associativity",
+			specSrc: `
+%name test
+
+%left foo
+
+s
+    : foo bar #prec foo
+    ;
+
+foo
+    : 'foo';
+bar
+    : 'bar';
+`,
+			validate: func(t *testing.T, g *Grammar) {
+				var fooPrec int
+				var fooAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("foo")
+					fooPrec = g.precAndAssoc.terminalPrecedence(s.num())
+					fooAssoc = g.precAndAssoc.terminalAssociativity(s.num())
+				}
+				var sPrec int
+				var sAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("s")
+					ps, _ := g.productionSet.findByLHS(s)
+					sPrec = g.precAndAssoc.productionPredence(ps[0].num)
+					sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num)
+				}
+				if fooPrec != 1 || fooAssoc != assocTypeLeft {
+					t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc)
+				}
+				if sPrec != fooPrec || sAssoc != assocTypeNil {
+					t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, assocTypeNil, sPrec, sAssoc)
+				}
+			},
+		},
+		{
+			caption: "the `#prec` directive changes only precedence, not associativity",
+			specSrc: `
+%name test
+
+%left foo
+%right bar
+
+s
+    : foo bar #prec foo
+    ;
+
+foo
+    : 'foo';
+bar
+    : 'bar';
+`,
+			validate: func(t *testing.T, g *Grammar) {
+				var fooPrec int
+				var fooAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("foo")
+					fooPrec = g.precAndAssoc.terminalPrecedence(s.num())
+					fooAssoc = g.precAndAssoc.terminalAssociativity(s.num())
+				}
+				var barPrec int
+				var barAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("bar")
+					barPrec = g.precAndAssoc.terminalPrecedence(s.num())
+					barAssoc = g.precAndAssoc.terminalAssociativity(s.num())
+				}
+				var sPrec int
+				var sAssoc assocType
+				{
+					s, _ := g.symbolTable.toSymbol("s")
+					ps, _ := g.productionSet.findByLHS(s)
+					sPrec = g.precAndAssoc.productionPredence(ps[0].num)
+					sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num)
+				}
+				if fooPrec != 1 || fooAssoc != assocTypeLeft {
+					t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc)
+				}
+				if barPrec != 2 || barAssoc != assocTypeRight {
+					t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc)
+				}
+				if sPrec != fooPrec || sAssoc != barAssoc {
+					t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, barAssoc, sPrec, sAssoc)
+				}
+			},
+		},
 	}
 
 	var tests []*okTest
@@ -1175,6 +1347,22 @@ foo
 `,
 			errs: []*SemanticError{semErrDirInvalidParam},
 		},
+		{
+			caption: "a symbol the `#prec` directive takes must be given precedence explicitly",
+			specSrc: `
+%name test
+
+s
+    : foo bar #prec foo
+    ;
+
+foo
+    : 'foo';
+bar
+    : 'bar';
+`,
+			errs: []*SemanticError{semErrUndefinedPrec},
+		},
 	}
 
 	recoverDirTests := []*specErrTest{
diff --git a/grammar/semantic_error.go b/grammar/semantic_error.go
index 079f826..c81cb5f 100644
--- a/grammar/semantic_error.go
+++ b/grammar/semantic_error.go
@@ -19,6 +19,7 @@ var (
 	semErrMDInvalidParam      = newSemanticError("invalid parameter")
 	semErrMDMissingName       = newSemanticError("name is missing")
 	semErrDuplicateAssoc      = newSemanticError("associativity and precedence cannot be specified multiple times for a symbol")
+	semErrUndefinedPrec       = newSemanticError("symbol must has precedence")
 	semErrUnusedProduction    = newSemanticError("unused production")
 	semErrUnusedTerminal      = newSemanticError("unused terminal")
 	semErrTermCannotBeSkipped = newSemanticError("a terminal used in productions cannot be skipped")