Mercurial > pub > ImplabNet
diff Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs @ 177:a0ff6a0e9c44 ref20160224
refactoring
author | cin |
---|---|
date | Wed, 23 Mar 2016 01:42:00 +0300 |
parents | 92d5278d1b10 |
children | d5c5db0335ee |
line wrap: on
line diff
--- a/Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs Tue Mar 22 18:58:40 2016 +0300 +++ b/Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs Wed Mar 23 01:42:00 2016 +0300 @@ -12,13 +12,14 @@ /// </summary> public class RegularExpressionVisitor<TTag> : IVisitor<TTag> { int m_idx; - Token<TTag> m_root; + Token m_root; 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>(); - readonly Dictionary<int, TTag> m_ends = new Dictionary<int, TTag>(); + readonly HashSet<int> m_ends = new HashSet<int>(); + readonly Dictionary<int, TTag> m_tags = new Dictionary<int, TTag>(); public Dictionary<int, HashSet<int>> FollowposMap { get { return m_followpos; } @@ -30,19 +31,19 @@ } bool Nullable(object n) { - if (n is EmptyToken<TTag> || n is StarToken<TTag>) + if (n is EmptyToken || n is StarToken) return true; - var altToken = n as AltToken<TTag>; + var altToken = n as AltToken; if (altToken != null) return Nullable(altToken.Left) || Nullable(altToken.Right); - var catToken = n as CatToken<TTag>; + var catToken = n as CatToken; if (catToken != null) return Nullable(catToken.Left) && Nullable(catToken.Right); return false; } - public void Visit(AltToken<TTag> token) { + public void Visit(AltToken token) { if (m_root == null) m_root = token; var firtspos = new HashSet<int>(); @@ -60,7 +61,7 @@ m_lastpos = lastpos; } - public void Visit(StarToken<TTag> token) { + public void Visit(StarToken token) { if (m_root == null) m_root = token; token.Token.Accept(this); @@ -69,7 +70,7 @@ Followpos(i).UnionWith(m_firstpos); } - public void Visit(CatToken<TTag> token) { + public void Visit(CatToken token) { if (m_root == null) m_root = token; @@ -97,12 +98,12 @@ } - public void Visit(EmptyToken<TTag> token) { + public void Visit(EmptyToken token) { if (m_root == null) m_root = token; } - public void Visit(SymbolToken<TTag> token) { + public void Visit(SymbolToken token) { if (m_root == null) m_root = token; m_idx++; @@ -119,7 +120,19 @@ m_firstpos = new HashSet<int>(new[] { m_idx }); m_lastpos = new HashSet<int>(new[] { m_idx }); Followpos(m_idx); - m_ends.Add(m_idx, token.Tag); + 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); } public void BuildDFA(ITaggedDFABuilder<TTag> dfa) { @@ -157,14 +170,18 @@ } } if (next.Count > 0) { - int s2 = states.Translate(next); - if (s2 == DFAConst.UNCLASSIFIED_INPUT) { + int s2; + if (states.Contains(next)) { + s2 = states.Translate(next); + } else { s2 = states.DefineSymbol(next); - tags = GetStateTags(next); - if (tags != null && tags.Length > 0) { + if (IsFinal(next)) { + dfa.MarkFinalState(s2); - dfa.SetStateTag(s2, tags); + tags = GetStateTags(next); + if (tags != null && tags.Length > 0) + dfa.SetStateTag(s2, tags); } queue.Enqueue(next); @@ -175,9 +192,14 @@ } } + bool IsFinal(IEnumerable<int> state) { + Debug.Assert(state != null); + return state.Any(m_ends.Contains); + } + TTag[] GetStateTags(IEnumerable<int> state) { Debug.Assert(state != null); - return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray(); + return state.Where(m_tags.ContainsKey).Select(pos => m_tags[pos]).ToArray(); } }