aboutsummaryrefslogtreecommitdiff
path: root/grammar/parsing_table_builder_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'grammar/parsing_table_builder_test.go')
-rw-r--r--grammar/parsing_table_builder_test.go847
1 files changed, 847 insertions, 0 deletions
diff --git a/grammar/parsing_table_builder_test.go b/grammar/parsing_table_builder_test.go
new file mode 100644
index 0000000..18add81
--- /dev/null
+++ b/grammar/parsing_table_builder_test.go
@@ -0,0 +1,847 @@
+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 := &lalrTableBuilder{
+ automaton: automaton,
+ 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 *lr0Automaton
+ 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)
+ }
+ automaton, err = genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol)
+ 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 := &slrTableBuilder{
+ automaton: automaton,
+ prods: gram.productionSet,
+ follow: follow,
+ 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 := []struct {
+ // kernelItems []*lrItem
+ // acts map[symbol]testActionEntry
+ // goTos map[symbol][]*lrItem
+ // }{
+ 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, gram, termCount)
+ testGoTo(t, &eState, state, ptab, automaton, nonTermCount)
+
+ // ACTION
+ {
+ // nonEmptyEntries := map[symbolNum]struct{}{}
+ // for eSym, eAct := range eState.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)
+ // }
+ // }
+ }
+
+ // GOTO
+ {
+ // nonEmptyEntries := map[symbolNum]struct{}{}
+ // for eSym, eGoTo := range eState.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)
+ // }
+ // }
+ }
+ })
+ }
+}
+
+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
+}