1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
package compiler
import (
"sort"
"github.com/nihei9/maleeni/spec"
)
type DFA struct {
States []string
InitialState string
AcceptingStatesTable map[string]int
TransitionTable map[string][256]string
}
func genDFA(root astNode, symTab *symbolTable) *DFA {
initialState := root.first()
initialStateHash := initialState.hash()
stateMap := map[string]symbolPositionSet{}
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.sort() {
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]int{}
{
for h, s := range stateMap {
for pos := range s {
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) {
state2Num := map[string]int{}
for i, s := range dfa.States {
state2Num[s] = i + 1
}
acc := map[int]int{}
for s, id := range dfa.AcceptingStatesTable {
acc[state2Num[s]] = id
}
tran := make([][]int, len(dfa.States)+1)
for s, tab := range dfa.TransitionTable {
entry := make([]int, 256)
for v, to := range tab {
entry[v] = state2Num[to]
}
tran[state2Num[s]] = entry
}
return &spec.TransitionTable{
InitialState: state2Num[dfa.InitialState],
AcceptingStates: acc,
Transition: tran,
}, nil
}
|
