tesla::internal::DFABuilder Class Reference

Detailed Description

Definition at line 706 of file Automaton.cpp.

Public Member Functions
DFA *	ConstructDFA (const NFA *N)
	Public interface to this class. Constructs a DFA from the provided NFA. More...

Member Function Documentation

DFA* tesla::internal::DFABuilder::ConstructDFA ( const NFA *  N )

inline

Public interface to this class. Constructs a DFA from the provided NFA.

Definition at line 770 of file Automaton.cpp.

References tesla::State::begin(), tesla::Transition::Copy(), tesla::debugs(), tesla::Transition::Destination(), tesla::State::end(), tesla::Automaton::getAssertion(), tesla::Transition::getKind(), tesla::Transition::GroupClasses(), tesla::State::ID(), tesla::Automaton::ID(), tesla::Transition::IsRealisable(), tesla::Automaton::Name(), tesla::Transition::Null, tesla::Automaton::States, tesla::Automaton::String(), and tesla::Automaton::Use().

Referenced by tesla::DFA::Convert().

                                  {
    assert(N != NULL);
    // We can't reuse these currently.
    assert(States.empty());
    // The set of DFA states that correspond to the current location
    NFAState CurrentState;
    stateForNFAState(N->States.front());
    while (!UnfinishedStates.empty()) {
      CurrentState = UnfinishedStates.back().first;
      auto StartFinal = UnfinishedStates.back().second;
      bool Start = StartFinal.first;
      bool Final = StartFinal.second;
      UnfinishedStates.pop_back();
      // Find the NFA states that correspond to the current state.
      State *DS = stateForNFAStates(CurrentState, Start, Final);
      if (FinishedStates.find(DS->ID()) != FinishedStates.end())
        continue;
      FinishedStates.insert(DS->ID());
      // Now we have a state, we need to handle its transitions.
      // If there is only one state in the current state set, then we can just
      // copy all of the transitions from it.
      unordered_set<Transition*> FinishedTransitions;
      // Loop over all of the NFA states and find their outgoing transitions
      for (auto SI=CurrentState.begin(), SE=CurrentState.end() ; SI!=SE ; ++SI) {
        unsigned I = *SI;
        State *NState = N->States[I];
        Start = false;
        Final = false;
        for (auto TI=NState->begin(), TE=NState->end() ; TI!=TE ; ++TI) {
          Transition *T = *TI;
          if (T->getKind() == Transition::Null) continue;
          assert(T->IsRealisable());
          if (FinishedTransitions.count(T) != 0) continue;
          NFAState Destinations;
          collectFrontier(Destinations, &T->Destination(), Start, Final);
          FinishedTransitions.insert(T);
          // Find the other transitions from this state that are equivalent to this one.
          auto DTI = TI;
          for (++DTI ; DTI!=TE ; ++DTI) {
            if ((*DTI)->EquivalentTo(*T)) {
              assert(FinishedTransitions.count(*DTI) == 0);
              FinishedTransitions.insert(*DTI);
              collectFrontier(Destinations, &(*DTI)->Destination(), Start, Final);
            }
          }
          auto DSI = SI;
          for (++DSI ; DSI!=SE ; ++DSI)
            for (Transition *DT : *N->States[*DSI]) {
            if (DT->EquivalentTo(*T)) {
              assert(FinishedTransitions.count(DT) == 0);
              FinishedTransitions.insert(DT);
              collectFrontier(Destinations, &DT->Destination(), Start, Final);
            }
          }

          State *Dest = stateForNFAStates(Destinations, Start, Final);
          Transition::Copy(*DS, *Dest, T, Transitions);
        }
      }
    }
    TransitionSets TEquivClasses;
    Transition::GroupClasses(Transitions, TEquivClasses);

    DFA *D = new DFA(N->ID(),
                     const_cast<AutomatonDescription&>(N->getAssertion()),
                     N->Use(), N->Name(), States, TEquivClasses);

    debugs("tesla.automata.dfa")
        << "DFA conversion results:\n"
        << "> NFA: " << N->String() << "\n"
        << "> DFA: " << D->String() << "\n"
        << ">>  DFA state map:\n"
        << DFAStates
        << ">>  DFA transition equivalence classes:\n"
        ;

    return D;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• tesla/common/Automaton.cpp