Mercurial > pub > ImplabNet
comparison Implab/Parsing/DFADefinition.cs @ 161:2a8466f0cb8a v2
DFA refactoring
author | cin |
---|---|
date | Fri, 19 Feb 2016 18:07:17 +0300 |
parents | 5802131432e4 |
children |
comparison
equal
deleted
inserted
replaced
160:5802131432e4 | 161:2a8466f0cb8a |
---|---|
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<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> { |
9 readonly List<DFAStateDescriptior> m_states; | 9 readonly List<DFAStateDescriptior<TTag>> 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<TTag>[] 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<TTag>>(); |
19 m_alpabetSize = alphabetSize; | 19 m_alpabetSize = alphabetSize; |
20 | 20 |
21 m_states.Add(new DFAStateDescriptior()); | 21 m_states.Add(new DFAStateDescriptior<TTag>()); |
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 } | 22 } |
31 | 23 |
32 public bool InitialStateIsFinal { | 24 public bool InitialStateIsFinal { |
33 get { | 25 get { |
34 return m_states[INITIAL_STATE].final; | 26 return m_states[INITIAL_STATE].final; |
35 } | 27 } |
36 } | 28 } |
37 | 29 |
38 public int AddState() { | 30 public int AddState() { |
39 var index = m_states.Count; | 31 var index = m_states.Count; |
40 m_states.Add(new DFAStateDescriptior { | 32 m_states.Add(new DFAStateDescriptior<TTag> { |
41 final = false, | 33 final = false, |
42 transitions = new int[AlphabetSize] | 34 transitions = new int[AlphabetSize] |
43 }); | 35 }); |
44 m_statesArray = null; | 36 m_statesArray = null; |
45 | 37 |
46 return index; | 38 return index; |
47 } | 39 } |
48 | 40 |
49 public int AddState(int[] tag) { | 41 public int AddState(TTag[] tag) { |
50 var index = m_states.Count; | 42 var index = m_states.Count; |
51 bool final = tag != null && tag.Length != 0; | 43 bool final = tag != null && tag.Length != 0; |
52 m_states.Add(new DFAStateDescriptior { | 44 m_states.Add(new DFAStateDescriptior<TTag> { |
53 final = final, | 45 final = final, |
54 transitions = new int[AlphabetSize], | 46 transitions = new int[AlphabetSize], |
55 tag = final ? tag : null | 47 tag = final ? tag : null |
56 }); | 48 }); |
57 m_statesArray = null; | 49 m_statesArray = null; |
58 return index; | 50 return index; |
59 } | 51 } |
60 | 52 |
61 public void DefineTransition(int s1,int s2, int symbol) { | 53 public void DefineTransition(TState s1, TState s2, TInput symbol) { |
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1"); | 54 int is1 = StateAlphabet.Translate(s1); |
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2"); | 55 int is2 = StateAlphabet.Translate(s2); |
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol"); | 56 int isym = InputAlphabet.Translate(symbol); |
65 | 57 |
66 m_states[s1].transitions[symbol] = s2; | 58 Safe.ArgumentAssert(is1 != 0, "s1"); |
67 } | 59 Safe.ArgumentAssert(is2 != 0, "s2"); |
68 | 60 Safe.ArgumentAssert(isym != 0, "symbol"); |
69 protected IDFADefinition Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) { | 61 |
62 m_states[is1].transitions[isym] = is2; | |
63 } | |
64 | |
65 #region IDFADefinition implementation | |
66 | |
67 public DFAStateDescriptior<TTag>[] GetTransitionTable() { | |
68 if (m_statesArray == null) | |
69 m_statesArray = m_states.ToArray(); | |
70 return m_statesArray; | |
71 } | |
72 | |
73 public IAlphabet<TInput> InputAlphabet { | |
74 get { | |
75 throw new NotImplementedException(); | |
76 } | |
77 } | |
78 | |
79 public IAlphabet<TState> StateAlphabet { | |
80 get { | |
81 throw new NotImplementedException(); | |
82 } | |
83 } | |
84 | |
85 #endregion | |
86 | |
87 protected IDFADefinition<> Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) { | |
70 Safe.ArgumentNotNull(dfaFactory, "dfaFactory"); | 88 Safe.ArgumentNotNull(dfaFactory, "dfaFactory"); |
71 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet"); | 89 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet"); |
72 | 90 |
73 var setComparer = new CustomEqualityComparer<HashSet<int>>( | 91 var setComparer = new CustomEqualityComparer<HashSet<int>>( |
74 (x, y) => x.SetEquals(y), | 92 (x, y) => x.SetEquals(y), |