1 files changed, 187 insertions, 0 deletions
diff --git a/tests/unit/grammar/lalr1_test.go b/tests/unit/grammar/lalr1_test.go
new file mode 100644
index 0000000..fd09333
--- /dev/null
+++ b/tests/unit/grammar/lalr1_test.go
@@ -0,0 +1,187 @@
+package grammar
+
+import (
+	"strings"
+	"testing"
+
+	"urubu/grammar/symbol"
+	"urubu/spec/grammar/parser"
+)
+
+func TestGenLALR1Automaton(t *testing.T) {
+	// This grammar belongs to LALR(1) class, not SLR(1).
+	src := `
+#name test;
+
+s: l eq r | r;
+l: ref r | id;
+r: l;
+eq: '=';
+ref: '*';
+id: "[A-Za-z0-9_]+";
+`
+
+	var gram *Grammar
+	var automaton *lalr1Automaton
+	{
+		ast, err := parser.Parse(strings.NewReader(src))
+		if err != nil {
+			t.Fatal(err)
+		}
+		b := GrammarBuilder{
+			AST: ast,
+		}
+		gram, err = b.build()
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol)
+		if err != nil {
+			t.Fatalf("failed to create a LR0 automaton: %v", err)
+		}
+
+		firstSet, err := genFirstSet(gram.productionSet)
+		if err != nil {
+			t.Fatalf("failed to create a FIRST set: %v", err)
+		}
+
+		automaton, err = genLALR1Automaton(lr0, gram.productionSet, firstSet)
+		if err != nil {
+			t.Fatalf("failed to create a LALR1 automaton: %v", err)
+		}
+		if automaton == nil {
+			t.Fatalf("genLALR1Automaton returns nil without any error")
+		}
+	}
+
+	initialState := automaton.states[automaton.initialState]
+	if initialState == nil {
+		t.Errorf("failed to get an initial status: %v", automaton.initialState)
+	}
+
+	genSym := newTestSymbolGenerator(t, gram.symbolTable)
+	genProd := newTestProductionGenerator(t, genSym)
+	genLR0Item := newTestLR0ItemGenerator(t, genProd)
+
+	expectedKernels := map[int][]*lrItem{
+		0: {
+			withLookAhead(genLR0Item("s'", 0, "s"), symbol.SymbolEOF),
+		},
+		1: {
+			withLookAhead(genLR0Item("s'", 1, "s"), symbol.SymbolEOF),
+		},
+		2: {
+			withLookAhead(genLR0Item("s", 1, "l", "eq", "r"), symbol.SymbolEOF),
+			withLookAhead(genLR0Item("r", 1, "l"), symbol.SymbolEOF),
+		},
+		3: {
+			withLookAhead(genLR0Item("s", 1, "r"), symbol.SymbolEOF),
+		},
+		4: {
+			withLookAhead(genLR0Item("l", 1, "ref", "r"), genSym("eq"), symbol.SymbolEOF),
+		},
+		5: {
+			withLookAhead(genLR0Item("l", 1, "id"), genSym("eq"), symbol.SymbolEOF),
+		},
+		6: {
+			withLookAhead(genLR0Item("s", 2, "l", "eq", "r"), symbol.SymbolEOF),
+		},
+		7: {
+			withLookAhead(genLR0Item("l", 2, "ref", "r"), genSym("eq"), symbol.SymbolEOF),
+		},
+		8: {
+			withLookAhead(genLR0Item("r", 1, "l"), genSym("eq"), symbol.SymbolEOF),
+		},
+		9: {
+			withLookAhead(genLR0Item("s", 3, "l", "eq", "r"), symbol.SymbolEOF),
+		},
+	}
+
+	expectedStates := []*expectedLRState{
+		{
+			kernelItems: expectedKernels[0],
+			nextStates: map[symbol.Symbol][]*lrItem{
+				genSym("s"):   expectedKernels[1],
+				genSym("l"):   expectedKernels[2],
+				genSym("r"):   expectedKernels[3],
+				genSym("ref"): expectedKernels[4],
+				genSym("id"):  expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[1],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("s'", "s"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[2],
+			nextStates: map[symbol.Symbol][]*lrItem{
+				genSym("eq"): expectedKernels[6],
+			},
+			reducibleProds: []*production{
+				genProd("r", "l"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[3],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("s", "r"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[4],
+			nextStates: map[symbol.Symbol][]*lrItem{
+				genSym("r"):   expectedKernels[7],
+				genSym("l"):   expectedKernels[8],
+				genSym("ref"): expectedKernels[4],
+				genSym("id"):  expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[5],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("l", "id"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[6],
+			nextStates: map[symbol.Symbol][]*lrItem{
+				genSym("r"):   expectedKernels[9],
+				genSym("l"):   expectedKernels[8],
+				genSym("ref"): expectedKernels[4],
+				genSym("id"):  expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[7],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("l", "ref", "r"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[8],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("r", "l"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[9],
+			nextStates:  map[symbol.Symbol][]*lrItem{},
+			reducibleProds: []*production{
+				genProd("s", "l", "eq", "r"),
+			},
+		},
+	}
+
+	testLRAutomaton(t, expectedStates, automaton.lr0Automaton)
+}