Mercurial > pub > ImplabNet

comparison Implab/Automaton/RegularExpressions/RegularDFA.cs @ 172:92d5278d1b10 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working on text scanner
author cin
date Mon, 14 Mar 2016 01:19:38 +0300
parents
children 0c3c69fe225b
comparison
equal deleted inserted replaced
171:0f70905b4652 172:92d5278d1b10
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4
5 namespace Implab.Automaton.RegularExpressions {
6 public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
7
8 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
9 readonly IAlphabet<TInput> m_alphabet;
10
11 public RegularDFA(IAlphabet<TInput> alphabet) {
12 Safe.ArgumentNotNull(alphabet, "aplhabet");
13
14 m_alphabet = alphabet;
15 }
16
17
18 public IAlphabet<TInput> InputAlphabet {
19 get {
20 return m_alphabet;
21 }
22 }
23
24 public void MarkFinalState(int s, TTag[] tags) {
25 MarkFinalState(s);
26 SetStateTag(s, tags);
27 }
28
29 public void SetStateTag(int s, TTag[] tags) {
30 Safe.ArgumentNotNull(tags, "tags");
31 m_tags[s] = tags;
32 }
33
34 public TTag[] GetStateTag(int s) {
35 TTag[] tags;
36 return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
37 }
38
39 public new DFAStateDescriptor<TTag>[] CreateTransitionTable() {
40 var table = new DFAStateDescriptor<TTag>[StateCount];
41
42 foreach (var t in this) {
43 if (table[t.s1].transitions == null)
44 table[t.s1] = new DFAStateDescriptor<TTag>(AlphabetSize, IsFinalState(t.s1), GetStateTag(t.s1));
45 if (table[t.s2].transitions == null)
46 table[t.s2] = new DFAStateDescriptor<TTag>(AlphabetSize, IsFinalState(t.s2), GetStateTag(t.s2));
47 table[t.s1].transitions[t.edge] = t.s2;
48 }
49
50 return table;
51 }
52
53 /// <summary>
54 /// Optimize the specified alphabet.
55 /// </summary>
56 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
57 public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
58 Safe.ArgumentNotNull(alphabet, "alphabet");
59
60 var dfa = new RegularDFA<TInput, TTag>(alphabet);
61
62 var states = new DummyAlphabet(StateCount);
63 var alphaMap = new Dictionary<int,int>();
64 var stateMap = new Dictionary<int,int>();
65
66 Optimize(dfa, alphaMap, stateMap);
67
68 // mark tags in the new DFA
69 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
70 dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
71
72 // make the alphabet for the new DFA
73 foreach (var pair in alphaMap)
74 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
75
76 return dfa;
77 }
78
79 protected override IEnumerable<HashSet<int>> GroupFinalStates() {
80 var arrayComparer = new CustomEqualityComparer<TTag[]>(
81 (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
82 x => x.Sum(it => x.GetHashCode())
83 );
84 return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
85 }
86
87 }
88 }
89