aboutsummaryrefslogtreecommitdiff
path: root/grammar
diff options
context:
space:
mode:
Diffstat (limited to 'grammar')
-rw-r--r--grammar/grammar.go61
-rw-r--r--grammar/grammar_test.go188
-rw-r--r--grammar/semantic_error.go1
3 files changed, 224 insertions, 26 deletions
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")