fsm.cpp

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

/*
  $Id: Fsm.cpp,v 1.4 1997/02/02 01:31:02 matt Exp $

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

#include <stdlib.h>
#include <contain/ClosedHash.h>
#include <contain/OrderedBinaryTree.h>
#include <contain/LinkedListIterExt.h>
#include <contain/LinkedListWithTailIterExt.h>
#include <util/OrderedPair.h>
#include <util/maxmin.h>

#include "Fsm.h"

#ifndef NCHECK
#ifdef __GNUC__
#include <memory.h>
#else
#include <mem.h>
#endif
#endif

class Hash
{
public:

  enum {HashSize = 512};

  static int hash (int i)
  {
    return i % HashSize;
  }
};

typedef OrderedPair<int> StateIDPair;
typedef TypeIOClosedHash(int, FsmEdgeList, Hash, Hash::HashSize) EdgesTable;
// use a hash table for below later
typedef TypeIOrderedBinaryTree(StateIDPair, FsmState) MapPairToState;
typedef TypeDLinkedListIterExt(FsmEdge) FsmEdgeListIterExt;
typedef TypeDLinkedListWithTailIterExt(FsmState) FsmIterExt;

Fsm::Fsm (const Fsm &fsm)
{
  FsmState **mappings = new FsmState * [FsmState::maxID () + 1];
   
#ifndef NCHECK
  memset (mappings, 0, (FsmState::maxID () + 1) * sizeof (FsmState *));
#endif
   
  // do copy
  FsmState::unmarkAll ();
  doCopy (fsm.head (), mappings);
   
  delete mappings;
}

FsmState &Fsm::addState ()
{
  states.addTail (*new FsmState);
   
  return states.peekTail ();
}

////////////////////////////////////////
// copy FSM starting from <source>, using <mappings> as a mapping from
// an ID in the old FSM to equivalent states in the new FSM.  returns
// first state of new FSM.
////////////////////////////////////////
FsmState &Fsm::doCopy (FsmState &source, FsmState **mappings)
{
  if (!source.isMarked ())
  {
    source.mark ();
      
    FsmState &mapState = addState ();
    mappings [source.getID ()] = &mapState;
      
    // iterate over edges
    for (FsmEdgeList::Iterator ei (source.getEdgeList ()); ei; ei++)
    {
      mapState.addEdge (ei.ref (),
			doCopy (ei.ref ().getTarget (), mappings));
    }
      
    return mapState;
      
  } else
  {
    CHECK (mappings [source.getID ()], "null FsmState mapping");
    return *(mappings [source.getID ()]);
  }
}

void Fsm::mergeWith (Fsm &dest)
{
  states.moveTo (dest.states);
}

////////////////////////////////////////
// see Fsm::markReferenced ().
////////////////////////////////////////
static int doMarkReferenced (FsmState &state)
{
  int marks = 0;

  if (!state.isMarked ())
  {
    state.mark ();
    marks++;

    for (FsmEdgeList::Iterator i (state.getEdgeList ()); i; i++)
    {
      marks += doMarkReferenced (i.ref ().getTarget ());
    }
  }

  return marks;
}

////////////////////////////////////////
// mark all referenced (non-orphan) states.
// returns number of states marked.
// works only with fully resolved FSM's (ie. no overlapping edges).
////////////////////////////////////////
int Fsm::markReferenced ()
{
  FsmState::unmarkAll ();

  // mark all states that can be reached from root
  return doMarkReferenced (head ());
}

////////////////////////////////////////
// remove cycles of epsilon edges
////////////////////////////////////////
void Fsm::clearEpsilonCycles ()
{
  for (States::Iterator i (states); i; i++)
  {
    FsmState::unmarkAll ();
      
    i.ref ().mergeEpsilonCycles (i.ref ());
  }
}

////////////////////////////////////////
// remove epsilon edges (no cycles should exist)
////////////////////////////////////////
void Fsm::clearEpsilon ()
{
  FsmState::unmarkAll ();
   
  for (States::Iterator i (states); i; i++)
    i.ref ().removeEpsilon ();
}

static void resolveState (Fsm &fsm, FsmState &state,
			  MapPairToState &pairToStateMapping,
			  EdgesTable &oldEdgeLists);

////////////////////////////////////////
// resolve overlapping edges. also edge optimizes all states.
////////////////////////////////////////
void Fsm::resolve ()
{
  MapPairToState pairToStateMapping;
  States::Iterator i (states);
  EdgesTable oldEdgeLists;

  // copy all states' edges
  for ( ; i; i++)
  {
    int id = i.ref ().getID ();
    oldEdgeLists.add (id,
		      *new FsmEdgeList (i.ref ().getEdgeList ()));
  }

  FsmState::unmarkAll ();
   
  for (i.reset (); i; i++) 
  {
    if (i.ref ().nEdges () > 1)
    {
      if (!i.ref ().isMarked ())
      {
	i.ref ().mark ();
	i.ref ().edgeOptimize ();
	resolveState (*this, i.ref (),
		      pairToStateMapping, oldEdgeLists);
      }
    }
  }
}

////////////////////////////////////////
// resolve edge overlaps for a single state <state> in <fsm>.
// <pairToStateMapping> maps pairs of state id's to their resolution
// state (if it exists).  <oldEdgeLists> maps a state id to a copy of
// its original edge list before resolution began.
////////////////////////////////////////
static void resolveState (Fsm &fsm, FsmState &state,
			  MapPairToState &pairToStateMapping,
			  EdgesTable &oldEdgeLists)
{
  int changed;

  do				// while changed
  {
    changed = 0;

    FsmEdgeListIterExt ei (state.getEdgeList ());

    for ( ; !changed && ei && ei.hasNext (); )
    {
      if (ei.ref ().overlaps (ei.refNext ()))
      {
	FsmEdge prev (ei.ref ()), cur (ei.refNext ());
	UCharRange overlap (cur);
	overlap.shadow (prev); // compute overlapping region
	FsmState *resState;
	StateIDPair pair (prev.getTarget ().getID (),
			  cur.getTarget ().getID ());
	    
	if (pair.item1 == pair.item2) // if both edges have same target
	  resState = &cur.getTarget ();
	else
	{
	  resState = pairToStateMapping.get (pair);
	    
	  if (resState == 0)
	  {
	    // build res state
	    resState = &(fsm.addState ());
		  
	    // update production number
	    resState->setProd (max (prev.getTarget ().getProd (),
				    cur.getTarget ().getProd ()));
		  
	    pairToStateMapping.add (pair, *resState);
		  
	    // add original (copied) edges for the two states
	    resState->addEdge
	      (*oldEdgeLists.get (prev.getTarget ().getID ()));
	    resState->addEdge
	      (*oldEdgeLists.get (cur.getTarget ().getID ()));
		  
	    // store edges of new state in old edges table
	    int id = resState->getID (); // copy id
	    oldEdgeLists.add 
	      (id,
	       *new FsmEdgeList (resState->getEdgeList ()));
	  }
	}

	ei.remove ();	// kill overlapping edges
	ei.remove ();

	state.addEdge (overlap, *resState);	// add edge pointing
	// to new state
	changed = 1;

	// adjust prev and cur
	if (prev.upper > overlap.upper)
	{
	  // if prev extends to right of overlap
	  uchar oldLower = prev.lower;
	  prev.lower = overlap.upper + 1;
	  state.addEdge (prev);
	  prev.lower = oldLower;
	}

	if (prev.lower < overlap.lower)
	{
	  // if prev extends to left of overlap
	  prev.upper = overlap.lower - 1;
	  state.addEdge (prev);
	}
	    
	if (cur.upper > overlap.upper)
	{
	  // if cur extends to right of overlap
	  cur.lower = overlap.upper + 1;
	  state.addEdge (cur);
	}
      }

      if (ei) ei++;
    }
  } while (changed);

  CHECK (state.getEdgeList ().isSorted (), "edge list ordering violation");
}

ostream &operator << (ostream &os, const Fsm &fsm)
{
  os << "states: " << fsm.states.nItems () << endl;
   
  for (Fsm::States::Iterator i (fsm.states); i; i++)
    os << i.ref () << endl;
   
  return os;
}

inline ostream &operator << (ostream &os, const StateIDPair &p)
{
  os << (OrderedPair<int> &)p;
  return os;
}

#ifdef __GNUC__
template class TypeIClosedHash (int, FsmEdgeList, Hash, Hash::HashSize);
template class TypeIClosedHashIter (int, FsmEdgeList, Hash, Hash::HashSize);
#endif