fsmstate.cpp

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

/*
  $Id: FsmState.cpp,v 1.2 1997/02/02 01:31:02 matt Exp $

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

#include <contain/LinkedListIterExt.h>

#include "FsmState.h"

typedef TypeDLinkedListIterExt(FsmEdge) FsmEdgeListIterExt;

int FsmState::idNext = 0;
int FsmState::theMarkGen = 1;

inline int max (int n1, int n2)
{
  return n1 > n2 ? n1 : n2;
}

ostream &operator << (ostream &os, const FsmState &state)
{
  os << "id: " << state.getID () << " edges: " << state.nEdges ();
   
  if (state.isFinal ()) os << " prod: " << state.getProd ();
   
  os << " sources: ";
  for (FsmState::SourceList::Iterator si (state.sources); si; si++)
    os << si.ref ().getID () << " ";

  os << endl;

  for (FsmEdgeList::Iterator i (state.edges); i; i++)
    cout << "  " << i.ref () << endl;

  return os;
}

void FsmState::addEdge (const FsmEdgeList &edgeList)
{
  edgeList.copyTo (edges);
  for (FsmEdgeList::Iterator i (edgeList); i; i++)
  {
    i.ref ().getTarget ().sources.add (*this);
  }
}

void FsmState::redirect (FsmState &dest)
{
  if (dest.getID () != getID ())
  {
    // redirect in-edges
    for (SourceList::Iterator s (sources); s; s++)
    {
      for (FsmEdgeList::Iterator e (s.ref ().edges); e; e++)
      {
	if (e.ref ().getTarget () == *this)
	{
	  e.ref ().setTarget (dest);
	  dest.sources.add (s.ref ());
	}
      }
    }
    sources.clear ();
  }
}

void FsmState::mergeWith (FsmState &dest)
{
  if (dest.getID () != getID ())
  {
    edges.moveTo (dest.edges);
    if (dest.getProd () < getProd ()) dest.setProd (getProd ());
    redirect (dest);
  }
}

////////////////////////////////////////
// merge all states lying on epsilon cycles and clear edges causing
// the cycles.
////////////////////////////////////////
int FsmState::mergeEpsilonCycles (FsmState &root)
{
  if (!isMarked ())
  {
    mark ();

    int merge = 0;

    // first pass does merges
    for (FsmEdgeList::Iterator i (getEdgeList ());
	 i && i.ref ().isEpsilon ();
	 i++)
    {
      if (i.ref ().getTarget ().mergeEpsilonCycles (*this))
	merge = 1;
    }
      
    // second pass removes edges pointing back at this state caused
    // by merges. the edges cannot be removed on first pass because
    // extended iter does not handle changes to edge list from
    // merges.
    // (cast below needed for Borland C++ 4)
    for (FsmEdgeListIterExt ix (getEdgeList ());
	 ix && ix.ref ().isEpsilon (); /* no ++ in loop */ )
    {
      if (ix.ref ().getTarget ().getID () == getID ())
	ix.remove ();
      else
	ix++;
    }

    if (merge)
      mergeWith (root);

    return merge;
  } else
    return 1;			// found a cycle
}

////////////////////////////////////////
// remove epsilon transitions (cycles are not handled)
////////////////////////////////////////
void FsmState::removeEpsilon ()
{
  if (!isMarked ())
  {
    mark ();

    // copy all edges from nodes pointed at by epsilon edges after
    // recursively invoking removeEpsilon to ensure target state has
    // no epsilon edges of its own.
    for (FsmEdgeList::Iterator i (getEdgeList ());
	 i && i.ref ().isEpsilon (); i++)
    {
      i.ref ().getTarget ().removeEpsilon ();
      i.ref ().getTarget ().copyTo (*this);
      // production is max of this and target
      setProd (max (getProd (),
		    i.ref ().getTarget ().getProd ()));
    }

    // delete all epsilon edges
    for (FsmEdgeListIterExt ix (getEdgeList ());
	 ix && ix.ref ().isEpsilon (); /* no ++ */ )
      ix.remove ();
  }
}

void FsmState::edgeOptimize ()
{
  if (nEdges () > 1)
  {
    FsmEdgeListIterExt i (getEdgeList ());
    i++;

    while (i)
    {
      FsmEdge &prev = i.refPrev (), &cur = i.ref ();

      if (prev.getTarget () == cur.getTarget () &&
	  prev.adjacent (cur))
      {
	prev.upper = cur.upper; // merge ranges
	i.remove ();		// kill old edge
      } else
	i++;
    }
  }
}