Click here to Skip to main content
12,348,594 members (71,104 online)
Click here to Skip to main content

Stats

119.9K views
5.6K downloads
113 bookmarked
Posted

An Implementation of Regular Expression Parser in C#

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

namespace RegularExpression
{
  internal class State
  {

    // the one and only Id tracker
    static private int m_nStateId = 0;

    // Set of transition objects
    public Map m_map = new Map();

    private int m_nId = 0;

    public State()
    {
      m_nId = m_nStateId++;
    }
    
    public int Id
    {
      get
      {
        return m_nId;
      }
    }

    public void AddTransition(string sInputSymbol, State stateTo)
    {      
      m_map.Add(sInputSymbol, stateTo);

      
    }

    public State[] GetTransitions(string sInputSymbol)
    {
      if (m_map.Contains(sInputSymbol) == true)
      {
        Set set = (Set)m_map[sInputSymbol];
        return (State[])set.ToArray(typeof(State));
      }
      return null;
    }

    public State GetSingleTransition(string sInputSymbol)
    {
      if (m_map.Contains(sInputSymbol) == true)
      {
        Set set = (Set)m_map[sInputSymbol];
        return (State) set[0];
      }
      return null;
    }
    public void RemoveTransition(string sInputSymbol)
    {
       m_map.Remove(sInputSymbol);
    }
    
    public int ReplaceTransitionState(State stateOld, State stateNew)
    {
      int nReplacementCount = 0;
      Set setTrans = null;
      foreach (DictionaryEntry de in m_map)
      {
        setTrans = (Set)de.Value;
        if (setTrans.ElementExist(stateOld) == true)
        {
          setTrans.RemoveElement(stateOld);
          setTrans.AddElement(stateNew);
          nReplacementCount++;
        }
      }
      return nReplacementCount;
    }

    private bool m_bAcceptingState = false;

    public bool AcceptingState
    {
      get { return m_bAcceptingState; }
      set { m_bAcceptingState = value; }
    }


    public bool IsDeadState()
    {
      if (m_bAcceptingState)
      {
        return false;
      }
      if (m_map.Count == 0)
      {
        return false;
      }
      Set setToState = null;
      foreach (DictionaryEntry de in m_map)
      {
        setToState = (Set)de.Value;
        
        State state = null;
        foreach (object objState in setToState)  // in a DFA, it should only iterate once
        {
          state = (State)objState;
          if (state.Equals(this) == false)
          {
            return false;
          }
        }
      }

      return true;
    }

    static public void ResetCounter()
    {
      m_nStateId = 0;
    }

    //public bool IsDeadEnd()
    //{
    //  return (m_map.Count == 0 && m_bAcceptingState == false ? true : false);
    //}

    
  }
}

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

You may also be interested in...

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