diff options
Diffstat (limited to 'grammar')
| -rw-r--r-- | grammar/grammar.go | 61 | ||||
| -rw-r--r-- | grammar/grammar_test.go | 188 | ||||
| -rw-r--r-- | grammar/semantic_error.go | 1 |
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") |