annotate Implab/Automaton/DFATable.cs @ 180:c32688129f14 ref20160224

refactoring complete, JSONParser rewritten
author cin
date Thu, 24 Mar 2016 02:30:46 +0300
parents d5c5db0335ee
children b2b6a6640aa3
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
1 using Implab;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
2 using System;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
3 using System.Collections.Generic;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
4 using System.Linq;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
5
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
6 namespace Implab.Automaton {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
7 public class DFATable : IDFATableBuilder {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
8 int m_stateCount;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
9 int m_symbolCount;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
10 int m_initialState;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
11
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
12 readonly HashSet<int> m_finalStates = new HashSet<int>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
14
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
15
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
16 #region IDFADefinition implementation
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
17
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
18 public bool IsFinalState(int s) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
19 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
20
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
21 return m_finalStates.Contains(s);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
22 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
23
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
24 public IEnumerable<int> FinalStates {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
25 get {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
26 return m_finalStates;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
27 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
28 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
29
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
30 public int StateCount {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
31 get { return m_stateCount; }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
32 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
33
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
34 public int AlphabetSize {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
35 get { return m_symbolCount; }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
36 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
37
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
38 public int InitialState {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
39 get { return m_initialState; }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
40 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
41
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
42 #endregion
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
43
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
44 public void SetInitialState(int s) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
45 Safe.ArgumentAssert(s >= 0, "s");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
46 m_initialState = s;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
47 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
48
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
49 public void MarkFinalState(int state) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
50 m_finalStates.Add(state);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
51 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
52
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
53 public void Add(AutomatonTransition item) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
54 Safe.ArgumentAssert(item.s1 >= 0, "item");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
55 Safe.ArgumentAssert(item.s2 >= 0, "item");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
56 Safe.ArgumentAssert(item.edge >= 0, "item");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
57
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
58 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
59 m_symbolCount = Math.Max(m_symbolCount, item.edge);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
60
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
61 m_transitions.Add(item);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
62 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
63
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
64 public void Clear() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
65 m_stateCount = 0;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
66 m_symbolCount = 0;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
67 m_finalStates.Clear();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
68 m_transitions.Clear();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
69 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
70
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
71 public bool Contains(AutomatonTransition item) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
72 return m_transitions.Contains(item);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
73 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
74
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
75 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
76 m_transitions.CopyTo(array, arrayIndex);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
77 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
78
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
79 public bool Remove(AutomatonTransition item) {
180
c32688129f14 refactoring complete, JSONParser rewritten
cin
parents: 178
diff changeset
80 return m_transitions.Remove(item);
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
81 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
82
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
83 public int Count {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
84 get {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
85 return m_transitions.Count;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
86 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
87 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
88
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
89 public bool IsReadOnly {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
90 get {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
91 return false;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
92 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
93 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
94
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
95 public IEnumerator<AutomatonTransition> GetEnumerator() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
96 return m_transitions.GetEnumerator();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
97 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
98
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
99 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
100 return GetEnumerator();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
101 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
102
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
103 public int[,] CreateTransitionTable() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
104 var table = new int[StateCount,AlphabetSize];
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
105
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
106 for (int i = 0; i < StateCount; i++)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
107 for (int j = 0; i < AlphabetSize; j++)
178
d5c5db0335ee working on JSON parser
cin
parents: 176
diff changeset
108 table[i, j] = AutomatonConst.UNREACHABLE_STATE;
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
109
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
110 foreach (var t in this)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
111 table[t.s1,t.edge] = t.s2;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
112
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
113 return table;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
114 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
115
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
116 public bool[] CreateFinalStateTable() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
117 var table = new bool[StateCount];
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
118
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
119 foreach (var s in FinalStates)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
120 table[s] = true;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
121
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
122 return table;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
123 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
124
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
125 /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
126 /// <remarks>
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
127 /// В процессе построения минимального автомата требуется разделить множество состояний,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
128 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
129 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
130 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
131 /// </remarks>
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
132 /// <returns>The final states.</returns>
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
133 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
134 return new HashSet<int>[] { m_finalStates };
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
135 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
136
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
137 protected void Optimize(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
138 IDFATableBuilder optimalDFA,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
139 IDictionary<int,int> alphabetMap,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
140 IDictionary<int,int> stateMap
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
141 ) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
142 Safe.ArgumentNotNull(optimalDFA, "dfa");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
143 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
144 Safe.ArgumentNotNull(stateMap, "stateMap");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
145
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
146
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
147 var setComparer = new CustomEqualityComparer<HashSet<int>>(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
148 (x, y) => x.SetEquals(y),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
149 s => s.Sum(x => x.GetHashCode())
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
150 );
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
151
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
152 var optimalStates = new HashSet<HashSet<int>>(setComparer);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
153 var queue = new HashSet<HashSet<int>>(setComparer);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
154
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
155 // получаем конечные состояния, сгруппированные по маркерам
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
156 optimalStates.UnionWith(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
157 GroupFinalStates()
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
158 );
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
159
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
160 var state = new HashSet<int>(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
161 Enumerable
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
162 .Range(0, m_stateCount - 1)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
163 .Where(i => !m_finalStates.Contains(i))
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
164 );
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
165
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
166 optimalStates.Add(state);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
167 queue.Add(state);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
168
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
169 var rmap = m_transitions
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
170 .GroupBy(t => t.s2)
180
c32688129f14 refactoring complete, JSONParser rewritten
cin
parents: 178
diff changeset
171 .ToDictionary(
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
172 g => g.Key, // s2
180
c32688129f14 refactoring complete, JSONParser rewritten
cin
parents: 178
diff changeset
173 g => g.GroupBy(t => t.edge, t => t.s1).ToDictionary(p => p.Key)
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
174 );
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
175
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
176 while (queue.Count > 0) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
177 var stateA = queue.First();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
178 queue.Remove(stateA);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
179
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
180 for (int c = 0; c < m_symbolCount; c++) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
181 var stateX = new HashSet<int>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
182 foreach(var a in stateA)
180
c32688129f14 refactoring complete, JSONParser rewritten
cin
parents: 178
diff changeset
183 stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
184
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
185 foreach (var stateY in optimalStates.ToArray()) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
186 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
187 var stateR1 = new HashSet<int>(stateY);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
188 var stateR2 = new HashSet<int>(stateY);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
189
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
190 stateR1.IntersectWith(stateX);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
191 stateR2.ExceptWith(stateX);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
192
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
193 optimalStates.Remove(stateY);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
194 optimalStates.Add(stateR1);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
195 optimalStates.Add(stateR2);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
196
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
197 if (queue.Contains(stateY)) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
198 queue.Remove(stateY);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
199 queue.Add(stateR1);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
200 queue.Add(stateR2);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
201 } else {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
202 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
203 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
204 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
205 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
206 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
207 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
208
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
209 // карта получения оптимального состояния по соотвествующему ему простому состоянию
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
210 var nextState = 0;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
211 foreach (var item in optimalStates) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
212 var id = nextState++;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
213 foreach (var s in item)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
214 stateMap[s] = id;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
215 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
216
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
217 // получаем минимальный алфавит
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
218 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
219 // для этого используем алгоритм кластеризации, сначала
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
220 // считаем, что все символы не различимы
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
221
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
222 var minClasses = new HashSet<HashSet<int>>(setComparer);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
223 var alphaQueue = new Queue<HashSet<int>>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
224 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
225
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
226 // для всех состояний, будем проверять каждый класс на различимость,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
227 // т.е. символы различимы, если они приводят к разным состояниям
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
228 for (int s = 0 ; s < optimalStates.Count; s++) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
229 var newQueue = new Queue<HashSet<int>>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
230
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
231 foreach (var A in alphaQueue) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
232 // классы из одного символа делить бесполезно, переводим их сразу в
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
233 // результирующий алфавит
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
234 if (A.Count == 1) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
235 minClasses.Add(A);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
236 continue;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
237 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
238
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
239 // различаем классы символов, которые переводят в различные оптимальные состояния
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
240 // optimalState -> alphaClass
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
241 var classes = new Dictionary<int, HashSet<int>>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
242
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
243 foreach (var term in A) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
244 // ищем все переходы класса по символу term
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
245 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
246
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
247 var s2 = res.Length > 0 ? res[0] : -1;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
248
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
249 HashSet<int> a2;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
250 if (!classes.TryGetValue(s2, out a2)) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
251 a2 = new HashSet<int>();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
252 newQueue.Enqueue(a2);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
253 classes[s2] = a2;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
254 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
255 a2.Add(term);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
256 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
257 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
258
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
259 if (newQueue.Count == 0)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
260 break;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
261 alphaQueue = newQueue;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
262 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
263
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
264 // после окончания работы алгоритма в очереди останутся минимальные различимые классы
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
265 // входных символов
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
266 foreach (var A in alphaQueue)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
267 minClasses.Add(A);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
268
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
269 // построение отображения алфавитов входных символов.
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
270 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
271 // специальное значение, тогда сохраним минимальный класс,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
272 // содержащий этот символ на томже месте.
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
273
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
274 var nextCls = 0;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
275 foreach (var item in minClasses) {
178
d5c5db0335ee working on JSON parser
cin
parents: 176
diff changeset
276 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
277 nextCls++;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
278
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
279 // сохраняем DFAConst.UNCLASSIFIED_INPUT
178
d5c5db0335ee working on JSON parser
cin
parents: 176
diff changeset
280 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls;
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
281
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
282 foreach (var a in item)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
283 alphabetMap[a] = cls;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
284
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
285 nextCls++;
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
286 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
287
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
288 // построение автомата
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
289 optimalDFA.SetInitialState(stateMap[m_initialState]);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
290
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
291 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
292 optimalDFA.MarkFinalState(sf);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
293
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
294 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
295 optimalDFA.Add(t);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
296 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
297
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
298 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
299 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
300 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
301
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
302 foreach(var t in m_transitions)
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
303 Console.WriteLine(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
304 "[{0}] -{{{1}}}-> [{2}]{3}",
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
305 String.Join(",", stateAlphabet.GetSymbols(t.s1)),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
306 String.Join("", inputAlphabet.GetSymbols(t.edge)),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
307 String.Join(",", stateAlphabet.GetSymbols(t.s2)),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
308 m_finalStates.Contains(t.s2) ? "$" : ""
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
309 );
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
310 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
311
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
312 }
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
313 }