fsm_opt.cpp

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

/*
  $Id: Fsm_opt.cpp,v 1.3 1997/02/02 01:31:02 matt Exp $

  FSM class optimisation functions.
  
  (c) Dec 95 Matt Phillips.
  */

#include <contain/LinkedList.h>
#include <contain/LinkedListIterExt.h>
#include <contain/ClosedHash.h>
#include <util/OrderedPair.h>

#include "Fsm.h"
#include "GraphNode.h"

class Hash
{
public:

  enum {HashSize = 512};

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

//////////////////// FSM state graph

// data associated with node in the pairs graph
class GraphNodeData
{
public:

  GraphNodeData (FsmState &s) : state (s), markGen (theMarkGen - 1) {}

  int operator == (const GraphNodeData &n) const
  {return state == n.state;}

  FsmState &getState () const {return state;}

  // mark stuff
  int isMarked () const {return markGen == theMarkGen;}
  void mark () {markGen = theMarkGen;}
  static void unmarkAll () {theMarkGen++;}

protected:

  FsmState &state;
  int markGen;			// the mark used for this node in
                                // graph searches
  static int theMarkGen;	// the current mark generation
};

int GraphNodeData::theMarkGen = 1;

typedef TypeIOGraphNode (GraphNodeData) GraphNode;

// the state pairs graph
class PairsGraph
{
  friend ostream &operator << (ostream &s, const PairsGraph &g);

public:

  typedef TypeIOLinkedList(GraphNode) Nodes;
  typedef TypeIClosedHash (int, GraphNode, Hash, Hash::HashSize) IdToNodeMap;

  // add a graph node for state
  GraphNode &add (FsmState &state);

       // the graph node associated with state, or null if none exists
       GraphNode *get (const FsmState &state)
  {return idToNodeMap.get (state.getID ());}

  // same as get () except if node does not exist it is created
  GraphNode &getOrCreate (FsmState &state);

  // returns nodes list
  Nodes &getNodes () {return nodes;}

protected:

