Mercurial > pub > ImplabNet

comparison Implab/Automaton/RegularExpressions/RegularDFABuilder.cs @ 165:e227e78d72e4 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DFA refactoring
author cin
date Mon, 29 Feb 2016 02:02:17 +0300
parents ec35731ae299
children 181119ef3b39
comparison
equal deleted inserted replaced
164:ec35731ae299 165:e227e78d72e4
9 /// Используется для построения ДКА по регулярному выражению, сначала обходит 9 /// Используется для построения ДКА по регулярному выражению, сначала обходит
10 /// регулярное выражение и вычисляет followpos, затем используется метод 10 /// регулярное выражение и вычисляет followpos, затем используется метод
11 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата. 11 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
12 /// </summary> 12 /// </summary>
13 public class RegularDFABuilder<TTag> : IVisitor<TTag> { 13 public class RegularDFABuilder<TTag> : IVisitor<TTag> {
14 int m_idx = 0; 14 int m_idx;
15 Token<TTag> m_root; 15 Token<TTag> m_root;
16 HashSet<int> m_firstpos; 16 HashSet<int> m_firstpos;
17 HashSet<int> m_lastpos; 17 HashSet<int> m_lastpos;
18 18
19 readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>(); 19 readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
24 get { return m_followpos; } 24 get { return m_followpos; }
25 } 25 }
26 26
27 public HashSet<int> Followpos(int pos) { 27 public HashSet<int> Followpos(int pos) {
28 HashSet<int> set; 28 HashSet<int> set;
29 if (m_followpos.TryGetValue(pos, out set)) 29 return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
30 return set;
31 return m_followpos[pos] = new HashSet<int>();
32 } 30 }
33 31
34 bool Nullable(object n) { 32 bool Nullable(object n) {
35 if (n is EmptyToken<TTag> || n is StarToken<TTag>) 33 if (n is EmptyToken<TTag> || n is StarToken<TTag>)
36 return true; 34 return true;
37 if (n is AltToken<TTag>) 35 var altToken = n as AltToken<TTag>;
38 return Nullable(((AltToken<TTag>)n).Left) || Nullable(((AltToken<TTag>)n).Right); 36 if (altToken != null)
39 if (n is CatToken<TTag>) 37 return Nullable(altToken.Left) || Nullable(altToken.Right);
40 return Nullable(((CatToken<TTag>)n).Left) && Nullable(((CatToken<TTag>)n).Right); 38 var catToken = n as CatToken<TTag>;
39 if (catToken != null)
40 return Nullable(catToken.Left) && Nullable(catToken.Right);
41 return false; 41 return false;
42 } 42 }
43 43
44 44
45 public void Visit(AltToken<TTag> token) { 45 public void Visit(AltToken<TTag> token) {
120 m_lastpos = new HashSet<int>(new[] { m_idx }); 120 m_lastpos = new HashSet<int>(new[] { m_idx });
121 Followpos(m_idx); 121 Followpos(m_idx);
122 m_ends.Add(m_idx, token.Tag); 122 m_ends.Add(m_idx, token.Tag);
123 } 123 }
124 124
125 public void BuildDFA(IDFATransitionTableBuilder<TTag> dfa) { 125 public void BuildDFA(IDFATableBuilder<TTag> dfa) {
126 Safe.ArgumentNotNull(dfa,"dfa"); 126 Safe.ArgumentNotNull(dfa,"dfa");
127 127
128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>( 128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
129 (x, y) => x.SetEquals(y), 129 (x, y) => x.SetEquals(y),
130 x => x.Sum(n => n.GetHashCode()) 130 x => x.Sum(n => n.GetHashCode())