namespace Lex
{
/*
 * Class: Nfa2Dfa
 */
using System;
using System.Text;
using System.Collections;
using BitSet;

class Nfa2Dfa
{
/*
 * Constants
 */
private const int NOT_IN_DSTATES = -1;

/*
 * Function: make_dfa
 * Deion: High-level access function to module.
 */
//public void make_dfa(Gen l, Spec s)
public static void MakeDFA(Spec s)
 {
 make_dtrans(s);
 free_nfa_states(s);
#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(s.dfa_states.Count
		 + " DFA states in original machine.");
#endif
 free_dfa_states(s);
 } 

/*
 * Function: make_dtrans
 * Deion: Creates uncompressed CDTrans transition table.
 */
//private void make_dtrans()
private static void make_dtrans(Spec s)
 {
 Dfa dfa;
 int nextstate;

 Console.Error.WriteLine("Working on DFA states.");

 /* Reference passing type and initializations. */
 s.InitUnmarkedDFA();

 /* Allocate mapping array. */
 int nstates = s.state_rules.Length;
 s.state_dtrans = new int[nstates];

 for (int istate = 0; istate < nstates; istate++)
 {
 /* Create start state and initialize fields. */

 Bunch bunch = new Bunch(s.state_rules[istate]);

 bunch.e_closure();
 add_to_dstates(s, bunch);

 s.state_dtrans[istate] = s.dtrans_list.Count;

 /* Main loop of DTrans creation. */
 while (null != (dfa = s.GetNextUnmarkedDFA()))
 {
 Console.Error.Write(".");
#if DEBUG
 Utility.assert(!dfa.IsMarked());
#endif
 /* Get first unmarked node, then mark it. */
 dfa.SetMarked();

 /* Allocate new DTrans, then initialize fields. */
 DTrans dt = new DTrans(s, dfa);

 /* Set dt array for each character transition. */
 for (int i = 0; i < s.dtrans_ncols; i++)
	{
	/* Create new dfa set by attempting character transition. */
	bunch.move(dfa, i);
	if (!bunch.IsEmpty())
	 bunch.e_closure();
#if DEBUG
	Utility.assert((null == bunch.GetNFASet() 
			 && null == bunch.GetNFABit())
			|| (null != bunch.GetNFASet() 
			 && null != bunch.GetNFABit()));
#endif
	/* Create new state or set state to empty. */
	if (bunch.IsEmpty())
	 {
	 nextstate = DTrans.F;
	 }
	else 
	 {
	 nextstate = in_dstates(s, bunch);

	 if (nextstate == NOT_IN_DSTATES)
	 nextstate = add_to_dstates(s, bunch);
	 }
#if DEBUG
	Utility.assert(nextstate < s.dfa_states.Count);
#endif
	dt.SetDTrans(i, nextstate);
	}
#if DEBUG
 Utility.assert(s.dtrans_list.Count == dfa.GetLabel());
#endif
#if DEBUG
 StringBuilder sb1 = new StringBuilder(Lex.MAXSTR);
 sb1.Append("Current count = "+s.dtrans_list.Count+"\n");
 for (int i1 = 0; i1 < dt.GetDTransLength(); i1++)
	sb1.Append(dt.GetDTrans(i1)+",");
 sb1.Append("end\n");
 Console.Error.Write(sb1.ToString());
#endif
 s.dtrans_list.Add(dt);
 }
 }
 Console.Error.WriteLine("");
 }

/*
 * Function: free_dfa_states
 */
//private void free_dfa_states()
private static void free_dfa_states(Spec s)
 {
 s.dfa_states = null;
 s.dfa_sets = null;
 }

/*
 * Function: free_nfa_states
 */
private static void free_nfa_states(Spec s)
 {
 /* UNDONE: Remove references to nfas from within dfas. */
 /* UNDONE: Don"t free CAccepts. */
 s.nfa_states = null;
 s.nfa_start = null;
 s.state_rules = null;
 }

/*
 * function: add_to_dstates
 * Deion: Takes as input a CBunch with details of
 * a dfa state that needs to be created.
 * 1) Allocates a new dfa state and saves it in the appropriate Spec list
 * 2) Initializes the fields of the dfa state with the information in the CBunch.
 * 3) Returns index of new dfa.
 */
private static int add_to_dstates(Spec s, Bunch bunch)
 {
 Dfa dfa;

#if DEBUG
 Utility.assert(null != bunch.GetNFASet());
 Utility.assert(null != bunch.GetNFABit());
 Utility.assert(null != bunch.GetAccept() || Spec.NONE == bunch.GetAnchor());
#endif

 /* Allocate, passing Spec so dfa label can be set. */
 dfa = Alloc.NewDfa(s);

 /* Initialize fields, including the mark field. */
 dfa.SetNFASet(new ArrayList(bunch.GetNFASet()));
 dfa.SetNFABit(new BitSet(bunch.GetNFABit()));
 dfa.SetAccept(bunch.GetAccept());
 dfa.SetAnchor(bunch.GetAnchor());
 dfa.ClearMarked();

#if OLD_DUMP_DEBUG
 Console.Error.WriteLine("[Created new dfa_state #"+dfa.GetLabel()+"]");
 dfa.dump();
#endif

 /* Register dfa state using BitSet in spec Hashtable. */
 s.dfa_sets[dfa.GetNFABit()] = dfa;

#if OLD_DUMP_DEBUG
 Console.Error.Write("Registering set : ");
 Print_Set(dfa.GetNFASet());
 Console.Error.WriteLine("");
#endif

 return dfa.GetLabel();
 }

/*
 * Function: in_dstates
 */
private static int in_dstates(Spec s, Bunch bunch)
 {
 Dfa dfa;

#if OLD_DEBUG
 Console.Error.Write("Looking for set : ");
 Print_Set(bunch.GetNFASet());
 bunch.dump();
#endif

 o = s.dfa_sets[bunch.GetNFABit()];

 if (null != o)
 {
 dfa = (Dfa) o;
#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(" FOUND!");
#endif
 return dfa.GetLabel();
 }

#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(" NOT FOUND!");
#endif
 return NOT_IN_DSTATES;
 }

#if OLD_DUMP_DEBUG
/*
 * function: Print_Set
 */
public static void Print_Set(ArrayList nfa_set)
 {
 int size; 
 int elem;

 size = nfa_set.Count;

 if (size == 0)
 {
 Console.Error.Write("empty ");
 }

 for (elem = 0; elem < size; ++elem)
 {
 Nfa nfa = (Nfa) nfa_set[elem];
 Console.Error.Write(nfa.GetLabel() + " ");
 }
 }
#endif
}
}

