Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATable.cs @ 181:b2b6a6640aa3 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
minor fixes and debug
author cin
date Thu, 24 Mar 2016 03:54:46 +0300
parents c32688129f14
children 76e8f2ba12b8
comparison
equal deleted inserted replaced
180:c32688129f14 181:b2b6a6640aa3
1 using Implab; 1 using Implab;
2 using System; 2 using System;
3 using System.Collections.Generic; 3 using System.Collections.Generic;
4 using System.Linq; 4 using System.Linq;
5 using System.Diagnostics;
5 6
6 namespace Implab.Automaton { 7 namespace Implab.Automaton {
7 public class DFATable : IDFATableBuilder { 8 public class DFATable : IDFATableBuilder {
8 int m_stateCount; 9 int m_stateCount;
9 int m_symbolCount; 10 int m_symbolCount;
41 42
42 #endregion 43 #endregion
43 44
44 public void SetInitialState(int s) { 45 public void SetInitialState(int s) {
45 Safe.ArgumentAssert(s >= 0, "s"); 46 Safe.ArgumentAssert(s >= 0, "s");
47 m_stateCount = Math.Max(m_stateCount, s + 1);
46 m_initialState = s; 48 m_initialState = s;
47 } 49 }
48 50
49 public void MarkFinalState(int state) { 51 public void MarkFinalState(int state) {
52 m_stateCount = Math.Max(m_stateCount, state + 1);
50 m_finalStates.Add(state); 53 m_finalStates.Add(state);
51 } 54 }
52 55
53 public void Add(AutomatonTransition item) { 56 public void Add(AutomatonTransition item) {
54 Safe.ArgumentAssert(item.s1 >= 0, "item"); 57 Safe.ArgumentAssert(item.s1 >= 0, "item");
55 Safe.ArgumentAssert(item.s2 >= 0, "item"); 58 Safe.ArgumentAssert(item.s2 >= 0, "item");
56 Safe.ArgumentAssert(item.edge >= 0, "item"); 59 Safe.ArgumentAssert(item.edge >= 0, "item");
57 60
58 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); 61 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
59 m_symbolCount = Math.Max(m_symbolCount, item.edge); 62 m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
60 63
61 m_transitions.Add(item); 64 m_transitions.Add(item);
62 } 65 }
63 66
64 public void Clear() { 67 public void Clear() {
102 105
103 public int[,] CreateTransitionTable() { 106 public int[,] CreateTransitionTable() {
104 var table = new int[StateCount,AlphabetSize]; 107 var table = new int[StateCount,AlphabetSize];
105 108
106 for (int i = 0; i < StateCount; i++) 109 for (int i = 0; i < StateCount; i++)
107 for (int j = 0; i < AlphabetSize; j++) 110 for (int j = 0; j < AlphabetSize; j++)
108 table[i, j] = AutomatonConst.UNREACHABLE_STATE; 111 table[i, j] = AutomatonConst.UNREACHABLE_STATE;
109 112
110 foreach (var t in this) 113 foreach (var t in this)
111 table[t.s1,t.edge] = t.s2; 114 table[t.s1,t.edge] = t.s2;
112 115
168 171
169 var rmap = m_transitions 172 var rmap = m_transitions
170 .GroupBy(t => t.s2) 173 .GroupBy(t => t.s2)
171 .ToDictionary( 174 .ToDictionary(
172 g => g.Key, // s2 175 g => g.Key, // s2
173 g => g.GroupBy(t => t.edge, t => t.s1).ToDictionary(p => p.Key) 176 g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
174 ); 177 );
175 178
176 while (queue.Count > 0) { 179 while (queue.Count > 0) {
177 var stateA = queue.First(); 180 var stateA = queue.First();
178 queue.Remove(stateA); 181 queue.Remove(stateA);
179 182
180 for (int c = 0; c < m_symbolCount; c++) { 183 for (int c = 0; c < m_symbolCount; c++) {
181 var stateX = new HashSet<int>(); 184 var stateX = new HashSet<int>();
182 foreach(var a in stateA) 185 foreach(var a in stateA.Where(rmap.ContainsKey))
183 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a' 186 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
184 187
185 foreach (var stateY in optimalStates.ToArray()) { 188 foreach (var stateY in optimalStates.ToArray()) {
186 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { 189 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
187 var stateR1 = new HashSet<int>(stateY); 190 var stateR1 = new HashSet<int>(stateY);
241 var classes = new Dictionary<int, HashSet<int>>(); 244 var classes = new Dictionary<int, HashSet<int>>();
242 245
243 foreach (var term in A) { 246 foreach (var term in A) {
244 // ищем все переходы класса по символу term 247 // ищем все переходы класса по символу term
245 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray(); 248 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
249
250 Debug.Assert(res.Length <= 1);
246 251
247 var s2 = res.Length > 0 ? res[0] : -1; 252 var s2 = res.Length > 0 ? res[0] : -1;
248 253
249 HashSet<int> a2; 254 HashSet<int> a2;
250 if (!classes.TryGetValue(s2, out a2)) { 255 if (!classes.TryGetValue(s2, out a2)) {
275 foreach (var item in minClasses) { 280 foreach (var item in minClasses) {
276 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT) 281 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
277 nextCls++; 282 nextCls++;
278 283
279 // сохраняем DFAConst.UNCLASSIFIED_INPUT 284 // сохраняем DFAConst.UNCLASSIFIED_INPUT
280 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls; 285 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
281 286
282 foreach (var a in item) 287 foreach (var a in item)
283 alphabetMap[a] = cls; 288 alphabetMap[a] = cls;
284
285 nextCls++;
286 } 289 }
287 290
288 // построение автомата 291 // построение автомата
289 optimalDFA.SetInitialState(stateMap[m_initialState]); 292 optimalDFA.SetInitialState(stateMap[m_initialState]);
290 293