Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATable.cs @ 182:76e8f2ba12b8 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
pretty print DFA, the minimization is still buggy
author cin
date Thu, 24 Mar 2016 18:52:10 +0300
parents b2b6a6640aa3
children 4f82e0f161c3
comparison
equal deleted inserted replaced
181:b2b6a6640aa3 182:76e8f2ba12b8
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 using System.Diagnostics;
6 using System.IO;
7 using System.CodeDom.Compiler;
8 using System.CodeDom;
6 9
7 namespace Implab.Automaton { 10 namespace Implab.Automaton {
8 public class DFATable : IDFATableBuilder { 11 public class DFATable : IDFATableBuilder {
9 int m_stateCount; 12 int m_stateCount;
10 int m_symbolCount; 13 int m_symbolCount;
99 return m_transitions.GetEnumerator(); 102 return m_transitions.GetEnumerator();
100 } 103 }
101 104
102 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { 105 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
103 return GetEnumerator(); 106 return GetEnumerator();
107 }
108
109 public void AddSymbol(int symbol) {
110 Safe.ArgumentAssert(symbol >= 0, "symbol");
111 m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
104 } 112 }
105 113
106 public int[,] CreateTransitionTable() { 114 public int[,] CreateTransitionTable() {
107 var table = new int[StateCount,AlphabetSize]; 115 var table = new int[StateCount,AlphabetSize];
108 116
160 GroupFinalStates() 168 GroupFinalStates()
161 ); 169 );
162 170
163 var state = new HashSet<int>( 171 var state = new HashSet<int>(
164 Enumerable 172 Enumerable
165 .Range(0, m_stateCount - 1) 173 .Range(0, m_stateCount)
166 .Where(i => !m_finalStates.Contains(i)) 174 .Where(i => !m_finalStates.Contains(i))
167 ); 175 );
168 176
169 optimalStates.Add(state); 177 optimalStates.Add(state);
170 queue.Add(state); 178 queue.Add(state);
180 var stateA = queue.First(); 188 var stateA = queue.First();
181 queue.Remove(stateA); 189 queue.Remove(stateA);
182 190
183 for (int c = 0; c < m_symbolCount; c++) { 191 for (int c = 0; c < m_symbolCount; c++) {
184 var stateX = new HashSet<int>(); 192 var stateX = new HashSet<int>();
185 foreach(var a in stateA.Where(rmap.ContainsKey)) 193 //foreach(var a in stateA.Where(rmap.ContainsKey))
186 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a' 194 // stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
187 195
188 foreach (var stateY in optimalStates.ToArray()) { 196 stateX.UnionWith(m_transitions.Where(t => stateA.Contains(t.s2) && t.edge == c).Select(t => t.s1));
197
198 var tmp = optimalStates.ToArray();
199 foreach (var stateY in tmp) {
189 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { 200 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
190 var stateR1 = new HashSet<int>(stateY); 201 var stateR1 = new HashSet<int>(stateY);
191 var stateR2 = new HashSet<int>(stateY); 202 var stateR2 = new HashSet<int>(stateY);
192 203
193 stateR1.IntersectWith(stateX); 204 stateR1.IntersectWith(stateX);
243 // optimalState -> alphaClass 254 // optimalState -> alphaClass
244 var classes = new Dictionary<int, HashSet<int>>(); 255 var classes = new Dictionary<int, HashSet<int>>();
245 256
246 foreach (var term in A) { 257 foreach (var term in A) {
247 // ищем все переходы класса по символу term 258 // ищем все переходы класса по символу term
248 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray(); 259 var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
249 260
250 Debug.Assert(res.Length <= 1);
251
252 var s2 = res.Length > 0 ? res[0] : -1;
253
254 HashSet<int> a2; 261 HashSet<int> a2;
255 if (!classes.TryGetValue(s2, out a2)) { 262 if (!classes.TryGetValue(s2, out a2)) {
256 a2 = new HashSet<int>(); 263 a2 = new HashSet<int>();
257 newQueue.Enqueue(a2); 264 newQueue.Enqueue(a2);
258 classes[s2] = a2; 265 classes[s2] = a2;
281 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT) 288 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
282 nextCls++; 289 nextCls++;
283 290
284 // сохраняем DFAConst.UNCLASSIFIED_INPUT 291 // сохраняем DFAConst.UNCLASSIFIED_INPUT
285 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++; 292 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
293 optimalDFA.AddSymbol(cls);
286 294
287 foreach (var a in item) 295 foreach (var a in item)
288 alphabetMap[a] = cls; 296 alphabetMap[a] = cls;
289 } 297 }
290 298
296 304
297 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct()) 305 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
298 optimalDFA.Add(t); 306 optimalDFA.Add(t);
299 } 307 }
300 308
301 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { 309 protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
302 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); 310 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
303 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); 311 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
304 312
305 foreach(var t in m_transitions) 313 var data = new List<string>();
306 Console.WriteLine( 314
307 "[{0}] -{{{1}}}-> [{2}]{3}", 315 data.Add("digraph dfa {");
308 String.Join(",", stateAlphabet.GetSymbols(t.s1)), 316
309 String.Join("", inputAlphabet.GetSymbols(t.edge)), 317 foreach (var final in m_finalStates)
310 String.Join(",", stateAlphabet.GetSymbols(t.s2)), 318 data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
311 m_finalStates.Contains(t.s2) ? "$" : "" 319
312 ); 320 foreach (var t in m_transitions)
313 } 321 data.Add(String.Format(
314 322 "{0} -> {2} [label={1}];",
323 String.Join("", stateAlphabet.GetSymbols(t.s1)),
324 ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
325 String.Join("", stateAlphabet.GetSymbols(t.s2))
326 ));
327 data.Add("}");
328 return String.Join("\n", data);
329 }
330
331 static string ToLiteral(string input)
332 {
333 using (var writer = new StringWriter())
334 {
335 using (var provider = CodeDomProvider.CreateProvider("CSharp"))
336 {
337 provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
338 return writer.ToString();
339 }
340 }
341 }
315 } 342 }
316 } 343 }