##// END OF EJS Templates
DFA refactoring, rx based dfa.
cin -
r170:181119ef3b39 ref20160224
parent child
Show More
@@ -14,7 +14,7 namespace Implab.Automaton.RegularExpres
14 }
14 }
15
15
16 public EndToken()
16 public EndToken()
17 : this(0) {
17 : this(default(TTag)) {
18 }
18 }
19
19
20 public TTag Tag {
20 public TTag Tag {
@@ -122,7 +122,7 namespace Implab.Automaton.RegularExpres
122 m_ends.Add(m_idx, token.Tag);
122 m_ends.Add(m_idx, token.Tag);
123 }
123 }
124
124
125 public void BuildDFA(IDFATableBuilder<TTag> dfa) {
125 public void BuildDFA(IDFATableBuilder dfa) {
126 Safe.ArgumentNotNull(dfa,"dfa");
126 Safe.ArgumentNotNull(dfa,"dfa");
127
127
128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
@@ -165,7 +165,7 namespace Implab.Automaton.RegularExpres
165
165
166 queue.Enqueue(next);
166 queue.Enqueue(next);
167 }
167 }
168 dfa.DefineTransition(s1, s2, a);
168 dfa.Add(new AutomatonTransition(s1, s2, a));
169 }
169 }
170 }
170 }
171 }
171 }
@@ -1,8 +1,11
1 using System;
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
2
4
3 namespace Implab.Automaton.RegularExpressions {
5 namespace Implab.Automaton.RegularExpressions {
4 public class RegularDFADefinition<TInput, TTag> : DFATable {
6 public class RegularDFADefinition<TInput, TTag> : DFATable {
5
7
8 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
6 readonly IAlphabet<TInput> m_alphabet;
9 readonly IAlphabet<TInput> m_alphabet;
7
10
8 public RegularDFADefinition(IAlphabet<TInput> alphabet) {
11 public RegularDFADefinition(IAlphabet<TInput> alphabet) {
@@ -25,16 +28,39 namespace Implab.Automaton.RegularExpres
25 return base.ConstructTransitionTable();
28 return base.ConstructTransitionTable();
26 }
29 }
27
30
31 public void MarkFinalState(int s, TTag[] tags) {
32 MarkFinalState(s);
33 SetStateTag(s, tags);
34 }
35
36 public void SetStateTag(int s, TTag[] tags) {
37 Safe.ArgumentNotNull(tags, "tags");
38 m_tags[s] = tags;
39 }
40
41 public TTag[] GetStateTag(int s) {
42 TTag[] tags;
43 return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
44 }
45
28 /// <summary>
46 /// <summary>
29 /// Optimize the specified alphabet.
47 /// Optimize the specified alphabet.
30 /// </summary>
48 /// </summary>
31 /// <param name = "dfaTable"></param>
32 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
49 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
33 public void Optimize(IDFATableBuilder<TTag> dfaTable, IAlphabetBuilder<TInput> alphabet) {
50 public RegularDFADefinition<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
34 Safe.ArgumentNotNull(alphabet, "alphabet");
51 Safe.ArgumentNotNull(alphabet, "alphabet");
35 Safe.ArgumentNotNull(dfaTable, "dfaTable");
52
53 var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
54
55 var states = new DummyAlphabet(StateCount);
56 var map = new MapAlphabet<int>();
36
57
37 Optimize(dfaTable, InputAlphabet, alphabet, new DummyAlphabet(StateCount), new MapAlphabet<int>());
58 Optimize(dfaTable, InputAlphabet, alphabet, states, map);
59
60 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => map.Translate(x.Key), x => x.Value ))
61 dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
62
63 return dfaTable;
38 }
64 }
39
65
40
66
@@ -190,7 +190,6
190 <Compile Include="Automaton\IDFATable.cs" />
190 <Compile Include="Automaton\IDFATable.cs" />
191 <Compile Include="Automaton\IDFATableBuilder.cs" />
191 <Compile Include="Automaton\IDFATableBuilder.cs" />
192 <Compile Include="Automaton\DFATable.cs" />
192 <Compile Include="Automaton\DFATable.cs" />
193 <Compile Include="Automaton\RegularExpressions\IDFATable2.cs" />
194 </ItemGroup>
193 </ItemGroup>
195 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
194 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
196 <ItemGroup />
195 <ItemGroup />
1 NO CONTENT: file was removed
NO CONTENT: file was removed
General Comments 0
You need to be logged in to leave comments. Login now