  Nodes nodes;
  IdToNodeMap idToNodeMap;
};

GraphNode &PairsGraph::add (FsmState &state)
{
  int key = state.getID ();
  GraphNode *node = new GraphNode (*new GraphNodeData (state));
  nodes.add (*node);
  idToNodeMap.add (key, *node);
   
  return *node;
}

GraphNode &PairsGraph::getOrCreate (FsmState &state)
{
  GraphNode *node = idToNodeMap.get (state.getID ());
   
  if (!node)			// if node does not exist
    return add (state);
  else
    return *node;
}

//////////////////// The optimization routines

// makes a pair for (s1, s2) if they are a feasible pair.
static void makePair (FsmState &s1, FsmState &s2,
		      PairsGraph &graph)
{
  if (s1.getProd () == s2.getProd () &&
      s1.getEdgeList () == s2.getEdgeList ())
  {
    GraphNode &n1 = graph.getOrCreate (s1),
      &n2 = graph.getOrCreate (s2);

    n1.addTarget (n2);	// pair the two nodes
    n2.addTarget (n1);
  }
}

void Fsm::makePairs (PairsGraph &graph)
{
  States::Iterator i1 (states), i2 (states);

  // iterate thru all possible pairs
  for ( ; i1; i1++)
  {
    if (i1.ref ().isMarked ()) 
    {				// if i1 is referenced
      // scan all other states
      for (i2.reset (); i2; i2++)
      {
	if (i2.ref ().isMarked ())
	{			// if i2 is referenced
	  FsmState &s1 = i1.ref (), &s2 = i2.ref ();

	  if (s1 < s2)
	  {			// only consider pairs once
	    makePair (s1, s2, graph);
	  }
	}
      }
    }
  }
}

// called by stripPairs ().  checks whether pair should be removed
static int checkPair (FsmState &s1, FsmState &s2, PairsGraph &graph)
{
  for (FsmEdgeList::Iterator i1 (s1.getEdgeList ()), i2 (s2.getEdgeList ());
       i1; i1++, i2++)
  {
    const FsmState &s1 = i1.ref ().getTarget (),
      &s2 = i2.ref ().getTarget ();
    if (s1 != s2)
    {				// a state is always paired with itself
      GraphNode *n1 = graph.get (s1), *n2 = graph.get (s2);

      if (!n1 || !n2)
      {			// if either are not in a pair
	return 0;
      } else if (!n1->hasTarget (*n2))
      {			// else if (n1, n2) is not a pair
	// remove connection from n2 -> n1. n1 -> n2 is removed by
	// stripPairs () function
	n2->clearTarget (*n1); 
	return 0;
      }
    }
  }

  return 1;
}

static int stripPairs (PairsGraph &graph)
{
  int changed = 0;
   
  // iterate over all pairs a
  for (PairsGraph::Nodes::Iterator ni (graph.getNodes ()); ni; ni++)
  {
    FsmState &s1 = ni.ref ().ref ().getState ();

    // iterate over targets
    for (GraphNode::TargetListIterExt ti (ni.ref ().getTargets ());
	 ti; )
    {
      FsmState &s2 = ti.ref ().ref ().getState ();

      if (!checkPair (s1, s2, graph))
      {
	changed = 1;
	// remove connection from n1 -> n2.  n2 -> n1 has already
	// been done by checkPair ().
	ti.remove ();
      } else
	ti++;
    }
  }

  return changed;
}

// transitively merges all states targeted by node with root
static void doTransitiveMerge (FsmState &root, GraphNode &node)
{
  node.ref ().mark ();

  for (GraphNode::TargetList::Iterator i (node.getTargets ()); i; i++)
  {
    GraphNode &n = i.ref ();

    if (!n.ref ().isMarked ())
    {
      doTransitiveMerge (root, n); // merge children
      n.ref ().getState ().redirect (root);
    }
  }
}

static void mergePairs (PairsGraph &graph)
{
  GraphNodeData::unmarkAll ();

  for (PairsGraph::Nodes::Iterator i (graph.getNodes ()); i; i++)
  {
    GraphNode &node = i.ref ();
    if (!node.ref ().isMarked ())
    {
      doTransitiveMerge (node.ref ().getState (), node);

      // do an edge optimize on the off chance that the merges
      // produced mergeable edges
      node.ref ().getState ().edgeOptimize ();
    }
  }
}

void Fsm::optimize ()
{
  PairsGraph graph;

  markReferenced ();		// so we can ignore unused states
  makePairs (graph);
  while (stripPairs (graph));
  mergePairs (graph);
}

ostream &operator << (ostream &s, const PairsGraph &g)
{
  s << g.nodes;
  return s;
}

ostream &operator << (ostream &s, const GraphNode &n)
{
  s << "state " << ((GraphNode &)n).ref ().getState ().getID () <<
    ": pairs: ";

  for (GraphNode::TargetList::Iterator i (((GraphNode &)n).getTargets ());
       i; i++)
  {
    s << i.ref ().ref ().getState ().getID () << " ";
  }

  return s;
}

template class ClosedHashImp<int, FsmEdgeList, ITLinkedAssocItem<int, FsmEdgeList, 1>, Hash, Hash::HashSize>;
template class ClosedHashImpIter<int, FsmEdgeList, ITLinkedAssocItem<int, FsmEdgeList, 1>, Hash, Hash::HashSize>;
template class ClosedHashImp<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ITLinkedAssocItem<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>, Hash, Hash::HashSize>;
template class ClosedHashImpIter<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ITLinkedAssocItem<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>, Hash, Hash::HashSize>;
template class ITLinkedAssocItem<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>;
template class ITAssocItem<int, GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>;
template class LinkedListImpIter<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 1> >;
template class GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >;
template ostream &operator<<(ostream &, Container<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> > > const &);
template class LinkedListImpIterExt<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0> >;
template class LinkedListImpIter<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0> >;
template class LinkedListImp<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 1> >;
template class Container<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> > >;
template class IContainerData<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 1>;
template class LinkedListImp<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0> >;
template class List<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> > >;
template class IContainerData<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>;
template class ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 1>;
template class ILinkedItem<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> >, 0>;
template class ListIter<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> > >;
template class IContainerData<GraphNodeData, 1>;
template class ContainerIter<GraphNodeImp<GraphNodeData, IContainerData<GraphNodeData, 1> > >;