Add SLR parsing table generator

10 files changed, 2201 insertions, 0 deletions

diff --git a/grammar/first.go b/grammar/first.go
new file mode 100644
index 0000000..72de282
--- /dev/null
+++ b/grammar/first.go
@@ -0,0 +1,144 @@
+package grammar
+
+import "fmt"
+
+type firstEntry struct {
+	symbols map[symbol]struct{}
+	empty   bool
+}
+
+func newFirstEntry() *firstEntry {
+	return &firstEntry{
+		symbols: map[symbol]struct{}{},
+		empty:   false,
+	}
+}
+
+func (e *firstEntry) add(sym symbol) bool {
+	if _, ok := e.symbols[sym]; ok {
+		return false
+	}
+	e.symbols[sym] = struct{}{}
+	return true
+}
+
+func (e *firstEntry) addEmpty() bool {
+	if !e.empty {
+		e.empty = true
+		return true
+	}
+	return false
+}
+
+func (e *firstEntry) mergeExceptEmpty(target *firstEntry) bool {
+	if target == nil {
+		return false
+	}
+	changed := false
+	for sym := range target.symbols {
+		added := e.add(sym)
+		if added {
+			changed = true
+		}
+	}
+	return changed
+}
+
+type firstSet struct {
+	set map[symbol]*firstEntry
+}
+
+func newFirstSet(prods *productionSet) *firstSet {
+	fst := &firstSet{
+		set: map[symbol]*firstEntry{},
+	}
+	for _, prod := range prods.getAllProductions() {
+		if _, ok := fst.set[prod.lhs]; ok {
+			continue
+		}
+		fst.set[prod.lhs] = newFirstEntry()
+	}
+
+	return fst
+}
+
+func (fst *firstSet) find(prod *production, head int) (*firstEntry, error) {
+	entry := newFirstEntry()
+	if prod.rhsLen <= head {
+		entry.addEmpty()
+		return entry, nil
+	}
+	for _, sym := range prod.rhs[head:] {
+		if sym.isTerminal() {
+			entry.add(sym)
+			return entry, nil
+		}
+
+		e := fst.findBySymbol(sym)
+		if e == nil {
+			return nil, fmt.Errorf("an entry of FIRST was not found; symbol: %s", sym)
+		}
+		for s := range e.symbols {
+			entry.add(s)
+		}
+		if !e.empty {
+			return entry, nil
+		}
+	}
+	entry.addEmpty()
+	return entry, nil
+}
+
+func (fst *firstSet) findBySymbol(sym symbol) *firstEntry {
+	return fst.set[sym]
+}
+
+type firstComContext struct {
+	first *firstSet
+}
+
+func newFirstComContext(prods *productionSet) *firstComContext {
+	return &firstComContext{
+		first: newFirstSet(prods),
+	}
+}
+
+func genFirstSet(prods *productionSet) (*firstSet, error) {
+	cc := newFirstComContext(prods)
+	for {
+		more := false
+		for _, prod := range prods.getAllProductions() {
+			e := cc.first.findBySymbol(prod.lhs)
+			changed, err := genProdFirstEntry(cc, e, prod)
+			if err != nil {
+				return nil, err
+			}
+			if changed {
+				more = true
+			}
+		}
+		if !more {
+			break
+		}
+	}
+	return cc.first, nil
+}
+
+func genProdFirstEntry(cc *firstComContext, acc *firstEntry, prod *production) (bool, error) {
+	if prod.isEmpty() {
+		return acc.addEmpty(), nil
+	}
+
+	for _, sym := range prod.rhs {
+		if sym.isTerminal() {
+			return acc.add(sym), nil
+		}
+
+		e := cc.first.findBySymbol(sym)
+		changed := acc.mergeExceptEmpty(e)
+		if !e.empty {
+			return changed, nil
+		}
+	}
+	return acc.addEmpty(), nil
+}
diff --git a/grammar/first_test.go b/grammar/first_test.go
new file mode 100644
index 0000000..b65b0ea
--- /dev/null
+++ b/grammar/first_test.go
@@ -0,0 +1,205 @@
+package grammar
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/nihei9/vartan/spec"
+)
+
+type first struct {
+	lhs     string
+	num     int
+	dot     int
+	symbols []string
+	empty   bool
+}
+
+func TestGenFirst(t *testing.T) {
+	tests := []struct {
+		caption string
+		src     string
+		first   []first
+	}{
+		{
+			caption: "productions contain only non-empty productions",
+			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_]*";
+`,
+			first: []first{
+				{lhs: "expr'", num: 0, dot: 0, symbols: []string{"l_paren", "id"}},
+				{lhs: "expr", num: 0, dot: 0, symbols: []string{"l_paren", "id"}},
+				{lhs: "expr", num: 0, dot: 1, symbols: []string{"add"}},
+				{lhs: "expr", num: 0, dot: 2, symbols: []string{"l_paren", "id"}},
+				{lhs: "expr", num: 1, dot: 0, symbols: []string{"l_paren", "id"}},
+				{lhs: "term", num: 0, dot: 0, symbols: []string{"l_paren", "id"}},
+				{lhs: "term", num: 0, dot: 1, symbols: []string{"mul"}},
+				{lhs: "term", num: 0, dot: 2, symbols: []string{"l_paren", "id"}},
+				{lhs: "term", num: 1, dot: 0, symbols: []string{"l_paren", "id"}},
+				{lhs: "factor", num: 0, dot: 0, symbols: []string{"l_paren"}},
+				{lhs: "factor", num: 0, dot: 1, symbols: []string{"l_paren", "id"}},
+				{lhs: "factor", num: 0, dot: 2, symbols: []string{"r_paren"}},
+				{lhs: "factor", num: 1, dot: 0, symbols: []string{"id"}},
+			},
+		},
+		{
+			caption: "productions contain the empty start production",
+			src: `
+s
+    :
+    ;
+`,
+			first: []first{
+				{lhs: "s'", num: 0, dot: 0, symbols: []string{}, empty: true},
+				{lhs: "s", num: 0, dot: 0, symbols: []string{}, empty: true},
+			},
+		},
+		{
+			caption: "productions contain an empty production",
+			src: `
+s
+    : foo bar
+    ;
+foo
+    :
+    ;
+bar: "bar";
+`,
+			first: []first{
+				{lhs: "s'", num: 0, dot: 0, symbols: []string{"bar"}, empty: false},
+				{lhs: "s", num: 0, dot: 0, symbols: []string{"bar"}, empty: false},
+				{lhs: "foo", num: 0, dot: 0, symbols: []string{}, empty: true},
+			},
+		},
+		{
+			caption: "a start production contains a non-empty alternative and empty alternative",
+			src: `
+s
+    : foo
+    |
+    ;
+foo: "foo";
+`,
+			first: []first{
+				{lhs: "s'", num: 0, dot: 0, symbols: []string{"foo"}, empty: true},
+				{lhs: "s", num: 0, dot: 0, symbols: []string{"foo"}},
+				{lhs: "s", num: 1, dot: 0, symbols: []string{}, empty: true},
+			},
+		},
+		{
+			caption: "a production contains non-empty alternative and empty alternative",
+			src: `
+s
+    : foo
+    ;
+foo
+    : bar
+    |
+    ;
+bar: "bar";
+`,
+			first: []first{
+				{lhs: "s'", num: 0, dot: 0, symbols: []string{"bar"}, empty: true},
+				{lhs: "s", num: 0, dot: 0, symbols: []string{"bar"}, empty: true},
+				{lhs: "foo", num: 0, dot: 0, symbols: []string{"bar"}},
+				{lhs: "foo", num: 1, dot: 0, symbols: []string{}, empty: true},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.caption, func(t *testing.T) {
+			fst, gram := genActualFirst(t, tt.src)
+
+			for _, ttFirst := range tt.first {
+				lhsSym, ok := gram.symbolTable.toSymbol(ttFirst.lhs)
+				if !ok {
+					t.Fatalf("a symbol was not found; symbol: %v", ttFirst.lhs)
+				}
+
+				prod, ok := gram.productionSet.findByLHS(lhsSym)
+				if !ok {
+					t.Fatalf("a production was not found; LHS: %v (%v)", ttFirst.lhs, lhsSym)
+				}
+
+				actualFirst, err := fst.find(prod[ttFirst.num], ttFirst.dot)
+				if err != nil {
+					t.Fatalf("failed to get a FIRST set; LHS: %v (%v), num: %v, dot: %v, error: %v", ttFirst.lhs, lhsSym, ttFirst.num, ttFirst.dot, err)
+				}
+
+				expectedFirst := genExpectedFirstEntry(t, ttFirst.symbols, ttFirst.empty, gram.symbolTable)
+
+				testFirst(t, actualFirst, expectedFirst)
+			}
+		})
+	}
+}
+
+func genActualFirst(t *testing.T, src string) (*firstSet, *Grammar) {
+	ast, err := spec.Parse(strings.NewReader(src))
+	if err != nil {
+		t.Fatal(err)
+	}
+	gram, err := NewGrammar(ast)
+	if err != nil {
+		t.Fatal(err)
+	}
+	fst, err := genFirstSet(gram.productionSet)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if fst == nil {
+		t.Fatal("genFiest returned nil without any error")
+	}
+
+	return fst, gram
+}
+
+func genExpectedFirstEntry(t *testing.T, symbols []string, empty bool, symTab *symbolTable) *firstEntry {
+	t.Helper()
+
+	entry := newFirstEntry()
+	if empty {
+		entry.addEmpty()
+	}
+	for _, sym := range symbols {
+		symSym, ok := symTab.toSymbol(sym)
+		if !ok {
+			t.Fatalf("a symbol was not found; symbol: %v", sym)
+		}
+		entry.add(symSym)
+	}
+
+	return entry
+}
+
+func testFirst(t *testing.T, actual, expected *firstEntry) {
+	if actual.empty != expected.empty {
+		t.Errorf("empty is mismatched\nwant: %v\ngot: %v", expected.empty, actual.empty)
+	}
+
+	if len(actual.symbols) != len(expected.symbols) {
+		t.Fatalf("invalid FIRST set\nwant: %+v\ngot: %+v", expected.symbols, actual.symbols)
+	}
+
+	for eSym := range expected.symbols {
+		if _, ok := actual.symbols[eSym]; !ok {
+			t.Fatalf("invalid FIRST set\nwant: %+v\ngot: %+v", expected.symbols, actual.symbols)
+		}
+	}
+}
diff --git a/grammar/follow.go b/grammar/follow.go
new file mode 100644
index 0000000..f835bba
--- /dev/null
+++ b/grammar/follow.go
@@ -0,0 +1,197 @@
+package grammar
+
+import (
+	"fmt"
+)
+
+type followEntry struct {
+	symbols map[symbol]struct{}
+	eof     bool
+}
+
+func newFollowEntry() *followEntry {
+	return &followEntry{
+		symbols: map[symbol]struct{}{},
+		eof:     false,
+	}
+}
+
+func (e *followEntry) add(sym symbol) bool {
+	if _, ok := e.symbols[sym]; ok {
+		return false
+	}
+	e.symbols[sym] = struct{}{}
+	return true
+}
+
+func (e *followEntry) addEOF() bool {
+	if !e.eof {
+		e.eof = true
+		return true
+	}
+	return false
+}
+
+func (e *followEntry) merge(fst *firstEntry, flw *followEntry) bool {
+	changed := false
+
+	if fst != nil {
+		for sym := range fst.symbols {
+			added := e.add(sym)
+			if added {
+				changed = true
+			}
+		}
+	}
+
+	if flw != nil {
+		for sym := range flw.symbols {
+			added := e.add(sym)
+			if added {
+				changed = true
+			}
+		}
+		if flw.eof {
+			added := e.addEOF()
+			if added {
+				changed = true
+			}
+		}
+	}
+
+	return changed
+}
+
+type followSet struct {
+	set map[symbol]*followEntry
+}
+
+func newFollow(prods *productionSet) *followSet {
+	flw := &followSet{
+		set: map[symbol]*followEntry{},
+	}
+	for _, prod := range prods.getAllProductions() {
+		if _, ok := flw.set[prod.lhs]; ok {
+			continue
+		}
+		flw.set[prod.lhs] = newFollowEntry()
+	}
+	return flw
+}
+
+func (flw *followSet) find(sym symbol) (*followEntry, error) {
+	e, ok := flw.set[sym]
+	if !ok {
+		return nil, fmt.Errorf("an entry of FOLLOW was not found; symbol: %s", sym)
+	}
+	return e, nil
+}
+
+type followComContext struct {
+	prods  *productionSet
+	first  *firstSet
+	follow *followSet
+}
+
+func newFollowComContext(prods *productionSet, first *firstSet) *followComContext {
+	return &followComContext{
+		prods:  prods,
+		first:  first,
+		follow: newFollow(prods),
+	}
+}
+
+func genFollowSet(prods *productionSet, first *firstSet) (*followSet, error) {
+	ntsyms := map[symbol]struct{}{}
+	for _, prod := range prods.getAllProductions() {
+		if _, ok := ntsyms[prod.lhs]; ok {
+			continue
+		}
+		ntsyms[prod.lhs] = struct{}{}
+	}
+
+	cc := newFollowComContext(prods, first)
+	for {
+		more := false
+		for ntsym := range ntsyms {
+			e, err := cc.follow.find(ntsym)
+			if err != nil {
+				return nil, err
+			}
+			if ntsym.isStart() {
+				changed := e.addEOF()
+				if changed {
+					more = true
+				}
+			}
+			for _, prod := range prods.getAllProductions() {
+				for i, sym := range prod.rhs {
+					if sym != ntsym {
+						continue
+					}
+					fst, err := first.find(prod, i+1)
+					if err != nil {
+						return nil, err
+					}
+					changed := e.merge(fst, nil)
+					if changed {
+						more = true
+					}
+					if fst.empty {
+						flw, err := cc.follow.find(prod.lhs)
+						if err != nil {
+							return nil, err
+						}
+						changed := e.merge(nil, flw)
+						if changed {
+							more = true
+						}
+					}
+				}
+			}
+		}
+		if !more {
+			break
+		}
+	}
+
+	return cc.follow, nil
+}
+
+func genFollowEntry(cc *followComContext, acc *followEntry, ntsym symbol) (bool, error) {
+	changed := false
+
+	if ntsym.isStart() {
+		added := acc.addEOF()
+		if added {
+			changed = true
+		}
+	}
+	for _, prod := range cc.prods.getAllProductions() {
+		for i, sym := range prod.rhs {
+			if sym != ntsym {
+				continue
+			}
+			fst, err := cc.first.find(prod, i+1)
+			if err != nil {
+				return false, err
+			}
+			added := acc.merge(fst, nil)
+			if added {
+				changed = true
+			}
+			if fst.empty {
+				flw, err := cc.follow.find(prod.lhs)
+				if err != nil {
+					return false, err
+				}
+				added := acc.merge(nil, flw)
+				if added {
+					changed = true
+				}
+			}
+		}
+	}
+
+	return changed, nil
+}
diff --git a/grammar/follow_test.go b/grammar/follow_test.go
new file mode 100644
index 0000000..042bc88
--- /dev/null
+++ b/grammar/follow_test.go
@@ -0,0 +1,188 @@
+package grammar
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/nihei9/vartan/spec"
+)
+
+type follow struct {
+	nonTermText string
+	symbols     []string
+	eof         bool
+}
+
+func TestFollowSet(t *testing.T) {
+	tests := []struct {
+		caption string
+		src     string
+		follow  []follow
+	}{
+		{
+			caption: "productions contain only non-empty productions",
+			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_]*";
+`,
+			follow: []follow{
+				{nonTermText: "expr'", symbols: []string{}, eof: true},
+				{nonTermText: "expr", symbols: []string{"add", "r_paren"}, eof: true},
+				{nonTermText: "term", symbols: []string{"add", "mul", "r_paren"}, eof: true},
+				{nonTermText: "factor", symbols: []string{"add", "mul", "r_paren"}, eof: true},
+			},
+		},
+		{
+			caption: "productions contain an empty start production",
+			src: `
+s
+    :
+    ;
+`,
+			follow: []follow{
+				{nonTermText: "s'", symbols: []string{}, eof: true},
+				{nonTermText: "s", symbols: []string{}, eof: true},
+			},
+		},
+		{
+			caption: "productions contain an empty production",
+			src: `
+s
+    : foo
+    ;
+foo
+    :
+;
+`,
+			follow: []follow{
+				{nonTermText: "s'", symbols: []string{}, eof: true},
+				{nonTermText: "s", symbols: []string{}, eof: true},
+				{nonTermText: "foo", symbols: []string{}, eof: true},
+			},
+		},
+		{
+			caption: "a start production contains a non-empty alternative and empty alternative",
+			src: `
+s
+    : foo
+    |
+    ;
+foo: "foo";
+`,
+			follow: []follow{
+				{nonTermText: "s'", symbols: []string{}, eof: true},
+				{nonTermText: "s", symbols: []string{}, eof: true},
+			},
+		},
+		{
+			caption: "a production contains non-empty alternative and empty alternative",
+			src: `
+s
+    : foo
+    ;
+foo
+    : bar
+    |
+    ;
+bar: "bar";
+`,
+			follow: []follow{
+				{nonTermText: "s'", symbols: []string{}, eof: true},
+				{nonTermText: "s", symbols: []string{}, eof: true},
+				{nonTermText: "foo", symbols: []string{}, eof: true},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.caption, func(t *testing.T) {
+			flw, gram := genActualFollow(t, tt.src)
+
+			for _, ttFollow := range tt.follow {
+				sym, ok := gram.symbolTable.toSymbol(ttFollow.nonTermText)
+				if !ok {
+					t.Fatalf("a symbol '%v' was not found", ttFollow.nonTermText)
+				}
+
+				actualFollow, err := flw.find(sym)
+				if err != nil {
+					t.Fatalf("failed to get a FOLLOW entry; non-terminal symbol: %v (%v), error: %v", ttFollow.nonTermText, sym, err)
+				}
+
+				expectedFollow := genExpectedFollowEntry(t, ttFollow.symbols, ttFollow.eof, gram.symbolTable)
+
+				testFollow(t, actualFollow, expectedFollow)
+			}
+		})
+	}
+}
+
+func genActualFollow(t *testing.T, src string) (*followSet, *Grammar) {
+	ast, err := spec.Parse(strings.NewReader(src))
+	if err != nil {
+		t.Fatal(err)
+	}
+	gram, err := NewGrammar(ast)
+	if err != nil {
+		t.Fatal(err)
+	}
+	fst, err := genFirstSet(gram.productionSet)
+	if err != nil {
+		t.Fatal(err)
+	}
+	flw, err := genFollowSet(gram.productionSet, fst)
+	if flw == nil {
+		t.Fatal("genFollow returned nil without any error")
+	}
+
+	return flw, gram
+}
+
+func genExpectedFollowEntry(t *testing.T, symbols []string, eof bool, symTab *symbolTable) *followEntry {
+	t.Helper()
+
+	entry := newFollowEntry()
+	if eof {
+		entry.addEOF()
+	}
+	for _, sym := range symbols {
+		symID, _ := symTab.toSymbol(sym)
+		if symID.isNil() {
+			t.Fatalf("a symbol '%v' was not found", sym)
+		}
+
+		entry.add(symID)
+	}
+
+	return entry
+}
+
+func testFollow(t *testing.T, actual, expected *followEntry) {
+	if actual.eof != expected.eof {
+		t.Errorf("eof is mismatched; want: %v, got: %v", expected.eof, actual.eof)
+	}
+
+	if len(actual.symbols) != len(expected.symbols) {
+		t.Fatalf("unexpected symbol count of a FOLLOW entry; want: %v, got: %v", expected.symbols, actual.symbols)
+	}
+
+	for eSym := range expected.symbols {
+		if _, ok := actual.symbols[eSym]; !ok {
+			t.Fatalf("invalid FOLLOW entry; want: %v, got: %v", expected.symbols, actual.symbols)
+		}
+	}
+}
diff --git a/grammar/grammar.go b/grammar/grammar.go
new file mode 100644
index 0000000..ce0ff19
--- /dev/null
+++ b/grammar/grammar.go
@@ -0,0 +1,158 @@
+package grammar
+
+import (
+	"fmt"
+
+	mlspec "github.com/nihei9/maleeni/spec"
+	"github.com/nihei9/vartan/spec"
+)
+
+type Grammar struct {
+	lexSpec              *mlspec.LexSpec
+	productionSet        *productionSet
+	augmentedStartSymbol symbol
+	symbolTable          *symbolTable
+}
+
+func NewGrammar(root *spec.RootNode) (*Grammar, error) {
+	symTab := newSymbolTable()
+	anonPat2Sym := map[string]symbol{}
+	var lexSpec *mlspec.LexSpec
+	{
+		entries := []*mlspec.LexEntry{}
+		anonPats := []string{}
+		for _, prod := range root.Productions {
+			if isLexicalProduction(prod) {
+				_, err := symTab.registerTerminalSymbol(prod.LHS)
+				if err != nil {
+					return nil, err
+				}
+
+				entries = append(entries, &mlspec.LexEntry{
+					Kind:    mlspec.LexKind(prod.LHS),
+					Pattern: mlspec.LexPattern(prod.RHS[0].Elements[0].Pattern),
+				})
+				continue
+			}
+
+			for _, alt := range prod.RHS {
+				for _, elem := range alt.Elements {
+					if elem.Pattern == "" {
+						continue
+					}
+					exist := false
+					for _, p := range anonPats {
+						if p == elem.Pattern {
+							exist = true
+							break
+						}
+					}
+					if exist {
+						continue
+					}
+					anonPats = append(anonPats, elem.Pattern)
+				}
+			}
+		}
+		for i, p := range anonPats {
+			kind := fmt.Sprintf("__%v__", i+1)
+
+			sym, err := symTab.registerTerminalSymbol(kind)
+			if err != nil {
+				return nil, err
+			}
+			anonPat2Sym[p] = sym
+
+			entries = append(entries, &mlspec.LexEntry{
+				Kind:    mlspec.LexKind(kind),
+				Pattern: mlspec.LexPattern(p),
+			})
+		}
+
+		lexSpec = &mlspec.LexSpec{
+			Entries: entries,
+		}
+	}
+
+	prods := newProductionSet()
+	var augStartSym symbol
+	{
+		startProd := root.Productions[0]
+		augStartText := fmt.Sprintf("%s'", startProd.LHS)
+		var err error
+		augStartSym, err = symTab.registerStartSymbol(augStartText)
+		if err != nil {
+			return nil, err
+		}
+		startSym, err := symTab.registerNonTerminalSymbol(startProd.LHS)
+		if err != nil {
+			return nil, err
+		}
+		p, err := newProduction(augStartSym, []symbol{
+			startSym,
+		})
+		if err != nil {
+			return nil, err
+		}
+		prods.append(p)
+
+		for _, prod := range root.Productions {
+			if isLexicalProduction(prod) {
+				continue
+			}
+			_, err := symTab.registerNonTerminalSymbol(prod.LHS)
+			if err != nil {
+				return nil, err
+			}
+		}
+
+		for _, prod := range root.Productions {
+			if isLexicalProduction(prod) {
+				continue
+			}
+			lhsSym, ok := symTab.toSymbol(prod.LHS)
+			if !ok {
+				return nil, fmt.Errorf("symbol '%v' is undefined", prod.LHS)
+			}
+			for _, alt := range prod.RHS {
+				altSyms := make([]symbol, len(alt.Elements))
+				for i, elem := range alt.Elements {
+					var sym symbol
+					if elem.Pattern != "" {
+						var ok bool
+						sym, ok = anonPat2Sym[elem.Pattern]
+						if !ok {
+							return nil, fmt.Errorf("pattern '%v' is undefined", elem.Pattern)
+						}
+					} else {
+						var ok bool
+						sym, ok = symTab.toSymbol(elem.ID)
+						if !ok {
+							return nil, fmt.Errorf("symbol '%v' is undefined", elem.ID)
+						}
+					}
+					altSyms[i] = sym
+				}
+				p, err := newProduction(lhsSym, altSyms)
+				if err != nil {
+					return nil, err
+				}
+				prods.append(p)
+			}
+		}
+	}
+
+	return &Grammar{
+		lexSpec:              lexSpec,
+		productionSet:        prods,
+		augmentedStartSymbol: augStartSym,
+		symbolTable:          symTab,
+	}, nil
+}
+
+func isLexicalProduction(prod *spec.ProductionNode) bool {
+	if len(prod.RHS) == 1 && len(prod.RHS[0].Elements) == 1 && prod.RHS[0].Elements[0].Pattern != "" {
+		return true
+	}
+	return false
+}
diff --git a/grammar/lr0_item.go b/grammar/lr0_item.go
new file mode 100644
index 0000000..2934061
--- /dev/null
+++ b/grammar/lr0_item.go
@@ -0,0 +1,343 @@
+package grammar
+
+import (
+	"crypto/sha256"
+	"encoding/binary"
+	"fmt"
+	"sort"
+	"strconv"
+)
+
+type lr0ItemID [32]byte
+
+func (id lr0ItemID) String() string {
+	return fmt.Sprintf("%x", id.num())
+}
+
+func (id lr0ItemID) num() uint32 {
+	return binary.LittleEndian.Uint32(id[:])
+}
+
+type lr0Item struct {
+	id   lr0ItemID
+	prod productionID
+
+	// E → E + T
+	//
+	// Dot | Dotted Symbol | Item
+	// ----+---------------+------------
+	// 0   | E             | E →・E + T
+	// 1   | +             | E → E・+ T
+	// 2   | T             | E → E +・T
+	// 3   | Nil           | E → E + T・
+	dot          int
+	dottedSymbol symbol
+
+	// When initial is true, the LHS of the production is the augmented start symbol and dot is 0.
+	// It looks like S' →・S.
+	initial bool
+
+	// When reducible is true, the item looks like E → E + T・.
+	reducible bool
+
+	// When kernel is true, the item is kernel item.
+	kernel bool
+}
+
+func newLR0Item(prod *production, dot int) (*lr0Item, error) {
+	if prod == nil {
+		return nil, fmt.Errorf("production must be non-nil")
+	}
+
+	if dot < 0 || dot > prod.rhsLen {
+		return nil, fmt.Errorf("dot must be between 0 and %v", prod.rhsLen)
+	}
+
+	var id lr0ItemID
+	{
+		b := []byte{}
+		b = append(b, prod.id[:]...)
+		bDot := make([]byte, 8)
+		binary.LittleEndian.PutUint64(bDot, uint64(dot))
+		b = append(b, bDot...)
+		id = sha256.Sum256(b)
+	}
+
+	dottedSymbol := symbolNil
+	if dot < prod.rhsLen {
+		dottedSymbol = prod.rhs[dot]
+	}
+
+	initial := false
+	if prod.lhs.isStart() && dot == 0 {
+		initial = true
+	}
+
+	reducible := false
+	if dot == prod.rhsLen {
+		reducible = true
+	}
+
+	kernel := false
+	if initial || dot > 0 {
+		kernel = true
+	}
+
+	item := &lr0Item{
+		id:           id,
+		prod:         prod.id,
+		dot:          dot,
+		dottedSymbol: dottedSymbol,
+		initial:      initial,
+		reducible:    reducible,
+		kernel:       kernel,
+	}
+
+	return item, nil
+}
+
+type kernelID [32]byte
+
+func (id kernelID) String() string {
+	return fmt.Sprintf("%x", binary.LittleEndian.Uint32(id[:]))
+}
+
+type kernel struct {
+	id    kernelID
+	items []*lr0Item
+}
+
+func newKernel(items []*lr0Item) (*kernel, error) {
+	if len(items) == 0 {
+		return nil, fmt.Errorf("a kernel need at least one item")
+	}
+
+	// Remove duplicates from items.
+	var sortedItems []*lr0Item
+	{
+		m := map[lr0ItemID]*lr0Item{}
+		for _, item := range items {
+			if !item.kernel {
+				return nil, fmt.Errorf("not a kernel item: %v", item)
+			}
+			m[item.id] = item
+		}
+		sortedItems = []*lr0Item{}
+		for _, item := range m {
+			sortedItems = append(sortedItems, item)
+		}
+		sort.Slice(sortedItems, func(i, j int) bool {
+			return sortedItems[i].id.num() < sortedItems[j].id.num()
+		})
+	}
+
+	var id kernelID
+	{
+		b := []byte{}
+		for _, item := range sortedItems {
+			b = append(b, item.id[:]...)
+		}
+		id = sha256.Sum256(b)
+	}
+
+	return &kernel{
+		id:    id,
+		items: sortedItems,
+	}, nil
+}
+
+type stateNum int
+
+const stateNumInitial = stateNum(0)
+
+func (n stateNum) Int() int {
+	return int(n)
+}
+
+func (n stateNum) String() string {
+	return strconv.Itoa(int(n))
+}
+
+func (n stateNum) next() stateNum {
+	return stateNum(n + 1)
+}
+
+type lr0State struct {
+	*kernel
+	num       stateNum
+	next      map[symbol]kernelID
+	reducible map[productionID]struct{}
+}
+
+type lr0Automaton struct {
+	initialState kernelID
+	states       map[kernelID]*lr0State
+}
+
+func genLR0Automaton(prods *productionSet, startSym symbol) (*lr0Automaton, error) {
+	if !startSym.isStart() {
+		return nil, fmt.Errorf("passed symbold is not a start symbol")
+	}
+
+	automaton := &lr0Automaton{
+		states: map[kernelID]*lr0State{},
+	}
+
+	currentState := stateNumInitial
+	knownKernels := map[kernelID]struct{}{}
+	uncheckedKernels := []*kernel{}
+
+	// Generate an initial kernel.
+	{
+		prods, _ := prods.findByLHS(startSym)
+		initialItem, err := newLR0Item(prods[0], 0)
+		if err != nil {
+			return nil, err
+		}
+
+		k, err := newKernel([]*lr0Item{initialItem})
+		if err != nil {
+			return nil, err
+		}
+
+		automaton.initialState = k.id
+		knownKernels[k.id] = struct{}{}
+		uncheckedKernels = append(uncheckedKernels, k)
+	}
+
+	for len(uncheckedKernels) > 0 {
+		nextUncheckedKernels := []*kernel{}
+		for _, k := range uncheckedKernels {
+			state, neighbours, err := genStateAndNeighbourKernels(k, prods)
+			if err != nil {
+				return nil, err
+			}
+			state.num = currentState
+			currentState = currentState.next()
+
+			automaton.states[state.id] = state
+
+			for _, k := range neighbours {
+				if _, known := knownKernels[k.id]; known {
+					continue
+				}
+				knownKernels[k.id] = struct{}{}
+				nextUncheckedKernels = append(nextUncheckedKernels, k)
+			}
+		}
+		uncheckedKernels = nextUncheckedKernels
+	}
+
+	return automaton, nil
+}
+
+func genStateAndNeighbourKernels(k *kernel, prods *productionSet) (*lr0State, []*kernel, error) {
+	items, err := genClosure(k, prods)
+	if err != nil {
+		return nil, nil, err
+	}
+	neighbours, err := genNeighbourKernels(items, prods)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	next := map[symbol]kernelID{}
+	kernels := []*kernel{}
+	for _, n := range neighbours {
+		next[n.symbol] = n.kernel.id
+		kernels = append(kernels, n.kernel)
+	}
+
+	reducible := map[productionID]struct{}{}
+	for _, item := range items {
+		if item.reducible {
+			reducible[item.prod] = struct{}{}
+		}
+	}
+
+	return &lr0State{
+		kernel:    k,
+		next:      next,
+		reducible: reducible,
+	}, kernels, nil
+}
+
+func genClosure(k *kernel, prods *productionSet) ([]*lr0Item, error) {
+	items := []*lr0Item{}
+	knownItems := map[lr0ItemID]struct{}{}
+	uncheckedItems := []*lr0Item{}
+	for _, item := range k.items {
+		items = append(items, item)
+		uncheckedItems = append(uncheckedItems, item)
+	}
+	for len(uncheckedItems) > 0 {
+		nextUncheckedItems := []*lr0Item{}
+		for _, item := range uncheckedItems {
+			if item.dottedSymbol.isTerminal() {
+				continue
+			}
+
+			ps, _ := prods.findByLHS(item.dottedSymbol)
+			for _, prod := range ps {
+				item, err := newLR0Item(prod, 0)
+				if err != nil {
+					return nil, err
+				}
+				if _, exist := knownItems[item.id]; exist {
+					continue
+				}
+				items = append(items, item)
+				knownItems[item.id] = struct{}{}
+				nextUncheckedItems = append(nextUncheckedItems, item)
+			}
+		}
+		uncheckedItems = nextUncheckedItems
+	}
+
+	return items, nil
+}
+
+type neighbourKernel struct {
+	symbol symbol
+	kernel *kernel
+}
+
+func genNeighbourKernels(items []*lr0Item, prods *productionSet) ([]*neighbourKernel, error) {
+	kItemMap := map[symbol][]*lr0Item{}
+	for _, item := range items {
+		if item.dottedSymbol.isNil() {
+			continue
+		}
+		prod, ok := prods.findByID(item.prod)
+		if !ok {
+			return nil, fmt.Errorf("a production was not found: %v", item.prod)
+		}
+		kItem, err := newLR0Item(prod, item.dot+1)
+		if err != nil {
+			return nil, err
+		}
+		kItemMap[item.dottedSymbol] = append(kItemMap[item.dottedSymbol], kItem)
+	}
+
+	nextSyms := []symbol{}
+	for sym := range kItemMap {
+		nextSyms = append(nextSyms, sym)
+	}
+	sort.Slice(nextSyms, func(i, j int) bool {
+		return nextSyms[i] < nextSyms[j]
+	})
+
+	kernels := []*neighbourKernel{}
+	for _, sym := range nextSyms {
+		k, err := newKernel(kItemMap[sym])
+		if err != nil {
+			return nil, err
+		}
+		kernels = append(kernels, &neighbourKernel{
+			symbol: sym,
+			kernel: k,
+		})
+	}
+
+	return kernels, nil
+}
diff --git a/grammar/lr0_item_test.go b/grammar/lr0_item_test.go
new file mode 100644
index 0000000..c04ce13
--- /dev/null
+++ b/grammar/lr0_item_test.go
@@ -0,0 +1,263 @@
+package grammar
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"github.com/nihei9/vartan/spec"
+)
+
+func TestGenLR0Automaton(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_]*";
+`
+
+	ast, err := spec.Parse(strings.NewReader(src))
+	if err != nil {
+		t.Fatal(err)
+	}
+	gram, err := NewGrammar(ast)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	automaton, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol)
+	if err != nil {
+		t.Fatalf("failed to create a LR0 automaton: %v", err)
+	}
+	if automaton == nil {
+		t.Fatalf("genLR0Automaton 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][]*lr0Item{
+		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 := []expectedLR0State{
+		{
+			kernelItems: expectedKernels[0],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("expr"):    expectedKernels[1],
+				genSym("term"):    expectedKernels[2],
+				genSym("factor"):  expectedKernels[3],
+				genSym("l_paren"): expectedKernels[4],
+				genSym("id"):      expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[1],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("add"): expectedKernels[6],
+			},
+			reducibleProds: []*production{
+				genProd("expr'", "expr"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[2],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("mul"): expectedKernels[7],
+			},
+			reducibleProds: []*production{
+				genProd("expr", "term"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[3],
+			nextStates:  map[symbol][]*lr0Item{},
+			reducibleProds: []*production{
+				genProd("term", "factor"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[4],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("expr"):    expectedKernels[8],
+				genSym("term"):    expectedKernels[2],
+				genSym("factor"):  expectedKernels[3],
+				genSym("l_paren"): expectedKernels[4],
+				genSym("id"):      expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[5],
+			nextStates:  map[symbol][]*lr0Item{},
+			reducibleProds: []*production{
+				genProd("factor", "id"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[6],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("term"):    expectedKernels[9],
+				genSym("factor"):  expectedKernels[3],
+				genSym("l_paren"): expectedKernels[4],
+				genSym("id"):      expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[7],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("factor"):  expectedKernels[10],
+				genSym("l_paren"): expectedKernels[4],
+				genSym("id"):      expectedKernels[5],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[8],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("add"):     expectedKernels[6],
+				genSym("r_paren"): expectedKernels[11],
+			},
+			reducibleProds: []*production{},
+		},
+		{
+			kernelItems: expectedKernels[9],
+			nextStates: map[symbol][]*lr0Item{
+				genSym("mul"): expectedKernels[7],
+			},
+			reducibleProds: []*production{
+				genProd("expr", "expr", "add", "term"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[10],
+			nextStates:  map[symbol][]*lr0Item{},
+			reducibleProds: []*production{
+				genProd("term", "term", "mul", "factor"),
+			},
+		},
+		{
+			kernelItems: expectedKernels[11],
+			nextStates:  map[symbol][]*lr0Item{},
+			reducibleProds: []*production{
+				genProd("factor", "l_paren", "expr", "r_paren"),
+			},
+		},
+	}
+
+	if len(automaton.states) != len(expectedStates) {
+		t.Errorf("state count is mismatched; want: %v, got: %v", len(expectedStates), len(automaton.states))
+	}
+
+	for i, eState := range expectedStates {
+		t.Run(fmt.Sprintf("state #%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("a kernel was not found: %v", k.id)
+			}
+
+			// test next states
+			{
+				if len(state.next) != len(eState.nextStates) {
+					t.Errorf("next state count is mismcthed; want: %v, got: %v", len(eState.nextStates), len(state.next))
+				}
+				for eSym, eKItems := range eState.nextStates {
+					nextStateKernel, err := newKernel(eKItems)
+					if err != nil {
+						t.Fatalf("failed to create a kernel item: %v", err)
+					}
+					nextState, ok := state.next[eSym]
+					if !ok {
+						t.Fatalf("next state was not found; state: %v, symbol: %v (%v)", state.id, "expr", eSym)
+					}
+					if nextState != nextStateKernel.id {
+						t.Fatalf("a kernel ID of the next state is mismatched; want: %v, got: %v", nextStateKernel.id, nextState)
+					}
+				}
+			}
+
+			// test reducible productions
+			{
+				if len(state.reducible) != len(eState.reducibleProds) {
+					t.Errorf("reducible production count is mismatched; want: %v, got: %v", len(eState.reducibleProds), len(state.reducible))
+				}
+				for _, eProd := range eState.reducibleProds {
+					if _, ok := state.reducible[eProd.id]; !ok {
+						t.Errorf("reducible production was not found: %v", eProd.id)
+					}
+				}
+			}
+		})
+	}
+}
+
+type expectedLR0State struct {
+	kernelItems    []*lr0Item
+	nextStates     map[symbol][]*lr0Item
+	reducibleProds []*production
+}
diff --git a/grammar/slr.go b/grammar/slr.go
new file mode 100644
index 0000000..a3ce803
--- /dev/null
+++ b/grammar/slr.go
@@ -0,0 +1,170 @@
+package grammar
+
+import (
+	"fmt"
+)
+
+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 ParsingTable struct {
+	actionTable      []actionEntry
+	goToTable        []goToEntry
+	stateCount       int
+	terminalCount    int
+	nonTerminalCount 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) error {
+	pos := state.Int()*t.terminalCount + sym.num().Int()
+	act := t.actionTable[pos]
+	if !act.isEmpty() {
+		ty, _, _ := act.describe()
+		if ty == ActionTypeReduce {
+			return fmt.Errorf("shift/reduce conflict")
+		}
+	}
+	t.actionTable[pos] = newShiftActionEntry(nextState)
+
+	return nil
+}
+
+func (t *ParsingTable) writeReduceAction(state stateNum, sym symbol, prod productionNum) error {
+	pos := state.Int()*t.terminalCount + sym.num().Int()
+	act := t.actionTable[pos]
+	if !act.isEmpty() {
+		ty, _, p := act.describe()
+		if ty == ActionTypeReduce && p != prod {
+			return fmt.Errorf("reduce/reduce conflict")
+		}
+		return fmt.Errorf("shift/reduce conflict")
+	}
+	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)
+}
+
+func genSLRParsingTable(automaton *lr0Automaton, prods *productionSet, follow *followSet, termCount, nonTermCount int) (*ParsingTable, error) {
+	var ptab *ParsingTable
+	{
+		initialState := automaton.states[automaton.initialState]
+		ptab = &ParsingTable{
+			actionTable:      make([]actionEntry, len(automaton.states)*termCount),
+			goToTable:        make([]goToEntry, len(automaton.states)*nonTermCount),
+			stateCount:       len(automaton.states),
+			terminalCount:    termCount,
+			nonTerminalCount: nonTermCount,
+			InitialState:     initialState.num,
+		}
+	}
+
+	for _, state := range automaton.states {
+		for sym, kID := range state.next {
+			nextState := automaton.states[kID]
+			if sym.isTerminal() {
+				err := ptab.writeShiftAction(state.num, sym, nextState.num)
+				if err != nil {
+					return nil, err
+				}
+			} else {
+				ptab.writeGoTo(state.num, sym, nextState.num)
+			}
+		}
+
+		for prodID := range state.reducible {
+			prod, _ := prods.findByID(prodID)
+			flw, err := follow.find(prod.lhs)
+			if err != nil {
+				return nil, err
+			}
+			for sym := range flw.symbols {
+				err := ptab.writeReduceAction(state.num, sym, prod.num)
+				if err != nil {
+					return nil, err
+				}
+			}
+			if flw.eof {
+				err := ptab.writeReduceAction(state.num, symbolEOF, prod.num)
+				if err != nil {
+					return nil, err
+				}
+			}
+		}
+	}
+
+	return ptab, nil
+}
diff --git a/grammar/slr_test.go b/grammar/slr_test.go
new file mode 100644
index 0000000..089b73b
--- /dev/null
+++ b/grammar/slr_test.go
@@ -0,0 +1,481 @@
+package grammar
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"github.com/nihei9/vartan/spec"
+)
+
+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)
+		}
+		gram, err = NewGrammar(ast)
+		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.getNonTerminalTexts()
+		if err != nil {
+			t.Fatal(err)
+		}
+		termTexts, err := gram.symbolTable.getTerminalTexts()
+		if err != nil {
+			t.Fatal(err)
+		}
+		nonTermCount = len(nonTermTexts)
+		termCount = len(termTexts)
+
+		ptab, err = genSLRParsingTable(automaton, gram.productionSet, follow, termCount, nonTermCount)
+		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][]*lr0Item{
+		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 []*lr0Item
+		acts        map[symbol]testActionEntry
+		goTos       map[symbol][]*lr0Item
+	}{
+		{
+			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][]*lr0Item{
+				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][]*lr0Item{
+				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][]*lr0Item{
+				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][]*lr0Item{
+				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)
+			}
+
+			// 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)
+					}
+				}
+			}
+		})
+	}
+}
+
+type testActionEntry struct {
+	ty         ActionType
+	nextState  []*lr0Item
+	production *production
+}
+
+func findStateByNum(states map[kernelID]*lr0State, num stateNum) *lr0State {
+	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/test_helper_test.go b/grammar/test_helper_test.go
new file mode 100644
index 0000000..8f5c372
--- /dev/null
+++ b/grammar/test_helper_test.go
@@ -0,0 +1,52 @@
+package grammar
+
+import "testing"
+
+type testSymbolGenerator func(text string) symbol
+
+func newTestSymbolGenerator(t *testing.T, symTab *symbolTable) testSymbolGenerator {
+	return func(text string) symbol {
+		t.Helper()
+
+		sym, ok := symTab.toSymbol(text)
+		if !ok {
+			t.Fatalf("symbol was not found: %v", text)
+		}
+		return sym
+	}
+}
+
+type testProductionGenerator func(lhs string, rhs ...string) *production
+
+func newTestProductionGenerator(t *testing.T, genSym testSymbolGenerator) testProductionGenerator {
+	return func(lhs string, rhs ...string) *production {
+		t.Helper()
+
+		rhsSym := []symbol{}
+		for _, text := range rhs {
+			rhsSym = append(rhsSym, genSym(text))
+		}
+		prod, err := newProduction(genSym(lhs), rhsSym)
+		if err != nil {
+			t.Fatalf("failed to create a production: %v", err)
+		}
+
+		return prod
+	}
+}
+
+type testLR0ItemGenerator func(lhs string, dot int, rhs ...string) *lr0Item
+
+func newTestLR0ItemGenerator(t *testing.T, genProd testProductionGenerator) testLR0ItemGenerator {
+	return func(lhs string, dot int, rhs ...string) *lr0Item {
+		t.Helper()
+
+		prod := genProd(lhs, rhs...)
+		item, err := newLR0Item(prod, dot)
+		if err != nil {
+			t.Fatalf("failed to create a LR0 item: %v", err)
+		}
+
+		return item
+	}
+}