##// END OF EJS Templates
implab » ImplabNet
RSS
Working on regular DFA
cin -
r171:0f70905b4652 ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -0,0 +1,23
1 using System;
2
3 namespace Implab.Automaton.RegularExpressions {
4 public struct DFAStateDescriptorT<T> {
5 public readonly bool final;
6
7 public readonly int[] transitions;
8
9 public readonly T[] tags;
10
11 public DFAStateDescriptorT(int size, bool final, T[] tags) {
12 Safe.ArgumentAssert(size >= 0, "size");
13 this.final = final;
14 this.tags = tags;
15
16 transitions = new int[size];
17
18 for (int i = 0; i < size; i++)
19 transitions[i] = DFAConst.UNREACHABLE_STATE;
20 }
21 }
22 }
23
Show file before | Show file after | Hide comments
@@ -5,8 +5,6 using System.Linq;
5
5
6 namespace Implab.Automaton {
6 namespace Implab.Automaton {
7 public class DFATable : IDFATableBuilder {
7 public class DFATable : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
9
10 int m_stateCount;
8 int m_stateCount;
11 int m_symbolCount;
9 int m_symbolCount;
12 int m_initialState;
10 int m_initialState;
@@ -14,30 +12,13 namespace Implab.Automaton {
14 readonly HashSet<int> m_finalStates = new HashSet<int>();
12 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16
14
17 void AssertNotReadOnly() {
18 if (m_dfaTable != null)
19 throw new InvalidOperationException("The object is readonly");
20 }
21
22
15
23 #region IDFADefinition implementation
16 #region IDFADefinition implementation
24
17
25 public DFAStateDescriptior[] GetTransitionTable() {
26 if (m_dfaTable == null) {
27 if (m_stateCount <= 0)
28 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
29 if (m_symbolCount <= 0)
30 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
31
32 m_dfaTable = ConstructTransitionTable();
33 }
34 return m_dfaTable;
35 }
36
37 public bool IsFinalState(int s) {
18 public bool IsFinalState(int s) {
38 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
19 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
39
20
40 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
21 return m_finalStates.Contains(s);
41 }
22 }
42
23
43 public IEnumerable<int> FinalStates {
24 public IEnumerable<int> FinalStates {
@@ -60,35 +41,16 namespace Implab.Automaton {
60
41
61 #endregion
42 #endregion
62
43
63 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
64 var dfaTable = new DFAStateDescriptior[m_stateCount];
65
66
67 foreach (var t in m_transitions) {
68 if (dfaTable[t.s1].transitions == null)
69 dfaTable[t.s1] = new DFAStateDescriptior(m_symbolCount, m_finalStates.Contains(t.s1));
70
71 dfaTable[t.s1].transitions[t.edge] = t.s2;
72 }
73
74 foreach (var s in m_finalStates)
75 if (!dfaTable[s].final)
76 m_dfaTable[s] = new DFAStateDescriptior(m_symbolCount, true);
77
78 }
79
80 public void SetInitialState(int s) {
44 public void SetInitialState(int s) {
81 Safe.ArgumentAssert(s >= 0, "s");
45 Safe.ArgumentAssert(s >= 0, "s");
82 m_initialState = s;
46 m_initialState = s;
83 }
47 }
84
48
85 public void MarkFinalState(int state) {
49 public void MarkFinalState(int state) {
86 AssertNotReadOnly();
87 m_finalStates.Add(state);
50 m_finalStates.Add(state);
88 }
51 }
89
52
90 public void Add(AutomatonTransition item) {
53 public void Add(AutomatonTransition item) {
91 AssertNotReadOnly();
92 Safe.ArgumentAssert(item.s1 >= 0, "item");
54 Safe.ArgumentAssert(item.s1 >= 0, "item");
93 Safe.ArgumentAssert(item.s2 >= 0, "item");
55 Safe.ArgumentAssert(item.s2 >= 0, "item");
94 Safe.ArgumentAssert(item.edge >= 0, "item");
56 Safe.ArgumentAssert(item.edge >= 0, "item");
@@ -100,8 +62,6 namespace Implab.Automaton {
100 }
62 }
101
63
102 public void Clear() {
64 public void Clear() {
103 AssertNotReadOnly();
104
105 m_stateCount = 0;
65 m_stateCount = 0;
106 m_symbolCount = 0;
66 m_symbolCount = 0;
107 m_finalStates.Clear();
67 m_finalStates.Clear();
@@ -117,7 +77,6 namespace Implab.Automaton {
117 }
77 }
118
78
119 public bool Remove(AutomatonTransition item) {
79 public bool Remove(AutomatonTransition item) {
120 AssertNotReadOnly();
121 m_transitions.Remove(item);
80 m_transitions.Remove(item);
122 }
81 }
123
82
@@ -129,7 +88,7 namespace Implab.Automaton {
129
88
130 public bool IsReadOnly {
89 public bool IsReadOnly {
131 get {
90 get {
132 return m_dfaTable != null;
91 return false;
133 }
92 }
134 }
93 }
135
94
@@ -153,23 +112,15 namespace Implab.Automaton {
153 return new HashSet<int>[] { m_finalStates };
112 return new HashSet<int>[] { m_finalStates };
154 }
113 }
155
114
156 protected void Optimize<TInput, TState>(
115 protected void Optimize(
157 IDFATableBuilder optimalDFA,
116 IDFATableBuilder optimalDFA,
158 IAlphabet<TInput> inputAlphabet,
117 IDictionary<int,int> alphabetMap,
159 IAlphabetBuilder<TInput> optimalInputAlphabet,
118 IDictionary<int,int> stateMap
160 IAlphabet<TState> stateAlphabet,
161 IAlphabetBuilder<TState> optimalStateAlphabet
162 ) {
119 ) {
163 Safe.ArgumentNotNull(optimalDFA, "dfa");
120 Safe.ArgumentNotNull(optimalDFA, "dfa");
164 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
121 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
165 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
122 Safe.ArgumentNotNull(stateMap, "stateMap");
166 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
167 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
168
123
169 if (inputAlphabet.Count != m_symbolCount)
170 throw new InvalidOperationException("The input symbols aphabet mismatch");
171 if (stateAlphabet.Count != m_stateCount)
172 throw new InvalidOperationException("The states alphabet mismatch");
173
124
174 var setComparer = new CustomEqualityComparer<HashSet<int>>(
125 var setComparer = new CustomEqualityComparer<HashSet<int>>(
175 (x, y) => x.SetEquals(y),
126 (x, y) => x.SetEquals(y),
@@ -234,46 +185,106 namespace Implab.Automaton {
234 }
185 }
235
186
236 // карта получения оптимального состояния по соотвествующему ему простому состоянию
187 // карта получения оптимального состояния по соотвествующему ему простому состоянию
237 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
188 var nextState = 0;
189 foreach (var item in optimalStates) {
190 var id = nextState++;
191 foreach (var s in item)
192 stateMap[s] = id;
193 }
238
194
239 // получаем минимальный алфавит
195 // получаем минимальный алфавит
240 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
196 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
241 var optimalAlphabet = m_transitions
197 // для этого используем алгоритм кластеризации, сначала
242 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
198 // считаем, что все символы не различимы
199
200 var minClasses = new HashSet<HashSet<int>>(setComparer);
201 var alphaQueue = new Queue<HashSet<int>>();
202 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
203
204 // для всех состояний, будем проверять каждый класс на различимость,
205 // т.е. символы различимы, если они приводят к разным состояниям
206 for (int s = 0 ; s < optimalStates.Count; s++) {
207 var newQueue = new Queue<HashSet<int>>();
208
209 foreach (var A in alphaQueue) {
210 // классы из одного символа делить бесполезно, переводим их сразу в
211 // результирующий алфавит
212 if (A.Count == 1) {
213 minClasses.Add(A);
214 continue;
215 }
216
217 // различаем классы символов, которые переводят в различные оптимальные состояния
218 // optimalState -> alphaClass
219 var classes = new Dictionary<int, HashSet<int>>();
220
221 foreach (var term in A) {
222 // ищем все переходы класса по символу term
223 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
224
225 var s2 = res.Length > 0 ? res[0] : -1;
243
226
244 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
227 HashSet<int> a2;
228 if (!classes.TryGetValue(s2, out a2)) {
229 a2 = new HashSet<int>();
230 newQueue.Enqueue(a2);
231 classes[s2] = a2;
232 }
233 a2.Add(term);
234 }
235 }
236
237 if (newQueue.Count == 0)
238 break;
239 alphaQueue = newQueue;
240 }
241
242 // после окончания работы алгоритма в очереди останутся минимальные различимые классы
243 // входных символов
244 foreach (var A in alphaQueue)
245 minClasses.Add(A);
246
247 // построение отображения алфавитов входных символов.
248 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
249 // специальное значение, тогда сохраним минимальный класс,
250 // содержащий этот символ на томже месте.
251
252 var nextCls = 0;
253 foreach (var item in minClasses) {
254 if (nextCls == DFAConst.UNCLASSIFIED_INPUT)
255 nextCls++;
256
257 // сохраняем DFAConst.UNCLASSIFIED_INPUT
258 var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
259
260 foreach (var a in item)
261 alphabetMap[a] = cls;
262
263 nextCls++;
264 }
245
265
246 // построение автомата
266 // построение автомата
247 optimalDFA.SetInitialState(statesMap[m_initialState]);
267 optimalDFA.SetInitialState(stateMap[m_initialState]);
248
268
249 foreach (var sf in m_finalStates.GroupBy(s => statesMap[s]))
269 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
250 optimalDFA.MarkFinalState(sf.Key);
270 optimalDFA.MarkFinalState(sf);
251
271
252 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
272 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
253 optimalDFA.Add(t);
273 optimalDFA.Add(t);
254
255 }
274 }
256
275
257 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
276 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
258 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
277 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
259 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
278 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
260
279
261 var inputMap = inputAlphabet.CreateReverseMap();
262 var stateMap = stateAlphabet.CreateReverseMap();
263
264 for (int i = 0; i < inputMap.Length; i++)
265 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
266
267
268 foreach(var t in m_transitions)
280 foreach(var t in m_transitions)
269 Console.WriteLine(
281 Console.WriteLine(
270 "[{0}] -{{{1}}}-> [{2}]{3}",
282 "[{0}] -{{{1}}}-> [{2}]{3}",
271 stateMap[t.s1],
283 String.Join(",", stateAlphabet.GetSymbols(t.s1)),
272 String.Join(",", inputMap[t.edge]),
284 String.Join("", inputAlphabet.GetSymbols(t.edge)),
273 stateMap[t.s2],
285 String.Join(",", stateAlphabet.GetSymbols(t.s2)),
274 m_finalStates.Contains(t.s2) ? "$" : ""
286 m_finalStates.Contains(t.s2) ? "$" : ""
275 );
287 );
276
277 }
288 }
278
289
279 }
290 }
Show file before | Show file after | Hide comments
@@ -24,24 +24,14 namespace Implab.Automaton {
24 Enumerable.Range(0, m_size).ToArray();
24 Enumerable.Range(0, m_size).ToArray();
25 }
25 }
26
26
27 public int[] Reclassify(IAlphabetBuilder<int> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
27 public int Translate(int symbol) {
28 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
28 Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
29 Safe.ArgumentNotNull(classes, "classes");
29 return symbol;
30 var map = new int[m_size];
31 foreach (var cls in classes) {
32 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
33 continue;
34 var newid = newAlphabet.DefineClass(cls);
35 foreach (var id in cls)
36 map[id] = newid;
37 }
30 }
38
31
39 return map;
32 public bool Contains(int symbol) {
40 }
33 Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
41
34 return true;
42 public int Translate(int symobl) {
43 Safe.ArgumentInRange(symobl, 0, m_size, "symbol");
44 return symobl;
45 }
35 }
46
36
47 public int Count {
37 public int Count {
Show file before | Show file after | Hide comments
@@ -21,28 +21,14 namespace Implab.Automaton {
21 int Count { get; }
21 int Count { get; }
22
22
23 /// <summary>
23 /// <summary>
24 /// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
25 /// ему исходным символам.
26 /// </summary>
27 /// <returns></returns>
28 List<TSymbol>[] CreateReverseMap();
29
30 /// <summary>
31 /// Создает новый алфавит на основе текущего, горппируя его сиволы в более
32 /// крупные непересекающиеся классы символов.
33 /// </summary>
34 /// <param name="newAlphabet">Новый, пустой алфавит, в котором быдут определены классы.</param>
35 /// <param name="classes">Множество классов символов текущего алфавита.</param>
36 /// <returns>Карта для перехода классов текущего
37 /// алфавита к классам нового.</returns>
38 /// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
39 int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<IEnumerable<int>> classes);
40
41 /// <summary>
42 /// Преобразует входной символ в индекс символа из алфавита.
24 /// Преобразует входной символ в индекс символа из алфавита.
43 /// </summary>
25 /// </summary>
44 /// <param name="symobl">Исходный символ</param>
26 /// <param name="symobl">Исходный символ</param>
45 /// <returns>Индекс в алфавите</returns>
27 /// <returns>Индекс в алфавите</returns>
46 int Translate(TSymbol symobl);
28 int Translate(TSymbol symobl);
29
30 bool Contains(TSymbol symbol);
31
32 IEnumerable<TSymbol> GetSymbols(int cls);
47 }
33 }
48 }
34 }
Show file before | Show file after | Hide comments
@@ -10,6 +10,8 namespace Implab.Automaton {
10 /// <param name="symbol">Символ для добавления.</param>
10 /// <param name="symbol">Символ для добавления.</param>
11 /// <returns>Индекс класса, который попоставлен с символом.</returns>
11 /// <returns>Индекс класса, который попоставлен с символом.</returns>
12 int DefineSymbol(TSymbol symbol);
12 int DefineSymbol(TSymbol symbol);
13
14 int DefineSymbol(TSymbol symbol, int cls);
13 /// <summary>
15 /// <summary>
14 /// Доабвляем класс символов. Множеству указанных исходных символов
16 /// Доабвляем класс символов. Множеству указанных исходных символов
15 /// будет сопоставлен символ в алфавите.
17 /// будет сопоставлен символ в алфавите.
@@ -17,6 +19,8 namespace Implab.Automaton {
17 /// <param name="symbols">Множестов исходных символов</param>
19 /// <param name="symbols">Множестов исходных символов</param>
18 /// <returns>Идентификатор символа алфавита.</returns>
20 /// <returns>Идентификатор символа алфавита.</returns>
19 int DefineClass(IEnumerable<TSymbol> symbols);
21 int DefineClass(IEnumerable<TSymbol> symbols);
22
23 int DefineClass(IEnumerable<TSymbol> symbols, int cls);
20 }
24 }
21 }
25 }
22
26
Show file before | Show file after | Hide comments
@@ -32,12 +32,6 namespace Implab.Automaton {
32 /// }
32 /// }
33 /// </example>
33 /// </example>
34 public interface IDFATable : IEnumerable<AutomatonTransition> {
34 public interface IDFATable : IEnumerable<AutomatonTransition> {
35 /// <summary>
36 /// Таблица переходов состояний автомата
37 /// </summary>
38 /// <returns>The transition table.</returns>
39 DFAStateDescriptior[] GetTransitionTable();
40
41 int StateCount {
35 int StateCount {
42 get;
36 get;
43 }
37 }
Show file before | Show file after | Hide comments
@@ -17,16 +17,13 namespace Implab.Automaton {
17 int m_nextId = 1;
17 int m_nextId = 1;
18 readonly int[] m_map;
18 readonly int[] m_map;
19
19
20 public int Count {
21 get { return m_nextId; }
22 }
23
24 protected IndexedAlphabetBase(int mapSize) {
20 protected IndexedAlphabetBase(int mapSize) {
25 m_map = new int[mapSize];
21 m_map = new int[mapSize];
26 }
22 }
27
23
28 protected IndexedAlphabetBase(int[] map) {
24 protected IndexedAlphabetBase(int[] map) {
29 Debug.Assert(map != null);
25 Debug.Assert(map != null && map.Length > 0);
26 Debug.Assert(map.All(x => x >= 0));
30
27
31 m_map = map;
28 m_map = map;
32 m_nextId = map.Max() + 1;
29 m_nextId = map.Max() + 1;
@@ -39,60 +36,41 namespace Implab.Automaton {
39 return m_map[index];
36 return m_map[index];
40 }
37 }
41
38
39 public int DefineSymbol(T symbol, int cls) {
40 var index = GetSymbolIndex(symbol);
41 m_map[index] = cls;
42 m_nextId = Math.Max(cls + 1, m_nextId);
43 return cls;
44 }
45
42 public int DefineClass(IEnumerable<T> symbols) {
46 public int DefineClass(IEnumerable<T> symbols) {
47 return DefineClass(symbols, m_nextId);
48 }
49
50 public int DefineClass(IEnumerable<T> symbols, int cls) {
43 Safe.ArgumentNotNull(symbols, "symbols");
51 Safe.ArgumentNotNull(symbols, "symbols");
44 symbols = symbols.Distinct();
52 symbols = symbols.Distinct();
45
53
46 foreach (var symbol in symbols) {
54 foreach (var symbol in symbols)
47 var index = GetSymbolIndex(symbol);
55 m_map[GetSymbolIndex(symbol)] = cls;
48 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
49 m_map[GetSymbolIndex(symbol)] = m_nextId;
50 else
51 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
52 }
53 return m_nextId++;
54 }
55
56 public List<T>[] CreateReverseMap() {
57 return
58 Enumerable.Range(0, Count)
59 .Select(
60 i => InputSymbols
61 .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
62 .ToList()
63 )
64 .ToArray();
65 }
66
56
67 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
57 m_nextId = Math.Max(cls + 1, m_nextId);
68 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
69 Safe.ArgumentNotNull(classes, "classes");
70 var reverseMap = CreateReverseMap();
71
72 var translationMap = new int[Count];
73
58
74 foreach (var scl in classes) {
59 return cls;
75 // skip if the supper class contains the unclassified element
76 if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
77 continue;
78 var range = new List<T>();
79 foreach (var cl in scl) {
80 if (cl < 0 || cl >= reverseMap.Length)
81 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
82 range.AddRange(reverseMap[cl]);
83 }
84 var newClass = newAlphabet.DefineClass(range);
85 foreach (var cl in scl)
86 translationMap[cl] = newClass;
87 }
88
89 return translationMap;
90 }
60 }
91
61
92 public virtual int Translate(T symbol) {
62 public virtual int Translate(T symbol) {
93 return m_map[GetSymbolIndex(symbol)];
63 return m_map[GetSymbolIndex(symbol)];
94 }
64 }
95
65
66 public int Count {
67 get { return m_nextId; }
68 }
69
70 public bool Contains(T symbol) {
71 return true;
72 }
73
96 public abstract int GetSymbolIndex(T symbol);
74 public abstract int GetSymbolIndex(T symbol);
97
75
98 public abstract IEnumerable<T> InputSymbols { get; }
76 public abstract IEnumerable<T> InputSymbols { get; }
Show file before | Show file after | Hide comments
@@ -5,96 +5,57 using System.Linq;
5 namespace Implab.Automaton {
5 namespace Implab.Automaton {
6 public class MapAlphabet<T> : IAlphabetBuilder<T> {
6 public class MapAlphabet<T> : IAlphabetBuilder<T> {
7 readonly Dictionary<T,int> m_map;
7 readonly Dictionary<T,int> m_map;
8 int m_nextCls = 1;
8 int m_nextCls;
9 readonly bool m_supportUnclassified;
9
10
10 public MapAlphabet() {
11 public MapAlphabet(bool supportUnclassified, IEqualityComparer<T> comparer) {
11 m_map = new Dictionary<T, int>();
12 m_map = comparer != null ? new Dictionary<T, int>(comparer) : new Dictionary<T,int>();
12 }
13 m_supportUnclassified = supportUnclassified;
13
14 m_nextCls = supportUnclassified ? 1 : 0;
14 public MapAlphabet(IEqualityComparer<T> comparer) {
15 m_map = new Dictionary<T, int>(comparer);
16 }
15 }
17
16
18 #region IAlphabetBuilder implementation
17 #region IAlphabetBuilder implementation
19
18
20 public int DefineSymbol(T symbol) {
19 public int DefineSymbol(T symbol) {
21 int cls;
20 int cls;
22 if (m_map.TryGetValue(symbol, out cls))
21 return m_map.TryGetValue(symbol, out cls) ? cls : DefineSymbol(symbol, m_nextCls);
23 return cls;
22 }
24
23
25 cls = m_nextCls++;
24 public int DefineSymbol(T symbol, int cls) {
25 Safe.ArgumentAssert(cls >= 0, "cls");
26
26
27 m_nextCls = Math.Max(cls + 1, m_nextCls);
27 m_map.Add(symbol, cls);
28 m_map.Add(symbol, cls);
28
29 return cls;
29 return cls;
30 }
30 }
31
31
32 public int DefineClass(IEnumerable<T> symbols) {
32 public int DefineClass(IEnumerable<T> symbols) {
33 return DefineClass(symbols, m_nextCls);
34 }
35
36 public int DefineClass(IEnumerable<T> symbols, int cls) {
37 Safe.ArgumentAssert(cls >= 0, "cls");
33 Safe.ArgumentNotNull(symbols, "symbols");
38 Safe.ArgumentNotNull(symbols, "symbols");
39
40 m_nextCls = Math.Max(cls + 1, m_nextCls);
34 symbols = symbols.Distinct();
41 symbols = symbols.Distinct();
35
42
36 foreach (var symbol in symbols) {
43 foreach (var symbol in symbols)
37 if (!m_map.Contains(symbol))
44 m_map[symbol] = cls;
38 m_map.Add(symbol, m_nextCls);
45 return cls;
39 else
40 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
41 }
42 return m_nextCls++;
43 }
46 }
44
47
45 #endregion
48 #endregion
46
49
47 #region IAlphabet implementation
50 #region IAlphabet implementation
48
51
49 public List<T>[] CreateReverseMap() {
52 public int Translate(T symbol) {
50 var empty = new List<T>();
51 var rmap = new List<T>[m_nextCls];
52
53 for (int i = 0; i < rmap.Length; i++)
54 rmap[i] = empty;
55
56 foreach (var pair in m_map) {
57 var symbols = rmap[pair.Value];
58 if (symbols == null) {
59 symbols = new List<T>();
60 rmap[pair.Value] = symbols;
61 }
62
63 symbols.Add(pair.Key);
64 }
65
66 return rmap;
67 }
68
69 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
70 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
71 Safe.ArgumentNotNull(classes, "classes");
72
73 var rmap = CreateReverseMap();
74 var map = new int[rmap.Length];
75
76 foreach (var cls in classes) {
77 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
78 continue;
79
80 var symbols = new List<T>();
81 foreach (var id in cls) {
82 if (id < 0 || id >= rmap.Length)
83 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", id));
84 if (rmap[id] != null)
85 symbols.AddRange(rmap[id]);
86 }
87
88 var newId = newAlphabet.DefineClass(symbols);
89
90 foreach (var id in cls)
91 map[id] = newId;
92 }
93 }
94
95 public int Translate(T symobl) {
96 int cls;
53 int cls;
97 return m_map.TryGetValue(symobl, out cls) ? cls : DFAConst.UNCLASSIFIED_INPUT;
54 if (m_map.TryGetValue(symbol, out cls))
55 return cls;
56 if (!m_supportUnclassified)
57 throw new ArgumentOutOfRangeException("symbol", "The specified symbol isn't in the alphabet");
58 return DFAConst.UNCLASSIFIED_INPUT;
98 }
59 }
99
60
100 public int Count {
61 public int Count {
@@ -103,6 +64,10 namespace Implab.Automaton {
103 }
64 }
104 }
65 }
105
66
67 public bool Contains(T symbol) {
68 return m_supportUnclassified || m_map.ContainsKey(symbol);
69 }
70
106 #endregion
71 #endregion
107 }
72 }
108 }
73 }
Show file before | Show file after | Hide comments
@@ -21,13 +21,6 namespace Implab.Automaton.RegularExpres
21 }
21 }
22 }
22 }
23
23
24 protected override DFAStateDescriptior[] ConstructTransitionTable() {
25 if (InputAlphabet.Count != m_alphabet.Count)
26 throw new InvalidOperationException("The alphabet doesn't match the transition table");
27
28 return base.ConstructTransitionTable();
29 }
30
31 public void MarkFinalState(int s, TTag[] tags) {
24 public void MarkFinalState(int s, TTag[] tags) {
32 MarkFinalState(s);
25 MarkFinalState(s);
33 SetStateTag(s, tags);
26 SetStateTag(s, tags);
@@ -53,16 +46,23 namespace Implab.Automaton.RegularExpres
53 var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
46 var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
54
47
55 var states = new DummyAlphabet(StateCount);
48 var states = new DummyAlphabet(StateCount);
56 var map = new MapAlphabet<int>();
49 var alphaMap = new Dictionary<int,int>();
50 var stateMap = new Dictionary<int,int>();
51 Optimize(dfaTable, alphaMap, stateMap);
57
52
58 Optimize(dfaTable, InputAlphabet, alphabet, states, map);
53 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
59
60 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => map.Translate(x.Key), x => x.Value ))
61 dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
54 dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
62
55
63 return dfaTable;
56 return dfaTable;
64 }
57 }
65
58
59 protected override IEnumerable<HashSet<int>> GroupFinalStates() {
60 var arrayComparer = new CustomEqualityComparer<TTag[]>(
61 (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
62 x => x.Sum(it => x.GetHashCode())
63 );
64 return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
65 }
66
66
67 }
67 }
68 }
68 }
Show file before | Show file after | Hide comments
@@ -190,6 +190,7
190 <Compile Include="Automaton\IDFATable.cs" />
190 <Compile Include="Automaton\IDFATable.cs" />
191 <Compile Include="Automaton\IDFATableBuilder.cs" />
191 <Compile Include="Automaton\IDFATableBuilder.cs" />
192 <Compile Include="Automaton\DFATable.cs" />
192 <Compile Include="Automaton\DFATable.cs" />
193 <Compile Include="Automaton\RegularExpressions\DFAStateDescriptorT.cs" />
193 </ItemGroup>
194 </ItemGroup>
194 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
195 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
195 <ItemGroup />
196 <ItemGroup />
General Comments 0
You need to be logged in to leave comments. Login now