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

Reworked cancelation handling, if the cancel handler isn't specified the OperationCanceledException will be handled by the error handler...

Reworked cancelation handling, if the cancel handler isn't specified the OperationCanceledException will be handled by the error handler Any unhandled OperationCanceledException will cause the promise cancelation

cin - - Load All Authors

File last commit:

r178:d5c5db0335ee ref20160224


                r187:dd4a3590f9c6

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