annotate Implab/Automaton/RegularExpressions/RegularDFABuilder.cs @ 165:e227e78d72e4 ref20160224

DFA refactoring
author cin
date Mon, 29 Feb 2016 02:02:17 +0300
parents ec35731ae299
children 181119ef3b39
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
1 using Implab;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
2 using System;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
3 using System.Collections.Generic;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
4 using System.Diagnostics;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
5 using System.Linq;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
6
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
7 namespace Implab.Automaton.RegularExpressions {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
8 /// <summary>
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
9 /// Используется для построения ДКА по регулярному выражению, сначала обходит
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
10 /// регулярное выражение и вычисляет followpos, затем используется метод
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
11 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
12 /// </summary>
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
13 public class RegularDFABuilder<TTag> : IVisitor<TTag> {
165
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
14 int m_idx;
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
15 Token<TTag> m_root;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
16 HashSet<int> m_firstpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
17 HashSet<int> m_lastpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
18
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
19 readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
20 readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
21 readonly Dictionary<int, TTag> m_ends = new Dictionary<int, TTag>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
22
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
23 public Dictionary<int, HashSet<int>> FollowposMap {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
24 get { return m_followpos; }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
25 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
26
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
27 public HashSet<int> Followpos(int pos) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
28 HashSet<int> set;
165
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
29 return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
30 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
31
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
32 bool Nullable(object n) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
33 if (n is EmptyToken<TTag> || n is StarToken<TTag>)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
34 return true;
165
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
35 var altToken = n as AltToken<TTag>;
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
36 if (altToken != null)
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
37 return Nullable(altToken.Left) || Nullable(altToken.Right);
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
38 var catToken = n as CatToken<TTag>;
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
39 if (catToken != null)
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
40 return Nullable(catToken.Left) && Nullable(catToken.Right);
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
41 return false;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
42 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
43
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
44
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
45 public void Visit(AltToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
46 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
47 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
48 var firtspos = new HashSet<int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
49 var lastpos = new HashSet<int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
50
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
51 token.Left.Accept(this);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
52 firtspos.UnionWith(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
53 lastpos.UnionWith(m_lastpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
54
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
55 token.Right.Accept(this);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
56 firtspos.UnionWith(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
57 lastpos.UnionWith(m_lastpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
58
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
59 m_firstpos = firtspos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
60 m_lastpos = lastpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
61 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
62
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
63 public void Visit(StarToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
64 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
65 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
66 token.Token.Accept(this);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
67
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
68 foreach (var i in m_lastpos)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
69 Followpos(i).UnionWith(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
70 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
71
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
72 public void Visit(CatToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
73 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
74 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
75
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
76 var firtspos = new HashSet<int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
77 var lastpos = new HashSet<int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
78 token.Left.Accept(this);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
79 firtspos.UnionWith(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
80 var leftLastpos = m_lastpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
81
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
82 token.Right.Accept(this);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
83 lastpos.UnionWith(m_lastpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
84 var rightFirstpos = m_firstpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
85
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
86 if (Nullable(token.Left))
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
87 firtspos.UnionWith(rightFirstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
88
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
89 if (Nullable(token.Right))
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
90 lastpos.UnionWith(leftLastpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
91
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
92 m_firstpos = firtspos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
93 m_lastpos = lastpos;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
94
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
95 foreach (var i in leftLastpos)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
96 Followpos(i).UnionWith(rightFirstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
97
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
98 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
99
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
100 public void Visit(EmptyToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
101 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
102 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
103 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
104
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
105 public void Visit(SymbolToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
106 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
107 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
108 m_idx++;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
109 m_indexes[m_idx] = token.Value;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
110 m_firstpos = new HashSet<int>(new[] { m_idx });
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
111 m_lastpos = new HashSet<int>(new[] { m_idx });
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
112 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
113
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
114 public void Visit(EndToken<TTag> token) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
115 if (m_root == null)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
116 m_root = token;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
117 m_idx++;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
118 m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
119 m_firstpos = new HashSet<int>(new[] { m_idx });
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
120 m_lastpos = new HashSet<int>(new[] { m_idx });
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
121 Followpos(m_idx);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
122 m_ends.Add(m_idx, token.Tag);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
123 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
124
165
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
125 public void BuildDFA(IDFATableBuilder<TTag> dfa) {
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
126 Safe.ArgumentNotNull(dfa,"dfa");
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
127
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
129 (x, y) => x.SetEquals(y),
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
130 x => x.Sum(n => n.GetHashCode())
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
131 ));
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
132
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
133 var initialState = states.DefineSymbol(m_firstpos);
164
ec35731ae299 Almost complete DFA refactoring
cin
parents: 163
diff changeset
134 dfa.SetInitialState(initialState);
ec35731ae299 Almost complete DFA refactoring
cin
parents: 163
diff changeset
135
163
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
136 var tags = GetStateTags(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
137 if (tags != null && tags.Length > 0)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
138 dfa.MarkFinalState(initialState, tags);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
139
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
140 var inputMax = m_indexes.Values.Max();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
141 var queue = new Queue<HashSet<int>>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
142
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
143 queue.Enqueue(m_firstpos);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
144
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
145 while (queue.Count > 0) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
146 var state = queue.Dequeue();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
147 var s1 = states.Translate(state);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
148 Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
149
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
150 for (int a = 0; a <= inputMax; a++) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
151 var next = new HashSet<int>();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
152 foreach (var p in state) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
153 if (m_indexes[p] == a) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
154 next.UnionWith(Followpos(p));
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
155 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
156 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
157 if (next.Count > 0) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
158 int s2 = states.Translate(next);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
159 if (s2 == DFAConst.UNCLASSIFIED_INPUT) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
160 s2 = states.DefineSymbol(next);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
161
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
162 tags = GetStateTags(next);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
163 if (tags != null && tags.Length > 0)
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
164 dfa.MarkFinalState(s2, tags);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
165
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
166 queue.Enqueue(next);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
167 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
168 dfa.DefineTransition(s1, s2, a);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
169 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
170 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
171 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
172 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
173
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
174 TTag[] GetStateTags(IEnumerable<int> state) {
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
175 Debug.Assert(state != null);
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
176 return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray();
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
177 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
178
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
179 }
419aa51b04fd JSON moved to Formats namespace
cin
parents:
diff changeset
180 }