Mercurial > pub > ImplabNet

comparison Implab/Parsing/DFADefinition.cs @ 161:2a8466f0cb8a v2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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),