• وبلاگ : پاي سيب
  • يادداشت : perl
  • نظرات : 0 خصوصي ، 68 عمومي
  • درب کنسرو بازکن برقی

    نام:
    ايميل:
    سايت:
       
    متن پيام :
    حداکثر 2000 حرف
    كد امنيتي:
      
      
     
    + نظريه 

    همانطور که مستحضريد در نظريه زبانها و ماشينها الگوريتمهاي مختلفي بکار ميرود که اکثر آن بصورت دستي و بر روي ورق انجام و ژياده سازي ميشود در ادامه تبديل گرامر NFA به Dfa را مشاهده مينماييد.

    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
    }
    }