package compiler import ( "sort" ) 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, } } type TransitionTable struct { InitialState int `json:"initial_state"` AcceptingStates map[int]int `json:"accepting_states"` Transition [][]int `json:"transition"` } func GenTransitionTable(dfa *DFA) (*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 &TransitionTable{ InitialState: state2Num[dfa.InitialState], AcceptingStates: acc, Transition: tran, }, nil }