Mercurial > pub > ImplabNet

comparison Implab/Parsing/DFABuilder.cs @ 55:c0bf853aa04f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added initial JSON support +JSONParser +JSONWriter
author cin
date Sun, 15 Jun 2014 19:39:11 +0400
parents
children 97fbbf816844
comparison
equal deleted inserted replaced
51:2c332a9c64c0 55:c0bf853aa04f
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Diagnostics;
5 using System.Linq;
6 using System.Text;
7 using System.Threading.Tasks;
8
9 namespace Implab.Parsing {
10 /// <summary>
11 /// Используется для построения ДКА по регулярному выражению, сначала обходит
12 /// регулярное выражение и вычисляет followpos, затем используется метод
13 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
14 /// </summary>
15 public class DFABuilder : IVisitor {
16 int m_idx = 0;
17 Token m_root;
18 HashSet<int> m_firstpos;
19 HashSet<int> m_lastpos;
20
21 Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
22 Dictionary<int, int> m_indexes = new Dictionary<int, int>();
23 Dictionary<int, int> m_ends = new Dictionary<int, int>();
24
25 public Dictionary<int, HashSet<int>> FollowposMap {
26 get { return m_followpos; }
27 }
28
29 public HashSet<int> Followpos(int pos) {
30 HashSet<int> set;
31 if (m_followpos.TryGetValue(pos, out set))
32 return set;
33 return m_followpos[pos] = new HashSet<int>();
34 }
35
36 bool Nullable(object n) {
37 if (n is EmptyToken || n is StarToken)
38 return true;
39 if (n is AltToken)
40 return Nullable(((AltToken)n).Left) || Nullable(((AltToken)n).Right);
41 if (n is CatToken)
42 return Nullable(((CatToken)n).Left) && Nullable(((CatToken)n).Right);
43 return false;
44 }
45
46
47 public void Visit(AltToken token) {
48 if (m_root == null)
49 m_root = token;
50 var firtspos = new HashSet<int>();
51 var lastpos = new HashSet<int>();
52
53 token.Left.Accept(this);
54 firtspos.UnionWith(m_firstpos);
55 lastpos.UnionWith(m_lastpos);
56
57 token.Right.Accept(this);
58 firtspos.UnionWith(m_firstpos);
59 lastpos.UnionWith(m_lastpos);
60
61 m_firstpos = firtspos;
62 m_lastpos = lastpos;
63 }
64
65 public void Visit(StarToken token) {
66 if (m_root == null)
67 m_root = token;
68 token.Token.Accept(this);
69
70 foreach (var i in m_lastpos)
71 Followpos(i).UnionWith(m_firstpos);
72 }
73
74 public void Visit(CatToken token) {
75 if (m_root == null)
76 m_root = token;
77
78 var firtspos = new HashSet<int>();
79 var lastpos = new HashSet<int>();
80 token.Left.Accept(this);
81 firtspos.UnionWith(m_firstpos);
82 var leftLastpos = m_lastpos;
83
84 token.Right.Accept(this);
85 lastpos.UnionWith(m_lastpos);
86 var rightFirstpos = m_firstpos;
87
88 if (Nullable(token.Left))
89 firtspos.UnionWith(rightFirstpos);
90
91 if (Nullable(token.Right))
92 lastpos.UnionWith(leftLastpos);
93
94 m_firstpos = firtspos;
95 m_lastpos = lastpos;
96
97 foreach (var i in leftLastpos)
98 Followpos(i).UnionWith(rightFirstpos);
99
100 }
101
102 public void Visit(EmptyToken token) {
103 if (m_root == null)
104 m_root = token;
105 ;
106 }
107
108 public void Visit(SymbolToken token) {
109 if (m_root == null)
110 m_root = token;
111 m_idx++;
112 m_indexes[m_idx] = token.Value;
113 m_firstpos = new HashSet<int>(new[] { m_idx });
114 m_lastpos = new HashSet<int>(new[] { m_idx });
115 }
116
117 public void Visit(EndToken token) {
118 if (m_root == null)
119 m_root = token;
120 m_idx++;
121 m_indexes[m_idx] = Alphabet.UNCLASSIFIED;
122 m_firstpos = new HashSet<int>(new[] { m_idx });
123 m_lastpos = new HashSet<int>(new[] { m_idx });
124 Followpos(m_idx);
125 m_ends.Add(m_idx, token.Tag);
126 }
127
128 public void BuildDFA(IDFADefinition dfa) {
129 Safe.ArgumentNotNull(dfa,"dfa");
130
131 var stateMap = new Dictionary<HashSet<int>, int>(new CustomEqualityComparer<HashSet<int>>(
132 (x, y) => x.SetEquals(y),
133 (x) => x.Sum(n => n.GetHashCode())
134 ));
135
136 stateMap[m_firstpos] = DefineState( dfa, m_firstpos);
137 Debug.Assert(stateMap[m_firstpos] == DFADefinitionBase.INITIAL_STATE);
138
139 var queue = new Queue<HashSet<int>>();
140
141 queue.Enqueue(m_firstpos);
142
143 while (queue.Count > 0) {
144 var state = queue.Dequeue();
145 var s1 = stateMap[state];
146
147 for (int a = 0; a < dfa.AlphabetSize; a++) {
148 var next = new HashSet<int>();
149 foreach (var p in state) {
150 if (m_indexes[p] == a) {
151 next.UnionWith(Followpos(p));
152 }
153 }
154 if (next.Count > 0) {
155 int s2;
156 if (!stateMap.TryGetValue(next, out s2)) {
157 stateMap[next] = s2 = DefineState(dfa, next);
158 queue.Enqueue(next);
159 }
160 dfa.DefineTransition(s1, s2, a);
161 }
162 }
163
164 }
165 }
166
167 int[] GetStateTags(HashSet<int> state) {
168 Debug.Assert(state != null);
169 return state.Where(pos => m_ends.ContainsKey(pos)).Select(pos => m_ends[pos]).ToArray();
170 }
171
172 int DefineState(IDFADefinition automa, HashSet<int> state) {
173 Debug.Assert(automa != null);
174 Debug.Assert(state != null);
175
176 var tags = GetStateTags(state);
177
178 return tags.Length > 0 ? automa.AddState(tags) : automa.AddState();
179 }
180
181 }
182 }