aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--driver/conflict_test.go109
-rw-r--r--driver/parser_test.go24
-rw-r--r--grammar/grammar.go46
-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
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 01:32:57 +0000