Mercurial > pub > ImplabNet

comparison Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs @ 172:92d5278d1b10 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working on text scanner
author cin
date Mon, 14 Mar 2016 01:19:38 +0300
parents
children a0ff6a0e9c44
comparison
equal deleted inserted replaced
171:0f70905b4652 172:92d5278d1b10
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Diagnostics;
5 using System.Linq;
6
7 namespace Implab.Automaton.RegularExpressions {
8 /// <summary>
9 /// Используется для построения ДКА по регулярному выражению, сначала обходит
10 /// регулярное выражение и вычисляет followpos, затем используется метод
11 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
12 /// </summary>
13 public class RegularExpressionVisitor<TTag> : IVisitor<TTag> {
14 int m_idx;
15 Token<TTag> m_root;
16 HashSet<int> m_firstpos;
17 HashSet<int> m_lastpos;
18
19 readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
20 readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
21 readonly Dictionary<int, TTag> m_ends = new Dictionary<int, TTag>();
22
23 public Dictionary<int, HashSet<int>> FollowposMap {
24 get { return m_followpos; }
25 }
26
27 public HashSet<int> Followpos(int pos) {
28 HashSet<int> set;
29 return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
30 }
31
32 bool Nullable(object n) {
33 if (n is EmptyToken<TTag> || n is StarToken<TTag>)
34 return true;
35 var altToken = n as AltToken<TTag>;
36 if (altToken != null)
37 return Nullable(altToken.Left) || Nullable(altToken.Right);
38 var catToken = n as CatToken<TTag>;
39 if (catToken != null)
40 return Nullable(catToken.Left) && Nullable(catToken.Right);
41 return false;
42 }
43
44
45 public void Visit(AltToken<TTag> token) {
46 if (m_root == null)
47 m_root = token;
48 var firtspos = new HashSet<int>();
49 var lastpos = new HashSet<int>();
50
51 token.Left.Accept(this);
52 firtspos.UnionWith(m_firstpos);
53 lastpos.UnionWith(m_lastpos);
54
55 token.Right.Accept(this);
56 firtspos.UnionWith(m_firstpos);
57 lastpos.UnionWith(m_lastpos);
58
59 m_firstpos = firtspos;
60 m_lastpos = lastpos;
61 }
62
63 public void Visit(StarToken<TTag> token) {
64 if (m_root == null)
65 m_root = token;
66 token.Token.Accept(this);
67
68 foreach (var i in m_lastpos)
69 Followpos(i).UnionWith(m_firstpos);
70 }
71
72 public void Visit(CatToken<TTag> token) {
73 if (m_root == null)
74 m_root = token;
75
76 var firtspos = new HashSet<int>();
77 var lastpos = new HashSet<int>();
78 token.Left.Accept(this);
79 firtspos.UnionWith(m_firstpos);
80 var leftLastpos = m_lastpos;
81
82 token.Right.Accept(this);
83 lastpos.UnionWith(m_lastpos);
84 var rightFirstpos = m_firstpos;
85
86 if (Nullable(token.Left))
87 firtspos.UnionWith(rightFirstpos);
88
89 if (Nullable(token.Right))
90 lastpos.UnionWith(leftLastpos);
91
92 m_firstpos = firtspos;
93 m_lastpos = lastpos;
94
95 foreach (var i in leftLastpos)
96 Followpos(i).UnionWith(rightFirstpos);
97
98 }
99
100 public void Visit(EmptyToken<TTag> token) {
101 if (m_root == null)
102 m_root = token;
103 }
104
105 public void Visit(SymbolToken<TTag> token) {
106 if (m_root == null)
107 m_root = token;
108 m_idx++;
109 m_indexes[m_idx] = token.Value;
110 m_firstpos = new HashSet<int>(new[] { m_idx });
111 m_lastpos = new HashSet<int>(new[] { m_idx });
112 }
113
114 public void Visit(EndToken<TTag> token) {
115 if (m_root == null)
116 m_root = token;
117 m_idx++;
118 m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
119 m_firstpos = new HashSet<int>(new[] { m_idx });
120 m_lastpos = new HashSet<int>(new[] { m_idx });
121 Followpos(m_idx);
122 m_ends.Add(m_idx, token.Tag);
123 }
124
125 public void BuildDFA(ITaggedDFABuilder<TTag> dfa) {
126 Safe.ArgumentNotNull(dfa,"dfa");
127
128 var states = new MapAlphabet<HashSet<int>>(
129 false,
130 new CustomEqualityComparer<HashSet<int>>(
131 (x, y) => x.SetEquals(y),
132 x => x.Sum(n => n.GetHashCode())
133 ));
134
135 var initialState = states.DefineSymbol(m_firstpos);
136 dfa.SetInitialState(initialState);
137
138 var tags = GetStateTags(m_firstpos);
139 if (tags != null && tags.Length > 0)
140 dfa.MarkFinalState(initialState, tags);
141
142 var inputMax = m_indexes.Values.Max();
143 var queue = new Queue<HashSet<int>>();
144
145 queue.Enqueue(m_firstpos);
146
147 while (queue.Count > 0) {
148 var state = queue.Dequeue();
149 var s1 = states.Translate(state);
150 Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);
151
152 for (int a = 0; a <= inputMax; a++) {
153 var next = new HashSet<int>();
154 foreach (var p in state) {
155 if (m_indexes[p] == a) {
156 next.UnionWith(Followpos(p));
157 }
158 }
159 if (next.Count > 0) {
160 int s2 = states.Translate(next);
161 if (s2 == DFAConst.UNCLASSIFIED_INPUT) {
162 s2 = states.DefineSymbol(next);
163
164 tags = GetStateTags(next);
165 if (tags != null && tags.Length > 0) {
166 dfa.MarkFinalState(s2);
167 dfa.SetStateTag(s2, tags);
168 }
169
170 queue.Enqueue(next);
171 }
172 dfa.Add(new AutomatonTransition(s1, s2, a));
173 }
174 }
175 }
176 }
177
178 TTag[] GetStateTags(IEnumerable<int> state) {
179 Debug.Assert(state != null);
180 return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray();
181 }
182
183 }
184 }