Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATable.cs @ 183:4f82e0f161c3 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fixed DFA optimization, JSON is fully functional
author cin
date Fri, 25 Mar 2016 02:49:02 +0300
parents 76e8f2ba12b8
children 5f7a3e1d32b9
comparison
equal deleted inserted replaced
182:76e8f2ba12b8 183:4f82e0f161c3
139 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества 139 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
140 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, 140 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
141 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. 141 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
142 /// </remarks> 142 /// </remarks>
143 /// <returns>The final states.</returns> 143 /// <returns>The final states.</returns>
144 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() { 144 protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
145 return new HashSet<int>[] { m_finalStates }; 145 return new [] { new HashSet<int>(states) };
146 } 146 }
147 147
148 protected void Optimize( 148 protected void Optimize(
149 IDFATableBuilder optimalDFA, 149 IDFATableBuilder optimalDFA,
150 IDictionary<int,int> alphabetMap, 150 IDictionary<int,int> alphabetMap,
161 ); 161 );
162 162
163 var optimalStates = new HashSet<HashSet<int>>(setComparer); 163 var optimalStates = new HashSet<HashSet<int>>(setComparer);
164 var queue = new HashSet<HashSet<int>>(setComparer); 164 var queue = new HashSet<HashSet<int>>(setComparer);
165 165
166 // получаем конечные состояния, сгруппированные по маркерам 166 optimalStates.Add(new HashSet<int>(FinalStates));
167 optimalStates.UnionWith(
168 GroupFinalStates()
169 );
170 167
171 var state = new HashSet<int>( 168 var state = new HashSet<int>(
172 Enumerable 169 Enumerable
173 .Range(0, m_stateCount) 170 .Range(0, m_stateCount)
174 .Where(i => !m_finalStates.Contains(i)) 171 .Where(i => !m_finalStates.Contains(i))
188 var stateA = queue.First(); 185 var stateA = queue.First();
189 queue.Remove(stateA); 186 queue.Remove(stateA);
190 187
191 for (int c = 0; c < m_symbolCount; c++) { 188 for (int c = 0; c < m_symbolCount; c++) {
192 var stateX = new HashSet<int>(); 189 var stateX = new HashSet<int>();
193 //foreach(var a in stateA.Where(rmap.ContainsKey)) 190 foreach(var a in stateA.Where(rmap.ContainsKey))
194 // stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a' 191 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
195
196 stateX.UnionWith(m_transitions.Where(t => stateA.Contains(t.s2) && t.edge == c).Select(t => t.s1));
197 192
198 var tmp = optimalStates.ToArray(); 193 var tmp = optimalStates.ToArray();
199 foreach (var stateY in tmp) { 194 foreach (var stateY in tmp) {
200 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { 195 var stateR1 = new HashSet<int>(stateY);
201 var stateR1 = new HashSet<int>(stateY); 196 var stateR2 = new HashSet<int>(stateY);
202 var stateR2 = new HashSet<int>(stateY); 197
203 198 stateR1.IntersectWith(stateX);
204 stateR1.IntersectWith(stateX); 199 stateR2.ExceptWith(stateX);
205 stateR2.ExceptWith(stateX); 200
201 if (stateR1.Count > 0 && stateR2.Count > 0) {
202
206 203
207 optimalStates.Remove(stateY); 204 optimalStates.Remove(stateY);
208 optimalStates.Add(stateR1); 205 optimalStates.Add(stateR1);
209 optimalStates.Add(stateR2); 206 optimalStates.Add(stateR2);
210 207
218 } 215 }
219 } 216 }
220 } 217 }
221 } 218 }
222 219
220 // дополнительно разбиваем конечные состояния
221 foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
222 optimalStates.Remove(final);
223 foreach (var split in SplitFinalStates(final))
224 optimalStates.Add(split);
225 }
226
227
223 // карта получения оптимального состояния по соотвествующему ему простому состоянию 228 // карта получения оптимального состояния по соотвествующему ему простому состоянию
224 var nextState = 0; 229 var nextState = 0;
225 foreach (var item in optimalStates) { 230 foreach (var item in optimalStates) {
226 var id = nextState++; 231 var id = nextState++;
227 foreach (var s in item) 232 foreach (var s in item)