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

Added ResetState to RunnableComponent to reset in case of failure...

Added ResetState to RunnableComponent to reset in case of failure Added StateChanged event to IRunnable Renamed Promise.SUCCESS -> Promise.Success Added Promise.FromException Renamed Bundle -> PromiseAll in PromiseExtensions

cin - - Load All Authors

File last commit:

r183:4f82e0f161c3 ref20160224


                r205:8200ab154c8a

Download file

             RegularDFA.cs
        
                    91 lines
            
             | 3.1 KiB
            
                | text/x-csharp
            
             |
                CSharpLexer
            
             / Implab / Automaton / RegularExpressions / RegularDFA.cs
          
                    History
                
                 |
                  Source
                 | Raw
                 |Copy content
                 |Copy permalink

        cin
    
refactoring

              r177
            
      using System.Collections.Generic;

        cin
    
Working on text scanner

              r172
            
      using System.Linq;

      namespace Implab.Automaton.RegularExpressions {

        cin
    
sync

              r179
            
          public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {

        cin
    
Working on text scanner

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

              readonly IAlphabet<TInput> m_alphabet;

        cin
    
sync

              r179
            
              public RegularDFA(IAlphabet<TInput> alphabet) {

        cin
    
Working on text scanner

              r172
            
                  Safe.ArgumentNotNull(alphabet, "aplhabet");

                  m_alphabet = alphabet;

              }

              public IAlphabet<TInput> InputAlphabet {

                  get {

                      return m_alphabet;

                  }

              }

              public void MarkFinalState(int s, TTag[] tags) {

                  MarkFinalState(s);

                  SetStateTag(s, tags);

              }

              public void SetStateTag(int s, TTag[] tags) {

                  Safe.ArgumentNotNull(tags, "tags");

                  m_tags[s] = tags;

              }

              public TTag[] GetStateTag(int s) {

                  TTag[] tags;

                  return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];

              }

        cin
    
rewritten the text scanner

              r176
            
              public TTag[][] CreateTagTable() {

                  var table = new TTag[StateCount][];

        cin
    
Working on text scanner

              r172
            
        cin
    
rewritten the text scanner

              r176
            
                  foreach (var pair in m_tags)

                      table[pair.Key] = pair.Value;

        cin
    
Working on text scanner

              r172
            
                  return table;

              }

              /// <summary>

              /// Optimize the specified alphabet.

              /// </summary>

              /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>

        cin
    
sync

              r179
            
              public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {

        cin
    
Working on text scanner

              r172
            
                  Safe.ArgumentNotNull(alphabet, "alphabet");

        cin
    
sync

              r179
            
                  var dfa = new RegularDFA<TInput, TTag>(alphabet);

        cin
    
Working on text scanner

              r172
            
                  var alphaMap = new Dictionary<int,int>();

                  var stateMap = new Dictionary<int,int>();

                  Optimize(dfa, alphaMap, stateMap); 

                  // mark tags in the new DFA

                  foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))

                      dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());

                  // make the alphabet for the new DFA

        cin
    
minor fixes and debug

              r181
            
                  // skip all unclassified symbols

                  foreach (var pair in alphaMap.Where(x => x.Value != 0))

        cin
    
Working on text scanner

              r172
            
                      alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);

                  return dfa;

              }

        cin
    
fixed DFA optimization, JSON is fully functional

              r183
            
              protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {

        cin
    
Working on text scanner

              r172
            
                  var arrayComparer = new CustomEqualityComparer<TTag[]>(

                      (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),

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

                  );

        cin
    
fixed DFA optimization, JSON is fully functional

              r183
            
                  return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));

        cin
    
Working on text scanner

              r172
            
              }

        cin
    
pretty print DFA, the minimization is still buggy

              r182
            
              public override string ToString() {

                  var states = new MapAlphabet<string>(false, null);

                  for (int i = 0; i < StateCount; i++)

                      states.DefineSymbol(string.Format("s{0}", i), i);

                  return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize);

              }

        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 refactoring	r177	using System.Collections.Generic;
cin Working on text scanner	r172	using System.Linq;

		namespace Implab.Automaton.RegularExpressions {
cin sync	r179	public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
cin Working on text scanner	r172
		readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
		readonly IAlphabet<TInput> m_alphabet;

cin sync	r179	public RegularDFA(IAlphabet<TInput> alphabet) {
cin Working on text scanner	r172	Safe.ArgumentNotNull(alphabet, "aplhabet");

		m_alphabet = alphabet;
		}


		public IAlphabet<TInput> InputAlphabet {
		get {
		return m_alphabet;
		}
		}

		public void MarkFinalState(int s, TTag[] tags) {
		MarkFinalState(s);
		SetStateTag(s, tags);
		}

		public void SetStateTag(int s, TTag[] tags) {
		Safe.ArgumentNotNull(tags, "tags");
		m_tags[s] = tags;
		}

		public TTag[] GetStateTag(int s) {
		TTag[] tags;
		return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
		}

cin rewritten the text scanner	r176	public TTag[][] CreateTagTable() {
		var table = new TTag[StateCount][];
cin Working on text scanner	r172
cin rewritten the text scanner	r176	foreach (var pair in m_tags)
		table[pair.Key] = pair.Value;
cin Working on text scanner	r172
		return table;
		}

		/// <summary>
		/// Optimize the specified alphabet.
		/// </summary>
		/// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
cin sync	r179	public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
cin Working on text scanner	r172	Safe.ArgumentNotNull(alphabet, "alphabet");

cin sync	r179	var dfa = new RegularDFA<TInput, TTag>(alphabet);
cin Working on text scanner	r172
		var alphaMap = new Dictionary<int,int>();
		var stateMap = new Dictionary<int,int>();

		Optimize(dfa, alphaMap, stateMap);

		// mark tags in the new DFA
		foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
		dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());

		// make the alphabet for the new DFA
cin minor fixes and debug	r181	// skip all unclassified symbols
		foreach (var pair in alphaMap.Where(x => x.Value != 0))
cin Working on text scanner	r172	alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
		return dfa;
		}

cin fixed DFA optimization, JSON is fully functional	r183	protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
cin Working on text scanner	r172	var arrayComparer = new CustomEqualityComparer<TTag[]>(
		(x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
		x => x.Sum(it => x.GetHashCode())
		);
cin fixed DFA optimization, JSON is fully functional	r183	return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
cin Working on text scanner	r172	}

cin pretty print DFA, the minimization is still buggy	r182	public override string ToString() {
		var states = new MapAlphabet<string>(false, null);

		for (int i = 0; i < StateCount; i++)
		states.DefineSymbol(string.Format("s{0}", i), i);

		return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize);
		}

cin Working on text scanner	r172	}
		}