@@ -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; |
|
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. |
|
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). |
|
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