Add a new DFA compiler that generates DFA from a set of CPTree

6 files changed, 1402 insertions, 0 deletions

diff --git a/compiler/dfa/dfa.go b/compiler/dfa/dfa.go
new file mode 100644
index 0000000..c56af90
--- /dev/null
+++ b/compiler/dfa/dfa.go
@@ -0,0 +1,173 @@
+package dfa
+
+import (
+	"sort"
+
+	"github.com/nihei9/maleeni/spec"
+)
+
+type symbolTable struct {
+	symPos2Byte map[symbolPosition]byteRange
+	endPos2ID   map[symbolPosition]spec.LexModeKindID
+}
+
+func genSymbolTable(root byteTree) *symbolTable {
+	symTab := &symbolTable{
+		symPos2Byte: map[symbolPosition]byteRange{},
+		endPos2ID:   map[symbolPosition]spec.LexModeKindID{},
+	}
+	return genSymTab(symTab, root)
+}
+
+func genSymTab(symTab *symbolTable, node byteTree) *symbolTable {
+	if node == nil {
+		return symTab
+	}
+
+	switch n := node.(type) {
+	case *symbolNode:
+		symTab.symPos2Byte[n.pos] = byteRange{
+			from: n.from,
+			to:   n.to,
+		}
+	case *endMarkerNode:
+		symTab.endPos2ID[n.pos] = n.id
+	default:
+		left, right := node.children()
+		genSymTab(symTab, left)
+		genSymTab(symTab, right)
+	}
+	return symTab
+}
+
+type DFA struct {
+	States               []string
+	InitialState         string
+	AcceptingStatesTable map[string]spec.LexModeKindID
+	TransitionTable      map[string][256]string
+}
+
+func GenDFA(root byteTree, symTab *symbolTable) *DFA {	
+	initialState := root.first()
+	initialStateHash := initialState.hash()
+	stateMap := map[string]*symbolPositionSet{
+		initialStateHash: initialState,
+	}
+	tranTab := map[string][256]string{}
+	{
+		follow := genFollowTable(root)
+		unmarkedStates := map[string]*symbolPositionSet{
+			initialStateHash: initialState,
+		}
+		for len(unmarkedStates) > 0 {
+			nextUnmarkedStates := map[string]*symbolPositionSet{}
+			for hash, state := range unmarkedStates {
+				tranTabOfState := [256]*symbolPositionSet{}
+				for _, pos := range state.set() {
+					if pos.isEndMark() {
+						continue
+					}
+					valRange := symTab.symPos2Byte[pos]
+					for symVal := valRange.from; symVal <= valRange.to; symVal++ {
+						if tranTabOfState[symVal] == nil {
+							tranTabOfState[symVal] = newSymbolPositionSet()
+						}
+						tranTabOfState[symVal].merge(follow[pos])
+					}
+				}
+				for _, t := range tranTabOfState {
+					if t == nil {
+						continue
+					}
+					h := t.hash()
+					if _, ok := stateMap[h]; ok {
+						continue
+					}
+					stateMap[h] = t
+					nextUnmarkedStates[h] = t
+				}
+				tabOfState := [256]string{}
+				for v, t := range tranTabOfState {
+					if t == nil {
+						continue
+					}
+					tabOfState[v] = t.hash()
+				}
+				tranTab[hash] = tabOfState
+			}
+			unmarkedStates = nextUnmarkedStates
+		}
+	}
+
+	accTab := map[string]spec.LexModeKindID{}
+	{
+		for h, s := range stateMap {
+			for _, pos := range s.set() {
+				if !pos.isEndMark() {
+					continue
+				}
+				priorID, ok := accTab[h]
+				if !ok {
+					accTab[h] = symTab.endPos2ID[pos]
+				} else {
+					id := symTab.endPos2ID[pos]
+					if id < priorID {
+						accTab[h] = id
+					}
+				}
+			}
+		}
+	}
+
+	var states []string
+	{
+		for s := range stateMap {
+			states = append(states, s)
+		}
+		sort.Slice(states, func(i, j int) bool {
+			return states[i] < states[j]
+		})
+	}
+
+	return &DFA{
+		States:               states,
+		InitialState:         initialStateHash,
+		AcceptingStatesTable: accTab,
+		TransitionTable:      tranTab,
+	}
+}
+
+func GenTransitionTable(dfa *DFA) (*spec.TransitionTable, error) {
+	stateHash2ID := map[string]spec.StateID{}
+	for i, s := range dfa.States {
+		// Since 0 represents an invalid value in a transition table,
+		// assign a number greater than or equal to 1 to states.
+		stateHash2ID[s] = spec.StateID(i + spec.StateIDMin.Int())
+	}
+
+	acc := make([]spec.LexModeKindID, len(dfa.States)+1)
+	for _, s := range dfa.States {
+		id, ok := dfa.AcceptingStatesTable[s]
+		if !ok {
+			continue
+		}
+		acc[stateHash2ID[s]] = id
+	}
+
+	rowCount := len(dfa.States) + 1
+	colCount := 256
+	tran := make([]spec.StateID, rowCount*colCount)
+	for s, tab := range dfa.TransitionTable {
+		for v, to := range tab {
+			tran[stateHash2ID[s].Int()*256+v] = stateHash2ID[to]
+		}
+	}
+
+	return &spec.TransitionTable{
+		InitialStateID:         stateHash2ID[dfa.InitialState],
+		AcceptingStates:        acc,
+		UncompressedTransition: tran,
+		RowCount:               rowCount,
+		ColCount:               colCount,
+	}, nil
+}
diff --git a/compiler/dfa/dfa_test.go b/compiler/dfa/dfa_test.go
new file mode 100644
index 0000000..dcf63db
--- /dev/null
+++ b/compiler/dfa/dfa_test.go
@@ -0,0 +1,121 @@
+package dfa
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/nihei9/maleeni/compiler/parser"
+	"github.com/nihei9/maleeni/spec"
+)
+
+func TestGenDFA(t *testing.T) {
+	p := parser.NewParser(spec.LexKindName("test"), strings.NewReader("(a|b)*abb"))
+	cpt, err := p.Parse()
+	if err != nil {
+		t.Fatal(err)
+	}
+	bt, symTab, err := ConvertCPTreeToByteTree(map[spec.LexModeKindID]parser.CPTree{
+		spec.LexModeKindIDMin: cpt,
+	})
+	if err != nil {
+		t.Fatal(err)
+	}
+	dfa := GenDFA(bt, symTab)
+	if dfa == nil {
+		t.Fatalf("DFA is nil")
+	}
+
+	symPos := func(n uint16) symbolPosition {
+		pos, err := newSymbolPosition(n, false)
+		if err != nil {
+			panic(err)
+		}
+		return pos
+	}
+
+	endPos := func(n uint16) symbolPosition {
+		pos, err := newSymbolPosition(n, true)
+		if err != nil {
+			panic(err)
+		}
+		return pos
+	}
+
+	s0 := newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3))
+	s1 := newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3)).add(symPos(4))
+	s2 := newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3)).add(symPos(5))
+	s3 := newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3)).add(endPos(6))
+
+	rune2Int := func(char rune, index int) uint8 {
+		return uint8([]byte(string(char))[index])
+	}
+
+	tranS0 := [256]string{}
+	tranS0[rune2Int('a', 0)] = s1.hash()
+	tranS0[rune2Int('b', 0)] = s0.hash()
+
+	tranS1 := [256]string{}
+	tranS1[rune2Int('a', 0)] = s1.hash()
+	tranS1[rune2Int('b', 0)] = s2.hash()
+
+	tranS2 := [256]string{}
+	tranS2[rune2Int('a', 0)] = s1.hash()
+	tranS2[rune2Int('b', 0)] = s3.hash()
+
+	tranS3 := [256]string{}
+	tranS3[rune2Int('a', 0)] = s1.hash()
+	tranS3[rune2Int('b', 0)] = s0.hash()
+
+	expectedTranTab := map[string][256]string{
+		s0.hash(): tranS0,
+		s1.hash(): tranS1,
+		s2.hash(): tranS2,
+		s3.hash(): tranS3,
+	}
+	if len(dfa.TransitionTable) != len(expectedTranTab) {
+		t.Errorf("transition table is mismatched: want: %v entries, got: %v entries", len(expectedTranTab), len(dfa.TransitionTable))
+	}
+	for h, eTranTab := range expectedTranTab {
+		tranTab, ok := dfa.TransitionTable[h]
+		if !ok {
+			t.Errorf("no entry; hash: %v", h)
+			continue
+		}
+		if len(tranTab) != len(eTranTab) {
+			t.Errorf("transition table is mismatched: hash: %v, want: %v entries, got: %v entries", h, len(eTranTab), len(tranTab))
+		}
+		for c, eNext := range eTranTab {
+			if eNext == "" {
+				continue
+			}
+
+			next := tranTab[c]
+			if next == "" {
+				t.Errorf("no enatry: hash: %v, char: %v", h, c)
+			}
+			if next != eNext {
+				t.Errorf("next state is mismatched: want: %v, got: %v", eNext, next)
+			}
+		}
+	}
+
+	if dfa.InitialState != s0.hash() {
+		t.Errorf("initial state is mismatched: want: %v, got: %v", s0.hash(), dfa.InitialState)
+	}
+
+	accTab := map[string]spec.LexModeKindID{
+		s3.hash(): 1,
+	}
+	if len(dfa.AcceptingStatesTable) != len(accTab) {
+		t.Errorf("accepting states are mismatched: want: %v entries, got: %v entries", len(accTab), len(dfa.AcceptingStatesTable))
+	}
+	for eState, eID := range accTab {
+		id, ok := dfa.AcceptingStatesTable[eState]
+		if !ok {
+			t.Errorf("accepting state is not found: state: %v", eState)
+		}
+		if id != eID {
+			t.Errorf("ID is mismatched: state: %v, want: %v, got: %v", eState, eID, id)
+		}
+	}
+}
diff --git a/compiler/dfa/symbol_position.go b/compiler/dfa/symbol_position.go
new file mode 100644
index 0000000..10d5a1e
--- /dev/null
+++ b/compiler/dfa/symbol_position.go
@@ -0,0 +1,198 @@
+package dfa
+
+import (
+	"encoding/binary"
+	"fmt"
+	"strings"
+)
+
+type symbolPosition uint16
+
+const (
+	symbolPositionNil symbolPosition = 0x0000
+
+	symbolPositionMin uint16 = 0x0001
+	symbolPositionMax uint16 = 0x7fff
+
+	symbolPositionMaskSymbol  uint16 = 0x0000
+	symbolPositionMaskEndMark uint16 = 0x8000
+
+	symbolPositionMaskValue uint16 = 0x7fff
+)
+
+func newSymbolPosition(n uint16, endMark bool) (symbolPosition, error) {
+	if n < symbolPositionMin || n > symbolPositionMax {
+		return symbolPositionNil, fmt.Errorf("symbol position must be within %v to %v: n: %v, endMark: %v", symbolPositionMin, symbolPositionMax, n, endMark)
+	}
+	if endMark {
+		return symbolPosition(n | symbolPositionMaskEndMark), nil
+	}
+	return symbolPosition(n | symbolPositionMaskSymbol), nil
+}
+
+func (p symbolPosition) String() string {
+	if p.isEndMark() {
+		return fmt.Sprintf("end#%v", uint16(p)&symbolPositionMaskValue)
+	}
+	return fmt.Sprintf("sym#%v", uint16(p)&symbolPositionMaskValue)
+}
+
+func (p symbolPosition) isEndMark() bool {
+	if uint16(p)&symbolPositionMaskEndMark > 1 {
+		return true
+	}
+	return false
+}
+
+func (p symbolPosition) describe() (uint16, bool) {
+	v := uint16(p) & symbolPositionMaskValue
+	if p.isEndMark() {
+		return v, true
+	}
+	return v, false
+}
+
+type symbolPositionSet struct {
+	// `s` represents a set of symbol positions.
+	// However, immediately after adding a symbol position, the elements may be duplicated.
+	// When you need an aligned set with no duplicates, you can get such value via the set function.
+	s      []symbolPosition
+	sorted bool
+}
+
+func newSymbolPositionSet() *symbolPositionSet {
+	return &symbolPositionSet{
+		s:      []symbolPosition{},
+		sorted: false,
+	}
+}
+
+func (s *symbolPositionSet) String() string {
+	if len(s.s) <= 0 {
+		return "{}"
+	}
+	ps := s.sortAndRemoveDuplicates()
+	var b strings.Builder
+	fmt.Fprintf(&b, "{")
+	for i, p := range ps {
+		if i <= 0 {
+			fmt.Fprintf(&b, "%v", p)
+			continue
+		}
+		fmt.Fprintf(&b, ", %v", p)
+	}
+	fmt.Fprintf(&b, "}")
+	return b.String()
+}
+
+func (s *symbolPositionSet) set() []symbolPosition {
+	s.sortAndRemoveDuplicates()
+	return s.s
+}
+
+func (s *symbolPositionSet) add(pos symbolPosition) *symbolPositionSet {
+	s.s = append(s.s, pos)
+	s.sorted = false
+	return s
+}
+
+func (s *symbolPositionSet) merge(t *symbolPositionSet) *symbolPositionSet {
+	s.s = append(s.s, t.s...)
+	s.sorted = false
+	return s
+}
+
+func (s *symbolPositionSet) intersect(set *symbolPositionSet) *symbolPositionSet {
+	in := newSymbolPositionSet()
+	for _, p1 := range s.s {
+		for _, p2 := range set.s {
+			if p1 != p2 {
+				continue
+			}
+			in.add(p1)
+		}
+	}
+	return in
+}
+
+func (s *symbolPositionSet) hash() string {
+	if len(s.s) <= 0 {
+		return ""
+	}
+	sorted := s.sortAndRemoveDuplicates()
+	var buf []byte
+	for _, p := range sorted {
+		b := make([]byte, 8)
+		binary.PutUvarint(b, uint64(p))
+		buf = append(buf, b...)
+	}
+	// Convert to a string to be able to use it as a key of a map.
+	// But note this byte sequence is made from values of symbol positions,
+	// so this is not a well-formed UTF-8 sequence.
+	return string(buf)
+}
+
+func (s *symbolPositionSet) sortAndRemoveDuplicates() []symbolPosition {
+	if s.sorted {
+		return s.s
+	}
+
+	sortSymbolPositions(s.s, 0, len(s.s)-1)
+
+	// Remove duplicates.
+	lastV := s.s[0]
+	nextIdx := 1
+	for _, v := range s.s[1:] {
+		if v == lastV {
+			continue
+		}
+		s.s[nextIdx] = v
+		nextIdx++
+		lastV = v
+	}
+	s.s = s.s[:nextIdx]
+	s.sorted = true
+
+	return s.s
+}
+
+// sortSymbolPositions sorts a slice of symbol positions as it uses quick sort.
+func sortSymbolPositions(ps []symbolPosition, left, right int) {
+	if left >= right {
+		return
+	}
+	var pivot symbolPosition
+	{
+		// Use a median as a pivot.
+		p1 := ps[left]
+		p2 := ps[(left+right)/2]
+		p3 := ps[right]
+		if p1 > p2 {
+			p1, p2 = p2, p1
+		}
+		if p2 > p3 {
+			p2, p3 = p3, p2
+			if p1 > p2 {
+				p1, p2 = p2, p1
+			}
+		}
+		pivot = p2
+	}
+	i := left
+	j := right
+	for i <= j {
+		for ps[i] < pivot {
+			i++
+		}
+		for ps[j] > pivot {
+			j--
+		}
+		if i <= j {
+			ps[i], ps[j] = ps[j], ps[i]
+			i++
+			j--
+		}
+	}
+	sortSymbolPositions(ps, left, j)
+	sortSymbolPositions(ps, i, right)
+}
diff --git a/compiler/dfa/symbol_position_test.go b/compiler/dfa/symbol_position_test.go
new file mode 100644
index 0000000..c867f64
--- /dev/null
+++ b/compiler/dfa/symbol_position_test.go
@@ -0,0 +1,79 @@
+package dfa
+
+import (
+	"fmt"
+	"testing"
+)
+
+func TestNewSymbolPosition(t *testing.T) {
+	tests := []struct {
+		n       uint16
+		endMark bool
+		err     bool
+	}{
+		{
+			n:       0,
+			endMark: false,
+			err:     true,
+		},
+		{
+			n:       0,
+			endMark: true,
+			err:     true,
+		},
+		{
+			n:       symbolPositionMin - 1,
+			endMark: false,
+			err:     true,
+		},
+		{
+			n:       symbolPositionMin - 1,
+			endMark: true,
+			err:     true,
+		},
+		{
+			n:       symbolPositionMin,
+			endMark: false,
+		},
+		{
+			n:       symbolPositionMin,
+			endMark: true,
+		},
+		{
+			n:       symbolPositionMax,
+			endMark: false,
+		},
+		{
+			n:       symbolPositionMax,
+			endMark: true,
+		},
+		{
+			n:       symbolPositionMax + 1,
+			endMark: false,
+			err:     true,
+		},
+		{
+			n:       symbolPositionMax + 1,
+			endMark: true,
+			err:     true,
+		},
+	}
+	for i, tt := range tests {
+		t.Run(fmt.Sprintf("#%v n: %v, endMark: %v", i, tt.n, tt.endMark), func(t *testing.T) {
+			pos, err := newSymbolPosition(tt.n, tt.endMark)
+			if tt.err {
+				if err == nil {
+					t.Fatal("err is nil")
+				}
+				return
+			}
+			if err != nil {
+				t.Fatal(err)
+			}
+			n, endMark := pos.describe()
+			if n != tt.n || endMark != tt.endMark {
+				t.Errorf("unexpected symbol position: want: n: %v, endMark: %v, got: n: %v, endMark: %v", tt.n, tt.endMark, n, endMark)
+			}
+		})
+	}
+}
diff --git a/compiler/dfa/tree.go b/compiler/dfa/tree.go
new file mode 100644
index 0000000..ab75eae
--- /dev/null
+++ b/compiler/dfa/tree.go
@@ -0,0 +1,571 @@
+package dfa
+
+import (
+	"fmt"
+	"io"
+	"sort"
+
+	"github.com/nihei9/maleeni/compiler/parser"
+	"github.com/nihei9/maleeni/spec"
+	"github.com/nihei9/maleeni/utf8"
+)
+
+type byteTree interface {
+	fmt.Stringer
+	children() (byteTree, byteTree)
+	nullable() bool
+	first() *symbolPositionSet
+	last() *symbolPositionSet
+	clone() byteTree
+}
+
+var (
+	_ byteTree = &symbolNode{}
+	_ byteTree = &endMarkerNode{}
+	_ byteTree = &concatNode{}
+	_ byteTree = &altNode{}
+	_ byteTree = &repeatNode{}
+	_ byteTree = &optionNode{}
+)
+
+type byteRange struct {
+	from byte
+	to   byte
+}
+
+type symbolNode struct {
+	byteRange
+	pos       symbolPosition
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newSymbolNode(value byte) *symbolNode {
+	return &symbolNode{
+		byteRange: byteRange{
+			from: value,
+			to:   value,
+		},
+		pos: symbolPositionNil,
+	}
+}
+
+func newRangeSymbolNode(from, to byte) *symbolNode {
+	return &symbolNode{
+		byteRange: byteRange{
+			from: from,
+			to:   to,
+		},
+		pos: symbolPositionNil,
+	}
+}
+
+func (n *symbolNode) String() string {
+	return fmt.Sprintf("symbol: value: %v-%v, pos: %v", n.from, n.to, n.pos)
+}
+
+func (n *symbolNode) children() (byteTree, byteTree) {
+	return nil, nil
+}
+
+func (n *symbolNode) nullable() bool {
+	return false
+}
+
+func (n *symbolNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.add(n.pos)
+	}
+	return n.firstMemo
+}
+
+func (n *symbolNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.add(n.pos)
+	}
+	return n.lastMemo
+}
+
+func (n *symbolNode) clone() byteTree {
+	return newRangeSymbolNode(n.from, n.to)
+}
+
+type endMarkerNode struct {
+	id        spec.LexModeKindID
+	pos       symbolPosition
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newEndMarkerNode(id spec.LexModeKindID) *endMarkerNode {
+	return &endMarkerNode{
+		id:  id,
+		pos: symbolPositionNil,
+	}
+}
+
+func (n *endMarkerNode) String() string {
+	return fmt.Sprintf("end: pos: %v", n.pos)
+}
+
+func (n *endMarkerNode) children() (byteTree, byteTree) {
+	return nil, nil
+}
+
+func (n *endMarkerNode) nullable() bool {
+	return false
+}
+
+func (n *endMarkerNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.add(n.pos)
+	}
+	return n.firstMemo
+}
+
+func (n *endMarkerNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.add(n.pos)
+	}
+	return n.lastMemo
+}
+
+func (n *endMarkerNode) clone() byteTree {
+	return newEndMarkerNode(n.id)
+}
+
+type concatNode struct {
+	left      byteTree
+	right     byteTree
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newConcatNode(left, right byteTree) *concatNode {
+	return &concatNode{
+		left:  left,
+		right: right,
+	}
+}
+
+func (n *concatNode) String() string {
+	return fmt.Sprintf("concat")
+}
+
+func (n *concatNode) children() (byteTree, byteTree) {
+	return n.left, n.right
+}
+
+func (n *concatNode) nullable() bool {
+	return n.left.nullable() && n.right.nullable()
+}
+
+func (n *concatNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.merge(n.left.first())
+		if n.left.nullable() {
+			n.firstMemo.merge(n.right.first())
+		}
+		n.firstMemo.sortAndRemoveDuplicates()
+	}
+	return n.firstMemo
+}
+
+func (n *concatNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.merge(n.right.last())
+		if n.right.nullable() {
+			n.lastMemo.merge(n.left.last())
+		}
+		n.lastMemo.sortAndRemoveDuplicates()
+	}
+	return n.lastMemo
+}
+
+func (n *concatNode) clone() byteTree {
+	return newConcatNode(n.left.clone(), n.right.clone())
+}
+
+type altNode struct {
+	left      byteTree
+	right     byteTree
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newAltNode(left, right byteTree) *altNode {
+	return &altNode{
+		left:  left,
+		right: right,
+	}
+}
+
+func (n *altNode) String() string {
+	return fmt.Sprintf("alt")
+}
+
+func (n *altNode) children() (byteTree, byteTree) {
+	return n.left, n.right
+}
+
+func (n *altNode) nullable() bool {
+	return n.left.nullable() || n.right.nullable()
+}
+
+func (n *altNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.merge(n.left.first())
+		n.firstMemo.merge(n.right.first())
+		n.firstMemo.sortAndRemoveDuplicates()
+	}
+	return n.firstMemo
+}
+
+func (n *altNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.merge(n.left.last())
+		n.lastMemo.merge(n.right.last())
+		n.lastMemo.sortAndRemoveDuplicates()
+	}
+	return n.lastMemo
+}
+
+func (n *altNode) clone() byteTree {
+	return newAltNode(n.left.clone(), n.right.clone())
+}
+
+type repeatNode struct {
+	left      byteTree
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newRepeatNode(left byteTree) *repeatNode {
+	return &repeatNode{
+		left: left,
+	}
+}
+
+func (n *repeatNode) String() string {
+	return fmt.Sprintf("repeat")
+}
+
+func (n *repeatNode) children() (byteTree, byteTree) {
+	return n.left, nil
+}
+
+func (n *repeatNode) nullable() bool {
+	return true
+}
+
+func (n *repeatNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.merge(n.left.first())
+		n.firstMemo.sortAndRemoveDuplicates()
+	}
+	return n.firstMemo
+}
+
+func (n *repeatNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.merge(n.left.last())
+		n.lastMemo.sortAndRemoveDuplicates()
+	}
+	return n.lastMemo
+}
+
+func (n *repeatNode) clone() byteTree {
+	return newRepeatNode(n.left.clone())
+}
+
+func newRepeatOneOrMoreNode(left byteTree) *concatNode {
+	return newConcatNode(
+		left,
+		&repeatNode{
+			left: left.clone(),
+		})
+}
+
+type optionNode struct {
+	left      byteTree
+	firstMemo *symbolPositionSet
+	lastMemo  *symbolPositionSet
+}
+
+func newOptionNode(left byteTree) *optionNode {
+	return &optionNode{
+		left: left,
+	}
+}
+
+func (n *optionNode) String() string {
+	return fmt.Sprintf("option")
+}
+
+func (n *optionNode) children() (byteTree, byteTree) {
+	return n.left, nil
+}
+
+func (n *optionNode) nullable() bool {
+	return true
+}
+
+func (n *optionNode) first() *symbolPositionSet {
+	if n.firstMemo == nil {
+		n.firstMemo = newSymbolPositionSet()
+		n.firstMemo.merge(n.left.first())
+		n.firstMemo.sortAndRemoveDuplicates()
+	}
+	return n.firstMemo
+}
+
+func (n *optionNode) last() *symbolPositionSet {
+	if n.lastMemo == nil {
+		n.lastMemo = newSymbolPositionSet()
+		n.lastMemo.merge(n.left.last())
+		n.lastMemo.sortAndRemoveDuplicates()
+	}
+	return n.lastMemo
+}
+
+func (n *optionNode) clone() byteTree {
+	return newOptionNode(n.left.clone())
+}
+
+type followTable map[symbolPosition]*symbolPositionSet
+
+func genFollowTable(root byteTree) followTable {
+	follow := followTable{}
+	calcFollow(follow, root)
+	return follow
+}
+
+func calcFollow(follow followTable, ast byteTree) {
+	if ast == nil {
+		return
+	}
+	left, right := ast.children()
+	calcFollow(follow, left)
+	calcFollow(follow, right)
+	switch n := ast.(type) {
+	case *concatNode:
+		l, r := n.children()
+		for _, p := range l.last().set() {
+			if _, ok := follow[p]; !ok {
+				follow[p] = newSymbolPositionSet()
+			}
+			follow[p].merge(r.first())
+		}
+	case *repeatNode:
+		for _, p := range n.last().set() {
+			if _, ok := follow[p]; !ok {
+				follow[p] = newSymbolPositionSet()
+			}
+			follow[p].merge(n.first())
+		}
+	}
+}
+
+func positionSymbols(node byteTree, n uint16) (uint16, error) {
+	if node == nil {
+		return n, nil
+	}
+
+	l, r := node.children()
+	p := n
+	p, err := positionSymbols(l, p)
+	if err != nil {
+		return p, err
+	}
+	p, err = positionSymbols(r, p)
+	if err != nil {
+		return p, err
+	}
+	switch n := node.(type) {
+	case *symbolNode:
+		n.pos, err = newSymbolPosition(p, false)
+		if err != nil {
+			return p, err
+		}
+		p++
+	case *endMarkerNode:
+		n.pos, err = newSymbolPosition(p, true)
+		if err != nil {
+			return p, err
+		}
+		p++
+	}
+	node.first()
+	node.last()
+	return p, nil
+}
+
+func concat(ts ...byteTree) byteTree {
+	nonNilNodes := []byteTree{}
+	for _, t := range ts {
+		if t == nil {
+			continue
+		}
+		nonNilNodes = append(nonNilNodes, t)
+	}
+	if len(nonNilNodes) <= 0 {
+		return nil
+	}
+	if len(nonNilNodes) == 1 {
+		return nonNilNodes[0]
+	}
+	concat := newConcatNode(nonNilNodes[0], nonNilNodes[1])
+	for _, t := range nonNilNodes[2:] {
+		concat = newConcatNode(concat, t)
+	}
+	return concat
+}
+
+func oneOf(ts ...byteTree) byteTree {
+	nonNilNodes := []byteTree{}
+	for _, t := range ts {
+		if t == nil {
+			continue
+		}
+		nonNilNodes = append(nonNilNodes, t)
+	}
+	if len(nonNilNodes) <= 0 {
+		return nil
+	}
+	if len(nonNilNodes) == 1 {
+		return nonNilNodes[0]
+	}
+	alt := newAltNode(nonNilNodes[0], nonNilNodes[1])
+	for _, t := range nonNilNodes[2:] {
+		alt = newAltNode(alt, t)
+	}
+	return alt
+}
+
+func printByteTree(w io.Writer, t byteTree, ruledLine string, childRuledLinePrefix string, withAttrs bool) {
+	if t == nil {
+		return
+	}
+	fmt.Fprintf(w, "%v%v", ruledLine, t)
+	if withAttrs {
+		fmt.Fprintf(w, ", nullable: %v, first: %v, last: %v", t.nullable(), t.first(), t.last())
+	}
+	fmt.Fprintf(w, "\n")
+	left, right := t.children()
+	children := []byteTree{}
+	if left != nil {
+		children = append(children, left)
+	}
+	if right != nil {
+		children = append(children, right)
+	}
+	num := len(children)
+	for i, child := range children {
+		line := "└─ "
+		if num > 1 {
+			if i == 0 {
+				line = "├─ "
+			} else if i < num-1 {
+				line = "│  "
+			}
+		}
+		prefix := "│  "
+		if i >= num-1 {
+			prefix = "    "
+		}
+		printByteTree(w, child, childRuledLinePrefix+line, childRuledLinePrefix+prefix, withAttrs)
+	}
+}
+
+func ConvertCPTreeToByteTree(cpTrees map[spec.LexModeKindID]parser.CPTree) (byteTree, *symbolTable, error) {
+	var ids []spec.LexModeKindID
+	for id := range cpTrees {
+		ids = append(ids, id)
+	}
+	sort.Slice(ids, func(i, j int) bool {
+		return ids[i] < ids[j]
+	})
+
+	var bt byteTree
+	for _, id := range ids {
+		cpTree := cpTrees[id]
+		t, err := convCPTreeToByteTree(cpTree)
+		if err != nil {
+			return nil, nil, err
+		}
+		bt = oneOf(bt, concat(t, newEndMarkerNode(id)))
+	}
+	positionSymbols(bt, symbolPositionMin)
+
+	return bt, genSymbolTable(bt), nil
+}
+
+func convCPTreeToByteTree(cpTree parser.CPTree) (byteTree, error) {
+	if from, to, ok := cpTree.Range(); ok {
+		bs, err := utf8.GenCharBlocks([]byte(string(from)), []byte(string(to)))
+		if err != nil {
+			return nil, err
+		}
+		var a byteTree
+		for _, b := range bs {
+			var c byteTree
+			for i := 0; i < len(b.From); i++ {
+				c = concat(c, newRangeSymbolNode(b.From[i], b.To[i]))
+			}
+			a = oneOf(a, c)
+		}
+		return a, nil
+	}
+
+	if tree, ok := cpTree.Repeatable(); ok {
+		t, err := convCPTreeToByteTree(tree)
+		if err != nil {
+			return nil, err
+		}
+		return newRepeatNode(t), nil
+	}
+
+	if tree, ok := cpTree.Optional(); ok {
+		t, err := convCPTreeToByteTree(tree)
+		if err != nil {
+			return nil, err
+		}
+		return newOptionNode(t), nil
+	}
+
+	if left, right, ok := cpTree.Concatenation(); ok {
+		l, err := convCPTreeToByteTree(left)
+		if err != nil {
+			return nil, err
+		}
+		r, err := convCPTreeToByteTree(right)
+		if err != nil {
+			return nil, err
+		}
+		return newConcatNode(l, r), nil
+	}
+
+	if left, right, ok := cpTree.Alternatives(); ok {
+		l, err := convCPTreeToByteTree(left)
+		if err != nil {
+			return nil, err
+		}
+		r, err := convCPTreeToByteTree(right)
+		if err != nil {
+			return nil, err
+		}
+		return newAltNode(l, r), nil
+	}
+
+	return nil, fmt.Errorf("invalid tree type: %T", cpTree)
+}
diff --git a/compiler/dfa/tree_test.go b/compiler/dfa/tree_test.go
new file mode 100644
index 0000000..e37a69c
--- /dev/null
+++ b/compiler/dfa/tree_test.go
@@ -0,0 +1,260 @@
+package dfa
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"github.com/nihei9/maleeni/compiler/parser"
+	"github.com/nihei9/maleeni/spec"
+)
+
+func TestByteTree(t *testing.T) {
+	tests := []struct {
+		root     byteTree
+		nullable bool
+		first    *symbolPositionSet
+		last     *symbolPositionSet
+	}{
+		{
+			root:     newSymbolNodeWithPos(0, 1),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(1),
+		},
+		{
+			root:     newEndMarkerNodeWithPos(1, 1),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(1),
+		},
+		{
+			root: newConcatNode(
+				newSymbolNodeWithPos(0, 1),
+				newSymbolNodeWithPos(0, 2),
+			),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(2),
+		},
+		{
+			root: newConcatNode(
+				newRepeatNode(newSymbolNodeWithPos(0, 1)),
+				newSymbolNodeWithPos(0, 2),
+			),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(2),
+		},
+		{
+			root: newConcatNode(
+				newSymbolNodeWithPos(0, 1),
+				newRepeatNode(newSymbolNodeWithPos(0, 2)),
+			),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root: newConcatNode(
+				newRepeatNode(newSymbolNodeWithPos(0, 1)),
+				newRepeatNode(newSymbolNodeWithPos(0, 2)),
+			),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root: newAltNode(
+				newSymbolNodeWithPos(0, 1),
+				newSymbolNodeWithPos(0, 2),
+			),
+			nullable: false,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root: newAltNode(
+				newRepeatNode(newSymbolNodeWithPos(0, 1)),
+				newSymbolNodeWithPos(0, 2),
+			),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root: newAltNode(
+				newSymbolNodeWithPos(0, 1),
+				newRepeatNode(newSymbolNodeWithPos(0, 2)),
+			),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root: newAltNode(
+				newRepeatNode(newSymbolNodeWithPos(0, 1)),
+				newRepeatNode(newSymbolNodeWithPos(0, 2)),
+			),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1).add(2),
+			last:     newSymbolPositionSet().add(1).add(2),
+		},
+		{
+			root:     newRepeatNode(newSymbolNodeWithPos(0, 1)),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(1),
+		},
+		{
+			root:     newOptionNode(newSymbolNodeWithPos(0, 1)),
+			nullable: true,
+			first:    newSymbolPositionSet().add(1),
+			last:     newSymbolPositionSet().add(1),
+		},
+	}
+	for i, tt := range tests {
+		t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) {
+			if tt.root.nullable() != tt.nullable {
+				t.Errorf("unexpected nullable attribute; want: %v, got: %v", tt.nullable, tt.root.nullable())
+			}
+			if tt.first.hash() != tt.root.first().hash() {
+				t.Errorf("unexpected first positions attribute; want: %v, got: %v", tt.first, tt.root.first())
+			}
+			if tt.last.hash() != tt.root.last().hash() {
+				t.Errorf("unexpected last positions attribute; want: %v, got: %v", tt.last, tt.root.last())
+			}
+		})
+	}
+}
+
+func newRangeSymbolNodeWithPos(from, to byte, pos symbolPosition) *symbolNode {
+	n := newRangeSymbolNode(from, to)
+	n.pos = pos
+	return n
+}
+
+func newSymbolNodeWithPos(v byte, pos symbolPosition) *symbolNode {
+	n := newSymbolNode(v)
+	n.pos = pos
+	return n
+}
+
+func newEndMarkerNodeWithPos(id int, pos symbolPosition) *endMarkerNode {
+	n := newEndMarkerNode(spec.LexModeKindID(id))
+	n.pos = pos
+	return n
+}
+
+func TestFollowAndSymbolTable(t *testing.T) {
+	symPos := func(n uint16) symbolPosition {
+		pos, err := newSymbolPosition(n, false)
+		if err != nil {
+			panic(err)
+		}
+		return pos
+	}
+
+	endPos := func(n uint16) symbolPosition {
+		pos, err := newSymbolPosition(n, true)
+		if err != nil {
+			panic(err)
+		}
+		return pos
+	}
+
+	p := parser.NewParser(spec.LexKindName("test"), strings.NewReader("(a|b)*abb"))
+	cpt, err := p.Parse()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	bt, symTab, err := ConvertCPTreeToByteTree(map[spec.LexModeKindID]parser.CPTree{
+		spec.LexModeKindIDMin: cpt,
+	})
+
+	{
+		followTab := genFollowTable(bt)
+		if followTab == nil {
+			t.Fatal("follow table is nil")
+		}
+		expectedFollowTab := followTable{
+			1: newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3)),
+			2: newSymbolPositionSet().add(symPos(1)).add(symPos(2)).add(symPos(3)),
+			3: newSymbolPositionSet().add(symPos(4)),
+			4: newSymbolPositionSet().add(symPos(5)),
+			5: newSymbolPositionSet().add(endPos(6)),
+		}
+		testFollowTable(t, expectedFollowTab, followTab)
+	}
+
+	{
+		entry := func(v byte) byteRange {
+			return byteRange{
+				from: v,
+				to:   v,
+			}
+		}
+
+		expectedSymTab := &symbolTable{
+			symPos2Byte: map[symbolPosition]byteRange{
+				symPos(1): entry(byte('a')),
+				symPos(2): entry(byte('b')),
+				symPos(3): entry(byte('a')),
+				symPos(4): entry(byte('b')),
+				symPos(5): entry(byte('b')),
+			},
+			endPos2ID: map[symbolPosition]spec.LexModeKindID{
+				endPos(6): 1,
+			},
+		}
+		testSymbolTable(t, expectedSymTab, symTab)
+	}
+}
+
+func testFollowTable(t *testing.T, expected, actual followTable) {
+	if len(actual) != len(expected) {
+		t.Errorf("unexpected number of the follow table entries; want: %v, got: %v", len(expected), len(actual))
+	}
+	for ePos, eSet := range expected {
+		aSet, ok := actual[ePos]
+		if !ok {
+			t.Fatalf("follow entry is not found: position: %v, follow: %v", ePos, eSet)
+		}
+		if aSet.hash() != eSet.hash() {
+			t.Fatalf("follow entry of position %v is mismatched: want: %v, got: %v", ePos, aSet, eSet)
+		}
+	}
+}
+
+func testSymbolTable(t *testing.T, expected, actual *symbolTable) {
+	t.Helper()
+
+	if len(actual.symPos2Byte) != len(expected.symPos2Byte) {
+		t.Errorf("unexpected symPos2Byte entries: want: %v entries, got: %v entries", len(expected.symPos2Byte), len(actual.symPos2Byte))
+	}
+	for ePos, eByte := range expected.symPos2Byte {
+		byte, ok := actual.symPos2Byte[ePos]
+		if !ok {
+			t.Errorf("a symbol position entry is not found: %v -> %v", ePos, eByte)
+			continue
+		}
+		if byte.from != eByte.from || byte.to != eByte.to {
+			t.Errorf("unexpected symbol position entry: want: %v -> %v, got: %v -> %v", ePos, eByte, ePos, byte)
+		}
+	}
+
+	if len(actual.endPos2ID) != len(expected.endPos2ID) {
+		t.Errorf("unexpected endPos2ID entries: want: %v entries, got: %v entries", len(expected.endPos2ID), len(actual.endPos2ID))
+	}
+	for ePos, eID := range expected.endPos2ID {
+		id, ok := actual.endPos2ID[ePos]
+		if !ok {
+			t.Errorf("an end position entry is not found: %v -> %v", ePos, eID)
+			continue
+		}
+		if id != eID {
+			t.Errorf("unexpected end position entry: want: %v -> %v, got: %v -> %v", ePos, eID, ePos, id)
+		}
+	}
+}