annotate Implab/Parsing/DFADefinition.cs @ 159:5558e43c79bb v2

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