Хм, а что сложного-то? Наоборот, повышение уровня абстракции.
Или повсюду в коде должны просматриваться кишки в виде операций по манипуляции указателями и приведению типов?
Вполне читабельный код получается
Код:
PROCEDURE SubsetConstruct*(nfa: RegExpNFA.NFA): RegExpDFA.DFA;
VAR
dfa: RegExpDFA.DFA;
trans: RegExpMaps.Transition;
lstlstMarked, lstlstUnmarked: Lists.LongintListList;
mapDFAStateNum: RegExpMaps.DFAStateNumMap;
lstNFAInitial, lstFirst, lstAState, lstNext: Lists.LongintList;
iNewState, iInput, i: LONGINT;
PROCEDURE gen_new_state(): LONGINT;
BEGIN
INC(iNewState);
RETURN iNewState
END gen_new_state;
BEGIN
NEW(dfa);
NEW(lstNFAInitial, {});
NEW(lstlstMarked, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
NEW(lstlstUnmarked, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
NEW(mapDFAStateNum);
iNewState := 0;
lstNFAInitial.Add(nfa.iInitial);
lstFirst := EpsClosure(nfa, lstNFAInitial);
lstlstUnmarked.Add(lstFirst);
dfa.iInitial := gen_new_state();
mapDFAStateNum.Add(lstFirst, dfa.iInitial);
WHILE ~lstlstUnmarked.IsEmpty() DO
lstAState := lstlstUnmarked.GetItem(0);
lstlstUnmarked.Remove(0);
lstlstMarked.Add(lstAState);
IF lstAState.IndexOf(nfa.iFinal) # -1 THEN
i := mapDFAStateNum.IndexOf(lstAState);
IF i # -1 THEN
dfa.lstFinal.Add(mapDFAStateNum.GetItem(i).iState)
END
END;
FOR iInput := 0 TO nfa.lstInputs.GetCount() - 1 DO
lstNext := EpsClosure(nfa,
Move(nfa, lstAState, nfa.lstInputs.GetItem(iInput)));
IF (lstlstUnmarked.IndexOf(lstNext) = -1) &
(lstlstMarked.IndexOf(lstNext) = -1)
THEN
lstlstUnmarked.Add(lstNext);
mapDFAStateNum.Add(lstNext, gen_new_state())
END;
i := mapDFAStateNum.IndexOf(lstAState);
IF i # -1 THEN
trans := RegExpMaps.NewTransition(
mapDFAStateNum.GetItem(i).iState,
nfa.lstInputs.GetItem(iInput));
i := mapDFAStateNum.IndexOf(lstNext);
IF (i # -1) & (dfa.mapTransition.IndexOf(trans) = -1) THEN
dfa.mapTransition.Add(trans,
mapDFAStateNum.GetItem(i).iState)
END
END
END
END;
dfa.nStates := mapDFAStateNum.GetCount();
RETURN dfa
END SubsetConstruct;
То-же на C++:
Код:
DFA subset_construct(NFA nfa)
{
DFA dfa;
// state_rep: a set of NFA states which is represented by some DFA state
//
typedef set<state> state_rep;
set<state_rep> marked_states;
set<state_rep> unmarked_states;
// gives a number to each state in the DFA
//
map<state_rep, state> dfa_state_num;
set<state> nfa_initial;
nfa_initial.insert(nfa.initial);
// initially, eps-closure(nfa.initial) is the only state in the DFAs states
// and it's unmarked
//
state_rep first(build_eps_closure(nfa, nfa_initial));
unmarked_states.insert(first);
// the initial dfa state
//
state dfa_initial = gen_new_state();
dfa_state_num[first] = dfa_initial;
dfa.start = dfa_initial;
while (!unmarked_states.empty())
{
// Take out one unmarked state and mark it (remove from the unmarked set,
// insert into the marked set)
//
state_rep a_state = *(unmarked_states.begin());
unmarked_states.erase(unmarked_states.begin());
marked_states.insert(a_state);
// If this state contains the NFA's final state, add it to the DFA's set
// of final states
//
if (a_state.find(nfa.final) != a_state.end())
dfa.final.insert(dfa_state_num[a_state]);
// for each input symbol the nfa knows
//
for (set<input>::const_iterator inp_i = nfa.inputs.begin(); inp_i != nfa.inputs.end(); ++inp_i)
{
// next state
//
state_rep next = build_eps_closure(nfa, nfa.move(a_state, *inp_i));
// if we haven't examined this state before, add it to the unmarked
// states, and make up a new number for it
//
if (unmarked_states.find(next) == unmarked_states.end() &&
marked_states.find(next) == marked_states.end())
{
unmarked_states.insert(next);
dfa_state_num[next] = gen_new_state();
}
dfa.trans_table[make_pair(dfa_state_num[a_state], *inp_i)] = dfa_state_num[next];
}
}
return dfa;
}
PS.
http://svn.assembla.com/svn/oberonru/tr ... /Lists.Modhttp://svn.assembla.com/svn/oberonru/tr ... es/RegExp/