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

refactoring

cin - - Load All Authors

File last commit:

r177:a0ff6a0e9c44 ref20160224


                r177:a0ff6a0e9c44

ref20160224

Download file

             RegularExpressionVisitor.cs
        
                    206 lines
            
             | 7.2 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>

          public class RegularExpressionVisitor<TTag> : IVisitor<TTag> {

              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>();

              readonly Dictionary<int, TTag> m_tags = new Dictionary<int, TTag>();

        cin
    
Working on text scanner

              r172
            
              public Dictionary<int, HashSet<int>> FollowposMap {

                  get { return m_followpos; }

              }

              public HashSet<int> Followpos(int pos) {

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

              }

              public void Visit(EndToken<TTag> token) {

                  if (m_root == null)

                      m_root = token;

                  m_idx++;

                  m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;

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

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

                  Followpos(m_idx);

        cin
    
refactoring

              r177
            
                  m_ends.Add(m_idx);

                  m_tags.Add(m_idx, token.Tag);

              }

              public void Visit(EndToken token) {

                  if (m_root == null)

                      m_root = token;

                  m_idx++;

                  m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;

                  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
            
              }

              public void BuildDFA(ITaggedDFABuilder<TTag> dfa) {

                  Safe.ArgumentNotNull(dfa,"dfa");

                  var states = new MapAlphabet<HashSet<int>>(

                                   false,

                                   new CustomEqualityComparer<HashSet<int>>(

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

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

                                   ));

                  var initialState = states.DefineSymbol(m_firstpos);

                  dfa.SetInitialState(initialState);

                  var tags = GetStateTags(m_firstpos);

                  if (tags != null && tags.Length > 0)

                      dfa.MarkFinalState(initialState, tags);

                  var inputMax = m_indexes.Values.Max();

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

                  queue.Enqueue(m_firstpos);

                  while (queue.Count > 0) {

                      var state = queue.Dequeue();

                      var s1 = states.Translate(state);

                      Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);

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

                          var next = new HashSet<int>();

                          foreach (var p in state) {

                              if (m_indexes[p] == a) {

                                  next.UnionWith(Followpos(p));

                              }

                          }

                          if (next.Count > 0) {

        cin
    
refactoring

              r177
            
                              int s2;

                              if (states.Contains(next)) {

                                  s2 = states.Translate(next);

                              } else {

        cin
    
Working on text scanner

              r172
            
                                  s2 = states.DefineSymbol(next);

        cin
    
refactoring

              r177
            
                                  if (IsFinal(next)) {

        cin
    
Working on text scanner

              r172
            
                                      dfa.MarkFinalState(s2);

        cin
    
refactoring

              r177
            
                                      tags = GetStateTags(next);

                                      if (tags != null && tags.Length > 0)

                                          dfa.SetStateTag(s2, tags);

        cin
    
Working on text scanner

              r172
            
                                  }

                                  queue.Enqueue(next);

                              }

                              dfa.Add(new AutomatonTransition(s1, s2, a));

                          }

                      }

                  }

              }

        cin
    
refactoring

              r177
            
              bool IsFinal(IEnumerable<int> state) {

                  Debug.Assert(state != null);

                  return state.Any(m_ends.Contains);

              }

        cin
    
Working on text scanner

              r172
            
              TTag[] GetStateTags(IEnumerable<int> state) {

                  Debug.Assert(state != null);

        cin
    
refactoring

              r177
            
                  return state.Where(m_tags.ContainsKey).Select(pos => m_tags[pos]).ToArray();

        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>
		public class RegularExpressionVisitor<TTag> : IVisitor<TTag> {
		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>();
		readonly Dictionary<int, TTag> m_tags = new Dictionary<int, TTag>();
cin Working on text scanner	r172
		public Dictionary<int, HashSet<int>> FollowposMap {
		get { return m_followpos; }
		}

		public HashSet<int> Followpos(int pos) {
		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 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 });
		}

		public void Visit(EndToken<TTag> token) {
		if (m_root == null)
		m_root = token;
		m_idx++;
		m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
		m_firstpos = new HashSet<int>(new[] { m_idx });
		m_lastpos = new HashSet<int>(new[] { m_idx });
		Followpos(m_idx);
cin refactoring	r177	m_ends.Add(m_idx);
		m_tags.Add(m_idx, token.Tag);
		}

		public void Visit(EndToken token) {
		if (m_root == null)
		m_root = token;
		m_idx++;
		m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
		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	}

		public void BuildDFA(ITaggedDFABuilder<TTag> dfa) {
		Safe.ArgumentNotNull(dfa,"dfa");

		var states = new MapAlphabet<HashSet<int>>(
		false,
		new CustomEqualityComparer<HashSet<int>>(
		(x, y) => x.SetEquals(y),
		x => x.Sum(n => n.GetHashCode())
		));

		var initialState = states.DefineSymbol(m_firstpos);
		dfa.SetInitialState(initialState);

		var tags = GetStateTags(m_firstpos);
		if (tags != null && tags.Length > 0)
		dfa.MarkFinalState(initialState, tags);

		var inputMax = m_indexes.Values.Max();
		var queue = new Queue<HashSet<int>>();

		queue.Enqueue(m_firstpos);

		while (queue.Count > 0) {
		var state = queue.Dequeue();
		var s1 = states.Translate(state);
		Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);

		for (int a = 0; a <= inputMax; a++) {
		var next = new HashSet<int>();
		foreach (var p in state) {
		if (m_indexes[p] == a) {
		next.UnionWith(Followpos(p));
		}
		}
		if (next.Count > 0) {
cin refactoring	r177	int s2;
		if (states.Contains(next)) {
		s2 = states.Translate(next);
		} else {
cin Working on text scanner	r172	s2 = states.DefineSymbol(next);

cin refactoring	r177	if (IsFinal(next)) {

cin Working on text scanner	r172	dfa.MarkFinalState(s2);
cin refactoring	r177	tags = GetStateTags(next);
		if (tags != null && tags.Length > 0)
		dfa.SetStateTag(s2, tags);
cin Working on text scanner	r172	}

		queue.Enqueue(next);
		}
		dfa.Add(new AutomatonTransition(s1, s2, a));
		}
		}
		}
		}

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

cin Working on text scanner	r172	TTag[] GetStateTags(IEnumerable<int> state) {
		Debug.Assert(state != null);
cin refactoring	r177	return state.Where(m_tags.ContainsKey).Select(pos => m_tags[pos]).ToArray();
cin Working on text scanner	r172	}

		}
		}