fsmstate.h

用于词法分析的词法分析器

/*
  $Id: FsmState.h,v 1.3 1997/02/02 01:31:02 matt Exp $

  FSM state class.
  
  (c) Feb 1995 Matt Phillips.
  */

#include <contain/SortedLinkedListUnique.h>
#include <util/checks.h>

#include "FsmEdgeList.h"

class FsmState
{
  friend ostream &operator << (ostream &os, const FsmState &state);
   
public:

  // using unique list to avoid lots of duplicates
  typedef TypeISortedLinkedListUnique(FsmState) SourceList;

  enum {NoProduction = -1};

  FsmState () :
    id (idNext++), prod (NoProduction), markGen (theMarkGen - 1) {}

  int operator == (const FsmState &s) const
  {return getID () == s.getID ();}

  int operator < (const FsmState &s) const
  {return getID () < s.getID ();}

  int operator <= (const FsmState &s) const
  {return getID () <= s.getID ();}

  int operator > (const FsmState &s) const
  {return getID () > s.getID ();}

  int operator >= (const FsmState &s) const
  {return getID () >= s.getID ();}

  int operator != (const FsmState &s) const
  {return getID () != s.getID ();}

  int getID () const {return id;}
  int getProd () const {return prod;}
  void setProd (int p) {prod = p;}
  int isFinal () const {return prod != NoProduction;}
  int nEdges () const {return edges.nItems ();}
  FsmEdgeList &getEdgeList () {return edges;}

  void addEdge (const UCharRange &rng, FsmState &state)
  {
    FsmEdge e (rng, state);
    edges.add (e);
    state.sources.add (*this);
  }

  void addEdge (uchar l, uchar u, FsmState &state)
  {
    FsmEdge e (l, u, state);
    edges.add (e);
    state.sources.add (*this);
  }
   
  void addEdge (const FsmEdge &edge) // is this necessary?
  {
    FsmEdge e (edge);

    edges.add (e);
    edge.getTarget ().sources.add (*this);
  }

  void addEdge (FsmState &state) // epsilon edge
  {
    FsmEdge e (state);

    edges.add (e);
    state.sources.add (*this);
  }

  void addEdge (const FsmEdge &edge, FsmState &t)
  {
    FsmEdge e (t, edge);

    edges.add (e);
    t.sources.add (*this);
  }

  void addEdge (const FsmEdgeList &edgeList);

  // maximum ID used for all states
  static int maxID () {return idNext - 1;}

  // reset ID counter
  // NOTE: do not use this unless you are sure that all states
  // allocated previously are destroyed, otherwise *very* strange
  // problems could result as physically different states are
  // treated as identical.
  static int resetID () {idNext = 0;}

  // mark stuff
  int isMarked () const {return markGen == theMarkGen;}
  void mark () {markGen = theMarkGen;}
  static void unmarkAll () {theMarkGen++;}
   
  // redirect all edges pointing to this node to dest
  void redirect (FsmState &dest);

  // merges this state with dest by moving all out edges, redirecting
  // in edges (with redirect (dest)) and setting the production of
  // dest to the maximum of this and dest
  void mergeWith (FsmState &dest);

  // copy all edges of this state to dest
  void copyTo (FsmState &dest) const
  {
    edges.copyTo (dest.edges);
  }

  // epsilon removal stuff
  int mergeEpsilonCycles (FsmState &root);
  void removeEpsilon ();

  // ensure that the minimum number of edges are used for this state
  void edgeOptimize ();

protected:

  static int idNext;		// next id counter
  static int theMarkGen;	// global mark generation
  int id;
  int prod;
  FsmEdgeList edges;		// out edges
  SourceList sources;		// states with out edges targetting
				// this state
  int markGen;			// this state's generation number
};

ostream &operator << (ostream &os, const FsmState &state);