Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

An Implementation of Regular Expression Parser in C#

, 24 Jun 2009 CPOL
An article on how one can implement regular expression parser
LexAnal3_regexpr2nfa.zip
LexAnal3_regexpr2nfa.pdf
LexAnal4_nfa2dfa.zip
LexAnal4_nfa2dfa.pdf
LexAnal5_minimaldfa.zip
LexAnal5_minimaldfa.pdf
RegExDemo.zip
RegExDemo
Driver
MatchInfoDS.xsc
MatchInfoDS.xss
Properties
Settings.settings
RegExImpl.suo
RegularExpression
FsaDS.xsc
FsaDS.xss
Properties
Settings.settings
RegExSource.zip
RegExSource
RegularExpression
FsaDS.xsc
FsaDS.xss
Properties
Settings.settings
RegEx_Demo.zip
RegularExpression.dll
Driver.exe
RegEx_Src.zip
RegularExpression
Properties
Settings.settings
Driver
MatchInfoDS.xsc
MatchInfoDS.xss
Properties
Settings.settings
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace RegularExpression
{
  /// <summary>
  /// this class simply the conversion process from the NFA to DFA.
  /// Many other implemention of NFA->DFA does this in the same method.
  /// But I thought having a helper class will make the code clearer.
  /// </summary>
  internal class NfaToDfaHelper
  {
    /// <summary>
    /// array of of DfaStateRecord
    /// </summary>
    private Hashtable m_hashStateTable = new Hashtable();


    /// <summary>
    /// A nested calss.
    /// A row with three feilds. to store DFA states with two other attributes.
    /// </summary>
    private class DfaStateRecord
    {
      /// <summary>
      /// set of NFA state from which the DFA state was created
      /// </summary>
      public Set SetEclosure = null;
      /// <summary>
      /// a flag to indicate wheather or not this DFA state has been processed.
      /// See the Subset Construction algorithom for detail
      /// </summary>
      public bool Marked = false;

    }

    public NfaToDfaHelper()
    {

    }
    /// <summary>
    /// Simply adds newly created DFA state to the table
    /// </summary>
    /// <param name="stateDfa">the newly created DFA state</param>
    /// <param name="setEclosure">set of Eclosure that was used to create the DFA state</param>
    public void AddDfaState(State stateDfa, Set setEclosure)
    {
      DfaStateRecord stateRecord = new DfaStateRecord();
      stateRecord.SetEclosure = setEclosure;

      m_hashStateTable[stateDfa] = stateRecord;
    }

    /// <summary>
    /// finds a DFA state using a set of Eclosure state as search criteria.
    /// because all DFAs are constructed from a set of NFA state
    /// </summary>
    /// <param name="setNfaState">set of Eclosure state as search criteria</param>
    /// <returns>if found, returns the DFA state record, or returns null</returns>
    public State FindDfaStateByEclosure(Set setEclosure)
    {
      DfaStateRecord stateRecord = null;

      foreach (DictionaryEntry de in m_hashStateTable)
      {
        stateRecord = (DfaStateRecord)de.Value;
        if (stateRecord.SetEclosure.IsEqual(setEclosure) == true)
        {
          return (State)de.Key;
        }
      }
      return null;

    }  // end of FindDfaStateByEclosure method

    public Set GetEclosureByDfaState(State state)
    {
      DfaStateRecord dsr = (DfaStateRecord)m_hashStateTable[state];

      if (dsr != null)
      { 
        return dsr.SetEclosure;
      }
      return null;
    }
    public State GetNextUnmarkedDfaState()
    {
      DfaStateRecord stateRecord = null;

      foreach (DictionaryEntry de in m_hashStateTable)
      {
        stateRecord = (DfaStateRecord)de.Value;

        if (stateRecord.Marked == false)
        {
          return (State) de.Key;
        }

      }  

      return null ;
    }
    public void Mark(State stateT)
    {
      DfaStateRecord stateRecord = (DfaStateRecord)m_hashStateTable[stateT];
      stateRecord.Marked = true;
    }

    /// <summary>
    /// checks to see if a set contains any state that is an accepting state.
    /// used in NFA to DFA conversion
    /// </summary>
    /// <param name="setState">set of state</param>
    /// <returns>true if set contains at least one accepting state, else false</returns>

    public Set GetAllDfaState()
    {
      Set setState = new Set();

      foreach (object objKey in m_hashStateTable.Keys)
      {
        setState.AddElement(objKey);
      }

      return setState;
    }

  }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mizan Rahman

Denmark Denmark
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.1411023.1 | Last Updated 24 Jun 2009
Article Copyright 2008 by Mizan Rahman
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid