##// END OF EJS Templates
minor fixes and debug
cin -
r181:b2b6a6640aa3 ref20160224
parent child
Show More
@@ -2,6 +2,7
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 {
@@ -43,10 +44,12 namespace Implab.Automaton {
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
@@ -56,7 +59,7 namespace Implab.Automaton {
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 }
@@ -104,7 +107,7 namespace Implab.Automaton {
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)
@@ -170,7 +173,7 namespace Implab.Automaton {
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) {
@@ -179,7 +182,7 namespace Implab.Automaton {
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()) {
@@ -244,6 +247,8 namespace Implab.Automaton {
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();
246
249
250 Debug.Assert(res.Length <= 1);
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;
@@ -277,12 +282,10 namespace Implab.Automaton {
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 // построение автомата
@@ -69,7 +69,7 namespace Implab.Automaton {
69
69
70
70
71 public IEnumerable<T> GetSymbols(int cls) {
71 public IEnumerable<T> GetSymbols(int cls) {
72 Safe.ArgumentAssert(cls > 0, "cls");
72 Safe.ArgumentAssert(!m_supportUnclassified || cls > 0, "cls");
73 return m_map.Where(p => p.Value == cls).Select(p => p.Key);
73 return m_map.Where(p => p.Value == cls).Select(p => p.Key);
74 }
74 }
75 #endregion
75 #endregion
@@ -63,7 +63,8 namespace Implab.Automaton.RegularExpres
63 dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
63 dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
64
64
65 // make the alphabet for the new DFA
65 // make the alphabet for the new DFA
66 foreach (var pair in alphaMap)
66 // skip all unclassified symbols
67 foreach (var pair in alphaMap.Where(x => x.Value != 0))
67 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
68 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
68
69
69 return dfa;
70 return dfa;
@@ -108,7 +108,7 namespace Implab.Formats.JSON {
108 }
108 }
109
109
110 Token SymbolRangeToken(char start, char stop) {
110 Token SymbolRangeToken(char start, char stop) {
111 return SymbolToken(Enumerable.Range(start,stop - start).Cast<char>());
111 return SymbolToken(Enumerable.Range(start,stop - start).Select(x => (char)x));
112 }
112 }
113
113
114 protected override IndexedAlphabetBase<char> CreateAlphabet() {
114 protected override IndexedAlphabetBase<char> CreateAlphabet() {
@@ -61,10 +61,16 namespace Implab.Formats {
61 while (pos < m_bufferSize) {
61 while (pos < m_bufferSize) {
62 var ch = m_buffer[pos];
62 var ch = m_buffer[pos];
63
63
64 state = dfa[state, ch > maxSymbol ? AutomatonConst.UNCLASSIFIED_INPUT : alphabet[ch]];
64 try {
65 if (state == AutomatonConst.UNREACHABLE_STATE)
65 var next = dfa[state, ch > maxSymbol ? AutomatonConst.UNCLASSIFIED_INPUT : alphabet[ch]];
66
67 if (next == AutomatonConst.UNREACHABLE_STATE)
66 break;
68 break;
67
69
70 state = next;
71 }catch {
72 throw;
73 }
68 pos++;
74 pos++;
69 }
75 }
70
76
General Comments 0
You need to be logged in to leave comments. Login now