@@ -2,6 +2,7 | |||
|
2 | 2 | using System; |
|
3 | 3 | using System.Collections.Generic; |
|
4 | 4 | using System.Linq; |
|
5 | using System.Diagnostics; | |
|
5 | 6 | |
|
6 | 7 | namespace Implab.Automaton { |
|
7 | 8 | public class DFATable : IDFATableBuilder { |
@@ -43,10 +44,12 namespace Implab.Automaton { | |||
|
43 | 44 | |
|
44 | 45 | public void SetInitialState(int s) { |
|
45 | 46 | Safe.ArgumentAssert(s >= 0, "s"); |
|
47 | m_stateCount = Math.Max(m_stateCount, s + 1); | |
|
46 | 48 | m_initialState = s; |
|
47 | 49 | } |
|
48 | 50 | |
|
49 | 51 | public void MarkFinalState(int state) { |
|
52 | m_stateCount = Math.Max(m_stateCount, state + 1); | |
|
50 | 53 | m_finalStates.Add(state); |
|
51 | 54 | } |
|
52 | 55 | |
@@ -56,7 +59,7 namespace Implab.Automaton { | |||
|
56 | 59 | Safe.ArgumentAssert(item.edge >= 0, "item"); |
|
57 | 60 | |
|
58 | 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 | 64 | m_transitions.Add(item); |
|
62 | 65 | } |
@@ -104,7 +107,7 namespace Implab.Automaton { | |||
|
104 | 107 | var table = new int[StateCount,AlphabetSize]; |
|
105 | 108 | |
|
106 | 109 | for (int i = 0; i < StateCount; i++) |
|
107 |
for (int j = 0; |
|
|
110 | for (int j = 0; j < AlphabetSize; j++) | |
|
108 | 111 | table[i, j] = AutomatonConst.UNREACHABLE_STATE; |
|
109 | 112 | |
|
110 | 113 | foreach (var t in this) |
@@ -170,7 +173,7 namespace Implab.Automaton { | |||
|
170 | 173 | .GroupBy(t => t.s2) |
|
171 | 174 | .ToDictionary( |
|
172 | 175 | g => g.Key, // s2 |
|
173 |
g => g. |
|
|
176 | g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key) | |
|
174 | 177 | ); |
|
175 | 178 | |
|
176 | 179 | while (queue.Count > 0) { |
@@ -179,7 +182,7 namespace Implab.Automaton { | |||
|
179 | 182 | |
|
180 | 183 | for (int c = 0; c < m_symbolCount; c++) { |
|
181 | 184 | var stateX = new HashSet<int>(); |
|
182 | foreach(var a in stateA) | |
|
185 | foreach(var a in stateA.Where(rmap.ContainsKey)) | |
|
183 | 186 | stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a' |
|
184 | 187 | |
|
185 | 188 | foreach (var stateY in optimalStates.ToArray()) { |
@@ -244,6 +247,8 namespace Implab.Automaton { | |||
|
244 | 247 | // ищем все переходы класса по символу term |
|
245 | 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 | 252 | var s2 = res.Length > 0 ? res[0] : -1; |
|
248 | 253 | |
|
249 | 254 | HashSet<int> a2; |
@@ -277,12 +282,10 namespace Implab.Automaton { | |||
|
277 | 282 | nextCls++; |
|
278 | 283 | |
|
279 | 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 | 287 | foreach (var a in item) |
|
283 | 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 | 71 | public IEnumerable<T> GetSymbols(int cls) { |
|
72 | Safe.ArgumentAssert(cls > 0, "cls"); | |
|
72 | Safe.ArgumentAssert(!m_supportUnclassified || cls > 0, "cls"); | |
|
73 | 73 | return m_map.Where(p => p.Value == cls).Select(p => p.Key); |
|
74 | 74 | } |
|
75 | 75 | #endregion |
@@ -63,7 +63,8 namespace Implab.Automaton.RegularExpres | |||
|
63 | 63 | dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray()); |
|
64 | 64 | |
|
65 | 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 | 68 | alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value); |
|
68 | 69 | |
|
69 | 70 | return dfa; |
@@ -108,7 +108,7 namespace Implab.Formats.JSON { | |||
|
108 | 108 | } |
|
109 | 109 | |
|
110 | 110 | Token SymbolRangeToken(char start, char stop) { |
|
111 |
return SymbolToken(Enumerable.Range(start,stop - start). |
|
|
111 | return SymbolToken(Enumerable.Range(start,stop - start).Select(x => (char)x)); | |
|
112 | 112 | } |
|
113 | 113 | |
|
114 | 114 | protected override IndexedAlphabetBase<char> CreateAlphabet() { |
@@ -61,10 +61,16 namespace Implab.Formats { | |||
|
61 | 61 | while (pos < m_bufferSize) { |
|
62 | 62 | var ch = m_buffer[pos]; |
|
63 | 63 | |
|
64 | state = dfa[state, ch > maxSymbol ? AutomatonConst.UNCLASSIFIED_INPUT : alphabet[ch]]; | |
|
65 | if (state == AutomatonConst.UNREACHABLE_STATE) | |
|
64 | try { | |
|
65 | var next = dfa[state, ch > maxSymbol ? AutomatonConst.UNCLASSIFIED_INPUT : alphabet[ch]]; | |
|
66 | ||
|
67 | if (next == AutomatonConst.UNREACHABLE_STATE) | |
|
66 | 68 | break; |
|
67 | 69 | |
|
70 | state = next; | |
|
71 | }catch { | |
|
72 | throw; | |
|
73 | } | |
|
68 | 74 | pos++; |
|
69 | 75 | } |
|
70 | 76 |
General Comments 0
You need to be logged in to leave comments.
Login now