Mercurial > pub > ImplabNet
annotate Implab/Automaton/DFATable.cs @ 260:547a2fc0d93e v3 v3.0.6
minor fixes
| author | cin |
|---|---|
| date | Fri, 13 Apr 2018 19:14:59 +0300 |
| parents | 7c7e9ad6fe4a |
| children |
| rev | line source |
|---|---|
| 176 | 1 using Implab; |
| 2 using System; | |
| 3 using System.Collections.Generic; | |
| 4 using System.Linq; | |
| 181 | 5 using System.Diagnostics; |
| 182 | 6 using System.IO; |
| 7 using System.CodeDom.Compiler; | |
| 8 using System.CodeDom; | |
| 176 | 9 |
| 10 namespace Implab.Automaton { | |
| 11 public class DFATable : IDFATableBuilder { | |
| 12 int m_stateCount; | |
| 13 int m_symbolCount; | |
| 14 int m_initialState; | |
| 15 | |
| 16 readonly HashSet<int> m_finalStates = new HashSet<int>(); | |
| 17 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); | |
| 18 | |
| 19 | |
| 20 #region IDFADefinition implementation | |
| 21 | |
| 22 public bool IsFinalState(int s) { | |
| 251 | 23 Safe.ArgumentInRange(s >= 0 && s < m_stateCount, nameof(s)); |
| 176 | 24 |
| 25 return m_finalStates.Contains(s); | |
| 26 } | |
| 27 | |
| 28 public IEnumerable<int> FinalStates { | |
| 29 get { | |
| 30 return m_finalStates; | |
| 31 } | |
| 32 } | |
| 33 | |
| 34 public int StateCount { | |
| 35 get { return m_stateCount; } | |
| 36 } | |
| 37 | |
| 38 public int AlphabetSize { | |
| 39 get { return m_symbolCount; } | |
| 40 } | |
| 41 | |
| 42 public int InitialState { | |
| 43 get { return m_initialState; } | |
| 44 } | |
| 45 | |
| 46 #endregion | |
| 47 | |
| 48 public void SetInitialState(int s) { | |
| 251 | 49 Safe.ArgumentInRange(s >= 0, nameof(s)); |
| 181 | 50 m_stateCount = Math.Max(m_stateCount, s + 1); |
| 176 | 51 m_initialState = s; |
| 52 } | |
| 53 | |
| 54 public void MarkFinalState(int state) { | |
| 181 | 55 m_stateCount = Math.Max(m_stateCount, state + 1); |
| 176 | 56 m_finalStates.Add(state); |
| 57 } | |
| 58 | |
| 59 public void Add(AutomatonTransition item) { | |
| 251 | 60 Safe.ArgumentAssert(item.s1 >= 0, nameof(item)); |
| 61 Safe.ArgumentAssert(item.s2 >= 0, nameof(item)); | |
| 62 Safe.ArgumentAssert(item.edge >= 0, nameof(item)); | |
| 176 | 63 |
| 64 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); | |
| 181 | 65 m_symbolCount = Math.Max(m_symbolCount, item.edge + 1); |
| 176 | 66 |
| 67 m_transitions.Add(item); | |
| 68 } | |
| 69 | |
| 70 public void Clear() { | |
| 71 m_stateCount = 0; | |
| 72 m_symbolCount = 0; | |
| 73 m_finalStates.Clear(); | |
| 74 m_transitions.Clear(); | |
| 75 } | |
| 76 | |
| 77 public bool Contains(AutomatonTransition item) { | |
| 78 return m_transitions.Contains(item); | |
| 79 } | |
| 80 | |
| 81 public void CopyTo(AutomatonTransition[] array, int arrayIndex) { | |
| 82 m_transitions.CopyTo(array, arrayIndex); | |
| 83 } | |
| 84 | |
| 85 public bool Remove(AutomatonTransition item) { | |
| 180 | 86 return m_transitions.Remove(item); |
| 176 | 87 } |
| 88 | |
| 89 public int Count { | |
| 90 get { | |
| 91 return m_transitions.Count; | |
| 92 } | |
| 93 } | |
| 94 | |
| 95 public bool IsReadOnly { | |
| 96 get { | |
| 97 return false; | |
| 98 } | |
| 99 } | |
| 100 | |
| 101 public IEnumerator<AutomatonTransition> GetEnumerator() { | |
| 102 return m_transitions.GetEnumerator(); | |
| 103 } | |
| 104 | |
| 105 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { | |
| 106 return GetEnumerator(); | |
| 107 } | |
| 108 | |
| 182 | 109 public void AddSymbol(int symbol) { |
| 110 Safe.ArgumentAssert(symbol >= 0, "symbol"); | |
| 111 m_symbolCount = Math.Max(symbol + 1, m_symbolCount); | |
| 112 } | |
| 113 | |
| 176 | 114 public int[,] CreateTransitionTable() { |
| 115 var table = new int[StateCount,AlphabetSize]; | |
| 116 | |
| 117 for (int i = 0; i < StateCount; i++) | |
| 181 | 118 for (int j = 0; j < AlphabetSize; j++) |
| 236 | 119 table[i, j] = AutomatonConst.UnreachableState; |
| 176 | 120 |
| 121 foreach (var t in this) | |
| 229 | 122 table[t.s1,t.edge] = (byte)t.s2; |
| 176 | 123 |
| 124 return table; | |
| 125 } | |
| 126 | |
| 127 public bool[] CreateFinalStateTable() { | |
| 128 var table = new bool[StateCount]; | |
| 129 | |
| 130 foreach (var s in FinalStates) | |
| 131 table[s] = true; | |
| 132 | |
| 133 return table; | |
| 134 } | |
| 135 | |
| 136 /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary> | |
| 137 /// <remarks> | |
| 138 /// В процессе построения минимального автомата требуется разделить множество состояний, | |
| 139 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества | |
| 140 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, | |
| 141 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. | |
| 142 /// </remarks> | |
| 143 /// <returns>The final states.</returns> | |
| 183 | 144 protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) { |
| 145 return new [] { new HashSet<int>(states) }; | |
| 176 | 146 } |
| 147 | |
| 148 protected void Optimize( | |
| 149 IDFATableBuilder optimalDFA, | |
| 150 IDictionary<int,int> alphabetMap, | |
| 151 IDictionary<int,int> stateMap | |
| 152 ) { | |
| 153 Safe.ArgumentNotNull(optimalDFA, "dfa"); | |
| 154 Safe.ArgumentNotNull(alphabetMap, "alphabetMap"); | |
| 155 Safe.ArgumentNotNull(stateMap, "stateMap"); | |
| 156 | |
| 157 | |
| 158 var setComparer = new CustomEqualityComparer<HashSet<int>>( | |
| 159 (x, y) => x.SetEquals(y), | |
| 160 s => s.Sum(x => x.GetHashCode()) | |
| 161 ); | |
| 162 | |
| 163 var optimalStates = new HashSet<HashSet<int>>(setComparer); | |
| 164 var queue = new HashSet<HashSet<int>>(setComparer); | |
| 165 | |
| 183 | 166 optimalStates.Add(new HashSet<int>(FinalStates)); |
| 176 | 167 |
| 168 var state = new HashSet<int>( | |
| 169 Enumerable | |
| 182 | 170 .Range(0, m_stateCount) |
| 176 | 171 .Where(i => !m_finalStates.Contains(i)) |
| 172 ); | |
| 173 | |
| 174 optimalStates.Add(state); | |
| 175 queue.Add(state); | |
| 176 | |
| 177 var rmap = m_transitions | |
| 178 .GroupBy(t => t.s2) | |
| 180 | 179 .ToDictionary( |
| 176 | 180 g => g.Key, // s2 |
| 181 | 181 g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key) |
| 176 | 182 ); |
| 183 | |
| 184 while (queue.Count > 0) { | |
| 185 var stateA = queue.First(); | |
| 186 queue.Remove(stateA); | |
| 187 | |
| 188 for (int c = 0; c < m_symbolCount; c++) { | |
| 189 var stateX = new HashSet<int>(); | |
| 183 | 190 foreach(var a in stateA.Where(rmap.ContainsKey)) |
| 191 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a' | |
| 182 | 192 |
| 193 var tmp = optimalStates.ToArray(); | |
| 194 foreach (var stateY in tmp) { | |
| 183 | 195 var stateR1 = new HashSet<int>(stateY); |
| 196 var stateR2 = new HashSet<int>(stateY); | |
| 176 | 197 |
| 183 | 198 stateR1.IntersectWith(stateX); |
| 199 stateR2.ExceptWith(stateX); | |
| 200 | |
| 201 if (stateR1.Count > 0 && stateR2.Count > 0) { | |
| 202 | |
| 176 | 203 |
| 204 optimalStates.Remove(stateY); | |
| 205 optimalStates.Add(stateR1); | |
| 206 optimalStates.Add(stateR2); | |
| 207 | |
| 208 if (queue.Contains(stateY)) { | |
| 209 queue.Remove(stateY); | |
| 210 queue.Add(stateR1); | |
| 211 queue.Add(stateR2); | |
| 212 } else { | |
| 213 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2); | |
| 214 } | |
| 215 } | |
| 216 } | |
| 217 } | |
| 218 } | |
| 219 | |
| 183 | 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 | |
| 176 | 228 // карта получения оптимального состояния по соотвествующему ему простому состоянию |
| 229 var nextState = 0; | |
| 230 foreach (var item in optimalStates) { | |
| 231 var id = nextState++; | |
| 232 foreach (var s in item) | |
| 233 stateMap[s] = id; | |
| 234 } | |
| 235 | |
| 236 // получаем минимальный алфавит | |
| 237 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s | |
| 238 // для этого используем алгоритм кластеризации, сначала | |
| 239 // считаем, что все символы не различимы | |
| 240 | |
| 241 var minClasses = new HashSet<HashSet<int>>(setComparer); | |
| 242 var alphaQueue = new Queue<HashSet<int>>(); | |
| 243 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize))); | |
| 244 | |
| 245 // для всех состояний, будем проверять каждый класс на различимость, | |
| 246 // т.е. символы различимы, если они приводят к разным состояниям | |
| 247 for (int s = 0 ; s < optimalStates.Count; s++) { | |
| 248 var newQueue = new Queue<HashSet<int>>(); | |
| 249 | |
| 250 foreach (var A in alphaQueue) { | |
| 251 // классы из одного символа делить бесполезно, переводим их сразу в | |
| 252 // результирующий алфавит | |
| 253 if (A.Count == 1) { | |
| 254 minClasses.Add(A); | |
| 255 continue; | |
| 256 } | |
| 257 | |
| 258 // различаем классы символов, которые переводят в различные оптимальные состояния | |
| 259 // optimalState -> alphaClass | |
| 260 var classes = new Dictionary<int, HashSet<int>>(); | |
| 261 | |
| 262 foreach (var term in A) { | |
| 263 // ищем все переходы класса по символу term | |
| 182 | 264 var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First(); |
| 176 | 265 |
| 266 HashSet<int> a2; | |
| 267 if (!classes.TryGetValue(s2, out a2)) { | |
| 268 a2 = new HashSet<int>(); | |
| 269 newQueue.Enqueue(a2); | |
| 270 classes[s2] = a2; | |
| 271 } | |
| 272 a2.Add(term); | |
| 273 } | |
| 274 } | |
| 275 | |
| 276 if (newQueue.Count == 0) | |
| 277 break; | |
| 278 alphaQueue = newQueue; | |
| 279 } | |
| 280 | |
| 281 // после окончания работы алгоритма в очереди останутся минимальные различимые классы | |
| 282 // входных символов | |
| 283 foreach (var A in alphaQueue) | |
| 284 minClasses.Add(A); | |
| 285 | |
| 286 // построение отображения алфавитов входных символов. | |
| 287 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь | |
| 288 // специальное значение, тогда сохраним минимальный класс, | |
| 289 // содержащий этот символ на томже месте. | |
| 290 | |
| 291 var nextCls = 0; | |
| 292 foreach (var item in minClasses) { | |
| 236 | 293 if (nextCls == AutomatonConst.UnclassifiedInput) |
| 176 | 294 nextCls++; |
| 295 | |
| 296 // сохраняем DFAConst.UNCLASSIFIED_INPUT | |
| 236 | 297 var cls = item.Contains(AutomatonConst.UnclassifiedInput) ? AutomatonConst.UnclassifiedInput : nextCls++; |
| 182 | 298 optimalDFA.AddSymbol(cls); |
| 176 | 299 |
| 300 foreach (var a in item) | |
| 301 alphabetMap[a] = cls; | |
| 302 } | |
| 303 | |
| 304 // построение автомата | |
| 305 optimalDFA.SetInitialState(stateMap[m_initialState]); | |
| 306 | |
| 307 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct()) | |
| 308 optimalDFA.MarkFinalState(sf); | |
| 309 | |
| 310 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct()) | |
| 311 optimalDFA.Add(t); | |
| 312 } | |
| 313 | |
|
240
fa6cbf4d8841
refactoring, moving to dotnercore, simplifying promises
cin
parents:
236
diff
changeset
|
314 /*protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { |
| 176 | 315 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); |
| 316 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); | |
| 317 | |
| 182 | 318 var data = new List<string>(); |
| 319 | |
| 320 data.Add("digraph dfa {"); | |
| 321 | |
| 322 foreach (var final in m_finalStates) | |
| 323 data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final)))); | |
| 324 | |
| 325 foreach (var t in m_transitions) | |
| 326 data.Add(String.Format( | |
| 327 "{0} -> {2} [label={1}];", | |
| 328 String.Join("", stateAlphabet.GetSymbols(t.s1)), | |
| 236 | 329 ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UnclassifiedInput ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))), |
| 182 | 330 String.Join("", stateAlphabet.GetSymbols(t.s2)) |
| 331 )); | |
| 332 data.Add("}"); | |
| 333 return String.Join("\n", data); | |
| 176 | 334 } |
| 335 | |
| 182 | 336 static string ToLiteral(string input) |
| 337 { | |
| 338 using (var writer = new StringWriter()) | |
| 339 { | |
| 340 using (var provider = CodeDomProvider.CreateProvider("CSharp")) | |
| 341 { | |
| 342 provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null); | |
| 343 return writer.ToString(); | |
| 344 } | |
| 345 } | |
|
240
fa6cbf4d8841
refactoring, moving to dotnercore, simplifying promises
cin
parents:
236
diff
changeset
|
346 }*/ |
| 176 | 347 } |
| 348 } |