From 94e2400aa8e6017165ab22ba5f2f70a6d0682f63 Mon Sep 17 00:00:00 2001 From: Ryo Nihei Date: Sat, 21 Aug 2021 16:18:56 +0900 Subject: Resolve conflicts by default rules When a shift/reduce conflict occurred, we prioritize the shift action, and when a reduce/reduce conflict occurred, we prioritize the production defined earlier in the grammar file. --- driver/conflict_test.go | 109 +++++ driver/parser_test.go | 24 +- grammar/grammar.go | 46 +- grammar/parsing_table.go | 486 +++++++++++++++++++++ grammar/parsing_table_builder.go | 466 --------------------- grammar/parsing_table_builder_test.go | 768 ---------------------------------- grammar/parsing_table_test.go | 768 ++++++++++++++++++++++++++++++++++ 7 files changed, 1391 insertions(+), 1276 deletions(-) create mode 100644 driver/conflict_test.go create mode 100644 grammar/parsing_table.go delete mode 100644 grammar/parsing_table_builder.go delete mode 100644 grammar/parsing_table_builder_test.go create mode 100644 grammar/parsing_table_test.go 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.go b/grammar/parsing_table.go new file mode 100644 index 0000000..903f95a --- /dev/null +++ b/grammar/parsing_table.go @@ -0,0 +1,486 @@ +package grammar + +import ( + "fmt" + "io" + "strings" +) + +type ActionType string + +const ( + ActionTypeShift = ActionType("shift") + ActionTypeReduce = ActionType("reduce") + ActionTypeError = ActionType("error") +) + +type actionEntry int + +const actionEntryEmpty = actionEntry(0) + +func newShiftActionEntry(state stateNum) actionEntry { + return actionEntry(state * -1) +} + +func newReduceActionEntry(prod productionNum) actionEntry { + return actionEntry(prod) +} + +func (e actionEntry) isEmpty() bool { + return e == actionEntryEmpty +} + +func (e actionEntry) describe() (ActionType, stateNum, productionNum) { + if e == actionEntryEmpty { + return ActionTypeError, stateNumInitial, productionNumNil + } + if e < 0 { + return ActionTypeShift, stateNum(e * -1), productionNumNil + } + return ActionTypeReduce, stateNumInitial, productionNum(e) +} + +type GoToType string + +const ( + GoToTypeRegistered = GoToType("registered") + GoToTypeError = GoToType("error") +) + +type goToEntry uint + +const goToEntryEmpty = goToEntry(0) + +func newGoToEntry(state stateNum) goToEntry { + return goToEntry(state) +} + +func (e goToEntry) isEmpty() bool { + return e == goToEntryEmpty +} + +func (e goToEntry) describe() (GoToType, stateNum) { + if e == goToEntryEmpty { + return GoToTypeError, stateNumInitial + } + return GoToTypeRegistered, stateNum(e) +} + +type conflict interface { + conflict() +} + +type shiftReduceConflict struct { + state stateNum + sym symbol + nextState stateNum + prodNum productionNum +} + +func (c *shiftReduceConflict) conflict() { +} + +type reduceReduceConflict struct { + state stateNum + sym symbol + prodNum1 productionNum + prodNum2 productionNum +} + +func (c *reduceReduceConflict) conflict() { +} + +var ( + _ conflict = &shiftReduceConflict{} + _ conflict = &reduceReduceConflict{} +) + +type ParsingTable struct { + actionTable []actionEntry + goToTable []goToEntry + stateCount int + terminalCount int + nonTerminalCount int + expectedTerminals [][]int + + InitialState stateNum +} + +func (t *ParsingTable) getAction(state stateNum, sym symbolNum) (ActionType, stateNum, productionNum) { + pos := state.Int()*t.terminalCount + sym.Int() + return t.actionTable[pos].describe() +} + +func (t *ParsingTable) getGoTo(state stateNum, sym symbolNum) (GoToType, stateNum) { + pos := state.Int()*t.nonTerminalCount + sym.Int() + return t.goToTable[pos].describe() +} + +func (t *ParsingTable) readAction(row int, col int) actionEntry { + return t.actionTable[row*t.terminalCount+col] +} + +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) { + pos := state.Int()*t.nonTerminalCount + sym.num().Int() + t.goToTable[pos] = newGoToEntry(nextState) +} + +type lrTableBuilder struct { + automaton *lr0Automaton + prods *productionSet + termCount int + nonTermCount int + symTab *symbolTable + sym2AnonPat map[symbol]string + + conflicts []conflict +} + +func (b *lrTableBuilder) build() (*ParsingTable, error) { + var ptab *ParsingTable + { + initialState := b.automaton.states[b.automaton.initialState] + ptab = &ParsingTable{ + actionTable: make([]actionEntry, len(b.automaton.states)*b.termCount), + goToTable: make([]goToEntry, len(b.automaton.states)*b.nonTermCount), + stateCount: len(b.automaton.states), + terminalCount: b.termCount, + nonTerminalCount: b.nonTermCount, + expectedTerminals: make([][]int, len(b.automaton.states)), + InitialState: initialState.num, + } + } + + for _, state := range b.automaton.states { + var eTerms []int + + for sym, kID := range state.next { + nextState := b.automaton.states[kID] + if sym.isTerminal() { + eTerms = append(eTerms, sym.num().Int()) + b.writeShiftAction(ptab, state.num, sym, nextState.num) + } else { + ptab.writeGoTo(state.num, sym, nextState.num) + } + } + + for prodID := range state.reducible { + reducibleProd, ok := b.prods.findByID(prodID) + if !ok { + return nil, fmt.Errorf("reducible production not found: %v", prodID) + } + + var reducibleItem *lrItem + for _, item := range state.items { + if item.prod != reducibleProd.id { + continue + } + + reducibleItem = item + break + } + if reducibleItem == nil { + for _, item := range state.emptyProdItems { + if item.prod != reducibleProd.id { + continue + } + + reducibleItem = item + break + } + if reducibleItem == nil { + return nil, fmt.Errorf("reducible item not found; state: %v, production: %v", state.num, reducibleProd.num) + } + } + + for a := range reducibleItem.lookAhead.symbols { + eTerms = append(eTerms, a.num().Int()) + b.writeReduceAction(ptab, state.num, a, reducibleProd.num) + } + } + + ptab.expectedTerminals[state.num] = eTerms + } + + return ptab, nil +} + +// 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, + }) + } + } + + 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) writeDescription(w io.Writer, tab *ParsingTable) { + conflicts := map[stateNum][]conflict{} + for _, con := range b.conflicts { + switch c := con.(type) { + case *shiftReduceConflict: + conflicts[c.state] = append(conflicts[c.state], c) + case *reduceReduceConflict: + conflicts[c.state] = append(conflicts[c.state], c) + } + } + + fmt.Fprintf(w, "# Conflicts\n\n") + + if len(b.conflicts) > 0 { + fmt.Fprintf(w, "%v conflics:\n\n", len(b.conflicts)) + + for _, conflict := range b.conflicts { + switch c := conflict.(type) { + case *shiftReduceConflict: + fmt.Fprintf(w, "%v: shift/reduce conflict (shift %v, reduce %v) on %v\n", c.state, c.nextState, c.prodNum, b.symbolToText(c.sym)) + case *reduceReduceConflict: + fmt.Fprintf(w, "%v: reduce/reduce conflict (reduce %v and %v) on %v\n", c.state, c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) + } + } + fmt.Fprintf(w, "\n") + } else { + fmt.Fprintf(w, "no conflicts\n\n") + } + + fmt.Fprintf(w, "# Terminals\n\n") + + termSyms := b.symTab.terminalSymbols() + + fmt.Fprintf(w, "%v symbols:\n\n", len(termSyms)) + + for _, sym := range termSyms { + text, ok := b.symTab.toText(sym) + if !ok { + text = fmt.Sprintf("", sym) + } + if strings.HasPrefix(text, "_") { + fmt.Fprintf(w, "%4v %v: \"%v\"\n", sym.num(), text, b.sym2AnonPat[sym]) + } else { + fmt.Fprintf(w, "%4v %v\n", sym.num(), text) + } + } + + fmt.Fprintf(w, "\n") + + fmt.Fprintf(w, "# Productions\n\n") + + fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions())) + + for _, prod := range b.prods.getAllProductions() { + fmt.Fprintf(w, "%4v %v\n", prod.num, b.productionToString(prod, -1)) + } + + fmt.Fprintf(w, "\n# States\n\n") + + fmt.Fprintf(w, "%v states:\n\n", len(b.automaton.states)) + + for _, state := range b.automaton.states { + fmt.Fprintf(w, "state %v\n", state.num) + for _, item := range state.items { + prod, ok := b.prods.findByID(item.prod) + if !ok { + fmt.Fprintf(w, "\n") + continue + } + fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot)) + } + + fmt.Fprintf(w, "\n") + + var shiftRecs []string + var reduceRecs []string + var gotoRecs []string + var accRec string + { + for sym, kID := range state.next { + nextState := b.automaton.states[kID] + if sym.isTerminal() { + shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, b.symbolToText(sym))) + } else { + gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, b.symbolToText(sym))) + } + } + + for prodID := range state.reducible { + prod, ok := b.prods.findByID(prodID) + if !ok { + reduceRecs = append(reduceRecs, "") + continue + } + if prod.lhs.isStart() { + accRec = "accept on " + continue + } + + var reducibleItem *lrItem + for _, item := range state.items { + if item.prod != prodID { + continue + } + + reducibleItem = item + break + } + if reducibleItem == nil { + for _, item := range state.emptyProdItems { + if item.prod != prodID { + continue + } + + reducibleItem = item + break + } + if reducibleItem == nil { + reduceRecs = append(reduceRecs, "") + continue + } + } + for a := range reducibleItem.lookAhead.symbols { + reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, b.symbolToText(a))) + } + } + } + + if len(shiftRecs) > 0 || len(reduceRecs) > 0 { + for _, rec := range shiftRecs { + fmt.Fprintf(w, " %v\n", rec) + } + for _, rec := range reduceRecs { + fmt.Fprintf(w, " %v\n", rec) + } + fmt.Fprintf(w, "\n") + } + if len(gotoRecs) > 0 { + for _, rec := range gotoRecs { + fmt.Fprintf(w, " %v\n", rec) + } + fmt.Fprintf(w, "\n") + } + if accRec != "" { + fmt.Fprintf(w, " %v\n\n", accRec) + } + + 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") + } + } +} + +func (b *lrTableBuilder) productionToString(prod *production, dot int) string { + var w strings.Builder + fmt.Fprintf(&w, "%v →", b.symbolToText(prod.lhs)) + for n, rhs := range prod.rhs { + if n == dot { + fmt.Fprintf(&w, " ・") + } + fmt.Fprintf(&w, " %v", b.symbolToText(rhs)) + } + if dot == len(prod.rhs) { + fmt.Fprintf(&w, " ・") + } + + return w.String() +} + +func (b *lrTableBuilder) symbolToText(sym symbol) string { + if sym.isNil() { + return "" + } + if sym.isEOF() { + return "" + } + + text, ok := b.symTab.toText(sym) + if !ok { + return fmt.Sprintf("", sym) + } + + if strings.HasPrefix(text, "_") { + pat, ok := b.sym2AnonPat[sym] + if !ok { + return fmt.Sprintf("", text) + } + + return fmt.Sprintf(`"%v"`, pat) + } + + return text +} diff --git a/grammar/parsing_table_builder.go b/grammar/parsing_table_builder.go deleted file mode 100644 index 82b0d34..0000000 --- a/grammar/parsing_table_builder.go +++ /dev/null @@ -1,466 +0,0 @@ -package grammar - -import ( - "fmt" - "io" - "strings" -) - -type ActionType string - -const ( - ActionTypeShift = ActionType("shift") - ActionTypeReduce = ActionType("reduce") - ActionTypeError = ActionType("error") -) - -type actionEntry int - -const actionEntryEmpty = actionEntry(0) - -func newShiftActionEntry(state stateNum) actionEntry { - return actionEntry(state * -1) -} - -func newReduceActionEntry(prod productionNum) actionEntry { - return actionEntry(prod) -} - -func (e actionEntry) isEmpty() bool { - return e == actionEntryEmpty -} - -func (e actionEntry) describe() (ActionType, stateNum, productionNum) { - if e == actionEntryEmpty { - return ActionTypeError, stateNumInitial, productionNumNil - } - if e < 0 { - return ActionTypeShift, stateNum(e * -1), productionNumNil - } - return ActionTypeReduce, stateNumInitial, productionNum(e) -} - -type GoToType string - -const ( - GoToTypeRegistered = GoToType("registered") - GoToTypeError = GoToType("error") -) - -type goToEntry uint - -const goToEntryEmpty = goToEntry(0) - -func newGoToEntry(state stateNum) goToEntry { - return goToEntry(state) -} - -func (e goToEntry) isEmpty() bool { - return e == goToEntryEmpty -} - -func (e goToEntry) describe() (GoToType, stateNum) { - if e == goToEntryEmpty { - return GoToTypeError, stateNumInitial - } - return GoToTypeRegistered, stateNum(e) -} - -type conflict interface { - conflict() -} - -type shiftReduceConflict struct { - state stateNum - sym symbol - nextState stateNum - prodNum productionNum -} - -func (c *shiftReduceConflict) conflict() { -} - -type reduceReduceConflict struct { - state stateNum - sym symbol - prodNum1 productionNum - prodNum2 productionNum -} - -func (c *reduceReduceConflict) conflict() { -} - -var ( - _ conflict = &shiftReduceConflict{} - _ conflict = &reduceReduceConflict{} -) - -type ParsingTable struct { - actionTable []actionEntry - goToTable []goToEntry - stateCount int - terminalCount int - nonTerminalCount int - expectedTerminals [][]int - - InitialState stateNum -} - -func (t *ParsingTable) getAction(state stateNum, sym symbolNum) (ActionType, stateNum, productionNum) { - pos := state.Int()*t.terminalCount + sym.Int() - return t.actionTable[pos].describe() -} - -func (t *ParsingTable) getGoTo(state stateNum, sym symbolNum) (GoToType, stateNum) { - pos := state.Int()*t.nonTerminalCount + sym.Int() - 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) 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) writeGoTo(state stateNum, sym symbol, nextState stateNum) { - pos := state.Int()*t.nonTerminalCount + sym.num().Int() - t.goToTable[pos] = newGoToEntry(nextState) -} - -type lrTableBuilder struct { - automaton *lr0Automaton - prods *productionSet - termCount int - nonTermCount int - symTab *symbolTable - sym2AnonPat map[symbol]string - - conflicts []conflict -} - -func (b *lrTableBuilder) build() (*ParsingTable, error) { - var ptab *ParsingTable - { - initialState := b.automaton.states[b.automaton.initialState] - ptab = &ParsingTable{ - actionTable: make([]actionEntry, len(b.automaton.states)*b.termCount), - goToTable: make([]goToEntry, len(b.automaton.states)*b.nonTermCount), - stateCount: len(b.automaton.states), - terminalCount: b.termCount, - nonTerminalCount: b.nonTermCount, - expectedTerminals: make([][]int, len(b.automaton.states)), - InitialState: initialState.num, - } - } - - var conflicts []conflict - for _, state := range b.automaton.states { - var eTerms []int - - for sym, kID := range state.next { - 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 - } - } else { - ptab.writeGoTo(state.num, sym, nextState.num) - } - } - - for prodID := range state.reducible { - reducibleProd, ok := b.prods.findByID(prodID) - if !ok { - return nil, fmt.Errorf("reducible production not found: %v", prodID) - } - - var reducibleItem *lrItem - for _, item := range state.items { - if item.prod != reducibleProd.id { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - for _, item := range state.emptyProdItems { - if item.prod != reducibleProd.id { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - return nil, fmt.Errorf("reducible item not found; state: %v, production: %v", state.num, reducibleProd.num) - } - } - - 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 - } - } - } - - ptab.expectedTerminals[state.num] = eTerms - } - - b.conflicts = conflicts - - if len(conflicts) > 0 { - return nil, fmt.Errorf("%v conflicts", len(conflicts)) - } - - return ptab, nil -} - -func (b *lrTableBuilder) write(w io.Writer) { - conflicts := map[stateNum][]conflict{} - for _, con := range b.conflicts { - switch c := con.(type) { - case *shiftReduceConflict: - conflicts[c.state] = append(conflicts[c.state], c) - case *reduceReduceConflict: - conflicts[c.state] = append(conflicts[c.state], c) - } - } - - fmt.Fprintf(w, "# Conflicts\n\n") - - if len(b.conflicts) > 0 { - fmt.Fprintf(w, "%v conflics:\n\n", len(b.conflicts)) - - for _, conflict := range b.conflicts { - switch c := conflict.(type) { - case *shiftReduceConflict: - fmt.Fprintf(w, "%v: shift/reduce conflict (shift %v, reduce %v) on %v\n", c.state, c.nextState, c.prodNum, b.symbolToText(c.sym)) - case *reduceReduceConflict: - fmt.Fprintf(w, "%v: reduce/reduce conflict (reduce %v and %v) on %v\n", c.state, c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) - } - } - fmt.Fprintf(w, "\n") - } else { - fmt.Fprintf(w, "no conflicts\n\n") - } - - fmt.Fprintf(w, "# Terminals\n\n") - - termSyms := b.symTab.terminalSymbols() - - fmt.Fprintf(w, "%v symbols:\n\n", len(termSyms)) - - for _, sym := range termSyms { - text, ok := b.symTab.toText(sym) - if !ok { - text = fmt.Sprintf("", sym) - } - if strings.HasPrefix(text, "_") { - fmt.Fprintf(w, "%4v %v: \"%v\"\n", sym.num(), text, b.sym2AnonPat[sym]) - } else { - fmt.Fprintf(w, "%4v %v\n", sym.num(), text) - } - } - - fmt.Fprintf(w, "\n") - - fmt.Fprintf(w, "# Productions\n\n") - - fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions())) - - for _, prod := range b.prods.getAllProductions() { - fmt.Fprintf(w, "%4v %v\n", prod.num, b.productionToString(prod, -1)) - } - - fmt.Fprintf(w, "\n# States\n\n") - - fmt.Fprintf(w, "%v states:\n\n", len(b.automaton.states)) - - for _, state := range b.automaton.states { - fmt.Fprintf(w, "state %v\n", state.num) - for _, item := range state.items { - prod, ok := b.prods.findByID(item.prod) - if !ok { - fmt.Fprintf(w, "\n") - continue - } - fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot)) - } - - fmt.Fprintf(w, "\n") - - var shiftRecs []string - var reduceRecs []string - var gotoRecs []string - var accRec string - { - for sym, kID := range state.next { - nextState := b.automaton.states[kID] - if sym.isTerminal() { - shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, b.symbolToText(sym))) - } else { - gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, b.symbolToText(sym))) - } - } - - for prodID := range state.reducible { - prod, ok := b.prods.findByID(prodID) - if !ok { - reduceRecs = append(reduceRecs, "") - continue - } - if prod.lhs.isStart() { - accRec = "accept on " - continue - } - - var reducibleItem *lrItem - for _, item := range state.items { - if item.prod != prodID { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - for _, item := range state.emptyProdItems { - if item.prod != prodID { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - reduceRecs = append(reduceRecs, "") - continue - } - } - for a := range reducibleItem.lookAhead.symbols { - reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, b.symbolToText(a))) - } - } - } - - if len(shiftRecs) > 0 || len(reduceRecs) > 0 { - for _, rec := range shiftRecs { - fmt.Fprintf(w, " %v\n", rec) - } - for _, rec := range reduceRecs { - fmt.Fprintf(w, " %v\n", rec) - } - fmt.Fprintf(w, "\n") - } - if len(gotoRecs) > 0 { - for _, rec := range gotoRecs { - fmt.Fprintf(w, " %v\n", rec) - } - fmt.Fprintf(w, "\n") - } - if accRec != "" { - fmt.Fprintf(w, " %v\n\n", accRec) - } - - cons, ok := conflicts[state.num] - if ok { - 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)) - case *reduceReduceConflict: - fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) - } - } - fmt.Fprintf(w, "\n") - } - } -} - -func (b *lrTableBuilder) productionToString(prod *production, dot int) string { - var w strings.Builder - fmt.Fprintf(&w, "%v →", b.symbolToText(prod.lhs)) - for n, rhs := range prod.rhs { - if n == dot { - fmt.Fprintf(&w, " ・") - } - fmt.Fprintf(&w, " %v", b.symbolToText(rhs)) - } - if dot == len(prod.rhs) { - fmt.Fprintf(&w, " ・") - } - - return w.String() -} - -func (b *lrTableBuilder) symbolToText(sym symbol) string { - if sym.isNil() { - return "" - } - if sym.isEOF() { - return "" - } - - text, ok := b.symTab.toText(sym) - if !ok { - return fmt.Sprintf("", sym) - } - - if strings.HasPrefix(text, "_") { - pat, ok := b.sym2AnonPat[sym] - if !ok { - return fmt.Sprintf("", text) - } - - return fmt.Sprintf(`"%v"`, pat) - } - - return text -} diff --git a/grammar/parsing_table_builder_test.go b/grammar/parsing_table_builder_test.go deleted file mode 100644 index 95bc543..0000000 --- a/grammar/parsing_table_builder_test.go +++ /dev/null @@ -1,768 +0,0 @@ -package grammar - -import ( - "fmt" - "strings" - "testing" - - "github.com/nihei9/vartan/spec" -) - -type expectedState struct { - kernelItems []*lrItem - acts map[symbol]testActionEntry - goTos map[symbol][]*lrItem -} - -func TestGenLALRParsingTable(t *testing.T) { - src := ` -S: L eq R | R; -L: ref R | id; -R: L; -eq: '='; -ref: '*'; -id: "[A-Za-z0-9_]+"; -` - - var ptab *ParsingTable - var automaton *lalr1Automaton - var gram *Grammar - var nonTermCount int - var termCount int - { - ast, err := spec.Parse(strings.NewReader(src)) - if err != nil { - t.Fatal(err) - } - b := GrammarBuilder{ - AST: ast, - } - gram, err = b.Build() - if err != nil { - t.Fatal(err) - } - first, err := genFirstSet(gram.productionSet) - if err != nil { - t.Fatal(err) - } - lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol) - if err != nil { - t.Fatal(err) - } - automaton, err = genLALR1Automaton(lr0, gram.productionSet, first) - if err != nil { - t.Fatal(err) - } - - nonTermTexts, err := gram.symbolTable.nonTerminalTexts() - if err != nil { - t.Fatal(err) - } - termTexts, err := gram.symbolTable.terminalTexts() - if err != nil { - t.Fatal(err) - } - nonTermCount = len(nonTermTexts) - termCount = len(termTexts) - - lalr := &lrTableBuilder{ - automaton: automaton.lr0Automaton, - prods: gram.productionSet, - termCount: termCount, - nonTermCount: nonTermCount, - symTab: gram.symbolTable, - } - ptab, err = lalr.build() - if err != nil { - t.Fatalf("failed to create a LALR parsing table: %v", err) - } - if ptab == nil { - t.Fatal("genLALRParsingTable returns nil without any error") - } - } - - genSym := newTestSymbolGenerator(t, gram.symbolTable) - genProd := newTestProductionGenerator(t, genSym) - genLR0Item := newTestLR0ItemGenerator(t, genProd) - - expectedKernels := map[int][]*lrItem{ - 0: { - withLookAhead(genLR0Item("S'", 0, "S"), symbolEOF), - }, - 1: { - withLookAhead(genLR0Item("S'", 1, "S"), symbolEOF), - }, - 2: { - withLookAhead(genLR0Item("S", 1, "L", "eq", "R"), symbolEOF), - withLookAhead(genLR0Item("R", 1, "L"), symbolEOF), - }, - 3: { - withLookAhead(genLR0Item("S", 1, "R"), symbolEOF), - }, - 4: { - withLookAhead(genLR0Item("L", 1, "ref", "R"), genSym("eq"), symbolEOF), - }, - 5: { - withLookAhead(genLR0Item("L", 1, "id"), genSym("eq"), symbolEOF), - }, - 6: { - withLookAhead(genLR0Item("S", 2, "L", "eq", "R"), symbolEOF), - }, - 7: { - withLookAhead(genLR0Item("L", 2, "ref", "R"), genSym("eq"), symbolEOF), - }, - 8: { - withLookAhead(genLR0Item("R", 1, "L"), genSym("eq"), symbolEOF), - }, - 9: { - withLookAhead(genLR0Item("S", 3, "L", "eq", "R"), symbolEOF), - }, - } - - expectedStates := []expectedState{ - { - kernelItems: expectedKernels[0], - acts: map[symbol]testActionEntry{ - genSym("ref"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("S"): expectedKernels[1], - genSym("L"): expectedKernels[2], - genSym("R"): expectedKernels[3], - }, - }, - { - kernelItems: expectedKernels[1], - acts: map[symbol]testActionEntry{ - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("S'", "S"), - }, - }, - }, - { - kernelItems: expectedKernels[2], - acts: map[symbol]testActionEntry{ - genSym("eq"): { - ty: ActionTypeShift, - nextState: expectedKernels[6], - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("R", "L"), - }, - }, - }, - { - kernelItems: expectedKernels[3], - acts: map[symbol]testActionEntry{ - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("S", "R"), - }, - }, - }, - { - kernelItems: expectedKernels[4], - acts: map[symbol]testActionEntry{ - genSym("ref"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("R"): expectedKernels[7], - genSym("L"): expectedKernels[8], - }, - }, - { - kernelItems: expectedKernels[5], - acts: map[symbol]testActionEntry{ - genSym("eq"): { - ty: ActionTypeReduce, - production: genProd("L", "id"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("L", "id"), - }, - }, - }, - { - kernelItems: expectedKernels[6], - acts: map[symbol]testActionEntry{ - genSym("ref"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("L"): expectedKernels[8], - genSym("R"): expectedKernels[9], - }, - }, - { - kernelItems: expectedKernels[7], - acts: map[symbol]testActionEntry{ - genSym("eq"): { - ty: ActionTypeReduce, - production: genProd("L", "ref", "R"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("L", "ref", "R"), - }, - }, - }, - { - kernelItems: expectedKernels[8], - acts: map[symbol]testActionEntry{ - genSym("eq"): { - ty: ActionTypeReduce, - production: genProd("R", "L"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("R", "L"), - }, - }, - }, - { - kernelItems: expectedKernels[9], - acts: map[symbol]testActionEntry{ - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("S", "L", "eq", "R"), - }, - }, - }, - } - - t.Run("initial state", func(t *testing.T) { - iniState := findStateByNum(automaton.states, ptab.InitialState) - if iniState == nil { - t.Fatalf("the initial state was not found: #%v", ptab.InitialState) - } - eIniState, err := newKernel(expectedKernels[0]) - if err != nil { - t.Fatalf("failed to create a kernel item: %v", err) - } - if iniState.id != eIniState.id { - t.Fatalf("the initial state is mismatched; want: %v, got: %v", eIniState.id, iniState.id) - } - }) - - for i, eState := range expectedStates { - t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { - k, err := newKernel(eState.kernelItems) - if err != nil { - t.Fatalf("failed to create a kernel item: %v", err) - } - state, ok := automaton.states[k.id] - if !ok { - t.Fatalf("state was not found: #%v", 0) - } - - testAction(t, &eState, state, ptab, automaton.lr0Automaton, gram, termCount) - testGoTo(t, &eState, state, ptab, automaton.lr0Automaton, nonTermCount) - }) - } -} - -func TestGenSLRParsingTable(t *testing.T) { - src := ` -expr - : expr add term - | term - ; -term - : term mul factor - | factor - ; -factor - : l_paren expr r_paren - | id - ; -add: "\+"; -mul: "\*"; -l_paren: "\("; -r_paren: "\)"; -id: "[A-Za-z_][0-9A-Za-z_]*"; -` - - var ptab *ParsingTable - var automaton *slr1Automaton - var gram *Grammar - var nonTermCount int - var termCount int - { - ast, err := spec.Parse(strings.NewReader(src)) - if err != nil { - t.Fatal(err) - } - b := GrammarBuilder{ - AST: ast, - } - gram, err = b.Build() - if err != nil { - t.Fatal(err) - } - first, err := genFirstSet(gram.productionSet) - if err != nil { - t.Fatal(err) - } - follow, err := genFollowSet(gram.productionSet, first) - if err != nil { - t.Fatal(err) - } - lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol) - if err != nil { - t.Fatal(err) - } - automaton, err = genSLR1Automaton(lr0, gram.productionSet, follow) - if err != nil { - t.Fatal(err) - } - - nonTermTexts, err := gram.symbolTable.nonTerminalTexts() - if err != nil { - t.Fatal(err) - } - termTexts, err := gram.symbolTable.terminalTexts() - if err != nil { - t.Fatal(err) - } - nonTermCount = len(nonTermTexts) - termCount = len(termTexts) - - slr := &lrTableBuilder{ - automaton: automaton.lr0Automaton, - prods: gram.productionSet, - termCount: termCount, - nonTermCount: nonTermCount, - symTab: gram.symbolTable, - } - ptab, err = slr.build() - if err != nil { - t.Fatalf("failed to create a SLR parsing table: %v", err) - } - if ptab == nil { - t.Fatal("genSLRParsingTable returns nil without any error") - } - } - - genSym := newTestSymbolGenerator(t, gram.symbolTable) - genProd := newTestProductionGenerator(t, genSym) - genLR0Item := newTestLR0ItemGenerator(t, genProd) - - expectedKernels := map[int][]*lrItem{ - 0: { - genLR0Item("expr'", 0, "expr"), - }, - 1: { - genLR0Item("expr'", 1, "expr"), - genLR0Item("expr", 1, "expr", "add", "term"), - }, - 2: { - genLR0Item("expr", 1, "term"), - genLR0Item("term", 1, "term", "mul", "factor"), - }, - 3: { - genLR0Item("term", 1, "factor"), - }, - 4: { - genLR0Item("factor", 1, "l_paren", "expr", "r_paren"), - }, - 5: { - genLR0Item("factor", 1, "id"), - }, - 6: { - genLR0Item("expr", 2, "expr", "add", "term"), - }, - 7: { - genLR0Item("term", 2, "term", "mul", "factor"), - }, - 8: { - genLR0Item("expr", 1, "expr", "add", "term"), - genLR0Item("factor", 2, "l_paren", "expr", "r_paren"), - }, - 9: { - genLR0Item("expr", 3, "expr", "add", "term"), - genLR0Item("term", 1, "term", "mul", "factor"), - }, - 10: { - genLR0Item("term", 3, "term", "mul", "factor"), - }, - 11: { - genLR0Item("factor", 3, "l_paren", "expr", "r_paren"), - }, - } - - expectedStates := []expectedState{ - { - kernelItems: expectedKernels[0], - acts: map[symbol]testActionEntry{ - genSym("l_paren"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("expr"): expectedKernels[1], - genSym("term"): expectedKernels[2], - genSym("factor"): expectedKernels[3], - }, - }, - { - kernelItems: expectedKernels[1], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeShift, - nextState: expectedKernels[6], - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("expr'", "expr"), - }, - }, - }, - { - kernelItems: expectedKernels[2], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("expr", "term"), - }, - genSym("mul"): { - ty: ActionTypeShift, - nextState: expectedKernels[7], - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("expr", "term"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("expr", "term"), - }, - }, - }, - { - kernelItems: expectedKernels[3], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("term", "factor"), - }, - genSym("mul"): { - ty: ActionTypeReduce, - production: genProd("term", "factor"), - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("term", "factor"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("term", "factor"), - }, - }, - }, - { - kernelItems: expectedKernels[4], - acts: map[symbol]testActionEntry{ - genSym("l_paren"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("expr"): expectedKernels[8], - genSym("term"): expectedKernels[2], - genSym("factor"): expectedKernels[3], - }, - }, - { - kernelItems: expectedKernels[5], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("factor", "id"), - }, - genSym("mul"): { - ty: ActionTypeReduce, - production: genProd("factor", "id"), - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("factor", "id"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("factor", "id"), - }, - }, - }, - { - kernelItems: expectedKernels[6], - acts: map[symbol]testActionEntry{ - genSym("l_paren"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("term"): expectedKernels[9], - genSym("factor"): expectedKernels[3], - }, - }, - { - kernelItems: expectedKernels[7], - acts: map[symbol]testActionEntry{ - genSym("l_paren"): { - ty: ActionTypeShift, - nextState: expectedKernels[4], - }, - genSym("id"): { - ty: ActionTypeShift, - nextState: expectedKernels[5], - }, - }, - goTos: map[symbol][]*lrItem{ - genSym("factor"): expectedKernels[10], - }, - }, - { - kernelItems: expectedKernels[8], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeShift, - nextState: expectedKernels[6], - }, - genSym("r_paren"): { - ty: ActionTypeShift, - nextState: expectedKernels[11], - }, - }, - }, - { - kernelItems: expectedKernels[9], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("expr", "expr", "add", "term"), - }, - genSym("mul"): { - ty: ActionTypeShift, - nextState: expectedKernels[7], - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("expr", "expr", "add", "term"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("expr", "expr", "add", "term"), - }, - }, - }, - { - kernelItems: expectedKernels[10], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("term", "term", "mul", "factor"), - }, - genSym("mul"): { - ty: ActionTypeReduce, - production: genProd("term", "term", "mul", "factor"), - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("term", "term", "mul", "factor"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("term", "term", "mul", "factor"), - }, - }, - }, - { - kernelItems: expectedKernels[11], - acts: map[symbol]testActionEntry{ - genSym("add"): { - ty: ActionTypeReduce, - production: genProd("factor", "l_paren", "expr", "r_paren"), - }, - genSym("mul"): { - ty: ActionTypeReduce, - production: genProd("factor", "l_paren", "expr", "r_paren"), - }, - genSym("r_paren"): { - ty: ActionTypeReduce, - production: genProd("factor", "l_paren", "expr", "r_paren"), - }, - symbolEOF: { - ty: ActionTypeReduce, - production: genProd("factor", "l_paren", "expr", "r_paren"), - }, - }, - }, - } - - t.Run("initial state", func(t *testing.T) { - iniState := findStateByNum(automaton.states, ptab.InitialState) - if iniState == nil { - t.Fatalf("the initial state was not found: #%v", ptab.InitialState) - } - eIniState, err := newKernel(expectedKernels[0]) - if err != nil { - t.Fatalf("failed to create a kernel item: %v", err) - } - if iniState.id != eIniState.id { - t.Fatalf("the initial state is mismatched; want: %v, got: %v", eIniState.id, iniState.id) - } - }) - - for i, eState := range expectedStates { - t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { - k, err := newKernel(eState.kernelItems) - if err != nil { - t.Fatalf("failed to create a kernel item: %v", err) - } - state, ok := automaton.states[k.id] - if !ok { - t.Fatalf("state was not found: #%v", 0) - } - - testAction(t, &eState, state, ptab, automaton.lr0Automaton, gram, termCount) - testGoTo(t, &eState, state, ptab, automaton.lr0Automaton, nonTermCount) - }) - } -} - -func testAction(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, gram *Grammar, termCount int) { - nonEmptyEntries := map[symbolNum]struct{}{} - for eSym, eAct := range expectedState.acts { - nonEmptyEntries[eSym.num()] = struct{}{} - - ty, stateNum, prodNum := ptab.getAction(state.num, eSym.num()) - if ty != eAct.ty { - t.Fatalf("action type is mismatched; want: %v, got: %v", eAct.ty, ty) - } - switch eAct.ty { - case ActionTypeShift: - eNextState, err := newKernel(eAct.nextState) - if err != nil { - t.Fatal(err) - } - nextState := findStateByNum(automaton.states, stateNum) - if nextState == nil { - t.Fatalf("state was not found; state: #%v", stateNum) - } - if nextState.id != eNextState.id { - t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) - } - case ActionTypeReduce: - prod := findProductionByNum(gram.productionSet, prodNum) - if prod == nil { - t.Fatalf("production was not found: #%v", prodNum) - } - if prod.id != eAct.production.id { - t.Fatalf("production is mismatched; symbol: %v, want: %v, got: %v", eSym, eAct.production.id, prod.id) - } - } - } - for symNum := 0; symNum < termCount; symNum++ { - if _, checked := nonEmptyEntries[symbolNum(symNum)]; checked { - continue - } - ty, stateNum, prodNum := ptab.getAction(state.num, symbolNum(symNum)) - if ty != ActionTypeError { - t.Errorf("unexpected ACTION entry; state: #%v, symbol: #%v, action type: %v, next state: #%v, prodction: #%v", state.num, symNum, ty, stateNum, prodNum) - } - } -} - -func testGoTo(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, nonTermCount int) { - nonEmptyEntries := map[symbolNum]struct{}{} - for eSym, eGoTo := range expectedState.goTos { - nonEmptyEntries[eSym.num()] = struct{}{} - - eNextState, err := newKernel(eGoTo) - if err != nil { - t.Fatal(err) - } - ty, stateNum := ptab.getGoTo(state.num, eSym.num()) - if ty != GoToTypeRegistered { - t.Fatalf("GOTO entry was not found; state: #%v, symbol: #%v", state.num, eSym) - } - nextState := findStateByNum(automaton.states, stateNum) - if nextState == nil { - t.Fatalf("state was not found: #%v", stateNum) - } - if nextState.id != eNextState.id { - t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) - } - } - for symNum := 0; symNum < nonTermCount; symNum++ { - if _, checked := nonEmptyEntries[symbolNum(symNum)]; checked { - continue - } - ty, _ := ptab.getGoTo(state.num, symbolNum(symNum)) - if ty != GoToTypeError { - t.Errorf("unexpected GOTO entry; state: #%v, symbol: #%v", state.num, symNum) - } - } -} - -type testActionEntry struct { - ty ActionType - nextState []*lrItem - production *production -} - -func findStateByNum(states map[kernelID]*lrState, num stateNum) *lrState { - for _, state := range states { - if state.num == num { - return state - } - } - return nil -} - -func findProductionByNum(prods *productionSet, num productionNum) *production { - for _, prod := range prods.getAllProductions() { - if prod.num == num { - return prod - } - } - return nil -} diff --git a/grammar/parsing_table_test.go b/grammar/parsing_table_test.go new file mode 100644 index 0000000..95bc543 --- /dev/null +++ b/grammar/parsing_table_test.go @@ -0,0 +1,768 @@ +package grammar + +import ( + "fmt" + "strings" + "testing" + + "github.com/nihei9/vartan/spec" +) + +type expectedState struct { + kernelItems []*lrItem + acts map[symbol]testActionEntry + goTos map[symbol][]*lrItem +} + +func TestGenLALRParsingTable(t *testing.T) { + src := ` +S: L eq R | R; +L: ref R | id; +R: L; +eq: '='; +ref: '*'; +id: "[A-Za-z0-9_]+"; +` + + var ptab *ParsingTable + var automaton *lalr1Automaton + var gram *Grammar + var nonTermCount int + var termCount int + { + ast, err := spec.Parse(strings.NewReader(src)) + if err != nil { + t.Fatal(err) + } + b := GrammarBuilder{ + AST: ast, + } + gram, err = b.Build() + if err != nil { + t.Fatal(err) + } + first, err := genFirstSet(gram.productionSet) + if err != nil { + t.Fatal(err) + } + lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol) + if err != nil { + t.Fatal(err) + } + automaton, err = genLALR1Automaton(lr0, gram.productionSet, first) + if err != nil { + t.Fatal(err) + } + + nonTermTexts, err := gram.symbolTable.nonTerminalTexts() + if err != nil { + t.Fatal(err) + } + termTexts, err := gram.symbolTable.terminalTexts() + if err != nil { + t.Fatal(err) + } + nonTermCount = len(nonTermTexts) + termCount = len(termTexts) + + lalr := &lrTableBuilder{ + automaton: automaton.lr0Automaton, + prods: gram.productionSet, + termCount: termCount, + nonTermCount: nonTermCount, + symTab: gram.symbolTable, + } + ptab, err = lalr.build() + if err != nil { + t.Fatalf("failed to create a LALR parsing table: %v", err) + } + if ptab == nil { + t.Fatal("genLALRParsingTable returns nil without any error") + } + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + withLookAhead(genLR0Item("S'", 0, "S"), symbolEOF), + }, + 1: { + withLookAhead(genLR0Item("S'", 1, "S"), symbolEOF), + }, + 2: { + withLookAhead(genLR0Item("S", 1, "L", "eq", "R"), symbolEOF), + withLookAhead(genLR0Item("R", 1, "L"), symbolEOF), + }, + 3: { + withLookAhead(genLR0Item("S", 1, "R"), symbolEOF), + }, + 4: { + withLookAhead(genLR0Item("L", 1, "ref", "R"), genSym("eq"), symbolEOF), + }, + 5: { + withLookAhead(genLR0Item("L", 1, "id"), genSym("eq"), symbolEOF), + }, + 6: { + withLookAhead(genLR0Item("S", 2, "L", "eq", "R"), symbolEOF), + }, + 7: { + withLookAhead(genLR0Item("L", 2, "ref", "R"), genSym("eq"), symbolEOF), + }, + 8: { + withLookAhead(genLR0Item("R", 1, "L"), genSym("eq"), symbolEOF), + }, + 9: { + withLookAhead(genLR0Item("S", 3, "L", "eq", "R"), symbolEOF), + }, + } + + expectedStates := []expectedState{ + { + kernelItems: expectedKernels[0], + acts: map[symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("S"): expectedKernels[1], + genSym("L"): expectedKernels[2], + genSym("R"): expectedKernels[3], + }, + }, + { + kernelItems: expectedKernels[1], + acts: map[symbol]testActionEntry{ + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("S'", "S"), + }, + }, + }, + { + kernelItems: expectedKernels[2], + acts: map[symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeShift, + nextState: expectedKernels[6], + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("R", "L"), + }, + }, + }, + { + kernelItems: expectedKernels[3], + acts: map[symbol]testActionEntry{ + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("S", "R"), + }, + }, + }, + { + kernelItems: expectedKernels[4], + acts: map[symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("R"): expectedKernels[7], + genSym("L"): expectedKernels[8], + }, + }, + { + kernelItems: expectedKernels[5], + acts: map[symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("L", "id"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("L", "id"), + }, + }, + }, + { + kernelItems: expectedKernels[6], + acts: map[symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("L"): expectedKernels[8], + genSym("R"): expectedKernels[9], + }, + }, + { + kernelItems: expectedKernels[7], + acts: map[symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("L", "ref", "R"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("L", "ref", "R"), + }, + }, + }, + { + kernelItems: expectedKernels[8], + acts: map[symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("R", "L"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("R", "L"), + }, + }, + }, + { + kernelItems: expectedKernels[9], + acts: map[symbol]testActionEntry{ + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("S", "L", "eq", "R"), + }, + }, + }, + } + + t.Run("initial state", func(t *testing.T) { + iniState := findStateByNum(automaton.states, ptab.InitialState) + if iniState == nil { + t.Fatalf("the initial state was not found: #%v", ptab.InitialState) + } + eIniState, err := newKernel(expectedKernels[0]) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + if iniState.id != eIniState.id { + t.Fatalf("the initial state is mismatched; want: %v, got: %v", eIniState.id, iniState.id) + } + }) + + for i, eState := range expectedStates { + t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { + k, err := newKernel(eState.kernelItems) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + state, ok := automaton.states[k.id] + if !ok { + t.Fatalf("state was not found: #%v", 0) + } + + testAction(t, &eState, state, ptab, automaton.lr0Automaton, gram, termCount) + testGoTo(t, &eState, state, ptab, automaton.lr0Automaton, nonTermCount) + }) + } +} + +func TestGenSLRParsingTable(t *testing.T) { + src := ` +expr + : expr add term + | term + ; +term + : term mul factor + | factor + ; +factor + : l_paren expr r_paren + | id + ; +add: "\+"; +mul: "\*"; +l_paren: "\("; +r_paren: "\)"; +id: "[A-Za-z_][0-9A-Za-z_]*"; +` + + var ptab *ParsingTable + var automaton *slr1Automaton + var gram *Grammar + var nonTermCount int + var termCount int + { + ast, err := spec.Parse(strings.NewReader(src)) + if err != nil { + t.Fatal(err) + } + b := GrammarBuilder{ + AST: ast, + } + gram, err = b.Build() + if err != nil { + t.Fatal(err) + } + first, err := genFirstSet(gram.productionSet) + if err != nil { + t.Fatal(err) + } + follow, err := genFollowSet(gram.productionSet, first) + if err != nil { + t.Fatal(err) + } + lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol) + if err != nil { + t.Fatal(err) + } + automaton, err = genSLR1Automaton(lr0, gram.productionSet, follow) + if err != nil { + t.Fatal(err) + } + + nonTermTexts, err := gram.symbolTable.nonTerminalTexts() + if err != nil { + t.Fatal(err) + } + termTexts, err := gram.symbolTable.terminalTexts() + if err != nil { + t.Fatal(err) + } + nonTermCount = len(nonTermTexts) + termCount = len(termTexts) + + slr := &lrTableBuilder{ + automaton: automaton.lr0Automaton, + prods: gram.productionSet, + termCount: termCount, + nonTermCount: nonTermCount, + symTab: gram.symbolTable, + } + ptab, err = slr.build() + if err != nil { + t.Fatalf("failed to create a SLR parsing table: %v", err) + } + if ptab == nil { + t.Fatal("genSLRParsingTable returns nil without any error") + } + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + genLR0Item("expr'", 0, "expr"), + }, + 1: { + genLR0Item("expr'", 1, "expr"), + genLR0Item("expr", 1, "expr", "add", "term"), + }, + 2: { + genLR0Item("expr", 1, "term"), + genLR0Item("term", 1, "term", "mul", "factor"), + }, + 3: { + genLR0Item("term", 1, "factor"), + }, + 4: { + genLR0Item("factor", 1, "l_paren", "expr", "r_paren"), + }, + 5: { + genLR0Item("factor", 1, "id"), + }, + 6: { + genLR0Item("expr", 2, "expr", "add", "term"), + }, + 7: { + genLR0Item("term", 2, "term", "mul", "factor"), + }, + 8: { + genLR0Item("expr", 1, "expr", "add", "term"), + genLR0Item("factor", 2, "l_paren", "expr", "r_paren"), + }, + 9: { + genLR0Item("expr", 3, "expr", "add", "term"), + genLR0Item("term", 1, "term", "mul", "factor"), + }, + 10: { + genLR0Item("term", 3, "term", "mul", "factor"), + }, + 11: { + genLR0Item("factor", 3, "l_paren", "expr", "r_paren"), + }, + } + + expectedStates := []expectedState{ + { + kernelItems: expectedKernels[0], + acts: map[symbol]testActionEntry{ + genSym("l_paren"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("expr"): expectedKernels[1], + genSym("term"): expectedKernels[2], + genSym("factor"): expectedKernels[3], + }, + }, + { + kernelItems: expectedKernels[1], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeShift, + nextState: expectedKernels[6], + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("expr'", "expr"), + }, + }, + }, + { + kernelItems: expectedKernels[2], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("expr", "term"), + }, + genSym("mul"): { + ty: ActionTypeShift, + nextState: expectedKernels[7], + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("expr", "term"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("expr", "term"), + }, + }, + }, + { + kernelItems: expectedKernels[3], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("term", "factor"), + }, + genSym("mul"): { + ty: ActionTypeReduce, + production: genProd("term", "factor"), + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("term", "factor"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("term", "factor"), + }, + }, + }, + { + kernelItems: expectedKernels[4], + acts: map[symbol]testActionEntry{ + genSym("l_paren"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("expr"): expectedKernels[8], + genSym("term"): expectedKernels[2], + genSym("factor"): expectedKernels[3], + }, + }, + { + kernelItems: expectedKernels[5], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("factor", "id"), + }, + genSym("mul"): { + ty: ActionTypeReduce, + production: genProd("factor", "id"), + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("factor", "id"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("factor", "id"), + }, + }, + }, + { + kernelItems: expectedKernels[6], + acts: map[symbol]testActionEntry{ + genSym("l_paren"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("term"): expectedKernels[9], + genSym("factor"): expectedKernels[3], + }, + }, + { + kernelItems: expectedKernels[7], + acts: map[symbol]testActionEntry{ + genSym("l_paren"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol][]*lrItem{ + genSym("factor"): expectedKernels[10], + }, + }, + { + kernelItems: expectedKernels[8], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeShift, + nextState: expectedKernels[6], + }, + genSym("r_paren"): { + ty: ActionTypeShift, + nextState: expectedKernels[11], + }, + }, + }, + { + kernelItems: expectedKernels[9], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("expr", "expr", "add", "term"), + }, + genSym("mul"): { + ty: ActionTypeShift, + nextState: expectedKernels[7], + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("expr", "expr", "add", "term"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("expr", "expr", "add", "term"), + }, + }, + }, + { + kernelItems: expectedKernels[10], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("term", "term", "mul", "factor"), + }, + genSym("mul"): { + ty: ActionTypeReduce, + production: genProd("term", "term", "mul", "factor"), + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("term", "term", "mul", "factor"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("term", "term", "mul", "factor"), + }, + }, + }, + { + kernelItems: expectedKernels[11], + acts: map[symbol]testActionEntry{ + genSym("add"): { + ty: ActionTypeReduce, + production: genProd("factor", "l_paren", "expr", "r_paren"), + }, + genSym("mul"): { + ty: ActionTypeReduce, + production: genProd("factor", "l_paren", "expr", "r_paren"), + }, + genSym("r_paren"): { + ty: ActionTypeReduce, + production: genProd("factor", "l_paren", "expr", "r_paren"), + }, + symbolEOF: { + ty: ActionTypeReduce, + production: genProd("factor", "l_paren", "expr", "r_paren"), + }, + }, + }, + } + + t.Run("initial state", func(t *testing.T) { + iniState := findStateByNum(automaton.states, ptab.InitialState) + if iniState == nil { + t.Fatalf("the initial state was not found: #%v", ptab.InitialState) + } + eIniState, err := newKernel(expectedKernels[0]) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + if iniState.id != eIniState.id { + t.Fatalf("the initial state is mismatched; want: %v, got: %v", eIniState.id, iniState.id) + } + }) + + for i, eState := range expectedStates { + t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { + k, err := newKernel(eState.kernelItems) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + state, ok := automaton.states[k.id] + if !ok { + t.Fatalf("state was not found: #%v", 0) + } + + testAction(t, &eState, state, ptab, automaton.lr0Automaton, gram, termCount) + testGoTo(t, &eState, state, ptab, automaton.lr0Automaton, nonTermCount) + }) + } +} + +func testAction(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, gram *Grammar, termCount int) { + nonEmptyEntries := map[symbolNum]struct{}{} + for eSym, eAct := range expectedState.acts { + nonEmptyEntries[eSym.num()] = struct{}{} + + ty, stateNum, prodNum := ptab.getAction(state.num, eSym.num()) + if ty != eAct.ty { + t.Fatalf("action type is mismatched; want: %v, got: %v", eAct.ty, ty) + } + switch eAct.ty { + case ActionTypeShift: + eNextState, err := newKernel(eAct.nextState) + if err != nil { + t.Fatal(err) + } + nextState := findStateByNum(automaton.states, stateNum) + if nextState == nil { + t.Fatalf("state was not found; state: #%v", stateNum) + } + if nextState.id != eNextState.id { + t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) + } + case ActionTypeReduce: + prod := findProductionByNum(gram.productionSet, prodNum) + if prod == nil { + t.Fatalf("production was not found: #%v", prodNum) + } + if prod.id != eAct.production.id { + t.Fatalf("production is mismatched; symbol: %v, want: %v, got: %v", eSym, eAct.production.id, prod.id) + } + } + } + for symNum := 0; symNum < termCount; symNum++ { + if _, checked := nonEmptyEntries[symbolNum(symNum)]; checked { + continue + } + ty, stateNum, prodNum := ptab.getAction(state.num, symbolNum(symNum)) + if ty != ActionTypeError { + t.Errorf("unexpected ACTION entry; state: #%v, symbol: #%v, action type: %v, next state: #%v, prodction: #%v", state.num, symNum, ty, stateNum, prodNum) + } + } +} + +func testGoTo(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, nonTermCount int) { + nonEmptyEntries := map[symbolNum]struct{}{} + for eSym, eGoTo := range expectedState.goTos { + nonEmptyEntries[eSym.num()] = struct{}{} + + eNextState, err := newKernel(eGoTo) + if err != nil { + t.Fatal(err) + } + ty, stateNum := ptab.getGoTo(state.num, eSym.num()) + if ty != GoToTypeRegistered { + t.Fatalf("GOTO entry was not found; state: #%v, symbol: #%v", state.num, eSym) + } + nextState := findStateByNum(automaton.states, stateNum) + if nextState == nil { + t.Fatalf("state was not found: #%v", stateNum) + } + if nextState.id != eNextState.id { + t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) + } + } + for symNum := 0; symNum < nonTermCount; symNum++ { + if _, checked := nonEmptyEntries[symbolNum(symNum)]; checked { + continue + } + ty, _ := ptab.getGoTo(state.num, symbolNum(symNum)) + if ty != GoToTypeError { + t.Errorf("unexpected GOTO entry; state: #%v, symbol: #%v", state.num, symNum) + } + } +} + +type testActionEntry struct { + ty ActionType + nextState []*lrItem + production *production +} + +func findStateByNum(states map[kernelID]*lrState, num stateNum) *lrState { + for _, state := range states { + if state.num == num { + return state + } + } + return nil +} + +func findProductionByNum(prods *productionSet, num productionNum) *production { + for _, prod := range prods.getAllProductions() { + if prod.num == num { + return prod + } + } + return nil +} -- cgit v1.2.3