nfa.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#ifndef ARCHON_UTILITIES_NFA_H
#define ARCHON_UTILITIES_NFA_H

#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>

#include <archon/util/dfa.H>
#include <archon/util/exception.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    class Regex; // See "regex.H"

    class NFA
    {
      friend class DFA;

      struct Edge
      {
        unsigned begin;
        unsigned end; // inclusive
        int targetState;
        Edge(unsigned begin, unsigned end, int targetState):
          begin(begin), end(end), targetState(targetState) {}
      };

      struct State
      {
        int finalValue; // -1 for non-final
        vector<Edge> symbolEdges;
        vector<int> epsilonEdges;
        State(int finalValue = -1): finalValue(finalValue) {}
      };

      vector<State> states;
      vector<int> startStates; // State indices

      void add(const NFA &, int routeTo = -1);
      bool closedAdd(int state, set<int> &stateSet) const;
      void updateDfaEdgeRange(Edge e, map<unsigned, pair<unsigned, set<int> > > &dEdges) const;
      int chooseFinalValue(const set<int> &stateSet) const;
      void constructDFA(DFA *, vector<set<int> > *, DFA::AnchorInfo *) const;

    public:
      NFA() {}

      NFA(basic_string<unsigned> s, int finalValue = 0);

      NFA(unsigned begin, unsigned end, int finalValue = 0);

      NFA(const vector<pair<unsigned, unsigned> > &ranges, int finalValue = 0);

      NFA(const DFA &);

      NFA(const Regex &, int finalValue = 0);

      void altern(const NFA &);

      void concat(const NFA &);

      void repeat(bool includeZero=false, int finalValue=0);

      void setFinalValue(int finalValue);

      int addStartState(int finalValue = -1);

      int addState(int finalValue = -1);

      void addEdge(int originalState, int targetState);

      void addEdge(int originalState, int targetState, unsigned symbol)
      {
        addEdge(originalState, targetState, symbol, symbol);
      }

      void addEdge(int originalState, int targetState,
                   unsigned begin, unsigned end);

      struct Printer
      {
        virtual string printSymbol(unsigned) const = 0;
        virtual ~Printer() {}
      };

      static const Printer &getDefaultPrinter();

      string print(const Printer &printer = getDefaultPrinter(), int width = 0) const;
    };
  }
}

#endif // ARCHON_UTILITIES_NFA_H

---