|
177
|
1 using System.Collections.Generic;
|
|
172
|
2 using System.Linq;
|
|
|
3
|
|
|
4 namespace Implab.Automaton.RegularExpressions {
|
|
179
|
5 public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
|
|
172
|
6
|
|
|
7 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
|
|
|
8 readonly IAlphabet<TInput> m_alphabet;
|
|
|
9
|
|
179
|
10 public RegularDFA(IAlphabet<TInput> alphabet) {
|
|
172
|
11 Safe.ArgumentNotNull(alphabet, "aplhabet");
|
|
|
12
|
|
|
13 m_alphabet = alphabet;
|
|
|
14 }
|
|
|
15
|
|
|
16
|
|
|
17 public IAlphabet<TInput> InputAlphabet {
|
|
|
18 get {
|
|
|
19 return m_alphabet;
|
|
|
20 }
|
|
|
21 }
|
|
|
22
|
|
|
23 public void MarkFinalState(int s, TTag[] tags) {
|
|
|
24 MarkFinalState(s);
|
|
|
25 SetStateTag(s, tags);
|
|
|
26 }
|
|
|
27
|
|
|
28 public void SetStateTag(int s, TTag[] tags) {
|
|
|
29 Safe.ArgumentNotNull(tags, "tags");
|
|
|
30 m_tags[s] = tags;
|
|
|
31 }
|
|
|
32
|
|
|
33 public TTag[] GetStateTag(int s) {
|
|
|
34 TTag[] tags;
|
|
|
35 return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
|
|
|
36 }
|
|
|
37
|
|
176
|
38 public TTag[][] CreateTagTable() {
|
|
|
39 var table = new TTag[StateCount][];
|
|
172
|
40
|
|
176
|
41 foreach (var pair in m_tags)
|
|
|
42 table[pair.Key] = pair.Value;
|
|
172
|
43
|
|
|
44 return table;
|
|
|
45 }
|
|
|
46
|
|
|
47 /// <summary>
|
|
|
48 /// Optimize the specified alphabet.
|
|
|
49 /// </summary>
|
|
|
50 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
|
|
179
|
51 public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
|
|
172
|
52 Safe.ArgumentNotNull(alphabet, "alphabet");
|
|
|
53
|
|
179
|
54 var dfa = new RegularDFA<TInput, TTag>(alphabet);
|
|
172
|
55
|
|
|
56 var alphaMap = new Dictionary<int,int>();
|
|
|
57 var stateMap = new Dictionary<int,int>();
|
|
|
58
|
|
|
59 Optimize(dfa, alphaMap, stateMap);
|
|
|
60
|
|
|
61 // mark tags in the new DFA
|
|
|
62 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
|
|
|
63 dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
|
|
|
64
|
|
|
65 // make the alphabet for the new DFA
|
|
181
|
66 // skip all unclassified symbols
|
|
|
67 foreach (var pair in alphaMap.Where(x => x.Value != 0))
|
|
172
|
68 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
|
|
|
69
|
|
|
70 return dfa;
|
|
|
71 }
|
|
|
72
|
|
|
73 protected override IEnumerable<HashSet<int>> GroupFinalStates() {
|
|
|
74 var arrayComparer = new CustomEqualityComparer<TTag[]>(
|
|
|
75 (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
|
|
|
76 x => x.Sum(it => x.GetHashCode())
|
|
|
77 );
|
|
|
78 return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
|
|
|
79 }
|
|
|
80
|
|
|
81 }
|
|
|
82 }
|
|
|
83
|
