implab/ImplabNet Files · Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs

working on runnable component

cin - - Load All Authors

File last commit:

r178:d5c5db0335ee ref20160224


                r184:d6a8cba73acc

ref20160224

Download file

             RegularExpressionVisitor.cs
        
                    212 lines
            
             | 6.8 KiB
            
                | text/x-csharp
            
             |
                CSharpLexer
            
             / Implab / Automaton / RegularExpressions / RegularExpressionVisitor.cs
          
                    History
                
                 |
                  Source
                 | Raw
                 |Copy content
                 |Copy permalink

        cin
    
Working on text scanner

              r172
            
      using Implab;

      using System;

      using System.Collections.Generic;

      using System.Diagnostics;

      using System.Linq;

      namespace Implab.Automaton.RegularExpressions {

          /// <summary>

          /// Используется для построения ДКА по регулярному выражению, сначала обходит

          /// регулярное выражение и вычисляет followpos, затем используется метод

          /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.

          /// </summary>

        cin
    
working on JSON parser

              r178
            
          public class RegularExpressionVisitor : IVisitor {

        cin
    
Working on text scanner

              r172
            
              int m_idx;

        cin
    
refactoring

              r177
            
              Token m_root;

        cin
    
Working on text scanner

              r172
            
              HashSet<int> m_firstpos;

              HashSet<int> m_lastpos;

              readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();

              readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();

        cin
    
refactoring

              r177
            
              readonly HashSet<int> m_ends = new HashSet<int>();

        cin
    
Working on text scanner

              r172
            
        cin
    
working on JSON parser

              r178
            
              readonly IDFATableBuilder m_builder;

              readonly IAlphabetBuilder<HashSet<int>> m_states = new MapAlphabet<HashSet<int>>(

                  false,

                  new CustomEqualityComparer<HashSet<int>>(

                      (x, y) => x.SetEquals(y),

                      x => x.Sum(n => n.GetHashCode())

                  )

              );

              public RegularExpressionVisitor(IDFATableBuilder builder) {

                  Safe.ArgumentNotNull(builder, "builder");

                  m_builder = builder;

        cin
    
Working on text scanner

              r172
            
              }

        cin
    
working on JSON parser

              r178
            
              HashSet<int> Followpos(int pos) {

        cin
    
Working on text scanner

              r172
            
                  HashSet<int> set;

                  return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();

              }

              bool Nullable(object n) {

        cin
    
refactoring

              r177
            
                  if (n is EmptyToken || n is StarToken)

        cin
    
Working on text scanner

              r172
            
                      return true;

        cin
    
refactoring

              r177
            
                  var altToken = n as AltToken;

        cin
    
Working on text scanner

              r172
            
                  if (altToken != null)

                      return Nullable(altToken.Left) || Nullable(altToken.Right);

        cin
    
refactoring

              r177
            
                  var catToken = n as CatToken;

        cin
    
Working on text scanner

              r172
            
                  if (catToken != null)

                      return Nullable(catToken.Left) && Nullable(catToken.Right);

                  return false;

              }

        cin
    
working on JSON parser

              r178
            
              protected int Index {

                  get { return m_idx; }

              }

        cin
    
Working on text scanner

              r172
            
        cin
    
refactoring

              r177
            
              public void Visit(AltToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

                  var firtspos = new HashSet<int>();

                  var lastpos = new HashSet<int>();

                  token.Left.Accept(this);

                  firtspos.UnionWith(m_firstpos);

                  lastpos.UnionWith(m_lastpos);

                  token.Right.Accept(this);

                  firtspos.UnionWith(m_firstpos);

                  lastpos.UnionWith(m_lastpos);

                  m_firstpos = firtspos;

                  m_lastpos = lastpos;

              }

        cin
    
refactoring

              r177
            
              public void Visit(StarToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

                  token.Token.Accept(this);

                  foreach (var i in m_lastpos)

                      Followpos(i).UnionWith(m_firstpos);

              }

        cin
    
refactoring

              r177
            
              public void Visit(CatToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

                  var firtspos = new HashSet<int>();

                  var lastpos = new HashSet<int>();

                  token.Left.Accept(this);

                  firtspos.UnionWith(m_firstpos);

                  var leftLastpos = m_lastpos;

                  token.Right.Accept(this);

                  lastpos.UnionWith(m_lastpos);

                  var rightFirstpos = m_firstpos;

                  if (Nullable(token.Left))

                      firtspos.UnionWith(rightFirstpos);

                  if (Nullable(token.Right))

                      lastpos.UnionWith(leftLastpos);

                  m_firstpos = firtspos;

                  m_lastpos = lastpos;

                  foreach (var i in leftLastpos)

                      Followpos(i).UnionWith(rightFirstpos);

              }

        cin
    
refactoring

              r177
            
              public void Visit(EmptyToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

              }

        cin
    
refactoring

              r177
            
              public void Visit(SymbolToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

                  m_idx++;

                  m_indexes[m_idx] = token.Value;

                  m_firstpos = new HashSet<int>(new[] { m_idx });

                  m_lastpos = new HashSet<int>(new[] { m_idx });

              }

        cin
    
working on JSON parser

              r178
            
              public virtual void Visit(EndToken token) {

        cin
    
Working on text scanner

              r172
            
                  if (m_root == null)

                      m_root = token;

                  m_idx++;

        cin
    
working on JSON parser

              r178
            
                  m_indexes[m_idx] = AutomatonConst.UNCLASSIFIED_INPUT;

        cin
    
refactoring

              r177
            
                  m_firstpos = new HashSet<int>(new[] { m_idx });

                  m_lastpos = new HashSet<int>(new[] { m_idx });

                  Followpos(m_idx);

                  m_ends.Add(m_idx);

        cin
    
Working on text scanner

              r172
            
              }

        cin
    
working on JSON parser

              r178
            
              public void BuildDFA() {

                  AddState(m_firstpos);

                  SetInitialState(m_firstpos);

        cin
    
Working on text scanner

              r172
            
        cin
    
working on JSON parser

              r178
            
                  if(IsFinal(m_firstpos))

                      MarkFinalState(m_firstpos);

        cin
    
Working on text scanner

              r172
            
                  var inputMax = m_indexes.Values.Max();

                  var queue = new Queue<HashSet<int>>();

                  queue.Enqueue(m_firstpos);

                  while (queue.Count > 0) {

        cin
    
working on JSON parser

              r178
            
                      var s1 = queue.Dequeue();

        cin
    
Working on text scanner

              r172
            
                      for (int a = 0; a <= inputMax; a++) {

        cin
    
working on JSON parser

              r178
            
                          var s2 = new HashSet<int>();

                          foreach (var p in s1) {

        cin
    
Working on text scanner

              r172
            
                              if (m_indexes[p] == a) {

        cin
    
working on JSON parser

              r178
            
                                  s2.UnionWith(Followpos(p));

        cin
    
Working on text scanner

              r172
            
                              }

                          }

        cin
    
working on JSON parser

              r178
            
                          if (s2.Count > 0) {

                              if (!HasState(s2)) {

                                  AddState(s2);

                                  if (IsFinal(s2))

                                      MarkFinalState(s2);

                                  queue.Enqueue(s2);

                              }

        cin
    
Working on text scanner

              r172
            
        cin
    
working on JSON parser

              r178
            
                              DefineTransition(s1, s2, a);

        cin
    
Working on text scanner

              r172
            
                          }

        cin
    
working on JSON parser

              r178
            
        cin
    
Working on text scanner

              r172
            
                      }

                  }

              }

        cin
    
working on JSON parser

              r178
            
              protected bool HasState(HashSet<int> state) {

                  return m_states.Contains(state);

              }

              protected void AddState(HashSet<int> state) {

                  Debug.Assert(!HasState(state));

                  m_states.DefineSymbol(state);

              }

              protected int Translate(HashSet<int> state) {

                  Debug.Assert(HasState(state));

                  return m_states.Translate(state);

              }

              protected virtual void SetInitialState(HashSet<int> state) {

                  m_builder.SetInitialState(Translate(state));

              }

              protected virtual void MarkFinalState(HashSet<int> state) {

                  m_builder.MarkFinalState(Translate(state));

              }

              protected virtual void DefineTransition(HashSet<int> s1, HashSet<int> s2, int ch) {

                  m_builder.Add(new AutomatonTransition(Translate(s1), Translate(s2), ch));

              }

        cin
    
refactoring

              r177
            
              bool IsFinal(IEnumerable<int> state) {

                  Debug.Assert(state != null);

                  return state.Any(m_ends.Contains);

              }

        cin
    
Working on text scanner

              r172
            
          }

      }

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

