fsm.h

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

/*
  $Id: Fsm.h,v 1.2 1997/02/02 01:31:02 matt Exp $

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

#ifndef _FSM_H
#define _FSM_H

#include <contain/LinkedListWithTail.h>

#include "FsmState.h"

class PairsGraph;		// see fsm_opt.cpp

class Fsm
{
   friend ostream &operator << (ostream &os, const Fsm &fsm);

public:

   typedef TypeIOLinkedListWithTail (FsmState) States;
   typedef States::Iterator Iterator;

   // creates an empty FSM
   Fsm () {}
   // copy constructor
   Fsm (const Fsm &fsm);

   // add a state to the FSM and return a reference
   FsmState &addState ();

   // gets the states list
   States &getStates () {return states;}

   // returns the first state created in the FSM
   FsmState &head () const {return states.peekHead ();}

   // returns the last state created in the FSM
   FsmState &tail () const {return states.peekTail ();}

   // returns the number of states in the FSM
   int nStates () const {return states.nItems ();}

   // returns an iterator for all states in the FSM
   States::Iterator getIter () const {return States::Iterator (states);}

   // move all states in this FSM to dest
   void mergeWith (Fsm &dest);

   // removes all epsilon edge cycles
   void clearEpsilonCycles ();

   // removes epsilon edges left over after epsilon cycle removal
   void clearEpsilon ();

   // resolves edge overlaps and does an edge optimisation
   void resolve ();

   // marks all states that can be reached from the head of the FSM.
   // returns the number of states referenced.
   int markReferenced ();

   // optimises FSM to minimum number of states and edges
   void optimize ();

protected:

   // used by copy constructor
   FsmState &doCopy (FsmState &source, FsmState **mappings);

   // used by optimize ()
   void makePairs (PairsGraph &graph);

   States states;		// the list of states in the FSM
};

ostream &operator << (ostream &os, const Fsm &fsm);

#endif