##// END OF EJS Templates
implab » ImplabNet
RSS
minor fix
cin -
r159:5558e43c79bb v2
parent child
Show More
Show file before | Show file after | Hide comments
@@ -1,262 +1,264
1 using Implab;
1 using Implab;
2 using System;
2 using System;
3 using System.Collections.Generic;
3 using System.Collections.Generic;
4 using System.Diagnostics;
4 using System.Diagnostics;
5 using System.Linq;
5 using System.Linq;
6
6
7 namespace Implab.Parsing {
7 namespace Implab.Parsing {
8 public class DFADefinition : IDFADefinition {
8 public class DFADefinition : IDFADefinition {
9 readonly List<DFAStateDescriptior> m_states;
9 readonly List<DFAStateDescriptior> m_states;
10
10
11 public const int INITIAL_STATE = 1;
11 public const int INITIAL_STATE = 1;
12 public const int UNREACHEBLE_STATE = 0;
12 public const int UNREACHEBLE_STATE = 0;
13
13
14 DFAStateDescriptior[] m_statesArray;
14 DFAStateDescriptior[] m_statesArray;
15 readonly int m_alpabetSize;
15 readonly int m_alpabetSize;
16
16
17 public DFADefinition(int alphabetSize) {
17 public DFADefinition(int alphabetSize) {
18 m_states = new List<DFAStateDescriptior>();
18 m_states = new List<DFAStateDescriptior>();
19 m_alpabetSize = alphabetSize;
19 m_alpabetSize = alphabetSize;
20
20
21 m_states.Add(new DFAStateDescriptior());
21 m_states.Add(new DFAStateDescriptior());
22 }
22 }
23
23
24 public DFAStateDescriptior[] States {
24 public DFAStateDescriptior[] States {
25 get {
25 get {
26 if (m_statesArray == null)
26 if (m_statesArray == null)
27 m_statesArray = m_states.ToArray();
27 m_statesArray = m_states.ToArray();
28 return m_statesArray;
28 return m_statesArray;
29 }
29 }
30 }
30 }
31
31
32 public bool InitialStateIsFinal {
32 public bool InitialStateIsFinal {
33 get {
33 get {
34 return m_states[INITIAL_STATE].final;
34 return m_states[INITIAL_STATE].final;
35 }
35 }
36 }
36 }
37
37
38 public int AddState() {
38 public int AddState() {
39 var index = m_states.Count;
39 var index = m_states.Count;
40 m_states.Add(new DFAStateDescriptior {
40 m_states.Add(new DFAStateDescriptior {
41 final = false,
41 final = false,
42 transitions = new int[AlphabetSize]
42 transitions = new int[AlphabetSize]
43 });
43 });
44 m_statesArray = null;
44 m_statesArray = null;
45
45
46 return index;
46 return index;
47 }
47 }
48
48
49 public int AddState(int[] tag) {
49 public int AddState(int[] tag) {
50 var index = m_states.Count;
50 var index = m_states.Count;
51 bool final = tag != null && tag.Length != 0;
51 bool final = tag != null && tag.Length != 0;
52 m_states.Add(new DFAStateDescriptior {
52 m_states.Add(new DFAStateDescriptior {
53 final = final,
53 final = final,
54 transitions = new int[AlphabetSize],
54 transitions = new int[AlphabetSize],
55 tag = final ? tag : null
55 tag = final ? tag : null
56 });
56 });
57 m_statesArray = null;
57 m_statesArray = null;
58 return index;
58 return index;
59 }
59 }
60
60
61 public void DefineTransition(int s1,int s2, int symbol) {
61 public void DefineTransition(int s1,int s2, int symbol) {
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
65
65
66 m_states[s1].transitions[symbol] = s2;
66 m_states[s1].transitions[symbol] = s2;
67 }
67 }
68
68
69 public void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
69 public void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
70 Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
70 Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
71 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
71 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
72
72
73 var setComparer = new CustomEqualityComparer<HashSet<int>>(
73 var setComparer = new CustomEqualityComparer<HashSet<int>>(
74 (x, y) => x.SetEquals(y),
74 (x, y) => x.SetEquals(y),
75 (s) => s.Sum(x => x.GetHashCode())
75 (s) => s.Sum(x => x.GetHashCode())
76 );
76 );
77
77
78 var arrayComparer = new CustomEqualityComparer<int[]>(
78 var arrayComparer = new CustomEqualityComparer<int[]>(
79 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
79 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
80 (a) => a.Sum(x => x.GetHashCode())
80 (a) => a.Sum(x => x.GetHashCode())
81 );
81 );
82
82
83 var optimalStates = new HashSet<HashSet<int>>(setComparer);
83 var optimalStates = new HashSet<HashSet<int>>(setComparer);
84 var queue = new HashSet<HashSet<int>>(setComparer);
84 var queue = new HashSet<HashSet<int>>(setComparer);
85
85
86 foreach (var g in Enumerable
86 foreach (var g in Enumerable
87 .Range(INITIAL_STATE, m_states.Count-1)
87 .Range(INITIAL_STATE, m_states.Count-1)
88 .Select(i => new {
88 .Select(i => new {
89 index = i,
89 index = i,
90 descriptor = m_states[i]
90 descriptor = m_states[i]
91 })
91 })
92 .Where(x => x.descriptor.final)
92 .Where(x => x.descriptor.final)
93 .GroupBy(x => x.descriptor.tag, arrayComparer)
93 .GroupBy(x => x.descriptor.tag, arrayComparer)
94 ) {
94 ) {
95 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
95 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
96 }
96 }
97
97
98 var state = new HashSet<int>(
98 var state = new HashSet<int>(
99 Enumerable
99 Enumerable
100 .Range(INITIAL_STATE, m_states.Count - 1)
100 .Range(INITIAL_STATE, m_states.Count - 1)
101 .Where(i => !m_states[i].final)
101 .Where(i => !m_states[i].final)
102 );
102 );
103 optimalStates.Add(state);
103 optimalStates.Add(state);
104 queue.Add(state);
104 queue.Add(state);
105
105
106 while (queue.Count > 0) {
106 while (queue.Count > 0) {
107 var stateA = queue.First();
107 var stateA = queue.First();
108 queue.Remove(stateA);
108 queue.Remove(stateA);
109
109
110 for (int c = 0; c < AlphabetSize; c++) {
110 for (int c = 0; c < AlphabetSize; c++) {
111 var stateX = new HashSet<int>();
111 var stateX = new HashSet<int>();
112
112
113 for(int s = 1; s < m_states.Count; s++) {
113 for(int s = 1; s < m_states.Count; s++) {
114 if (stateA.Contains(m_states[s].transitions[c]))
114 if (stateA.Contains(m_states[s].transitions[c]))
115 stateX.Add(s);
115 stateX.Add(s);
116 }
116 }
117
117
118 foreach (var stateY in optimalStates.ToArray()) {
118 foreach (var stateY in optimalStates.ToArray()) {
119 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
119 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
120 var stateR1 = new HashSet<int>(stateY);
120 var stateR1 = new HashSet<int>(stateY);
121 var stateR2 = new HashSet<int>(stateY);
121 var stateR2 = new HashSet<int>(stateY);
122
122
123 stateR1.IntersectWith(stateX);
123 stateR1.IntersectWith(stateX);
124 stateR2.ExceptWith(stateX);
124 stateR2.ExceptWith(stateX);
125
125
126 optimalStates.Remove(stateY);
126 optimalStates.Remove(stateY);
127 optimalStates.Add(stateR1);
127 optimalStates.Add(stateR1);
128 optimalStates.Add(stateR2);
128 optimalStates.Add(stateR2);
129
129
130 if (queue.Contains(stateY)) {
130 if (queue.Contains(stateY)) {
131 queue.Remove(stateY);
131 queue.Remove(stateY);
132 queue.Add(stateR1);
132 queue.Add(stateR1);
133 queue.Add(stateR2);
133 queue.Add(stateR2);
134 } else {
134 } else {
135 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
135 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
136 }
136 }
137 }
137 }
138 }
138 }
139 }
139 }
140 }
140 }
141
141
142 // строим ΠΊΠ°Ρ€Ρ‚Ρ‹ соотвСствия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний с ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ
142 // строим ΠΊΠ°Ρ€Ρ‚Ρ‹ соотвСствия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний с ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ
143
143
144 var initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
144 var initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
145
145
146 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
146 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
147 int[] reveseOptimalMap = new int[m_states.Count];
147 int[] reveseOptimalMap = new int[m_states.Count];
148 // ΠΊΠ°Ρ€Ρ‚Π° с индСксами ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний
148 // ΠΊΠ°Ρ€Ρ‚Π° с индСксами ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний
149 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
149 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
150 {
150 {
151 optimalMap[0] = new HashSet<int>(); // unreachable state
151 optimalMap[0] = new HashSet<int>(); // unreachable state
152 optimalMap[1] = initialState; // initial state
152 optimalMap[1] = initialState; // initial state
153 foreach (var ss in initialState)
153 foreach (var ss in initialState)
154 reveseOptimalMap[ss] = 1;
154 reveseOptimalMap[ss] = 1;
155
155
156 int i = 2;
156 int i = 2;
157 foreach (var s in optimalStates) {
157 foreach (var s in optimalStates) {
158 if (s.SetEquals(initialState))
158 if (s.SetEquals(initialState))
159 continue;
159 continue;
160 optimalMap[i] = s;
160 optimalMap[i] = s;
161 foreach (var ss in s)
161 foreach (var ss in s)
162 reveseOptimalMap[ss] = i;
162 reveseOptimalMap[ss] = i;
163 i++;
163 i++;
164 }
164 }
165 }
165 }
166
166
167 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
167 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
168
168
169 var minClasses = new HashSet<HashSet<int>>(setComparer);
169 var minClasses = new HashSet<HashSet<int>>(setComparer);
170 var alphaQueue = new Queue<HashSet<int>>();
170 var alphaQueue = new Queue<HashSet<int>>();
171 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
171 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
172
172
173 for (int s = 1 ; s < optimalMap.Length; s++) {
173 for (int s = 1 ; s < optimalMap.Length; s++) {
174 var newQueue = new Queue<HashSet<int>>();
174 var newQueue = new Queue<HashSet<int>>();
175
175
176 foreach (var A in alphaQueue) {
176 foreach (var A in alphaQueue) {
177 if (A.Count == 1) {
177 if (A.Count == 1) {
178 minClasses.Add(A);
178 minClasses.Add(A);
179 continue;
179 continue;
180 }
180 }
181
181
182 // Ρ€Π°Π·Π»ΠΈΡ‡Π°Π΅ΠΌ классы символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ пСрСводят Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ состояния
182 // Ρ€Π°Π·Π»ΠΈΡ‡Π°Π΅ΠΌ классы символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ пСрСводят Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ состояния
183 // optimalState -> alphaClass
183 // optimalState -> alphaClass
184 var classes = new Dictionary<int, HashSet<int>>();
184 var classes = new Dictionary<int, HashSet<int>>();
185
185
186 foreach (var term in A) {
186 foreach (var term in A) {
187 // ΠΈΡ‰Π΅ΠΌ всС ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Ρ‹ класса ΠΏΠΎ символу term
187 // ΠΈΡ‰Π΅ΠΌ всС ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Ρ‹ класса ΠΏΠΎ символу term
188 var s2 = reveseOptimalMap[
188 var s2 = reveseOptimalMap[
189 optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // ΠΏΠ΅Ρ€Π²ΠΎΠ΅ допустимоС элСмСнтарноС состояниС, Ссли Π΅ΡΡ‚ΡŒ
189 optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // ΠΏΠ΅Ρ€Π²ΠΎΠ΅ допустимоС элСмСнтарноС состояниС, Ссли Π΅ΡΡ‚ΡŒ
190 ];
190 ];
191
191
192 HashSet<int> A2;
192 HashSet<int> A2;
193 if (!classes.TryGetValue(s2, out A2)) {
193 if (!classes.TryGetValue(s2, out A2)) {
194 A2 = new HashSet<int>();
194 A2 = new HashSet<int>();
195 newQueue.Enqueue(A2);
195 newQueue.Enqueue(A2);
196 classes[s2] = A2;
196 classes[s2] = A2;
197 }
197 }
198 A2.Add(term);
198 A2.Add(term);
199 }
199 }
200 }
200 }
201
201
202 if (newQueue.Count == 0)
202 if (newQueue.Count == 0)
203 break;
203 break;
204 alphaQueue = newQueue;
204 alphaQueue = newQueue;
205 }
205 }
206
206
207 foreach (var A in alphaQueue)
207 foreach (var A in alphaQueue)
208 minClasses.Add(A);
208 minClasses.Add(A);
209
209
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
211
211
212 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
212 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
213
213
214 var states = new int[ optimalMap.Length ];
214 var states = new int[ optimalMap.Length ];
215 states[0] = UNREACHEBLE_STATE;
215 states[0] = UNREACHEBLE_STATE;
216
216
217 for(var s = INITIAL_STATE; s < states.Length; s++) {
217 for(var s = INITIAL_STATE; s < states.Length; s++) {
218 var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
218 var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
219 if (tags.Length > 0)
219 if (tags.Length > 0)
220 states[s] = minimalDFA.AddState(tags);
220 states[s] = minimalDFA.AddState(tags);
221 else
221 else
222 states[s] = minimalDFA.AddState();
222 states[s] = minimalDFA.AddState();
223 }
223 }
224
224
225 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
225 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
226
226
227 for (int s1 = 1; s1 < m_states.Count; s1++) {
227 for (int s1 = 1; s1 < m_states.Count; s1++) {
228 for (int c = 0; c < AlphabetSize; c++) {
228 for (int c = 0; c < AlphabetSize; c++) {
229 var s2 = m_states[s1].transitions[c];
229 var s2 = m_states[s1].transitions[c];
230 if (s2 != UNREACHEBLE_STATE) {
230 if (s2 != UNREACHEBLE_STATE) {
231 minimalDFA.DefineTransition(
231 minimalDFA.DefineTransition(
232 reveseOptimalMap[s1],
232 reveseOptimalMap[s1],
233 reveseOptimalMap[s2],
233 reveseOptimalMap[s2],
234 alphabetMap[c]
234 alphabetMap[c]
235 );
235 );
236 }
236 }
237 }
237 }
238 }
238 }
239
239
240 }
240 }
241
241
242 public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
242 public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
243
243
244 var reverseMap = alphabet.CreateReverseMap();
244 var reverseMap = alphabet.CreateReverseMap();
245
245
246 for (int i = 1; i < reverseMap.Length; i++) {
246 for (int i = 1; i < reverseMap.Length; i++) {
247 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
247 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
248 }
248 }
249
249
250 for (int i = 1; i < m_states.Count; i++) {
250 for (int i = 1; i < m_states.Count; i++) {
251 var s = m_states[i];
251 var s = m_states[i];
252 for (int c = 0; c < AlphabetSize; c++)
252 for (int c = 0; c < AlphabetSize; c++)
253 if (s.transitions[c] != UNREACHEBLE_STATE)
253 if (s.transitions[c] != UNREACHEBLE_STATE)
254 Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
254 Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
255 }
255 }
256 }
256 }
257
257
258 public int AlphabetSize {
258 public int AlphabetSize {
259 get;
259 get {
260 return m_alpabetSize;
260 }
261 }
261 }
262 }
262 }
263 }
264 }
General Comments 0
You need to be logged in to leave comments. Login now