namespace Lex
{
/*
 * Class: Nfa2Dfa
 */
using System;
using System.Text;
using System.Collections;
using BitSet;

class Nfa2Dfa
{
/*
 * Constants
 */
private const int NOT_IN_DSTATES = -1;

/*
 * Function: make_dfa
 * Deion: High-level access function to module.
 */
//public void make_dfa(Gen l, Spec s)
public static void MakeDFA(Spec s)
 {
 make_dtrans(s);
 free_nfa_states(s);
#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(s.dfa_states.Count
		 + " DFA states in original machine.");
#endif
 free_dfa_states(s);
 } 

/*
 * Function: make_dtrans
 * Deion: Creates uncompressed CDTrans transition table.
 */
//private void make_dtrans()
private static void make_dtrans(Spec s)
 {
 Dfa dfa;
 int nextstate;

 Console.Error.WriteLine("Working on DFA states.");

 /* Reference passing type and initializations. */
 s.InitUnmarkedDFA();

 /* Allocate mapping array. */
 int nstates = s.state_rules.Length;
 s.state_dtrans = new int[nstates];

 for (int istate = 0; istate < nstates; istate++)
 {
 /* Create start state and initialize fields. */

 Bunch bunch = new Bunch(s.state_rules[istate]);

 bunch.e_closure();
 add_to_dstates(s, bunch);

 s.state_dtrans[istate] = s.dtrans_list.Count;

 /* Main loop of DTrans creation. */
 while (null != (dfa = s.GetNextUnmarkedDFA()))
 {
 Console.Error.Write(".");
#if DEBUG
 Utility.assert(!dfa.IsMarked());
#endif
 /* Get first unmarked node, then mark it. */
 dfa.SetMarked();

 /* Allocate new DTrans, then initialize fields. */
 DTrans dt = new DTrans(s, dfa);

 /* Set dt array for each character transition. */
 for (int i = 0; i < s.dtrans_ncols; i++)
	{
	/* Create new dfa set by attempting character transition. */
	bunch.move(dfa, i);
	if (!bunch.IsEmpty())
	 bunch.e_closure();
#if DEBUG
	Utility.assert((null == bunch.GetNFASet() 
			 && null == bunch.GetNFABit())
			|| (null != bunch.GetNFASet() 
			 && null != bunch.GetNFABit()));
#endif
	/* Create new state or set state to empty. */
	if (bunch.IsEmpty())
	 {
	 nextstate = DTrans.F;
	 }
	else 
	 {
	 nextstate = in_dstates(s, bunch);

	 if (nextstate == NOT_IN_DSTATES)
	 nextstate = add_to_dstates(s, bunch);
	 }
#if DEBUG
	Utility.assert(nextstate < s.dfa_states.Count);
#endif
	dt.SetDTrans(i, nextstate);
	}
#if DEBUG
 Utility.assert(s.dtrans_list.Count == dfa.GetLabel());
#endif
#if DEBUG
 StringBuilder sb1 = new StringBuilder(Lex.MAXSTR);
 sb1.Append("Current count = "+s.dtrans_list.Count+"\n");
 for (int i1 = 0; i1 < dt.GetDTransLength(); i1++)
	sb1.Append(dt.GetDTrans(i1)+",");
 sb1.Append("end\n");
 Console.Error.Write(sb1.ToString());
#endif
 s.dtrans_list.Add(dt);
 }
 }
 Console.Error.WriteLine("");
 }

/*
 * Function: free_dfa_states
 */
//private void free_dfa_states()
private static void free_dfa_states(Spec s)
 {
 s.dfa_states = null;
 s.dfa_sets = null;
 }

/*
 * Function: free_nfa_states
 */
private static void free_nfa_states(Spec s)
 {
 /* UNDONE: Remove references to nfas from within dfas. */
 /* UNDONE: Don"t free CAccepts. */
 s.nfa_states = null;
 s.nfa_start = null;
 s.state_rules = null;
 }

/*
 * function: add_to_dstates
 * Deion: Takes as input a CBunch with details of
 * a dfa state that needs to be created.
 * 1) Allocates a new dfa state and saves it in the appropriate Spec list
 * 2) Initializes the fields of the dfa state with the information in the CBunch.
 * 3) Returns index of new dfa.
 */
private static int add_to_dstates(Spec s, Bunch bunch)
 {
 Dfa dfa;

#if DEBUG
 Utility.assert(null != bunch.GetNFASet());
 Utility.assert(null != bunch.GetNFABit());
 Utility.assert(null != bunch.GetAccept() || Spec.NONE == bunch.GetAnchor());
#endif

 /* Allocate, passing Spec so dfa label can be set. */
 dfa = Alloc.NewDfa(s);

 /* Initialize fields, including the mark field. */
 dfa.SetNFASet(new ArrayList(bunch.GetNFASet()));
 dfa.SetNFABit(new BitSet(bunch.GetNFABit()));
 dfa.SetAccept(bunch.GetAccept());
 dfa.SetAnchor(bunch.GetAnchor());
 dfa.ClearMarked();

#if OLD_DUMP_DEBUG
 Console.Error.WriteLine("[Created new dfa_state #"+dfa.GetLabel()+"]");
 dfa.dump();
#endif

 /* Register dfa state using BitSet in spec Hashtable. */
 s.dfa_sets[dfa.GetNFABit()] = dfa;

#if OLD_DUMP_DEBUG
 Console.Error.Write("Registering set : ");
 Print_Set(dfa.GetNFASet());
 Console.Error.WriteLine("");
#endif

 return dfa.GetLabel();
 }

/*
 * Function: in_dstates
 */
private static int in_dstates(Spec s, Bunch bunch)
 {
 Dfa dfa;

#if OLD_DEBUG
 Console.Error.Write("Looking for set : ");
 Print_Set(bunch.GetNFASet());
 bunch.dump();
#endif

 o = s.dfa_sets[bunch.GetNFABit()];

 if (null != o)
 {
 dfa = (Dfa) o;
#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(" FOUND!");
#endif
 return dfa.GetLabel();
 }

#if OLD_DUMP_DEBUG
 Console.Error.WriteLine(" NOT FOUND!");
#endif
 return NOT_IN_DSTATES;
 }

#if OLD_DUMP_DEBUG
/*
 * function: Print_Set
 */
public static void Print_Set(ArrayList nfa_set)
 {
 int size; 
 int elem;

 size = nfa_set.Count;

 if (size == 0)
 {
 Console.Error.Write("empty ");
 }

 for (elem = 0; elem < size; ++elem)
 {
 Nfa nfa = (Nfa) nfa_set[elem];
 Console.Error.Write(nfa.GetLabel() + " ");
 }
 }
#endif
}
}

مرجع اصلي درس طراحي الگوريتم ها CLRS

Compiled HTML Help file : Introduction to Algorithms لينک دانلود

PDF: CLRS لينک دانلود