Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATransitionTable.cs @ 168:8fb9c9507a26 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sync
author cin
date Wed, 02 Mar 2016 19:59:16 +0300
parents 96681e9d0cea
children
comparison
equal deleted inserted replaced
167:96681e9d0cea 168:8fb9c9507a26
51 51
52 public int InitialState { 52 public int InitialState {
53 get { return m_initialState; } 53 get { return m_initialState; }
54 } 54 }
55 55
56 int[] NewTransitionArray() {
57 var t = new int[m_symbolCount];
58
59 for (var i = 0; i < m_symbolCount; i++)
60 t[i] = DFAConst.UNREACHABLE_STATE;
61 return t;
62 }
63
56 #endregion 64 #endregion
57 65
58 protected virtual DFAStateDescriptior[] ConstructTransitionTable() { 66 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
59 var dfaTable = new DFAStateDescriptior[m_stateCount]; 67 var dfaTable = new DFAStateDescriptior[m_stateCount];
60 68
61 foreach (var pair in m_finalStates) {
62 var idx = pair.Key;
63
64 dfaTable[idx].final = true;
65 dfaTable[idx].tag = pair.Value;
66 }
67 69
68 foreach (var t in m_transitions) { 70 foreach (var t in m_transitions) {
69 if (dfaTable[t.s1].transitions == null) { 71 if (dfaTable[t.s1].transitions == null)
70 dfaTable[t.s1].transitions = new int[m_symbolCount]; 72 dfaTable[t.s1] = new DFAStateDescriptior(NewTransitionArray(), m_finalStates.Contains(t.s1));
71 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++) 73
72 dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
73 }
74
75 dfaTable[t.s1].transitions[t.edge] = t.s2; 74 dfaTable[t.s1].transitions[t.edge] = t.s2;
76 } 75 }
76
77 foreach (var s in m_finalStates)
78 if (!dfaTable[s].final)
79 m_dfaTable[s] = new DFAStateDescriptior(NewTransitionArray, true);
80
77 } 81 }
78 82
79 #region IDFADefinitionBuilder 83 #region IDFADefinitionBuilder
80 84
81 public void DefineTransition(int s1, int s2, int symbol) { 85 public void DefineTransition(int s1, int s2, int symbol) {
105 } 109 }
106 110
107 111
108 #endregion 112 #endregion
109 113
114 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
115 return new HashSet<int>[] { m_finalStates };
116 }
117
110 protected void Optimize<TInput, TState>( 118 protected void Optimize<TInput, TState>(
111 IDFATableBuilder<TTag> optimalDFA, 119 IDFATableBuilder optimalDFA,
112 IAlphabet<TInput> inputAlphabet, 120 IAlphabet<TInput> inputAlphabet,
113 IAlphabetBuilder<TInput> optimalInputAlphabet, 121 IAlphabetBuilder<TInput> optimalInputAlphabet,
114 IAlphabet<TState> stateAlphabet, 122 IAlphabet<TState> stateAlphabet,
115 IAlphabetBuilder<TState> optimalStateAlphabet 123 IAlphabetBuilder<TState> optimalStateAlphabet
116 ) { 124 ) {
128 var setComparer = new CustomEqualityComparer<HashSet<int>>( 136 var setComparer = new CustomEqualityComparer<HashSet<int>>(
129 (x, y) => x.SetEquals(y), 137 (x, y) => x.SetEquals(y),
130 s => s.Sum(x => x.GetHashCode()) 138 s => s.Sum(x => x.GetHashCode())
131 ); 139 );
132 140
133 var arrayComparer = new CustomEqualityComparer<TTag[]>(
134 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
135 a => a.Sum(x => x.GetHashCode())
136 );
137
138 var optimalStates = new HashSet<HashSet<int>>(setComparer); 141 var optimalStates = new HashSet<HashSet<int>>(setComparer);
139 var queue = new HashSet<HashSet<int>>(setComparer); 142 var queue = new HashSet<HashSet<int>>(setComparer);
140 143
141 // получаем конечные состояния, сгруппированные по маркерам 144 // получаем конечные состояния, сгруппированные по маркерам
142 optimalStates.UnionWith( 145 optimalStates.UnionWith(
143 m_finalStates 146 GroupFinalStates()
144 .GroupBy(pair => pair.Value, arrayComparer)
145 .Select(
146 g => new HashSet<int>(
147 g.Select( pair => pair.Key)
148 )
149 )
150 ); 147 );
151 148
152 var state = new HashSet<int>( 149 var state = new HashSet<int>(
153 Enumerable 150 Enumerable
154 .Range(0, m_stateCount - 1) 151 .Range(0, m_stateCount - 1)
155 .Where(i => !m_finalStates.ContainsKey(i)) 152 .Where(i => !m_finalStates.Contains(i))
156 ); 153 );
154
157 optimalStates.Add(state); 155 optimalStates.Add(state);
158 queue.Add(state); 156 queue.Add(state);
159 157
160 var rmap = m_transitions 158 var rmap = m_transitions
161 .GroupBy(t => t.s2) 159 .GroupBy(t => t.s2)
206 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge); 204 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
207 205
208 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet); 206 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
209 207
210 var optimalTags = m_finalStates 208 var optimalTags = m_finalStates
211 .GroupBy(pair => statesMap[pair.Key]) 209 .GroupBy(s => statesMap[s])
212 .ToDictionary( 210 .ToDictionary(
213 g => g.Key, 211 g => g.Key,
214 g => g.SelectMany(pair => pair.Value).ToArray() 212 g => g.ToArray()
215 ); 213 );
216 214
217 // построение автомата 215 // построение автомата
218 optimalDFA.SetInitialState(statesMap[m_initialState]); 216 optimalDFA.SetInitialState(statesMap[m_initialState]);
219 217
220 foreach (var pair in optimalTags) 218 foreach (var pair in optimalTags)
221 optimalDFA.MarkFinalState(pair.Key, pair.Value); 219 optimalDFA.MarkFinalState(pair.Key, pair.Value);
222 220
223 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct()) 221 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
224 optimalDFA.DefineTransition(t.s1, t.s2, t.edge); 222 optimalDFA.Add(new AutomatonTransition(t.s1, t.s2, t.edge));
225 223
224 }
225
226 public void MarkFinalState(int state) {
227 throw new NotImplementedException();
228 }
229
230 public void Add(AutomatonTransition item) {
231 throw new NotImplementedException();
232 }
233
234 public void Clear() {
235 throw new NotImplementedException();
236 }
237
238 public bool Contains(AutomatonTransition item) {
239 throw new NotImplementedException();
240 }
241
242 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
243 throw new NotImplementedException();
244 }
245
246 public bool Remove(AutomatonTransition item) {
247 throw new NotImplementedException();
248 }
249
250 public int Count {
251 get {
252 throw new NotImplementedException();
253 }
254 }
255
256 public bool IsReadOnly {
257 get {
258 throw new NotImplementedException();
259 }
260 }
261
262 public IEnumerator<AutomatonTransition> GetEnumerator() {
263 throw new NotImplementedException();
264 }
265
266 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
267 throw new NotImplementedException();
226 } 268 }
227 269
228 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { 270 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
229 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); 271 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
230 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); 272 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");