diff options
| -rw-r--r-- | driver/parser_test.go | 92 | ||||
| -rw-r--r-- | grammar/grammar.go | 58 |
2 files changed, 140 insertions, 10 deletions
diff --git a/driver/parser_test.go b/driver/parser_test.go index 224f12e..4779a00 100644 --- a/driver/parser_test.go +++ b/driver/parser_test.go @@ -447,6 +447,98 @@ a: 'a'; `, specErr: true, }, + // The 'prec' directive can set precedence and associativity of a production. + { + specSrc: ` +%left mul div +%left add sub + +expr + : expr add expr + | expr sub expr + | expr mul expr + | expr div expr + | sub expr #prec mul // This 'sub' means a unary minus symbol. + | int + ; + +ws: "[\u{0009}\u{0020}]+" #skip; +int: "0|[1-9][0-9]*"; +add: '+'; +sub: '-'; +mul: '*'; +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`. + // + // (((-1) * 20) / 5) + // + // If the production doesn't have the `#prec` directive, this source will be recognized as + // the following structure. + // + // (- ((1 * 20) / 5)) + src: `-1*20/5`, + cst: nonTermNode("expr", + nonTermNode("expr", + nonTermNode("expr", + termNode("sub", "-"), + nonTermNode("expr", + termNode("int", "1"), + ), + ), + termNode("mul", "*"), + nonTermNode("expr", + termNode("int", "20"), + ), + ), + termNode("div", "/"), + nonTermNode("expr", + termNode("int", "5"), + ), + ), + }, + // The 'prec' directive needs an ID parameter. + { + specSrc: ` +s + : a #prec + ; + +a: 'a'; +`, + specErr: true, + }, + // The 'prec' directive cannot take an unknown symbol. + { + specSrc: ` +s + : a #prec foo + ; + +a: 'a'; +`, + specErr: true, + }, + // The 'prec' directive cannot take a non-terminal symbol. + { + specSrc: ` +s + : foo #prec bar + | bar + ; +foo + : a + ; +bar + : b + ; + +a: 'a'; +b: 'b'; +`, + specErr: true, + }, // The grammar can contain the 'error' symbol. { specSrc: ` diff --git a/grammar/grammar.go b/grammar/grammar.go index b87d368..1f4f166 100644 --- a/grammar/grammar.go +++ b/grammar/grammar.go @@ -117,7 +117,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) { return nil, b.errs } - pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods) + pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods, prodsAndActs.prodPrecs) if err != nil { return nil, err } @@ -552,6 +552,7 @@ type productionsAndActions struct { prods *productionSet augStartSym symbol astActs map[productionID][]*astActionEntry + prodPrecs map[productionID]symbol recoverProds map[productionID]struct{} } @@ -570,6 +571,7 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd prods := newProductionSet() var augStartSym symbol astActs := map[productionID][]*astActionEntry{} + prodPrecs := map[productionID]symbol{} recoverProds := map[productionID]struct{}{} startProd := root.Productions[0] @@ -788,6 +790,36 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd } } astActs[p.id] = astAct + case "prec": + if len(dir.Parameters) != 1 || dir.Parameters[0].ID == "" { + b.errs = append(b.errs, &verr.SpecError{ + Cause: semErrDirInvalidParam, + Detail: fmt.Sprintf("'prec' directive needs an ID parameter"), + 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 + } + prodPrecs[p.id] = sym case "recover": if len(dir.Parameters) > 0 { b.errs = append(b.errs, &verr.SpecError{ @@ -816,11 +848,12 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd prods: prods, augStartSym: augStartSym, astActs: astActs, + prodPrecs: prodPrecs, recoverProds: recoverProds, }, nil } -func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet) (*precAndAssoc, error) { +func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet, prodPrecs map[productionID]symbol) (*precAndAssoc, error) { termPrec := map[symbolNum]int{} termAssoc := map[symbolNum]assocType{} { @@ -879,23 +912,28 @@ 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 + term, ok := prodPrecs[prod.id] + if !ok { + mostrightTerm := symbolNil + for _, sym := range prod.rhs { + if !sym.isTerminal() { + continue + } + mostrightTerm = sym } - mostRightTerm = sym + + term = mostrightTerm } - if mostRightTerm.isNil() { + if term.isNil() { continue } - prec, ok := termPrec[mostRightTerm.num()] + prec, ok := termPrec[term.num()] if !ok { continue } - assoc, ok := termAssoc[mostRightTerm.num()] + assoc, ok := termAssoc[term.num()] if !ok { continue } |