diff options
Diffstat (limited to 'grammar')
| -rw-r--r-- | grammar/grammar.go | 266 | ||||
| -rw-r--r-- | grammar/grammar_test.go | 825 | ||||
| -rw-r--r-- | grammar/semantic_error.go | 1 |
3 files changed, 969 insertions, 123 deletions
diff --git a/grammar/grammar.go b/grammar/grammar.go index da1c77c..a5d6cb7 100644 --- a/grammar/grammar.go +++ b/grammar/grammar.go @@ -150,7 +150,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) { return nil, b.errs } - pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods, prodsAndActs.prodPrecs, prodsAndActs.prodPrecPoss) + pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs) if err != nil { return nil, err } @@ -597,12 +597,13 @@ func genLexEntry(prod *spec.ProductionNode) (*mlspec.LexEntry, bool, string, *ve } type productionsAndActions struct { - prods *productionSet - augStartSym symbol - astActs map[productionID][]*astActionEntry - prodPrecs map[productionID]symbol - prodPrecPoss map[productionID]*spec.Position - recoverProds map[productionID]struct{} + prods *productionSet + augStartSym symbol + astActs map[productionID][]*astActionEntry + prodPrecsTerm map[productionID]symbol + prodPrecsOrdSym map[productionID]string + prodPrecPoss map[productionID]*spec.Position + recoverProds map[productionID]struct{} } func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAndLexSpec *symbolTableAndLexSpec) (*productionsAndActions, error) { @@ -620,7 +621,8 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd prods := newProductionSet() var augStartSym symbol astActs := map[productionID][]*astActionEntry{} - prodPrecs := map[productionID]symbol{} + prodPrecsTerm := map[productionID]symbol{} + prodPrecsOrdSym := map[productionID]string{} prodPrecPoss := map[productionID]*spec.Position{} recoverProds := map[productionID]struct{}{} @@ -918,36 +920,42 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd } astActs[p.id] = astAct case "prec": - if len(dir.Parameters) != 1 || dir.Parameters[0].ID == "" { + if len(dir.Parameters) != 1 || (dir.Parameters[0].ID == "" && dir.Parameters[0].OrderedSymbol == "") { b.errs = append(b.errs, &verr.SpecError{ Cause: semErrDirInvalidParam, - Detail: "'prec' directive needs an ID parameter", + Detail: "'prec' directive needs just one ID parameter or ordered symbol", Row: dir.Pos.Row, Col: dir.Pos.Col, }) continue LOOP_RHS } - sym, ok := symTab.toSymbol(dir.Parameters[0].ID) - if !ok { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidParam, - Detail: fmt.Sprintf("unknown terminal symbol: %v", dir.Parameters[0].ID), - Row: dir.Pos.Row, - Col: dir.Pos.Col, - }) - continue LOOP_RHS - } - if !sym.isTerminal() { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidParam, - Detail: fmt.Sprintf("the symbol must be a terminal: %v", dir.Parameters[0].ID), - Row: dir.Pos.Row, - Col: dir.Pos.Col, - }) - continue LOOP_RHS + switch { + case dir.Parameters[0].ID != "": + sym, ok := symTab.toSymbol(dir.Parameters[0].ID) + if !ok { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDirInvalidParam, + Detail: fmt.Sprintf("unknown terminal symbol: %v", dir.Parameters[0].ID), + Row: dir.Pos.Row, + Col: dir.Pos.Col, + }) + continue LOOP_RHS + } + if !sym.isTerminal() { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDirInvalidParam, + Detail: fmt.Sprintf("the symbol must be a terminal: %v", dir.Parameters[0].ID), + Row: dir.Pos.Row, + Col: dir.Pos.Col, + }) + continue LOOP_RHS + } + prodPrecsTerm[p.id] = sym + prodPrecPoss[p.id] = &dir.Parameters[0].Pos + case dir.Parameters[0].OrderedSymbol != "": + prodPrecsOrdSym[p.id] = dir.Parameters[0].OrderedSymbol + prodPrecPoss[p.id] = &dir.Parameters[0].Pos } - 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{ @@ -973,18 +981,20 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd } return &productionsAndActions{ - prods: prods, - augStartSym: augStartSym, - astActs: astActs, - prodPrecs: prodPrecs, - prodPrecPoss: prodPrecPoss, - recoverProds: recoverProds, + prods: prods, + augStartSym: augStartSym, + astActs: astActs, + prodPrecsTerm: prodPrecsTerm, + prodPrecsOrdSym: prodPrecsOrdSym, + prodPrecPoss: prodPrecPoss, + recoverProds: recoverProds, }, nil } -func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet, prodPrecs map[productionID]symbol, prodPrecPoss map[productionID]*spec.Position) (*precAndAssoc, error) { +func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prodsAndActs *productionsAndActions) (*precAndAssoc, error) { termPrec := map[symbolNum]int{} termAssoc := map[symbolNum]assocType{} + ordSymPrec := map[string]int{} { var precGroup []*spec.DirectiveNode for _, dir := range b.AST.Directives { @@ -1004,9 +1014,10 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS if dir.Name != "name" && dir.Name != "prec" { b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidName, - Row: dir.Pos.Row, - Col: dir.Pos.Col, + Cause: semErrDirInvalidName, + Detail: dir.Name, + Row: dir.Pos.Row, + Col: dir.Pos.Col, }) continue } @@ -1024,9 +1035,10 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS assocTy = assocTypeNil default: b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidName, - Row: dir.Pos.Row, - Col: dir.Pos.Col, + Cause: semErrDirInvalidName, + Detail: dir.Name, + Row: dir.Pos.Row, + Col: dir.Pos.Col, }) return nil, nil } @@ -1042,63 +1054,85 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS } ASSOC_PARAM_LOOP: for _, p := range dir.Parameters { - if p.ID == "" { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidParam, - Detail: "a parameter must be an ID", - Row: p.Pos.Row, - Col: p.Pos.Col, - }) - return nil, nil - } - - sym, ok := symTab.toSymbol(p.ID) - if !ok { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidParam, - Detail: fmt.Sprintf("'%v' is undefined", p.ID), - Row: p.Pos.Row, - Col: p.Pos.Col, - }) - return nil, nil - } - if !sym.isTerminal() { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDirInvalidParam, - Detail: fmt.Sprintf("associativity can take only terminal symbol ('%v' is a non-terminal)", p.ID), - Row: p.Pos.Row, - Col: p.Pos.Col, - }) - return nil, nil - } - if prec, alreadySet := termPrec[sym.num()]; alreadySet { - if prec == precN { - b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDuplicateAssoc, - Detail: fmt.Sprintf("'%v' already has the same associativity and precedence", p.ID), - Row: p.Pos.Row, - Col: p.Pos.Col, - }) - } else if assoc := termAssoc[sym.num()]; assoc == assocTy { + switch { + case p.ID != "": + sym, ok := symTab.toSymbol(p.ID) + if !ok { b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDuplicateAssoc, - Detail: fmt.Sprintf("'%v' already has different precedence", p.ID), + Cause: semErrDirInvalidParam, + Detail: fmt.Sprintf("'%v' is undefined", p.ID), Row: p.Pos.Row, Col: p.Pos.Col, }) - } else { + return nil, nil + } + if !sym.isTerminal() { b.errs = append(b.errs, &verr.SpecError{ - Cause: semErrDuplicateAssoc, - Detail: fmt.Sprintf("'%v' already has different associativity and precedence", p.ID), + Cause: semErrDirInvalidParam, + Detail: fmt.Sprintf("associativity can take only terminal symbol ('%v' is a non-terminal)", p.ID), Row: p.Pos.Row, Col: p.Pos.Col, }) + return nil, nil + } + if prec, alreadySet := termPrec[sym.num()]; alreadySet { + if prec == precN { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDuplicateAssoc, + Detail: fmt.Sprintf("'%v' already has the same associativity and precedence", p.ID), + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + } else if assoc := termAssoc[sym.num()]; assoc == assocTy { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDuplicateAssoc, + Detail: fmt.Sprintf("'%v' already has different precedence", p.ID), + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + } else { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDuplicateAssoc, + Detail: fmt.Sprintf("'%v' already has different associativity and precedence", p.ID), + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + } + break ASSOC_PARAM_LOOP + } + + termPrec[sym.num()] = precN + termAssoc[sym.num()] = assocTy + case p.OrderedSymbol != "": + if prec, alreadySet := ordSymPrec[p.OrderedSymbol]; alreadySet { + if prec == precN { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDuplicateAssoc, + Detail: fmt.Sprintf("'$%v' already has the same precedence", p.OrderedSymbol), + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + } else { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDuplicateAssoc, + Detail: fmt.Sprintf("'$%v' already has different precedence", p.OrderedSymbol), + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + } + break ASSOC_PARAM_LOOP } - break ASSOC_PARAM_LOOP - } - termPrec[sym.num()] = precN - termAssoc[sym.num()] = assocTy + ordSymPrec[p.OrderedSymbol] = precN + default: + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDirInvalidParam, + Detail: "a parameter must be an ID or an ordered symbol", + Row: p.Pos.Row, + Col: p.Pos.Col, + }) + return nil, nil + } } precN++ @@ -1110,36 +1144,46 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS prodPrec := map[productionNum]int{} prodAssoc := map[productionNum]assocType{} - for _, prod := range prods.getAllProductions() { - mostrightTerm := symbolNil - for _, sym := range prod.rhs { - if !sym.isTerminal() { - continue - } - mostrightTerm = sym - } - 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 - } - } - - // #prec directive changes only precedence, not associativity. - if term, ok := prodPrecs[prod.id]; ok { + for _, prod := range prodsAndActs.prods.getAllProductions() { + // A #prec directive changes only precedence, not associativity. + if term, ok := prodsAndActs.prodPrecsTerm[prod.id]; ok { if prec, ok := termPrec[term.num()]; ok { prodPrec[prod.num] = prec + prodAssoc[prod.num] = assocTypeNil } 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, + Row: prodsAndActs.prodPrecPoss[prod.id].Row, + Col: prodsAndActs.prodPrecPoss[prod.id].Col, }) } + } else if ordSym, ok := prodsAndActs.prodPrecsOrdSym[prod.id]; ok { + if prec, ok := ordSymPrec[ordSym]; ok { + prodPrec[prod.num] = prec + prodAssoc[prod.num] = assocTypeNil + } else { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrUndefinedOrdSym, + Detail: fmt.Sprintf("$%v", ordSym), + Row: prodsAndActs.prodPrecPoss[prod.id].Row, + Col: prodsAndActs.prodPrecPoss[prod.id].Col, + }) + } + } else { + // A production inherits precedence and associativity from the right-most terminal symbol. + mostrightTerm := symbolNil + for _, sym := range prod.rhs { + if !sym.isTerminal() { + continue + } + mostrightTerm = sym + } + if !mostrightTerm.isNil() { + prodPrec[prod.num] = termPrec[mostrightTerm.num()] + prodAssoc[prod.num] = termAssoc[mostrightTerm.num()] + } } } if len(b.errs) > 0 { diff --git a/grammar/grammar_test.go b/grammar/grammar_test.go index d4a361d..62823e1 100644 --- a/grammar/grammar_test.go +++ b/grammar/grammar_test.go @@ -464,6 +464,189 @@ bar }, }, { + caption: "even if a non-terminal symbol apears to a terminal symbol, a production inherits precedence and associativity from the right-most terminal symbol, not from the non-terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar +); + +s + : foo a // This alternative has the same precedence and associativity as the right-most terminal symbol 'foo', not 'a'. + ; +a + : bar + ; + +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 aPrec int + var aAssoc assocType + { + s, _ := g.symbolTable.toSymbol("a") + ps, _ := g.productionSet.findByLHS(s) + aPrec = g.precAndAssoc.productionPredence(ps[0].num) + aAssoc = g.precAndAssoc.productionAssociativity(ps[0].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 aPrec != barPrec || aAssoc != barAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, aPrec, aAssoc) + } + if sPrec != fooPrec || sAssoc != fooAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, sPrec, sAssoc) + } + }, + }, + { + caption: "each alternative in the same production can have its own precedence and associativity", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar + #assign baz +); + +s + : foo + | bar + | baz + | bra + ; + +foo + : 'foo'; +bar + : 'bar'; +baz + : 'baz'; +bra + : 'bra'; +`, + validate: func(t *testing.T, g *Grammar) { + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + var alt3Prec int + var alt3Assoc assocType + var alt4Prec int + var alt4Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + alt3Prec = g.precAndAssoc.productionPredence(ps[2].num) + alt3Assoc = g.precAndAssoc.productionAssociativity(ps[2].num) + alt4Prec = g.precAndAssoc.productionPredence(ps[3].num) + alt4Assoc = g.precAndAssoc.productionAssociativity(ps[3].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeLeft { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeRight { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, alt2Prec, alt2Assoc) + } + if alt3Prec != 3 || alt3Assoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt3Prec, alt3Assoc) + } + if alt4Prec != precNil || alt4Assoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, alt4Prec, alt4Assoc) + } + }, + }, + { + caption: "when a production contains no terminal symbols, the production will not have precedence and associativiry", + specSrc: ` +#name test; + +#prec ( + #left foo +); + +s + : a + ; +a + : foo + ; + +foo + : 'foo'; +`, + 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 aPrec int + var aAssoc assocType + { + s, _ := g.symbolTable.toSymbol("a") + ps, _ := g.productionSet.findByLHS(s) + aPrec = g.precAndAssoc.productionPredence(ps[0].num) + aAssoc = g.precAndAssoc.productionAssociativity(ps[0].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 aPrec != fooPrec || aAssoc != fooAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, aPrec, aAssoc) + } + if sPrec != precNil || sAssoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, sPrec, sAssoc) + } + }, + }, + { caption: "the `#prec` directive applied to an alternative changes only precedence, not associativity", specSrc: ` #name test; @@ -553,8 +736,310 @@ bar 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) + 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: "an ordered symbol can appear in a `#left` directive", + specSrc: ` +#name test; + +#prec ( + #left $high + #right foo bar + #left $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +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()) + } + if fooPrec != 2 || fooAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.toSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.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) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 3 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "an ordered symbol can appear in a `#right` directive", + specSrc: ` +#name test; + +#prec ( + #right $high + #left foo bar + #right $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +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()) + } + if fooPrec != 2 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.toSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.num()) + } + if barPrec != 2 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 3 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "an ordered symbol can appear in a `#assign` directive", + specSrc: ` +#name test; + +#prec ( + #assign $high + #left foo + #right bar + #assign $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +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()) + } + if fooPrec != 2 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.toSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.num()) + } + if barPrec != 3 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeRight, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 4 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 4, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "names of an ordered symbol and a terminal symbol can duplicate", + specSrc: ` +#name test; + +#prec ( + #left foo bar + #right $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 barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.toSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.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 != 1 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != fooPrec || alt1Assoc != fooAssoc { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "names of an ordered symbol and a non-terminal symbol can duplicate", + specSrc: ` +#name test; + +#prec ( + #left foo bar + #right $a +); + +s + : a + | bar #prec $a + ; +a + : 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()) + } + if barPrec != 1 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.toSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != precNil || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeNil, alt2Prec, alt2Assoc) } }, }, @@ -1001,6 +1486,22 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#prec` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec $x; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#prec` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -1160,7 +1661,7 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { - caption: "the `#left` dirctive cannot be specified multiple times for a symbol", + caption: "the `#left` dirctive cannot be specified multiple times for a terminal symbol", specSrc: ` #name test; @@ -1178,7 +1679,25 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different precedence", + caption: "the `#left` dirctive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #left $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", specSrc: ` #name test; @@ -1197,7 +1716,26 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different associativity", + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #left $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", specSrc: ` #name test; @@ -1215,6 +1753,25 @@ foo `, errs: []*SemanticError{semErrDuplicateAssoc}, }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #right $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, } rightDirTests := []*specErrTest{ @@ -1327,7 +1884,7 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { - caption: "the `#right` directive cannot be specified multiple times for a symbol", + caption: "the `#right` directive cannot be specified multiple times for a terminal symbol", specSrc: ` #name test; @@ -1345,7 +1902,25 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different precedence", + caption: "the `#right` directive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #right $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", specSrc: ` #name test; @@ -1364,7 +1939,26 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different associativity", + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #right $x + #right $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", specSrc: ` #name test; @@ -1382,6 +1976,25 @@ foo `, errs: []*SemanticError{semErrDuplicateAssoc}, }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #left $x + #right $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, } assignDirTests := []*specErrTest{ @@ -1494,7 +2107,7 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { - caption: "the `#assign` dirctive cannot be specified multiple times for a symbol", + caption: "the `#assign` dirctive cannot be specified multiple times for a terminal symbol", specSrc: ` #name test; @@ -1512,7 +2125,25 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different precedence", + caption: "the `#assign` dirctive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #assign $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", specSrc: ` #name test; @@ -1531,7 +2162,26 @@ foo errs: []*SemanticError{semErrDuplicateAssoc}, }, { - caption: "a symbol cannot have different associativity", + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #assign $x + #assign $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", specSrc: ` #name test; @@ -1549,6 +2199,25 @@ foo `, errs: []*SemanticError{semErrDuplicateAssoc}, }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #assign $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDuplicateAssoc}, + }, } errorSymTests := []*specErrTest{ @@ -1618,6 +2287,24 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#ast` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo #ast $x + ; + +foo + : "foo"; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#ast` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -1825,7 +2512,7 @@ foo altPrecDirTests := []*specErrTest{ { - caption: "the `#prec` directive needs an ID parameter", + caption: "the `#prec` directive needs an ID parameter or an ordered symbol parameter", specSrc: ` #name test; @@ -1876,6 +2563,20 @@ bar errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#prec` directive cannot take an undefined ordered symbol parameter", + specSrc: ` +#name test; + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrUndefinedOrdSym}, + }, + { caption: "the `#prec` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -1951,6 +2652,24 @@ foo errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#recover` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo #recover $x + ; + +foo + : 'foo'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#recover` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -2120,6 +2839,26 @@ bar #mode errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#mode` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo + : 'foo'; +bar #mode $x + : 'bar'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#mode` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -2203,6 +2942,26 @@ bar #mode mode_1 errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#push` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo #push $x + : 'foo'; +bar + : 'bar'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#push` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -2272,6 +3031,28 @@ baz #pop mode_1 errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#pop` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop $x + : 'baz'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#pop` directive cannot take a pattern parameter", specSrc: ` #name test; @@ -2345,6 +3126,26 @@ bar errs: []*SemanticError{semErrDirInvalidParam}, }, { + caption: "the `#skip` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo #skip $x + : 'foo'; +bar + : 'bar'; +`, + errs: []*SemanticError{semErrDirInvalidParam}, + }, + { caption: "the `#skip` directive cannot take a pattern parameter", specSrc: ` #name test; diff --git a/grammar/semantic_error.go b/grammar/semantic_error.go index a843719..794d8da 100644 --- a/grammar/semantic_error.go +++ b/grammar/semantic_error.go @@ -18,6 +18,7 @@ var ( semErrNoGrammarName = newSemanticError("name is missing") semErrDuplicateAssoc = newSemanticError("associativity and precedence cannot be specified multiple times for a symbol") semErrUndefinedPrec = newSemanticError("symbol must has precedence") + semErrUndefinedOrdSym = newSemanticError("undefined ordered symbol") semErrUnusedProduction = newSemanticError("unused production") semErrUnusedTerminal = newSemanticError("unused terminal") semErrTermCannotBeSkipped = newSemanticError("a terminal used in productions cannot be skipped") |