diff options
-rw-r--r-- | driver/conflict_test.go | 109 | ||||
-rw-r--r-- | driver/parser_test.go | 24 | ||||
-rw-r--r-- | grammar/grammar.go | 46 | ||||
-rw-r--r-- | grammar/parsing_table.go (renamed from grammar/parsing_table_builder.go) | 136 | ||||
-rw-r--r-- | grammar/parsing_table_test.go (renamed from grammar/parsing_table_builder_test.go) | 0 |
5 files changed, 215 insertions, 100 deletions
diff --git a/driver/conflict_test.go b/driver/conflict_test.go new file mode 100644 index 0000000..750ed4e --- /dev/null +++ b/driver/conflict_test.go @@ -0,0 +1,109 @@ +package driver + +import ( + "fmt" + "os" + "strings" + "testing" + + "github.com/nihei9/vartan/grammar" + "github.com/nihei9/vartan/spec" +) + +func TestParserWithConflicts(t *testing.T) { + tests := []struct { + caption string + specSrc string + src string + cst *Node + }{ + { + caption: "when a shift/reduce conflict occurred, we prioritize the shift action", + specSrc: ` +expr + : expr assign expr + | id + ; + +id: "[A-Za-z0-9_]+"; +assign: '='; +`, + src: `foo=bar=baz`, + cst: nonTermNode("expr", + nonTermNode("expr", + termNode("id", "foo"), + ), + termNode("assign", "="), + nonTermNode("expr", + nonTermNode("expr", + termNode("id", "bar"), + ), + termNode("assign", "="), + nonTermNode("expr", + termNode("id", "baz"), + ), + ), + ), + }, + { + caption: "when a reduce/reduce conflict occurred, we prioritize the production defined earlier in the grammar", + specSrc: ` +s + : a + | b + ; +a + : id + ; +b + : id + ; + +id: "[A-Za-z0-9_]+"; +`, + src: `foo`, + cst: nonTermNode("s", + nonTermNode("a", + termNode("id", "foo"), + ), + ), + }, + } + + for _, tt := range tests { + t.Run(tt.caption, func(t *testing.T) { + ast, err := spec.Parse(strings.NewReader(tt.specSrc)) + if err != nil { + t.Fatal(err) + } + + b := grammar.GrammarBuilder{ + AST: ast, + } + g, err := b.Build() + if err != nil { + t.Fatal(err) + } + + gram, err := grammar.Compile(g, grammar.SpecifyClass(grammar.ClassSLR)) + if err != nil { + t.Fatal(err) + } + + p, err := NewParser(gram, strings.NewReader(tt.src), MakeCST()) + if err != nil { + t.Fatal(err) + } + + err = p.Parse() + if err != nil { + t.Fatal(err) + } + + fmt.Printf("CST:\n") + PrintTree(os.Stdout, p.CST()) + + testTree(t, p.CST(), tt.cst) + }) + } +} diff --git a/driver/parser_test.go b/driver/parser_test.go index 0776232..d50ee85 100644 --- a/driver/parser_test.go +++ b/driver/parser_test.go @@ -10,22 +10,22 @@ import ( "github.com/nihei9/vartan/spec" ) -func TestParser_Parse(t *testing.T) { - termNode := func(kind string, text string, children ...*Node) *Node { - return &Node{ - KindName: kind, - Text: text, - Children: children, - } +func termNode(kind string, text string, children ...*Node) *Node { + return &Node{ + KindName: kind, + Text: text, + Children: children, } +} - nonTermNode := func(kind string, children ...*Node) *Node { - return &Node{ - KindName: kind, - Children: children, - } +func nonTermNode(kind string, children ...*Node) *Node { + return &Node{ + KindName: kind, + Children: children, } +} +func TestParser_Parse(t *testing.T) { tests := []struct { specSrc string src string diff --git a/grammar/grammar.go b/grammar/grammar.go index bca82e9..85eedcc 100644 --- a/grammar/grammar.go +++ b/grammar/grammar.go @@ -688,7 +688,7 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error return nil, err } - var tab *ParsingTable + var automaton *lr0Automaton switch config.class { case ClassSLR: followSet, err := genFollowSet(gram.productionSet, firstSet) @@ -701,44 +701,30 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error return nil, err } - slr := &lrTableBuilder{ - automaton: slr1.lr0Automaton, - prods: gram.productionSet, - termCount: len(terms), - nonTermCount: len(nonTerms), - symTab: gram.symbolTable, - sym2AnonPat: gram.sym2AnonPat, - } - tab, err = slr.build() - - if config.descriptionFileName != "" { - f, err := os.OpenFile(config.descriptionFileName, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644) - if err != nil { - return nil, err - } - defer f.Close() - - slr.write(f) - } - - if err != nil { - return nil, err - } + automaton = slr1.lr0Automaton case ClassLALR: lalr1, err := genLALR1Automaton(lr0, gram.productionSet, firstSet) if err != nil { return nil, err } - lalr := &lrTableBuilder{ - automaton: lalr1.lr0Automaton, + automaton = lalr1.lr0Automaton + } + + var tab *ParsingTable + { + b := &lrTableBuilder{ + automaton: automaton, prods: gram.productionSet, termCount: len(terms), nonTermCount: len(nonTerms), symTab: gram.symbolTable, sym2AnonPat: gram.sym2AnonPat, } - tab, err = lalr.build() + tab, err = b.build() + if err != nil { + return nil, err + } if config.descriptionFileName != "" { f, err := os.OpenFile(config.descriptionFileName, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644) @@ -747,11 +733,11 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error } defer f.Close() - lalr.write(f) + b.writeDescription(f, tab) } - if err != nil { - return nil, err + if len(b.conflicts) > 0 { + fmt.Fprintf(os.Stderr, "%v conflicts\n", len(b.conflicts)) } } diff --git a/grammar/parsing_table_builder.go b/grammar/parsing_table.go index 82b0d34..903f95a 100644 --- a/grammar/parsing_table_builder.go +++ b/grammar/parsing_table.go @@ -116,48 +116,12 @@ func (t *ParsingTable) getGoTo(state stateNum, sym symbolNum) (GoToType, stateNu return t.goToTable[pos].describe() } -func (t *ParsingTable) writeShiftAction(state stateNum, sym symbol, nextState stateNum) conflict { - pos := state.Int()*t.terminalCount + sym.num().Int() - act := t.actionTable[pos] - if !act.isEmpty() { - ty, _, p := act.describe() - if ty == ActionTypeReduce { - return &shiftReduceConflict{ - state: state, - sym: sym, - nextState: nextState, - prodNum: p, - } - } - } - t.actionTable[pos] = newShiftActionEntry(nextState) - - return nil +func (t *ParsingTable) readAction(row int, col int) actionEntry { + return t.actionTable[row*t.terminalCount+col] } -func (t *ParsingTable) writeReduceAction(state stateNum, sym symbol, prod productionNum) conflict { - pos := state.Int()*t.terminalCount + sym.num().Int() - act := t.actionTable[pos] - if !act.isEmpty() { - ty, s, p := act.describe() - if ty == ActionTypeReduce && p != prod { - return &reduceReduceConflict{ - state: state, - sym: sym, - prodNum1: p, - prodNum2: prod, - } - } - return &shiftReduceConflict{ - state: state, - sym: sym, - nextState: s, - prodNum: prod, - } - } - t.actionTable[pos] = newReduceActionEntry(prod) - - return nil +func (t *ParsingTable) writeAction(row int, col int, act actionEntry) { + t.actionTable[row*t.terminalCount+col] = act } func (t *ParsingTable) writeGoTo(state stateNum, sym symbol, nextState stateNum) { @@ -191,7 +155,6 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) { } } - var conflicts []conflict for _, state := range b.automaton.states { var eTerms []int @@ -199,12 +162,7 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) { nextState := b.automaton.states[kID] if sym.isTerminal() { eTerms = append(eTerms, sym.num().Int()) - - c := ptab.writeShiftAction(state.num, sym, nextState.num) - if c != nil { - conflicts = append(conflicts, c) - continue - } + b.writeShiftAction(ptab, state.num, sym, nextState.num) } else { ptab.writeGoTo(state.num, sym, nextState.num) } @@ -241,28 +199,78 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) { for a := range reducibleItem.lookAhead.symbols { eTerms = append(eTerms, a.num().Int()) - - c := ptab.writeReduceAction(state.num, a, reducibleProd.num) - if c != nil { - conflicts = append(conflicts, c) - continue - } + b.writeReduceAction(ptab, state.num, a, reducibleProd.num) } } ptab.expectedTerminals[state.num] = eTerms } - b.conflicts = conflicts + return ptab, nil +} - if len(conflicts) > 0 { - return nil, fmt.Errorf("%v conflicts", len(conflicts)) +// writeShiftAction writes a shift action to the parsing table. When a shift/reduce conflict occurred, +// we prioritize the shift action. +func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym symbol, nextState stateNum) { + act := tab.readAction(state.Int(), sym.num().Int()) + if !act.isEmpty() { + ty, _, p := act.describe() + if ty == ActionTypeReduce { + b.conflicts = append(b.conflicts, &shiftReduceConflict{ + state: state, + sym: sym, + nextState: nextState, + prodNum: p, + }) + } } - return ptab, nil + tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState)) +} + +// writeReduceAction writes a reduce action to the parsing table. When a shift/reduce conflict occurred, +// we prioritize the shift action, and when a reduce/reduce conflict we prioritize the action that reduces +// teh production with higher priority. Productions defined earlier in the grammar file have a higher priority. +func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sym symbol, prod productionNum) { + act := tab.readAction(state.Int(), sym.num().Int()) + if !act.isEmpty() { + ty, s, p := act.describe() + switch ty { + case ActionTypeReduce: + if p == prod { + return + } + + b.conflicts = append(b.conflicts, &reduceReduceConflict{ + state: state, + sym: sym, + prodNum1: p, + prodNum2: prod, + }) + + if p < prod { + tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(p)) + } else { + tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod)) + } + case ActionTypeShift: + b.conflicts = append(b.conflicts, &shiftReduceConflict{ + state: state, + sym: sym, + nextState: s, + prodNum: prod, + }) + + tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(s)) + } + + return + } + + tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod)) } -func (b *lrTableBuilder) write(w io.Writer) { +func (b *lrTableBuilder) writeDescription(w io.Writer, tab *ParsingTable) { conflicts := map[stateNum][]conflict{} for _, con := range b.conflicts { switch c := con.(type) { @@ -411,12 +419,24 @@ func (b *lrTableBuilder) write(w io.Writer) { cons, ok := conflicts[state.num] if ok { + syms := map[symbol]struct{}{} for _, con := range cons { switch c := con.(type) { case *shiftReduceConflict: fmt.Fprintf(w, " shift/reduce conflict (shift %v, reduce %v) on %v\n", c.nextState, c.prodNum, b.symbolToText(c.sym)) + syms[c.sym] = struct{}{} case *reduceReduceConflict: fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) + syms[c.sym] = struct{}{} + } + } + for sym := range syms { + ty, s, p := tab.getAction(state.num, sym.num()) + switch ty { + case ActionTypeShift: + fmt.Fprintf(w, " adopted shift %4v on %v\n", s, b.symbolToText(sym)) + case ActionTypeReduce: + fmt.Fprintf(w, " adopted reduce %4v on %v\n", p, b.symbolToText(sym)) } } fmt.Fprintf(w, "\n") diff --git a/grammar/parsing_table_builder_test.go b/grammar/parsing_table_test.go index 95bc543..95bc543 100644 --- a/grammar/parsing_table_builder_test.go +++ b/grammar/parsing_table_test.go |