cin Working on text scanner	r172	using Implab;
		using System;
		using System.Collections.Generic;
		using System.Diagnostics;
		using System.Linq;

		namespace Implab.Automaton.RegularExpressions {
		/// <summary>
		/// Используется для построения ДКА по регулярному выражению, сначала обходит
		/// регулярное выражение и вычисляет followpos, затем используется метод
		/// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
		/// </summary>
cin working on JSON parser	r178	public class RegularExpressionVisitor : IVisitor {
cin Working on text scanner	r172	int m_idx;
cin refactoring	r177	Token m_root;
cin Working on text scanner	r172	HashSet<int> m_firstpos;
		HashSet<int> m_lastpos;

		readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
		readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
cin refactoring	r177	readonly HashSet<int> m_ends = new HashSet<int>();
cin Working on text scanner	r172
cin working on JSON parser	r178	readonly IDFATableBuilder m_builder;
		readonly IAlphabetBuilder<HashSet<int>> m_states = new MapAlphabet<HashSet<int>>(
		false,
		new CustomEqualityComparer<HashSet<int>>(
		(x, y) => x.SetEquals(y),
		x => x.Sum(n => n.GetHashCode())
		)
		);

		public RegularExpressionVisitor(IDFATableBuilder builder) {
		Safe.ArgumentNotNull(builder, "builder");

		m_builder = builder;
cin Working on text scanner	r172	}

cin working on JSON parser	r178	HashSet<int> Followpos(int pos) {
cin Working on text scanner	r172	HashSet<int> set;
		return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
		}

		bool Nullable(object n) {
cin refactoring	r177	if (n is EmptyToken \|\| n is StarToken)
cin Working on text scanner	r172	return true;
cin refactoring	r177	var altToken = n as AltToken;
cin Working on text scanner	r172	if (altToken != null)
		return Nullable(altToken.Left) \|\| Nullable(altToken.Right);
cin refactoring	r177	var catToken = n as CatToken;
cin Working on text scanner	r172	if (catToken != null)
		return Nullable(catToken.Left) && Nullable(catToken.Right);
		return false;
		}

cin working on JSON parser	r178	protected int Index {
		get { return m_idx; }
		}
cin Working on text scanner	r172
cin refactoring	r177	public void Visit(AltToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;
		var firtspos = new HashSet<int>();
		var lastpos = new HashSet<int>();

		token.Left.Accept(this);
		firtspos.UnionWith(m_firstpos);
		lastpos.UnionWith(m_lastpos);

		token.Right.Accept(this);
		firtspos.UnionWith(m_firstpos);
		lastpos.UnionWith(m_lastpos);

		m_firstpos = firtspos;
		m_lastpos = lastpos;
		}

cin refactoring	r177	public void Visit(StarToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;
		token.Token.Accept(this);

		foreach (var i in m_lastpos)
		Followpos(i).UnionWith(m_firstpos);
		}

cin refactoring	r177	public void Visit(CatToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;

		var firtspos = new HashSet<int>();
		var lastpos = new HashSet<int>();
		token.Left.Accept(this);
		firtspos.UnionWith(m_firstpos);
		var leftLastpos = m_lastpos;

		token.Right.Accept(this);
		lastpos.UnionWith(m_lastpos);
		var rightFirstpos = m_firstpos;

		if (Nullable(token.Left))
		firtspos.UnionWith(rightFirstpos);

		if (Nullable(token.Right))
		lastpos.UnionWith(leftLastpos);

		m_firstpos = firtspos;
		m_lastpos = lastpos;

		foreach (var i in leftLastpos)
		Followpos(i).UnionWith(rightFirstpos);

		}

cin refactoring	r177	public void Visit(EmptyToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;
		}

cin refactoring	r177	public void Visit(SymbolToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;
		m_idx++;
		m_indexes[m_idx] = token.Value;
		m_firstpos = new HashSet<int>(new[] { m_idx });
		m_lastpos = new HashSet<int>(new[] { m_idx });
		}

cin working on JSON parser	r178	public virtual void Visit(EndToken token) {
cin Working on text scanner	r172	if (m_root == null)
		m_root = token;
		m_idx++;
cin working on JSON parser	r178	m_indexes[m_idx] = AutomatonConst.UNCLASSIFIED_INPUT;
cin refactoring	r177	m_firstpos = new HashSet<int>(new[] { m_idx });
		m_lastpos = new HashSet<int>(new[] { m_idx });
		Followpos(m_idx);
		m_ends.Add(m_idx);
cin Working on text scanner	r172	}

cin working on JSON parser	r178	public void BuildDFA() {
		AddState(m_firstpos);
		SetInitialState(m_firstpos);
cin Working on text scanner	r172
cin working on JSON parser	r178	if(IsFinal(m_firstpos))
		MarkFinalState(m_firstpos);
cin Working on text scanner	r172
		var inputMax = m_indexes.Values.Max();
		var queue = new Queue<HashSet<int>>();

		queue.Enqueue(m_firstpos);

		while (queue.Count > 0) {
cin working on JSON parser	r178	var s1 = queue.Dequeue();
cin Working on text scanner	r172
		for (int a = 0; a <= inputMax; a++) {
cin working on JSON parser	r178	var s2 = new HashSet<int>();
		foreach (var p in s1) {
cin Working on text scanner	r172	if (m_indexes[p] == a) {
cin working on JSON parser	r178	s2.UnionWith(Followpos(p));
cin Working on text scanner	r172	}
		}
cin working on JSON parser	r178	if (s2.Count > 0) {
		if (!HasState(s2)) {
		AddState(s2);
		if (IsFinal(s2))
		MarkFinalState(s2);

		queue.Enqueue(s2);
		}
cin Working on text scanner	r172
cin working on JSON parser	r178	DefineTransition(s1, s2, a);
cin Working on text scanner	r172	}
cin working on JSON parser	r178
cin Working on text scanner	r172	}
		}
		}

cin working on JSON parser	r178	protected bool HasState(HashSet<int> state) {
		return m_states.Contains(state);
		}

		protected void AddState(HashSet<int> state) {
		Debug.Assert(!HasState(state));

		m_states.DefineSymbol(state);
		}

		protected int Translate(HashSet<int> state) {
		Debug.Assert(HasState(state));

		return m_states.Translate(state);
		}

		protected virtual void SetInitialState(HashSet<int> state) {
		m_builder.SetInitialState(Translate(state));
		}

		protected virtual void MarkFinalState(HashSet<int> state) {
		m_builder.MarkFinalState(Translate(state));
		}

		protected virtual void DefineTransition(HashSet<int> s1, HashSet<int> s2, int ch) {

		m_builder.Add(new AutomatonTransition(Translate(s1), Translate(s2), ch));
		}

cin refactoring	r177	bool IsFinal(IEnumerable<int> state) {
		Debug.Assert(state != null);
		return state.Any(m_ends.Contains);
		}

cin Working on text scanner	r172	}
		}