Mercurial > pub > ImplabNet

comparison Implab/Parsing/DFADefinitionBase.cs @ 55:c0bf853aa04f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added initial JSON support +JSONParser +JSONWriter
author cin
date Sun, 15 Jun 2014 19:39:11 +0400
parents
children 97fbbf816844
comparison
equal deleted inserted replaced
51:2c332a9c64c0 55:c0bf853aa04f
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Diagnostics;
5 using System.Linq;
6 using System.Text;
7 using System.Threading.Tasks;
8
9 namespace Implab.Parsing {
10 public abstract class DFADefinitionBase : IDFADefinition {
11 readonly List<DFAStateDescriptior> m_states;
12
13 public const int INITIAL_STATE = 1;
14 public const int UNREACHEBLE_STATE = 0;
15
16 DFAStateDescriptior[] m_statesArray;
17
18 public DFADefinitionBase() {
19 m_states = new List<DFAStateDescriptior>();
20
21 m_states.Add(new DFAStateDescriptior());
22 }
23
24 public DFAStateDescriptior[] States {
25 get {
26 if (m_statesArray == null)
27 m_statesArray = m_states.ToArray();
28 return m_statesArray;
29 }
30 }
31
32 public bool InitialStateIsFinal {
33 get {
34 return m_states[INITIAL_STATE].final;
35 }
36 }
37
38 public int AddState() {
39 var index = m_states.Count;
40 m_states.Add(new DFAStateDescriptior {
41 final = false,
42 transitions = new int[AlphabetSize]
43 });
44
45 return index;
46 }
47
48 public int AddState(int[] tag) {
49 var index = m_states.Count;
50 bool final = tag == null || tag.Length == 0 ? false : true;
51 m_states.Add(new DFAStateDescriptior {
52 final = final,
53 transitions = new int[AlphabetSize],
54 tag = final ? tag : null
55 });
56 return index;
57 }
58
59 public void DefineTransition(int s1,int s2, int symbol) {
60 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
61 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
62 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
63
64 m_states[s1].transitions[symbol] = s2;
65 }
66
67 protected void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
68 Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
69 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
70
71 var setComparer = new CustomEqualityComparer<HashSet<int>>(
72 (x, y) => x.SetEquals(y),
73 (s) => s.Sum(x => x.GetHashCode())
74 );
75
76 var arrayComparer = new CustomEqualityComparer<int[]>(
77 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
78 (a) => a.Sum(x => x.GetHashCode())
79 );
80
81 var optimalStates = new HashSet<HashSet<int>>(setComparer);
82 var queue = new HashSet<HashSet<int>>(setComparer);
83
84 foreach (var g in Enumerable
85 .Range(INITIAL_STATE, m_states.Count-1)
86 .Select(i => new {
87 index = i,
88 descriptor = m_states[i]
89 })
90 .Where(x => x.descriptor.final)
91 .GroupBy(x => x.descriptor.tag, arrayComparer)
92 ) {
93 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
94 }
95
96 var state = new HashSet<int>(
97 Enumerable
98 .Range(INITIAL_STATE, m_states.Count - 1)
99 .Where(i => !m_states[i].final)
100 );
101 optimalStates.Add(state);
102 queue.Add(state);
103
104 while (queue.Count > 0) {
105 var stateA = queue.First();
106 queue.Remove(stateA);
107
108 for (int c = 0; c < AlphabetSize; c++) {
109 var stateX = new HashSet<int>();
110
111 for(int s = 1; s < m_states.Count; s++) {
112 if (stateA.Contains(m_states[s].transitions[c]))
113 stateX.Add(s);
114 }
115
116 foreach (var stateY in optimalStates.ToArray()) {
117 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
118 var stateR1 = new HashSet<int>(stateY);
119 var stateR2 = new HashSet<int>(stateY);
120
121 stateR1.IntersectWith(stateX);
122 stateR2.ExceptWith(stateX);
123
124 optimalStates.Remove(stateY);
125 optimalStates.Add(stateR1);
126 optimalStates.Add(stateR2);
127
128 if (queue.Contains(stateY)) {
129 queue.Remove(stateY);
130 queue.Add(stateR1);
131 queue.Add(stateR2);
132 } else {
133 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
134 }
135 }
136 }
137 }
138 }
139
140 // строим карты соотвествия оптимальных состояний с оригинальными
141
142 var initialState = optimalStates.Where(x => x.Contains(INITIAL_STATE)).Single();
143
144 // карта получения оптимального состояния по соотвествующему ему простому состоянию
145 int[] reveseOptimalMap = new int[m_states.Count];
146 // карта с индексами оптимальных состояний
147 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
148 {
149 optimalMap[0] = new HashSet<int>(); // unreachable state
150 optimalMap[1] = initialState; // initial state
151 foreach (var ss in initialState)
152 reveseOptimalMap[ss] = 1;
153
154 int i = 2;
155 foreach (var s in optimalStates) {
156 if (s.SetEquals(initialState))
157 continue;
158 optimalMap[i] = s;
159 foreach (var ss in s)
160 reveseOptimalMap[ss] = i;
161 i++;
162 }
163 }
164
165 // получаем минимальный алфавит
166
167 var minClasses = new HashSet<HashSet<int>>(setComparer);
168 var alphaQueue = new Queue<HashSet<int>>();
169 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
170
171 for (int s = 1 ; s < optimalMap.Length; s++) {
172 var newQueue = new Queue<HashSet<int>>();
173
174 foreach (var A in alphaQueue) {
175 if (A.Count == 1) {
176 minClasses.Add(A);
177 continue;
178 }
179
180 // различаем классы символов, которые переводят в различные оптимальные состояния
181 // optimalState -> alphaClass
182 var classes = new Dictionary<int, HashSet<int>>();
183
184 foreach (var term in A) {
185 // ищем все переходы класса по символу term
186 var s2 = reveseOptimalMap[
187 optimalMap[s].Select(x => m_states[x].transitions[term]) // все элементарные состояния, куда переходит класс s
188 .Where(x => x != 0) // только допустимые
189 .FirstOrDefault() // первое допустимое элементарное состояние, если есть
190 ];
191
192 HashSet<int> A2;
193 if (!classes.TryGetValue(s2, out A2)) {
194 A2 = new HashSet<int>();
195 newQueue.Enqueue(A2);
196 classes[s2] = A2;
197 }
198 A2.Add(term);
199 }
200 }
201
202 if (newQueue.Count == 0)
203 break;
204 alphaQueue = newQueue;
205 }
206
207 foreach (var A in alphaQueue)
208 minClasses.Add(A);
209
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
211
212 // построение автомата
213
214 var states = new int[ optimalMap.Length ];
215 states[0] = UNREACHEBLE_STATE;
216
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();
219 if (tags.Length > 0)
220 states[s] = minimalDFA.AddState(tags);
221 else
222 states[s] = minimalDFA.AddState();
223 }
224
225 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
226
227 for (int s1 = 1; s1 < m_states.Count; s1++) {
228 for (int c = 0; c < AlphabetSize; c++) {
229 var s2 = m_states[s1].transitions[c];
230 if (s2 != UNREACHEBLE_STATE) {
231 minimalDFA.DefineTransition(
232 reveseOptimalMap[s1],
233 reveseOptimalMap[s2],
234 alphabetMap[c]
235 );
236 }
237 }
238 }
239
240 }
241
242 protected void PrintDFA<TA>(IAlphabet<TA> alphabet) {
243
244 var reverseMap = alphabet.CreateReverseMap();
245
246 for (int i = 1; i < reverseMap.Length; i++) {
247 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
248 }
249
250 for (int i = 1; i < m_states.Count; i++) {
251 var s = m_states[i];
252 for (int c = 0; c < AlphabetSize; c++)
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 ? "$" : "");
255 }
256 }
257
258 public abstract int AlphabetSize {
259 get;
260 }
261 }
262 }