##// END OF EJS Templates
DFA refactoring
cin -
r165:e227e78d72e4 ref20160224
parent child
Show More
@@ -0,0 +1,59
1 using System.Collections.Generic;
2
3
4 namespace Implab.Automaton {
5 /// <summary>
6 /// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
7 /// </summary>
8 /// <example>
9 /// class MyAutomaton {
10 /// int m_current;
11 /// readonly DFAStateDescriptor<string>[] m_automaton;
12 /// readonly IAlphabet<MyCommands> m_commands;
13 ///
14 /// public MyAutomaton(IDFADefinition&lt;MyCommands,MyStates,string&gt; definition) {
15 /// m_current = definition.StateAlphabet.Translate(MyStates.Initial);
16 /// m_automaton = definition.GetTransitionTable();
17 /// m_commands = definition.InputAlphabet;
18 /// }
19 ///
20 /// // defined a method which will move the automaton to the next state
21 /// public void Move(MyCommands cmd) {
22 /// // use transition map to determine the next state
23 /// var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
24 ///
25 /// // validate that we aren't in the unreachable state
26 /// if (next == DFAConst.UNREACHABLE_STATE)
27 /// throw new InvalidOperationException("The specified command is invalid");
28 ///
29 /// // if everything is ok
30 /// m_current = next;
31 /// }
32 /// }
33 /// </example>
34 public interface IDFATable {
35 /// <summary>
36 /// Таблица переходов состояний автомата
37 /// </summary>
38 /// <returns>The transition table.</returns>
39 DFAStateDescriptior[] GetTransitionTable();
40
41 int StateCount {
42 get;
43 }
44
45 int AlphabetSize {
46 get;
47 }
48
49 int InitialState {
50 get;
51 }
52
53 bool IsFinalState(int s);
54
55 IEnumerable<int> FinalStates {
56 get;
57 }
58 }
59 }
@@ -0,0 +1,24
1 using System;
2
3 namespace Implab.Automaton {
4 public interface IDFATableBuilder : IDFATable {
5 /// <summary>
6 /// Marks the state as final.
7 /// </summary>
8 /// <param name="state">State.</param>
9 void MarkFinalState(int state);
10
11 /// <summary>
12 /// Defines the transition from <paramref name="s1"/> to
13 /// <paramref name="s2"/> with input <paramref name="symbol"/>.
14 /// </summary>
15 /// <param name="s1">S1.</param>
16 /// <param name="s2">S2.</param>
17 /// <param name="symbol">Symbol.</param>
18 void DefineTransition(int s1, int s2, int symbol);
19
20 void SetInitialState(int s);
21
22 }
23 }
24
@@ -0,0 +1,17
1 using System;
2 using Implab.Automaton.RegularExpressions;
3
4 namespace Implab.Formats {
5 public class RegularCharDFADefinition<TTag> : RegularDFADefinition<char,TTag> {
6 readonly CharAlphabet m_alphabet;
7
8 public RegularCharDFADefinition(CharAlphabet alphabet) : base(alphabet) {
9 m_alphabet = alphabet;
10 }
11
12 public new CharAlphabet InputAlphabet {
13 get { return m_alphabet; }
14 }
15 }
16 }
17
@@ -1,7 +1,15
1 1 namespace Implab.Automaton {
2 public struct DFAStateDescriptior<TTag> {
3 public bool final;
4 public TTag[] tag;
5 public int[] transitions;
2 public struct DFAStateDescriptior {
3 public readonly bool final;
4 public readonly int[] transitions;
5
6
7 public DFAStateDescriptior(int[] transitions, bool final) {
8 this.transitions = transitions;
9 this.final = final;
10 }
11
12 public DFAStateDescriptior(int[] transitions) : this(transitions, false) {
13 }
6 14 }
7 15 }
@@ -1,251 +1,251
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 5
6 6 namespace Implab.Automaton {
7 public class DFATransitionTable<TTag> : IDFATransitionTableBuilder<TTag> {
8 DFAStateDescriptior<TTag>[] m_dfaTable;
7 public class DFATransitionTable<TTag> : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
9 9
10 10 int m_stateCount;
11 11 int m_symbolCount;
12 12 int m_initialState;
13 13
14 14 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
15 15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16 16
17 17
18 18 #region IDFADefinition implementation
19 19
20 public DFAStateDescriptior<TTag>[] GetTransitionTable() {
20 public DFAStateDescriptior[] GetTransitionTable() {
21 21 if (m_dfaTable == null) {
22 22 if (m_stateCount <= 0)
23 23 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
24 24 if (m_symbolCount <= 0)
25 25 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
26 26
27 27 m_dfaTable = ConstructTransitionTable();
28 28 }
29 29 return m_dfaTable;
30 30 }
31 31
32 32 public bool IsFinalState(int s) {
33 33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
34 34
35 35 return m_finalStates.ContainsKey(s);
36 36 }
37 37
38 38 public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
39 39 get {
40 40 return m_finalStates;
41 41 }
42 42 }
43 43
44 44 public int StateCount {
45 45 get { return m_stateCount; }
46 46 }
47 47
48 48 public int AlphabetSize {
49 49 get { return m_symbolCount; }
50 50 }
51 51
52 52 public int InitialState {
53 53 get { return m_initialState; }
54 54 }
55 55
56 56 #endregion
57 57
58 58 protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
59 59 var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
60 60
61 61 foreach (var pair in m_finalStates) {
62 62 var idx = pair.Key;
63 63
64 64 dfaTable[idx].final = true;
65 65 dfaTable[idx].tag = pair.Value;
66 66 }
67 67
68 68 foreach (var t in m_transitions) {
69 69 if (dfaTable[t.s1].transitions == null) {
70 70 dfaTable[t.s1].transitions = new int[m_symbolCount];
71 71 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
72 72 dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
73 73 }
74 74
75 75 dfaTable[t.s1].transitions[t.edge] = t.s2;
76 76 }
77 77 }
78 78
79 79 #region IDFADefinitionBuilder
80 80
81 81 public void DefineTransition(int s1, int s2, int symbol) {
82 82 if (m_dfaTable != null)
83 83 throw new InvalidOperationException("The transition table is already built");
84 84
85 85 Safe.ArgumentAssert(s1 > 0, "s1");
86 86 Safe.ArgumentAssert(s2 > 0, "s2");
87 87 Safe.ArgumentAssert(symbol >= 0, "symbol");
88 88
89 89 m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
90 90 m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
91 91
92 92 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
93 93 }
94 94
95 95 public void MarkFinalState(int state, params TTag[] tags) {
96 96 if (m_dfaTable != null)
97 97 throw new InvalidOperationException("The transition table is already built");
98 98
99 99 m_finalStates[state] = tags;
100 100 }
101 101
102 102 public void SetInitialState(int s) {
103 103 Safe.ArgumentAssert(s >= 0, "s");
104 104 m_initialState = s;
105 105 }
106 106
107 107
108 108 #endregion
109 109
110 110 protected void Optimize<TInput, TState>(
111 IDFATransitionTableBuilder<TTag> optimalDFA,
111 IDFATableBuilder<TTag> optimalDFA,
112 112 IAlphabet<TInput> inputAlphabet,
113 113 IAlphabetBuilder<TInput> optimalInputAlphabet,
114 114 IAlphabet<TState> stateAlphabet,
115 115 IAlphabetBuilder<TState> optimalStateAlphabet
116 116 ) {
117 117 Safe.ArgumentNotNull(optimalDFA, "dfa");
118 118 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
119 119 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
120 120 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
121 121 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
122 122
123 123 if (inputAlphabet.Count != m_symbolCount)
124 124 throw new InvalidOperationException("The input symbols aphabet mismatch");
125 125 if (stateAlphabet.Count != m_stateCount)
126 126 throw new InvalidOperationException("The states alphabet mismatch");
127 127
128 128 var setComparer = new CustomEqualityComparer<HashSet<int>>(
129 129 (x, y) => x.SetEquals(y),
130 130 s => s.Sum(x => x.GetHashCode())
131 131 );
132 132
133 133 var arrayComparer = new CustomEqualityComparer<TTag[]>(
134 134 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
135 135 a => a.Sum(x => x.GetHashCode())
136 136 );
137 137
138 138 var optimalStates = new HashSet<HashSet<int>>(setComparer);
139 139 var queue = new HashSet<HashSet<int>>(setComparer);
140 140
141 141 // получаем конечные состояния, сгруппированные по маркерам
142 142 optimalStates.UnionWith(
143 143 m_finalStates
144 144 .GroupBy(pair => pair.Value, arrayComparer)
145 145 .Select(
146 146 g => new HashSet<int>(
147 147 g.Select( pair => pair.Key)
148 148 )
149 149 )
150 150 );
151 151
152 152 var state = new HashSet<int>(
153 153 Enumerable
154 154 .Range(0, m_stateCount - 1)
155 155 .Where(i => !m_finalStates.ContainsKey(i))
156 156 );
157 157 optimalStates.Add(state);
158 158 queue.Add(state);
159 159
160 160 var rmap = m_transitions
161 161 .GroupBy(t => t.s2)
162 162 .ToLookup(
163 163 g => g.Key, // s2
164 164 g => g.ToLookup(t => t.edge, t => t.s1)
165 165 );
166 166
167 167 while (queue.Count > 0) {
168 168 var stateA = queue.First();
169 169 queue.Remove(stateA);
170 170
171 171 for (int c = 0; c < m_symbolCount; c++) {
172 172 var stateX = new HashSet<int>();
173 173 foreach(var a in stateA)
174 174 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
175 175
176 176 foreach (var stateY in optimalStates.ToArray()) {
177 177 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
178 178 var stateR1 = new HashSet<int>(stateY);
179 179 var stateR2 = new HashSet<int>(stateY);
180 180
181 181 stateR1.IntersectWith(stateX);
182 182 stateR2.ExceptWith(stateX);
183 183
184 184 optimalStates.Remove(stateY);
185 185 optimalStates.Add(stateR1);
186 186 optimalStates.Add(stateR2);
187 187
188 188 if (queue.Contains(stateY)) {
189 189 queue.Remove(stateY);
190 190 queue.Add(stateR1);
191 191 queue.Add(stateR2);
192 192 } else {
193 193 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
194 194 }
195 195 }
196 196 }
197 197 }
198 198 }
199 199
200 200 // карта получения оптимального состояния по соотвествующему ему простому состоянию
201 201 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
202 202
203 203 // получаем минимальный алфавит
204 204 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
205 205 var optimalAlphabet = m_transitions
206 206 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
207 207
208 208 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
209 209
210 210 var optimalTags = m_finalStates
211 211 .GroupBy(pair => statesMap[pair.Key])
212 212 .ToDictionary(
213 213 g => g.Key,
214 214 g => g.SelectMany(pair => pair.Value).ToArray()
215 215 );
216 216
217 217 // построение автомата
218 218 optimalDFA.SetInitialState(statesMap[m_initialState]);
219 219
220 220 foreach (var pair in optimalTags)
221 221 optimalDFA.MarkFinalState(pair.Key, pair.Value);
222 222
223 223 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
224 224 optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
225 225
226 226 }
227 227
228 228 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
229 229 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
230 230 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
231 231
232 232 var inputMap = inputAlphabet.CreateReverseMap();
233 233 var stateMap = stateAlphabet.CreateReverseMap();
234 234
235 235 for (int i = 0; i < inputMap.Length; i++)
236 236 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
237 237
238 238
239 239 foreach(var t in m_transitions)
240 240 Console.WriteLine(
241 241 "[{0}] -{{{1}}}-> [{2}]{3}",
242 242 stateMap[t.s1],
243 243 String.Join(",", inputMap[t.edge]),
244 244 stateMap[t.s2],
245 245 m_finalStates.ContainsKey(t.s2) ? "$" : ""
246 246 );
247 247
248 248 }
249 249
250 250 }
251 251 }
@@ -1,95 +1,91
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 using System.Text;
6 using System.Threading.Tasks;
7 5
8 6 namespace Implab.Automaton.RegularExpressions {
9 7 /// <summary>
10 8 /// Базовый абстрактный класс. Грамматика, позволяет формулировать выражения над алфавитом типа <c>char</c>.
11 9 /// </summary>
12 public abstract class Grammar<TSymbol, TTag> {
10 public abstract class Grammar<TSymbol, TTag> {
13 11
14 public abstract IAlphabetBuilder<TSymbol> Alphabet {
12 protected abstract IAlphabetBuilder<TSymbol> AlphabetBuilder {
15 13 get;
16 14 }
17 15
18 public SymbolToken<TTag> UnclassifiedToken() {
16 protected SymbolToken<TTag> UnclassifiedToken() {
19 17 return new SymbolToken<TTag>(DFAConst.UNCLASSIFIED_INPUT);
20 18 }
21 19
22 public void DefineAlphabet(IEnumerable<TSymbol> alphabet) {
20 protected void DefineAlphabet(IEnumerable<TSymbol> alphabet) {
23 21 Safe.ArgumentNotNull(alphabet, "alphabet");
24 22
25 23 foreach (var ch in alphabet)
26 Alphabet.DefineSymbol(ch);
24 AlphabetBuilder.DefineSymbol(ch);
27 25 }
28 26
29 public Token<TTag> SymbolToken(TSymbol symbol) {
27 protected Token<TTag> SymbolToken(TSymbol symbol) {
30 28 return Token<TTag>.New(TranslateOrAdd(symbol));
31 29 }
32 30
33 public Token<TTag> SymbolToken(IEnumerable<TSymbol> symbols) {
31 protected Token<TTag> SymbolToken(IEnumerable<TSymbol> symbols) {
34 32 Safe.ArgumentNotNull(symbols, "symbols");
35 33
36 34 return Token<TTag>.New(TranslateOrAdd(symbols).ToArray());
37 35 }
38 36
39 public Token<TTag> SymbolSetToken(params TSymbol[] set) {
37 protected Token<TTag> SymbolSetToken(params TSymbol[] set) {
40 38 return SymbolToken(set);
41 39 }
42 40
43 41 int TranslateOrAdd(TSymbol ch) {
44 var t = Alphabet.Translate(ch);
42 var t = AlphabetBuilder.Translate(ch);
45 43 if (t == DFAConst.UNCLASSIFIED_INPUT)
46 t = Alphabet.DefineSymbol(ch);
44 t = AlphabetBuilder.DefineSymbol(ch);
47 45 return t;
48 46 }
49 47
50 48 IEnumerable<int> TranslateOrAdd(IEnumerable<TSymbol> symbols) {
51 49 return symbols.Distinct().Select(TranslateOrAdd);
52 50 }
53 51
54 52 int TranslateOrDie(TSymbol ch) {
55 var t = Alphabet.Translate(ch);
53 var t = AlphabetBuilder.Translate(ch);
56 54 if (t == DFAConst.UNCLASSIFIED_INPUT)
57 55 throw new ApplicationException(String.Format("Symbol '{0}' is UNCLASSIFIED", ch));
58 56 return t;
59 57 }
60 58
61 59 IEnumerable<int> TranslateOrDie(IEnumerable<TSymbol> symbols) {
62 60 return symbols.Distinct().Select(TranslateOrDie);
63 61 }
64 62
65 public Token<TTag> SymbolTokenExcept(IEnumerable<TSymbol> symbols) {
63 protected Token<TTag> SymbolTokenExcept(IEnumerable<TSymbol> symbols) {
66 64 Safe.ArgumentNotNull(symbols, "symbols");
67 65
68 return Token<TTag>.New( Enumerable.Range(0, Alphabet.Count).Except(TranslateOrDie(symbols)).ToArray() );
66 return Token<TTag>.New( Enumerable.Range(0, AlphabetBuilder.Count).Except(TranslateOrDie(symbols)).ToArray() );
69 67 }
70 68
71 protected CDFADefinition BuildDFA(Token<TTag> lang) {
69 protected void BuildDFA(Token<TTag> lang, IDFATableBuilder<TTag> dfaTable, IAlphabetBuilder<TSymbol> dfaAlphabet) {
72 70 Safe.ArgumentNotNull(lang, "lang");
71 Safe.ArgumentNotNull(dfaAlphabet, "dfaAlphabet");
73 72
74 var dfa = new RegularDFADefinition<TSymbol, TTag>(Alphabet, 0);
75
76 var table = new DFATransitionTable<TTag>();
73 var dfa = new RegularDFADefinition<TSymbol, TTag>(AlphabetBuilder);
77 74
78 75 var builder = new RegularDFABuilder<TTag>();
79 76
80 77 lang.Accept( builder );
81 78
82 var initialState = builder.BuildDFA(table);
83 if (table.IsFinalState(initialState))
79 builder.BuildDFA(dfa);
80
81 if (dfa.IsFinalState(dfa.InitialState))
84 82 throw new ApplicationException("The specified language contains empty token");
85 83
86 return dfa.Optimize();
84 dfa.Optimize(dfaTable, dfaAlphabet);
85
87 86 }
88 87
89
90
91 //protected abstract TGrammar CreateInstance();
92 88 }
93 89
94 90
95 91 }
@@ -1,180 +1,180
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Diagnostics;
5 5 using System.Linq;
6 6
7 7 namespace Implab.Automaton.RegularExpressions {
8 8 /// <summary>
9 9 /// Используется для построения ДКА по регулярному выражению, сначала обходит
10 10 /// регулярное выражение и вычисляет followpos, затем используется метод
11 11 /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
12 12 /// </summary>
13 13 public class RegularDFABuilder<TTag> : IVisitor<TTag> {
14 int m_idx = 0;
14 int m_idx;
15 15 Token<TTag> m_root;
16 16 HashSet<int> m_firstpos;
17 17 HashSet<int> m_lastpos;
18 18
19 19 readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
20 20 readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
21 21 readonly Dictionary<int, TTag> m_ends = new Dictionary<int, TTag>();
22 22
23 23 public Dictionary<int, HashSet<int>> FollowposMap {
24 24 get { return m_followpos; }
25 25 }
26 26
27 27 public HashSet<int> Followpos(int pos) {
28 28 HashSet<int> set;
29 if (m_followpos.TryGetValue(pos, out set))
30 return set;
31 return m_followpos[pos] = new HashSet<int>();
29 return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
32 30 }
33 31
34 32 bool Nullable(object n) {
35 33 if (n is EmptyToken<TTag> || n is StarToken<TTag>)
36 34 return true;
37 if (n is AltToken<TTag>)
38 return Nullable(((AltToken<TTag>)n).Left) || Nullable(((AltToken<TTag>)n).Right);
39 if (n is CatToken<TTag>)
40 return Nullable(((CatToken<TTag>)n).Left) && Nullable(((CatToken<TTag>)n).Right);
35 var altToken = n as AltToken<TTag>;
36 if (altToken != null)
37 return Nullable(altToken.Left) || Nullable(altToken.Right);
38 var catToken = n as CatToken<TTag>;
39 if (catToken != null)
40 return Nullable(catToken.Left) && Nullable(catToken.Right);
41 41 return false;
42 42 }
43 43
44 44
45 45 public void Visit(AltToken<TTag> token) {
46 46 if (m_root == null)
47 47 m_root = token;
48 48 var firtspos = new HashSet<int>();
49 49 var lastpos = new HashSet<int>();
50 50
51 51 token.Left.Accept(this);
52 52 firtspos.UnionWith(m_firstpos);
53 53 lastpos.UnionWith(m_lastpos);
54 54
55 55 token.Right.Accept(this);
56 56 firtspos.UnionWith(m_firstpos);
57 57 lastpos.UnionWith(m_lastpos);
58 58
59 59 m_firstpos = firtspos;
60 60 m_lastpos = lastpos;
61 61 }
62 62
63 63 public void Visit(StarToken<TTag> token) {
64 64 if (m_root == null)
65 65 m_root = token;
66 66 token.Token.Accept(this);
67 67
68 68 foreach (var i in m_lastpos)
69 69 Followpos(i).UnionWith(m_firstpos);
70 70 }
71 71
72 72 public void Visit(CatToken<TTag> token) {
73 73 if (m_root == null)
74 74 m_root = token;
75 75
76 76 var firtspos = new HashSet<int>();
77 77 var lastpos = new HashSet<int>();
78 78 token.Left.Accept(this);
79 79 firtspos.UnionWith(m_firstpos);
80 80 var leftLastpos = m_lastpos;
81 81
82 82 token.Right.Accept(this);
83 83 lastpos.UnionWith(m_lastpos);
84 84 var rightFirstpos = m_firstpos;
85 85
86 86 if (Nullable(token.Left))
87 87 firtspos.UnionWith(rightFirstpos);
88 88
89 89 if (Nullable(token.Right))
90 90 lastpos.UnionWith(leftLastpos);
91 91
92 92 m_firstpos = firtspos;
93 93 m_lastpos = lastpos;
94 94
95 95 foreach (var i in leftLastpos)
96 96 Followpos(i).UnionWith(rightFirstpos);
97 97
98 98 }
99 99
100 100 public void Visit(EmptyToken<TTag> token) {
101 101 if (m_root == null)
102 102 m_root = token;
103 103 }
104 104
105 105 public void Visit(SymbolToken<TTag> token) {
106 106 if (m_root == null)
107 107 m_root = token;
108 108 m_idx++;
109 109 m_indexes[m_idx] = token.Value;
110 110 m_firstpos = new HashSet<int>(new[] { m_idx });
111 111 m_lastpos = new HashSet<int>(new[] { m_idx });
112 112 }
113 113
114 114 public void Visit(EndToken<TTag> token) {
115 115 if (m_root == null)
116 116 m_root = token;
117 117 m_idx++;
118 118 m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
119 119 m_firstpos = new HashSet<int>(new[] { m_idx });
120 120 m_lastpos = new HashSet<int>(new[] { m_idx });
121 121 Followpos(m_idx);
122 122 m_ends.Add(m_idx, token.Tag);
123 123 }
124 124
125 public void BuildDFA(IDFATransitionTableBuilder<TTag> dfa) {
125 public void BuildDFA(IDFATableBuilder<TTag> dfa) {
126 126 Safe.ArgumentNotNull(dfa,"dfa");
127 127
128 128 var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
129 129 (x, y) => x.SetEquals(y),
130 130 x => x.Sum(n => n.GetHashCode())
131 131 ));
132 132
133 133 var initialState = states.DefineSymbol(m_firstpos);
134 134 dfa.SetInitialState(initialState);
135 135
136 136 var tags = GetStateTags(m_firstpos);
137 137 if (tags != null && tags.Length > 0)
138 138 dfa.MarkFinalState(initialState, tags);
139 139
140 140 var inputMax = m_indexes.Values.Max();
141 141 var queue = new Queue<HashSet<int>>();
142 142
143 143 queue.Enqueue(m_firstpos);
144 144
145 145 while (queue.Count > 0) {
146 146 var state = queue.Dequeue();
147 147 var s1 = states.Translate(state);
148 148 Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);
149 149
150 150 for (int a = 0; a <= inputMax; a++) {
151 151 var next = new HashSet<int>();
152 152 foreach (var p in state) {
153 153 if (m_indexes[p] == a) {
154 154 next.UnionWith(Followpos(p));
155 155 }
156 156 }
157 157 if (next.Count > 0) {
158 158 int s2 = states.Translate(next);
159 159 if (s2 == DFAConst.UNCLASSIFIED_INPUT) {
160 160 s2 = states.DefineSymbol(next);
161 161
162 162 tags = GetStateTags(next);
163 163 if (tags != null && tags.Length > 0)
164 164 dfa.MarkFinalState(s2, tags);
165 165
166 166 queue.Enqueue(next);
167 167 }
168 168 dfa.DefineTransition(s1, s2, a);
169 169 }
170 170 }
171 171 }
172 172 }
173 173
174 174 TTag[] GetStateTags(IEnumerable<int> state) {
175 175 Debug.Assert(state != null);
176 176 return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray();
177 177 }
178 178
179 179 }
180 180 }
@@ -1,46 +1,43
1 1 using System;
2 2
3 3 namespace Implab.Automaton.RegularExpressions {
4 4 public class RegularDFADefinition<TInput, TTag> : DFATransitionTable<TTag>, IDFATransitionTable<TTag> {
5 5
6 6 readonly IAlphabet<TInput> m_alphabet;
7 readonly int m_initialState;
8 7
9 public RegularDFADefinition(IAlphabet<TInput> alphabet, int initialState) {
8 public RegularDFADefinition(IAlphabet<TInput> alphabet) {
10 9 Safe.ArgumentNotNull(alphabet, "aplhabet");
11 10
12 11 m_alphabet = alphabet;
13 m_initialState = initialState;
14 12 }
15 13
16 14
17 15 public IAlphabet<TInput> InputAlphabet {
18 16 get {
19 17 return m_alphabet;
20 18 }
21 19 }
22 20
23 21 protected override DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
24 22 if (InputAlphabet.Count != m_alphabet.Count)
25 23 throw new InvalidOperationException("The alphabet doesn't match the transition table");
26 24
27 25 return base.ConstructTransitionTable();
28 26 }
29 27
30 28 /// <summary>
31 29 /// Optimize the specified alphabet.
32 30 /// </summary>
31 /// <param name = "dfaTable"></param>
33 32 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
34 public RegularDFADefinition<TInput, TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
33 public void Optimize(IDFATableBuilder<TTag> dfaTable, IAlphabetBuilder<TInput> alphabet) {
35 34 Safe.ArgumentNotNull(alphabet, "alphabet");
35 Safe.ArgumentNotNull(dfaTable, "dfaTable");
36 36
37 var optimalDFA = new RegularDFADefinition<TInput,TTag>(alphabet, m_initialState);
38
39 Optimize(optimalDFA, InputAlphabet, alphabet, new DummyAlphabet(StateCount), new MapAlphabet<int>());
40
37 Optimize(dfaTable, InputAlphabet, alphabet, new DummyAlphabet(StateCount), new MapAlphabet<int>());
41 38 }
42 39
43 40
44 41 }
45 42 }
46 43
@@ -1,63 +1,63
1 1 using Implab;
2 2 using System;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton.RegularExpressions {
6 6 public abstract class Token<TTag> {
7 7 public abstract void Accept(IVisitor<TTag> visitor);
8 8
9 9 public Token<TTag> Extend() {
10 10 return Cat(new EndToken<TTag>());
11 11 }
12 12
13 public Token<TTag> Tag<T>(T tag) where T : IConvertible {
13 public Token<TTag> Tag(TTag tag) {
14 14 return Cat(new EndToken<TTag>(tag));
15 15 }
16 16
17 17 public Token<TTag> Cat(Token<TTag> right) {
18 18 return new CatToken<TTag>(this, right);
19 19 }
20 20
21 21 public Token<TTag> Or(Token<TTag> right) {
22 22 return new AltToken<TTag>(this, right);
23 23 }
24 24
25 25 public Token<TTag> Optional() {
26 26 return Or(new EmptyToken<TTag>());
27 27 }
28 28
29 29 public Token<TTag> EClosure() {
30 30 return new StarToken<TTag>(this);
31 31 }
32 32
33 33 public Token<TTag> Closure() {
34 34 return Cat(new StarToken<TTag>(this));
35 35 }
36 36
37 37 public Token<TTag> Repeat(int count) {
38 38 Token<TTag> token = null;
39 39
40 40 for (int i = 0; i < count; i++)
41 41 token = token != null ? token.Cat(this) : this;
42 42 return token ?? new EmptyToken<TTag>();
43 43 }
44 44
45 45 public Token<TTag> Repeat(int min, int max) {
46 46 if (min > max || min < 1)
47 47 throw new ArgumentOutOfRangeException();
48 48 var token = Repeat(min);
49 49
50 50 for (int i = min; i < max; i++)
51 token = token.Cat( this.Optional() );
51 token = token.Cat( Optional() );
52 52 return token;
53 53 }
54 54
55 public static Token<TTag> New<T>(params T[] set) where T : struct, IConvertible {
55 public static Token<TTag> New(params int[] set) {
56 56 Safe.ArgumentNotNull(set, "set");
57 57 Token<TTag> token = null;
58 58 foreach(var c in set.Distinct())
59 59 token = token == null ? new SymbolToken<TTag>(c) : token.Or(new SymbolToken<TTag>(c));
60 60 return token;
61 61 }
62 62 }
63 63 }
@@ -1,265 +1,265
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.IO;
5 5 using Implab.Components;
6 6
7 7 namespace Implab.Automaton {
8 8 /// <summary>
9 9 /// Базовый класс для разбора потока входных символов на токены.
10 10 /// </summary>
11 11 /// <remarks>
12 12 /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два
13 13 /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения
14 14 /// конца токена и допустимости текущего символа.
15 15 /// </remarks>
16 16 public abstract class Scanner<TTag> : Disposable {
17 17 struct ScannerConfig {
18 18 public DFAStateDescriptior<TTag>[] states;
19 19 public int[] alphabetMap;
20 20 public int initialState;
21 21 }
22 22
23 23 Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>();
24 24
25 25 DFAStateDescriptior<TTag>[] m_states;
26 26 int[] m_alphabetMap;
27 27 int m_initialState;
28 28
29 29 protected DFAStateDescriptior<TTag> m_currentState;
30 30 int m_previewCode;
31 31
32 protected int m_tokenLen = 0;
32 protected int m_tokenLen;
33 33 protected int m_tokenOffset;
34 34
35 35 protected char[] m_buffer;
36 36 protected int m_bufferSize;
37 37 protected int m_pointer;
38 38
39 39 TextReader m_reader;
40 40 bool m_disposeReader;
41 41 int m_chunkSize = 1024; // 1k
42 42 int m_limit = 10 * 1024 * 1024; // 10Mb
43 43
44 44 protected Scanner(DFAStateDescriptior<TTag>[] states, int[] alphabet, int initialState) {
45 45 Safe.ArgumentNotEmpty(states, "states");
46 46 Safe.ArgumentNotNull(alphabet, "alphabet");
47 47
48 48 m_states = states;
49 49 m_alphabetMap = alphabet;
50 50 m_initialState = initialState;
51 51
52 52 Feed(new char[0]);
53 53 }
54 54
55 55 /// <summary>
56 56 /// Заполняет входными данными буффер.
57 57 /// </summary>
58 58 /// <param name="data">Данные для обработки.</param>
59 59 /// <remarks>Копирование данных не происходит, переданный массив используется в
60 60 /// качестве входного буффера.</remarks>
61 61 public void Feed(char[] data) {
62 62 Safe.ArgumentNotNull(data, "data");
63 63
64 64 Feed(data, data.Length);
65 65 }
66 66
67 67 /// <summary>
68 68 /// Заполняет буффур чтения входными данными.
69 69 /// </summary>
70 70 /// <param name="data">Данные для обработки.</param>
71 71 /// <param name="length">Длина данных для обработки.</param>
72 72 /// <remarks>Копирование данных не происходит, переданный массив используется в
73 73 /// качестве входного буффера.</remarks>
74 74 public void Feed(char[] data, int length) {
75 75 Safe.ArgumentNotNull(data, "data");
76 76 Safe.ArgumentInRange(length, 0, data.Length, "length");
77 77 AssertNotDisposed();
78 78
79 79 m_pointer = -1;
80 80 m_buffer = data;
81 81 m_bufferSize = length;
82 82 Shift();
83 83 }
84 84
85 85 public void Feed(TextReader reader, bool dispose) {
86 86 Safe.ArgumentNotNull(reader, "reader");
87 87 AssertNotDisposed();
88 88
89 89 if (m_reader != null && m_disposeReader)
90 90 m_reader.Dispose();
91 91
92 92 m_reader = reader;
93 93 m_disposeReader = dispose;
94 94 m_pointer = -1;
95 95 m_buffer = new char[m_chunkSize];
96 96 m_bufferSize = 0;
97 97 Shift();
98 98 }
99 99
100 100 /// <summary>
101 101 /// Получает текущий токен в виде строки.
102 102 /// </summary>
103 103 /// <returns></returns>
104 104 protected string GetTokenValue() {
105 105 return new String(m_buffer, m_tokenOffset, m_tokenLen);
106 106 }
107 107
108 108 /// <summary>
109 109 /// Метки текущего токена, которые были назначены в регулярном выражении.
110 110 /// </summary>
111 111 protected TTag[] TokenTags {
112 112 get {
113 113 return m_currentState.tag;
114 114 }
115 115 }
116 116
117 117 /// <summary>
118 118 /// Признак конца данных
119 119 /// </summary>
120 120 public bool EOF {
121 121 get {
122 122 return m_pointer >= m_bufferSize;
123 123 }
124 124 }
125 125
126 126 /// <summary>
127 127 /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена,
128 128 /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в
129 129 /// котором находится токен.
130 130 /// </summary>
131 131 /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns>
132 132 protected bool ReadTokenInternal() {
133 133 if (m_pointer >= m_bufferSize)
134 134 return false;
135 135
136 136 m_currentState = m_states[m_initialState];
137 137 m_tokenLen = 0;
138 138 m_tokenOffset = m_pointer;
139 139 int nextState;
140 140 do {
141 141 nextState = m_currentState.transitions[m_previewCode];
142 142 if (nextState == DFAConst.UNREACHABLE_STATE) {
143 143 if (m_currentState.final)
144 144 return true;
145 else
146 throw new ParserException(
147 String.Format(
148 "Unexpected symbol '{0}', at pos {1}",
149 m_buffer[m_pointer],
150 Position
151 )
152 );
153 } else {
154 m_currentState = m_states[nextState];
155 m_tokenLen++;
145
146 throw new ParserException(
147 String.Format(
148 "Unexpected symbol '{0}', at pos {1}",
149 m_buffer[m_pointer],
150 Position
151 )
152 );
156 153 }
154 m_currentState = m_states[nextState];
155 m_tokenLen++;
157 156
158 157 } while (Shift());
159 158
160 159 // END OF DATA
161 160 if (!m_currentState.final)
162 161 throw new ParserException("Unexpected end of data");
163 162
164 163 return true;
165 164 }
166 165
167 166
168 167 bool Shift() {
169 168 m_pointer++;
170 169
171 170 if (m_pointer >= m_bufferSize) {
172 171 if (!ReadNextChunk())
173 172 return false;
174 173 }
175 174
176 175 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
177 176
178 177 return true;
179 178 }
180 179
181 180 bool ReadNextChunk() {
182 181 if (m_reader == null)
183 182 return false;
184 183
185 184 // extend buffer if nesessary
186 185 if (m_pointer + m_chunkSize > m_buffer.Length) {
187 186 // trim unused buffer head
188 187 var size = m_tokenLen + m_chunkSize;
189 188 if (size >= m_limit)
190 189 throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit));
191 190 var temp = new char[size];
192 191 Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen);
193 192 m_pointer -= m_tokenOffset;
194 193 m_bufferSize -= m_tokenOffset;
195 194 m_tokenOffset = 0;
196 195 m_buffer = temp;
197 196 }
198 197
199 198 var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize);
200 199 if (read == 0)
201 200 return false;
202 201
203 202 m_bufferSize += read;
204 203
205 204 return true;
206 205 }
207 206
208 207 /// <summary>
209 208 /// Позиция сканнера во входном буфере
210 209 /// </summary>
211 210 public int Position {
212 211 get {
213 212 return m_pointer + 1;
214 213 }
215 214 }
216 215
217 216 /// <summary>
218 217 /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей
219 218 /// группировки.
220 219 /// </summary>
221 220 /// <param name="states">Таблица состояний нового ДКА</param>
222 221 /// <param name="alphabet">Таблица входных символов для нового ДКА</param>
222 /// <param name = "initialState"></param>
223 223 protected void Switch(DFAStateDescriptior<TTag>[] states, int[] alphabet, int initialState) {
224 224 Safe.ArgumentNotNull(states, "dfa");
225 225
226 226 m_defs.Push(new ScannerConfig {
227 227 states = m_states,
228 228 alphabetMap = m_alphabetMap,
229 229 initialState = m_initialState
230 230 });
231 231
232 232 m_states = states;
233 233 m_alphabetMap = alphabet;
234 234 m_initialState = initialState;
235 235
236 236 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
237 237 }
238 238
239 239 /// <summary>
240 240 /// Восстанавливает предыдущей ДКА сканнера.
241 241 /// </summary>
242 242 protected void Restore() {
243 243 if (m_defs.Count == 0)
244 244 throw new InvalidOperationException();
245 245 var prev = m_defs.Pop();
246 246 m_states = prev.states;
247 247 m_alphabetMap = prev.alphabetMap;
248 248 m_initialState = prev.initialState;
249 249 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
250 250 }
251 251
252 252 protected override void Dispose(bool disposing) {
253 253 if (disposing) {
254 254 if (m_reader != null && m_disposeReader)
255 255 m_reader.Dispose();
256 256 m_buffer = null;
257 257 m_bufferSize = 0;
258 258 m_pointer = 0;
259 259 m_tokenLen = 0;
260 260 m_tokenOffset = 0;
261 261 }
262 262 base.Dispose(disposing);
263 263 }
264 264 }
265 265 }
@@ -1,25 +1,25
1 using System;
2 using System.Collections.Generic;
1 using System.Collections.Generic;
3 2 using System.Linq;
3 using Implab.Automaton;
4 4
5 namespace Implab.Automaton {
5 namespace Implab.Formats {
6 6 public class ByteAlphabet : IndexedAlphabetBase<byte> {
7 7 public ByteAlphabet() : base(byte.MaxValue + 1){
8 8 }
9 9
10 10 #region implemented abstract members of IndexedAlphabetBase
11 11
12 12 public override int GetSymbolIndex(byte symbol) {
13 13 return (int)symbol;
14 14 }
15 15
16 16 public IEnumerable<byte> InputSymbols {
17 17 get {
18 18 return Enumerable.Range(byte.MinValue, byte.MaxValue).Cast<byte>();
19 19 }
20 20 }
21 21
22 22 #endregion
23 23 }
24 24 }
25 25
@@ -1,23 +1,20
1 using Implab;
2 using System;
3 using System.Collections.Generic;
1 using System.Collections.Generic;
4 2 using System.Linq;
5 using System.Text;
6 using System.Threading.Tasks;
3 using Implab.Automaton;
7 4
8 namespace Implab.Automaton {
5 namespace Implab.Formats {
9 6 public class CharAlphabet: IndexedAlphabetBase<char> {
10 7
11 8 public CharAlphabet()
12 9 : base(char.MaxValue + 1) {
13 10 }
14 11
15 12 public override int GetSymbolIndex(char symbol) {
16 13 return symbol;
17 14 }
18 15
19 16 public override IEnumerable<char> InputSymbols {
20 17 get { return Enumerable.Range(char.MinValue, char.MaxValue).Cast<char>(); }
21 18 }
22 19 }
23 20 }
@@ -1,17 +1,11
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace Implab.JSON {
1 namespace Implab.Formats.JSON {
8 2 /// <summary>
9 3 /// internal
10 4 /// </summary>
11 public enum JSONElementContext {
5 enum JSONElementContext {
12 6 None,
13 7 Object,
14 8 Array,
15 9 Closed
16 10 }
17 11 }
@@ -1,34 +1,28
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace Implab.JSON {
1 namespace Implab.Formats.JSON {
8 2 /// <summary>
9 3 /// Тип элемента на котором находится парсер
10 4 /// </summary>
11 5 public enum JSONElementType {
12 6 None,
13 7 /// <summary>
14 8 /// Начало объекта
15 9 /// </summary>
16 10 BeginObject,
17 11 /// <summary>
18 12 /// Конец объекта
19 13 /// </summary>
20 14 EndObject,
21 15 /// <summary>
22 16 /// Начало массива
23 17 /// </summary>
24 18 BeginArray,
25 19 /// <summary>
26 20 /// Конец массива
27 21 /// </summary>
28 22 EndArray,
29 23 /// <summary>
30 24 /// Простое значение
31 25 /// </summary>
32 26 Value
33 27 }
34 28 }
@@ -1,99 +1,115
1 1 using System.Linq;
2 2 using Implab.Automaton.RegularExpressions;
3 using System;
3 4
4 5 namespace Implab.Formats.JSON {
5 class JSONGrammar : Grammar<JSONGrammar> {
6 class JSONGrammar : Grammar<char,JSONGrammar.TokenType> {
6 7 public enum TokenType {
7 8 None,
8 9 BeginObject,
9 10 EndObject,
10 11 BeginArray,
11 12 EndArray,
12 13 String,
13 14 Number,
14 15 Literal,
15 16 NameSeparator,
16 17 ValueSeparator,
17 18
18 19 StringBound,
19 20 EscapedChar,
20 21 UnescapedChar,
21 22 EscapedUnicode,
22 23
23 24 Minus,
24 25 Plus,
25 26 Sign,
26 27 Integer,
27 28 Dot,
28 29 Exp
29 30 }
30 31
31 readonly CDFADefinition m_jsonDFA;
32 readonly CDFADefinition m_stringDFA;
32 static Lazy<JSONGrammar> _instance = new Lazy<JSONGrammar>();
33
34 public static JSONGrammar Instance {
35 get { return _instance.Value; }
36 }
37
38 readonly RegularCharDFADefinition<TokenType> m_jsonDFA;
39 readonly RegularCharDFADefinition<TokenType> m_stringDFA;
33 40
34 41 public JSONGrammar() {
35 42 DefineAlphabet(Enumerable.Range(0, 0x20).Select(x => (char)x));
36 43 var hexDigit = SymbolRangeToken('a','f').Or(SymbolRangeToken('A','F')).Or(SymbolRangeToken('0','9'));
37 44 var digit9 = SymbolRangeToken('1', '9');
38 45 var zero = SymbolToken('0');
39 46 var digit = zero.Or(digit9);
40 47 var dot = SymbolToken('.');
41 48 var minus = SymbolToken('-');
42 49 var sign = SymbolSetToken('-', '+');
43 50 var expSign = SymbolSetToken('e', 'E');
44 51 var letters = SymbolRangeToken('a', 'z');
45 52 var integer = zero.Or(digit9.Cat(digit.EClosure()));
46 53 var frac = dot.Cat(digit.Closure());
47 54 var exp = expSign.Cat(sign.Optional()).Cat(digit.Closure());
48 55 var quote = SymbolToken('"');
49 56 var backSlash = SymbolToken('\\');
50 57 var specialEscapeChars = SymbolSetToken('\\', '"', '/', 'b', 'f', 't', 'n', 'r');
51 58 var unicodeEspace = SymbolToken('u').Cat(hexDigit.Repeat(4));
52 59 var whitespace = SymbolSetToken('\n', '\r', '\t', ' ').EClosure();
53 60 var beginObject = whitespace.Cat(SymbolToken('{')).Cat(whitespace);
54 61 var endObject = whitespace.Cat(SymbolToken('}')).Cat(whitespace);
55 62 var beginArray = whitespace.Cat(SymbolToken('[')).Cat(whitespace);
56 63 var endArray = whitespace.Cat(SymbolToken(']')).Cat(whitespace);
57 64 var nameSep = whitespace.Cat(SymbolToken(':')).Cat(whitespace);
58 65 var valueSep = whitespace.Cat(SymbolToken(',')).Cat(whitespace);
59 66
60 67 var number = minus.Optional().Cat(integer).Cat(frac.Optional()).Cat(exp.Optional());
61 68 var literal = letters.Closure();
62 69 var unescaped = SymbolTokenExcept(Enumerable.Range(0, 0x20).Union(new int[] { '\\', '"' }).Select(x => (char)x));
63 70
64 71 var jsonExpression =
65 72 number.Tag(TokenType.Number)
66 73 .Or(literal.Tag(TokenType.Literal))
67 74 .Or(quote.Tag(TokenType.StringBound))
68 75 .Or(beginObject.Tag(TokenType.BeginObject))
69 76 .Or(endObject.Tag(TokenType.EndObject))
70 77 .Or(beginArray.Tag(TokenType.BeginArray))
71 78 .Or(endArray.Tag(TokenType.EndArray))
72 79 .Or(nameSep.Tag(TokenType.NameSeparator))
73 80 .Or(valueSep.Tag(TokenType.ValueSeparator));
74 81
75 82
76 83 var jsonStringExpression =
77 84 quote.Tag(TokenType.StringBound)
78 85 .Or(backSlash.Cat(specialEscapeChars).Tag(TokenType.EscapedChar))
79 86 .Or(backSlash.Cat(unicodeEspace).Tag(TokenType.EscapedUnicode))
80 87 .Or(unescaped.Closure().Tag(TokenType.UnescapedChar));
81 88
82 89
83 m_jsonDFA = BuildDFA(jsonExpression);
84 m_stringDFA = BuildDFA(jsonStringExpression);
90 m_jsonDFA = new RegularCharDFADefinition<TokenType>(new CharAlphabet());
91 BuildDFA(jsonExpression, m_jsonDFA, m_jsonDFA.InputAlphabet);
92
93
94 m_stringDFA = new RegularCharDFADefinition<TokenType>(new CharAlphabet());
95 BuildDFA(jsonStringExpression, m_jsonDFA, m_jsonDFA.InputAlphabet);
85 96 }
86 97
87 public CDFADefinition JsonDFA {
98 public RegularCharDFADefinition<TokenType> JsonDFA {
88 99 get {
89 100 return m_jsonDFA;
90 101 }
91 102 }
92 103
93 public CDFADefinition JsonStringDFA {
104 public RegularDFADefinition<char,TokenType> JsonStringDFA {
94 105 get {
95 106 return m_stringDFA;
96 107 }
97 108 }
109
110 Token<TokenType> SymbolRangeToken(char start, char stop) {
111 return SymbolToken(Enumerable.Range(start,stop - start).Cast<char>());
112 }
113
98 114 }
99 115 }
@@ -1,277 +1,280
1 using Implab.Parsing;
2 using System;
1 using System;
3 2 using System.Diagnostics;
4 3 using System.IO;
4 using Implab.Automaton;
5 using Implab.Automaton.RegularExpressions;
6 using System.Linq;
7 using Implab.Components;
5 8
6 namespace Implab.JSON {
9 namespace Implab.Formats.JSON {
7 10 /// <summary>
8 11 /// internal
9 12 /// </summary>
10 13 public struct JSONParserContext {
11 14 public string memberName;
12 15 public JSONElementContext elementContext;
13 16 }
14 17
15 18 /// <summary>
16 19 /// Pull парсер JSON данных.
17 20 /// </summary>
18 21 /// <remarks>
19 22 /// Следует отметить отдельную интерпретацию свойства <see cref="Level"/>,
20 23 /// оно означает текущий уровень вложенности объектов, однако закрывающий
21 24 /// элемент объекта и массива имеет уровень меньше, чем сам объект.
22 25 /// <code>
23 26 /// { // Level = 1
24 27 /// "name" : "Peter", // Level = 1
25 28 /// "address" : { // Level = 2
26 29 /// city : "Stern" // Level = 2
27 30 /// } // Level = 1
28 31 /// } // Level = 0
29 32 /// </code>
30 33 /// </remarks>
31 public class JSONParser : DFAutomaton<JSONParserContext>, IDisposable {
34 public class JSONParser : Disposable {
32 35
33 36 enum MemberContext {
34 37 MemberName,
35 38 MemberValue
36 39 }
37 40
41 struct ParserContext {
42 DFAStateDescriptior<object>
43 }
44
38 45 static readonly EnumAlphabet<JsonTokenType> _alphabet = EnumAlphabet<JsonTokenType>.FullAlphabet;
39 static readonly DFAStateDescriptior[] _jsonDFA;
40 static readonly DFAStateDescriptior[] _objectDFA;
41 static readonly DFAStateDescriptior[] _arrayDFA;
46 static readonly DFAStateDescriptior<object>[] _jsonDFA;
47 static readonly int _jsonDFAInitialState;
48 static readonly DFAStateDescriptior<object>[] _objectDFA;
49 static readonly int _objectDFAInitialState;
50 static readonly DFAStateDescriptior<object>[] _arrayDFA;
51 static readonly int _arrayDFAInitialState;
42 52
43 53 static JSONParser() {
44 54
45 55
46 var valueExpression = Token.New(JsonTokenType.BeginArray, JsonTokenType.BeginObject, JsonTokenType.Literal, JsonTokenType.Number, JsonTokenType.String);
47 var memberExpression = Token.New(JsonTokenType.String).Cat(Token.New(JsonTokenType.NameSeparator)).Cat(valueExpression);
56 var valueExpression = Token(JsonTokenType.BeginArray, JsonTokenType.BeginObject, JsonTokenType.Literal, JsonTokenType.Number, JsonTokenType.String);
57 var memberExpression = Token(JsonTokenType.String).Cat(Token(JsonTokenType.NameSeparator)).Cat(valueExpression);
48 58
49 59 var objectExpression = memberExpression
50 60 .Cat(
51 Token.New(JsonTokenType.ValueSeparator)
61 Token(JsonTokenType.ValueSeparator)
52 62 .Cat(memberExpression)
53 63 .EClosure()
54 64 )
55 65 .Optional()
56 .Cat(Token.New(JsonTokenType.EndObject))
57 .Tag(0);
66 .Cat(Token(JsonTokenType.EndObject))
67 .Tag(null);
58 68 var arrayExpression = valueExpression
59 69 .Cat(
60 Token.New(JsonTokenType.ValueSeparator)
70 Token(JsonTokenType.ValueSeparator)
61 71 .Cat(valueExpression)
62 72 .EClosure()
63 73 )
64 74 .Optional()
65 .Cat(Token.New(JsonTokenType.EndArray))
66 .Tag(0);
75 .Cat(Token(JsonTokenType.EndArray))
76 .Tag(null);
67 77
68 var jsonExpression = valueExpression.Tag(0);
78 var jsonExpression = valueExpression.Tag(null);
69 79
70 _jsonDFA = BuildDFA(jsonExpression).States;
71 _objectDFA = BuildDFA(objectExpression).States;
72 _arrayDFA = BuildDFA(arrayExpression).States;
80 _jsonDFA = CreateDFA(jsonExpression).GetTransitionTable();
81 _objectDFA = CreateDFA(objectExpression).GetTransitionTable();
82 _arrayDFA = CreateDFA(arrayExpression).GetTransitionTable();
73 83 }
74 84
75 static EDFADefinition<JsonTokenType> BuildDFA(Token expr) {
76 var builder = new DFABuilder();
77 var dfa = new EDFADefinition<JsonTokenType>(_alphabet);
85 static Token<object> Token(params JsonTokenType[] input) {
86 return Token<object>.New(input.Select(t => _alphabet.Translate(t)).ToArray());
87 }
88
89 static RegularDFADefinition<JsonTokenType,object> CreateDFA(Token<object> expr) {
90 var builder = new RegularDFABuilder<object>();
91 var dfa = new RegularDFADefinition<JsonTokenType,object>(_alphabet);
92
78 93 expr.Accept(builder);
79 94
80 95 builder.BuildDFA(dfa);
81 96 return dfa;
82 97 }
83 98
84 99 JSONScanner m_scanner;
85 100 MemberContext m_memberContext;
86 101
87 102 JSONElementType m_elementType;
88 103 object m_elementValue;
89 104
90 105 /// <summary>
91 106 /// Создает новый парсер на основе строки, содержащей JSON
92 107 /// </summary>
93 108 /// <param name="text"></param>
94 109 public JSONParser(string text)
95 110 : base(_jsonDFA, INITIAL_STATE, new JSONParserContext { elementContext = JSONElementContext.None, memberName = String.Empty }) {
96 111 Safe.ArgumentNotEmpty(text, "text");
97 112 m_scanner = new JSONScanner();
98 113 m_scanner.Feed(text.ToCharArray());
99 114 }
100 115
101 116 /// <summary>
102 117 /// Создает новый экземпляр парсера, на основе текстового потока.
103 118 /// </summary>
104 119 /// <param name="reader">Текстовый поток.</param>
105 120 /// <param name="dispose">Признак того, что парсер должен конролировать время жизни входного потока.</param>
106 121 public JSONParser(TextReader reader, bool dispose)
107 122 : base(_jsonDFA, INITIAL_STATE, new JSONParserContext { elementContext = JSONElementContext.None, memberName = String.Empty }) {
108 123 Safe.ArgumentNotNull(reader, "reader");
109 124 m_scanner = new JSONScanner();
110 125 m_scanner.Feed(reader, dispose);
111 126 }
112 127
113 128 /// <summary>
114 129 /// Тип текущего элемента на котором стоит парсер.
115 130 /// </summary>
116 131 public JSONElementType ElementType {
117 132 get { return m_elementType; }
118 133 }
119 134
120 135 /// <summary>
121 136 /// Имя элемента - имя свойства родительского контейнера. Для элементов массивов и корневого всегда
122 137 /// пустая строка.
123 138 /// </summary>
124 139 public string ElementName {
125 140 get { return m_context.info.memberName; }
126 141 }
127 142
128 143 /// <summary>
129 144 /// Значение элемента. Только для элементов типа <see cref="JSONElementType.Value"/>, для остальных <c>null</c>
130 145 /// </summary>
131 146 public object ElementValue {
132 147 get { return m_elementValue; }
133 148 }
134 149
135 150 /// <summary>
136 151 /// Читает слеюудущий объект из потока
137 152 /// </summary>
138 153 /// <returns><c>true</c> - операция чтения прошла успешно, <c>false</c> - конец данных</returns>
139 154 public bool Read() {
140 155 if (m_context.current == UNREACHEBLE_STATE)
141 156 throw new InvalidOperationException("The parser is in invalid state");
142 157 object tokenValue;
143 158 JsonTokenType tokenType;
144 159 m_context.info.memberName = String.Empty;
145 160 while (m_scanner.ReadToken(out tokenValue, out tokenType)) {
146 161 Move((int)tokenType);
147 162 if (m_context.current == UNREACHEBLE_STATE)
148 163 UnexpectedToken(tokenValue, tokenType);
149 164 switch (tokenType) {
150 165 case JsonTokenType.BeginObject:
151 166 Switch(
152 167 _objectDFA,
153 168 INITIAL_STATE,
154 169 new JSONParserContext {
155 170 memberName = m_context.info.memberName,
156 171 elementContext = JSONElementContext.Object
157 172 }
158 173 );
159 174 m_elementValue = null;
160 175 m_memberContext = MemberContext.MemberName;
161 176 m_elementType = JSONElementType.BeginObject;
162 177 return true;
163 178 case JsonTokenType.EndObject:
164 179 Restore();
165 180 m_elementValue = null;
166 181 m_elementType = JSONElementType.EndObject;
167 182 return true;
168 183 case JsonTokenType.BeginArray:
169 184 Switch(
170 185 _arrayDFA,
171 186 INITIAL_STATE,
172 187 new JSONParserContext {
173 188 memberName = m_context.info.memberName,
174 189 elementContext = JSONElementContext.Array
175 190 }
176 191 );
177 192 m_elementValue = null;
178 193 m_memberContext = MemberContext.MemberValue;
179 194 m_elementType = JSONElementType.BeginArray;
180 195 return true;
181 196 case JsonTokenType.EndArray:
182 197 Restore();
183 198 m_elementValue = null;
184 199 m_elementType = JSONElementType.EndArray;
185 200 return true;
186 201 case JsonTokenType.String:
187 202 if (m_memberContext == MemberContext.MemberName) {
188 203 m_context.info.memberName = (string)tokenValue;
189 204 break;
190 205 }
191 206 m_elementType = JSONElementType.Value;
192 207 m_elementValue = tokenValue;
193 208 return true;
194 209 case JsonTokenType.Number:
195 210 m_elementType = JSONElementType.Value;
196 211 m_elementValue = tokenValue;
197 212 return true;
198 213 case JsonTokenType.Literal:
199 214 m_elementType = JSONElementType.Value;
200 215 m_elementValue = ParseLiteral((string)tokenValue);
201 216 return true;
202 217 case JsonTokenType.NameSeparator:
203 218 m_memberContext = MemberContext.MemberValue;
204 219 break;
205 220 case JsonTokenType.ValueSeparator:
206 221 m_memberContext = m_context.info.elementContext == JSONElementContext.Object ? MemberContext.MemberName : MemberContext.MemberValue;
207 222 break;
208 223 default:
209 224 UnexpectedToken(tokenValue, tokenType);
210 225 break;
211 226 }
212 227 }
213 228 if (m_context.info.elementContext != JSONElementContext.None)
214 229 throw new ParserException("Unexpedted end of data");
215 230 return false;
216 231 }
217 232
218 233 object ParseLiteral(string literal) {
219 234 switch (literal) {
220 235 case "null":
221 236 return null;
222 237 case "false":
223 238 return false;
224 239 case "true":
225 240 return true;
226 241 default:
227 242 UnexpectedToken(literal, JsonTokenType.Literal);
228 243 return null; // avoid compliler error
229 244 }
230 245 }
231 246
232 247 void UnexpectedToken(object value, JsonTokenType tokenType) {
233 248 throw new ParserException(String.Format("Unexpected token {0}: '{1}'", tokenType, value));
234 249 }
235 250
236 251
237 252 /// <summary>
238 253 /// Признак конца потока
239 254 /// </summary>
240 255 public bool EOF {
241 256 get {
242 257 return m_scanner.EOF;
243 258 }
244 259 }
245 260
246 protected virtual void Dispose(bool disposing) {
261 protected override void Dispose(bool disposing) {
247 262 if (disposing) {
248 263 m_scanner.Dispose();
249 264 }
250 265 }
251 266
252 267 /// <summary>
253 /// Освобождает парсер и связанный с ним сканнер.
254 /// </summary>
255 public void Dispose() {
256 Dispose(true);
257 GC.SuppressFinalize(this);
258 }
259
260 ~JSONParser() {
261 Dispose(false);
262 }
263
264 /// <summary>
265 268 /// Переходит в конец текущего объекта.
266 269 /// </summary>
267 270 public void SeekElementEnd() {
268 271 var level = Level - 1;
269 272
270 273 Debug.Assert(level >= 0);
271 274
272 275 while (Level != level)
273 276 Read();
274 277 }
275 278 }
276 279
277 280 }
@@ -1,100 +1,96
1 using Implab.Parsing;
2 using System;
3 using System.Collections.Generic;
1 using System;
4 2 using System.Globalization;
5 using System.Linq;
6 using System.Text;
7 using System.Threading.Tasks;
3 using Implab.Automaton;
8 4
9 namespace Implab.JSON {
5 namespace Implab.Formats.JSON {
10 6 /// <summary>
11 7 /// Сканнер (лексер), разбивающий поток символов на токены JSON.
12 8 /// </summary>
13 public class JSONScanner : Scanner {
9 public class JSONScanner : Scanner<object> {
14 10 char[] m_stringBuffer;
15 DFAStateDescriptior[] m_stringDFA;
11 DFAStateDescriptior<>[] m_stringDFA;
16 12 int[] m_stringAlphabet;
17 13
18 14 /// <summary>
19 15 /// Создает новый экземпляр сканнера
20 16 /// </summary>
21 17 public JSONScanner()
22 : base(JSONGrammar.Instance.JsonDFA.States, JSONGrammar.Instance.JsonDFA.Alphabet.GetTranslationMap()) {
18 : base(JSONGrammar.Instance.JsonDFA.GetTransitionTable(), JSONGrammar.Instance.JsonDFA.Alphabet.GetTranslationMap()) {
23 19 m_stringBuffer = new char[1024];
24 20 var dfa = JSONGrammar.Instance.JsonStringDFA;
25 21 m_stringAlphabet = dfa.Alphabet.GetTranslationMap();
26 22 m_stringDFA = dfa.States;
27 23 }
28 24
29 25 /// <summary>
30 26 /// Читает следующий лексический элемент из входных данных.
31 27 /// </summary>
32 28 /// <param name="tokenValue">Возвращает значение прочитанного токена.</param>
33 29 /// <param name="tokenType">Возвращает тип прочитанного токена.</param>
34 30 /// <returns><c>true</c> - чтение произведено успешно. <c>false</c> - достигнут конец входных данных</returns>
35 31 /// <remarks>В случе если токен не распознается, возникает исключение. Значения токенов обрабатываются, т.е.
36 32 /// в строках обрабатываются экранированные символы, числа становтся типа double.</remarks>
37 33 public bool ReadToken(out object tokenValue, out JsonTokenType tokenType) {
38 34 if (ReadTokenInternal()) {
39 35 switch ((JSONGrammar.TokenType)m_currentState.tag[0]) {
40 36 case JSONGrammar.TokenType.StringBound:
41 37 tokenValue = ReadString();
42 38 tokenType = JsonTokenType.String;
43 39 break;
44 40 case JSONGrammar.TokenType.Number:
45 41 tokenValue = Double.Parse(new String(m_buffer, m_tokenOffset, m_tokenLen), CultureInfo.InvariantCulture);
46 42 tokenType = JsonTokenType.Number;
47 43 break;
48 44 default:
49 45 tokenType = (JsonTokenType)m_currentState.tag[0];
50 46 tokenValue = new String(m_buffer, m_tokenOffset, m_tokenLen);
51 47 break;
52 48 }
53 49 return true;
54 50 }
55 51 tokenValue = null;
56 52 tokenType = JsonTokenType.None;
57 53 return false;
58 54 }
59 55
60 56 string ReadString() {
61 57 int pos = 0;
62 58 Switch(m_stringDFA, m_stringAlphabet);
63 59 while (ReadTokenInternal()) {
64 60 switch ((JSONGrammar.TokenType)m_currentState.tag[0]) {
65 61 case JSONGrammar.TokenType.StringBound:
66 62 Restore();
67 63 return new String(m_stringBuffer, 0, pos);
68 64 case JSONGrammar.TokenType.UnescapedChar:
69 65 EnsureStringBufferSize(pos + m_tokenLen);
70 66 Array.Copy(m_buffer, m_tokenOffset, m_stringBuffer, pos, m_tokenLen);
71 67 pos += m_tokenLen;
72 68 break;
73 69 case JSONGrammar.TokenType.EscapedUnicode:
74 70 EnsureStringBufferSize(pos + 1);
75 71 m_stringBuffer[pos] = StringTranslator.TranslateHexUnicode(m_buffer, m_tokenOffset + 2);
76 72 pos++;
77 73 break;
78 74 case JSONGrammar.TokenType.EscapedChar:
79 75 EnsureStringBufferSize(pos + 1);
80 76 m_stringBuffer[pos] = StringTranslator.TranslateEscapedChar(m_buffer[m_tokenOffset + 1]);
81 77 pos++;
82 78 break;
83 79 default:
84 80 break;
85 81 }
86 82
87 83 }
88 84
89 85 throw new ParserException("Unexpected end of data");
90 86 }
91 87
92 88 void EnsureStringBufferSize(int size) {
93 89 if (size > m_stringBuffer.Length) {
94 90 var newBuffer = new char[size];
95 91 m_stringBuffer.CopyTo(newBuffer, 0);
96 92 m_stringBuffer = newBuffer;
97 93 }
98 94 }
99 95 }
100 96 }
@@ -1,50 +1,44
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace Implab.JSON {
1 namespace Implab.Formats.JSON {
8 2 /// <summary>
9 3 /// Тип токенов, возвращаемых <see cref="JSONScanner"/>.
10 4 /// </summary>
11 5 public enum JsonTokenType : int {
12 6 None = 0,
13 7 /// <summary>
14 8 /// Начало объекта
15 9 /// </summary>
16 10 BeginObject,
17 11 /// <summary>
18 12 /// Конец объекта
19 13 /// </summary>
20 14 EndObject,
21 15 /// <summary>
22 16 /// Начало массива
23 17 /// </summary>
24 18 BeginArray,
25 19 /// <summary>
26 20 /// Конец массива
27 21 /// </summary>
28 22 EndArray,
29 23 /// <summary>
30 24 /// Строка
31 25 /// </summary>
32 26 String,
33 27 /// <summary>
34 28 /// Число
35 29 /// </summary>
36 30 Number,
37 31 /// <summary>
38 32 /// Литерал
39 33 /// </summary>
40 34 Literal,
41 35 /// <summary>
42 36 /// Разделитель имени <c>:</c>
43 37 /// </summary>
44 38 NameSeparator,
45 39 /// <summary>
46 40 /// Разделитель имени <c>,</c>
47 41 /// </summary>
48 42 ValueSeparator
49 43 }
50 44 }
@@ -1,271 +1,271
1 1 <?xml version="1.0" encoding="utf-8"?>
2 2 <Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3 3 <PropertyGroup>
4 4 <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
5 5 <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
6 6 <ProjectGuid>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</ProjectGuid>
7 7 <OutputType>Library</OutputType>
8 8 <RootNamespace>Implab</RootNamespace>
9 9 <AssemblyName>Implab</AssemblyName>
10 10 <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
11 11 <ReleaseVersion>0.2</ReleaseVersion>
12 12 <ProductVersion>8.0.30703</ProductVersion>
13 13 <SchemaVersion>2.0</SchemaVersion>
14 14 </PropertyGroup>
15 15 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
16 16 <DebugSymbols>true</DebugSymbols>
17 17 <DebugType>full</DebugType>
18 18 <Optimize>false</Optimize>
19 19 <OutputPath>bin\Debug</OutputPath>
20 20 <DefineConstants>TRACE;DEBUG;</DefineConstants>
21 21 <ErrorReport>prompt</ErrorReport>
22 22 <WarningLevel>4</WarningLevel>
23 23 <ConsolePause>false</ConsolePause>
24 24 <RunCodeAnalysis>true</RunCodeAnalysis>
25 25 </PropertyGroup>
26 26 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
27 27 <DebugType>full</DebugType>
28 28 <Optimize>true</Optimize>
29 29 <OutputPath>bin\Release</OutputPath>
30 30 <ErrorReport>prompt</ErrorReport>
31 31 <WarningLevel>4</WarningLevel>
32 32 <ConsolePause>false</ConsolePause>
33 33 </PropertyGroup>
34 34 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug 4.5|AnyCPU' ">
35 35 <DebugSymbols>true</DebugSymbols>
36 36 <DebugType>full</DebugType>
37 37 <Optimize>false</Optimize>
38 38 <OutputPath>bin\Debug</OutputPath>
39 39 <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants>
40 40 <ErrorReport>prompt</ErrorReport>
41 41 <WarningLevel>4</WarningLevel>
42 42 <RunCodeAnalysis>true</RunCodeAnalysis>
43 43 <ConsolePause>false</ConsolePause>
44 44 </PropertyGroup>
45 45 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release 4.5|AnyCPU' ">
46 46 <Optimize>true</Optimize>
47 47 <OutputPath>bin\Release</OutputPath>
48 48 <ErrorReport>prompt</ErrorReport>
49 49 <WarningLevel>4</WarningLevel>
50 50 <ConsolePause>false</ConsolePause>
51 51 <DefineConstants>NET_4_5</DefineConstants>
52 52 </PropertyGroup>
53 53 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'DebugMono|AnyCPU' ">
54 54 <DebugSymbols>true</DebugSymbols>
55 55 <DebugType>full</DebugType>
56 56 <Optimize>false</Optimize>
57 57 <OutputPath>bin\Debug</OutputPath>
58 58 <DefineConstants>TRACE;DEBUG;NET_4_5;MONO</DefineConstants>
59 59 <ErrorReport>prompt</ErrorReport>
60 60 <WarningLevel>4</WarningLevel>
61 61 <RunCodeAnalysis>true</RunCodeAnalysis>
62 62 <ConsolePause>false</ConsolePause>
63 63 </PropertyGroup>
64 64 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'ReleaseMono|AnyCPU' ">
65 65 <Optimize>true</Optimize>
66 66 <OutputPath>bin\Release</OutputPath>
67 67 <DefineConstants>NET_4_5;MONO;</DefineConstants>
68 68 <ErrorReport>prompt</ErrorReport>
69 69 <WarningLevel>4</WarningLevel>
70 70 <ConsolePause>false</ConsolePause>
71 71 </PropertyGroup>
72 72 <ItemGroup>
73 73 <Reference Include="System" />
74 74 <Reference Include="System.Xml" />
75 75 <Reference Include="mscorlib" />
76 76 </ItemGroup>
77 77 <ItemGroup>
78 78 <Compile Include="CustomEqualityComparer.cs" />
79 79 <Compile Include="Diagnostics\ConsoleTraceListener.cs" />
80 80 <Compile Include="Diagnostics\EventText.cs" />
81 81 <Compile Include="Diagnostics\LogChannel.cs" />
82 82 <Compile Include="Diagnostics\LogicalOperation.cs" />
83 83 <Compile Include="Diagnostics\TextFileListener.cs" />
84 84 <Compile Include="Diagnostics\TraceLog.cs" />
85 85 <Compile Include="Diagnostics\TraceEvent.cs" />
86 86 <Compile Include="Diagnostics\TraceEventType.cs" />
87 87 <Compile Include="ICancellable.cs" />
88 88 <Compile Include="IProgressHandler.cs" />
89 89 <Compile Include="IProgressNotifier.cs" />
90 90 <Compile Include="IPromiseT.cs" />
91 91 <Compile Include="IPromise.cs" />
92 92 <Compile Include="IServiceLocator.cs" />
93 93 <Compile Include="ITaskController.cs" />
94 94 <Compile Include="Parallels\DispatchPool.cs" />
95 95 <Compile Include="Parallels\ArrayTraits.cs" />
96 96 <Compile Include="Parallels\MTQueue.cs" />
97 97 <Compile Include="Parallels\WorkerPool.cs" />
98 98 <Compile Include="ProgressInitEventArgs.cs" />
99 99 <Compile Include="Properties\AssemblyInfo.cs" />
100 100 <Compile Include="Parallels\AsyncPool.cs" />
101 101 <Compile Include="Safe.cs" />
102 102 <Compile Include="ValueEventArgs.cs" />
103 103 <Compile Include="PromiseExtensions.cs" />
104 104 <Compile Include="SyncContextPromise.cs" />
105 105 <Compile Include="Diagnostics\OperationContext.cs" />
106 106 <Compile Include="Diagnostics\TraceContext.cs" />
107 107 <Compile Include="Diagnostics\LogEventArgs.cs" />
108 108 <Compile Include="Diagnostics\LogEventArgsT.cs" />
109 109 <Compile Include="Diagnostics\Extensions.cs" />
110 110 <Compile Include="PromiseEventType.cs" />
111 111 <Compile Include="Parallels\AsyncQueue.cs" />
112 112 <Compile Include="PromiseT.cs" />
113 113 <Compile Include="IDeferred.cs" />
114 114 <Compile Include="IDeferredT.cs" />
115 115 <Compile Include="Promise.cs" />
116 116 <Compile Include="PromiseTransientException.cs" />
117 117 <Compile Include="Parallels\Signal.cs" />
118 118 <Compile Include="Parallels\SharedLock.cs" />
119 119 <Compile Include="Diagnostics\ILogWriter.cs" />
120 120 <Compile Include="Diagnostics\ListenerBase.cs" />
121 121 <Compile Include="Parallels\BlockingQueue.cs" />
122 122 <Compile Include="AbstractEvent.cs" />
123 123 <Compile Include="AbstractPromise.cs" />
124 124 <Compile Include="AbstractPromiseT.cs" />
125 125 <Compile Include="FuncTask.cs" />
126 126 <Compile Include="FuncTaskBase.cs" />
127 127 <Compile Include="FuncTaskT.cs" />
128 128 <Compile Include="ActionChainTaskBase.cs" />
129 129 <Compile Include="ActionChainTask.cs" />
130 130 <Compile Include="ActionChainTaskT.cs" />
131 131 <Compile Include="FuncChainTaskBase.cs" />
132 132 <Compile Include="FuncChainTask.cs" />
133 133 <Compile Include="FuncChainTaskT.cs" />
134 134 <Compile Include="ActionTaskBase.cs" />
135 135 <Compile Include="ActionTask.cs" />
136 136 <Compile Include="ActionTaskT.cs" />
137 137 <Compile Include="ICancellationToken.cs" />
138 138 <Compile Include="SuccessPromise.cs" />
139 139 <Compile Include="SuccessPromiseT.cs" />
140 140 <Compile Include="PromiseAwaiterT.cs" />
141 141 <Compile Include="PromiseAwaiter.cs" />
142 142 <Compile Include="Components\ComponentContainer.cs" />
143 143 <Compile Include="Components\Disposable.cs" />
144 144 <Compile Include="Components\DisposablePool.cs" />
145 145 <Compile Include="Components\ObjectPool.cs" />
146 146 <Compile Include="Components\ServiceLocator.cs" />
147 147 <Compile Include="Components\IInitializable.cs" />
148 148 <Compile Include="TaskController.cs" />
149 149 <Compile Include="Components\App.cs" />
150 150 <Compile Include="Components\IRunnable.cs" />
151 151 <Compile Include="Components\ExecutionState.cs" />
152 152 <Compile Include="Components\RunnableComponent.cs" />
153 153 <Compile Include="Components\IFactory.cs" />
154 154 <Compile Include="Automaton\DFAStateDescriptor.cs" />
155 <Compile Include="Automaton\DFAutomaton.cs" />
156 155 <Compile Include="Automaton\EnumAlphabet.cs" />
157 156 <Compile Include="Automaton\IAlphabet.cs" />
158 157 <Compile Include="Automaton\ParserException.cs" />
159 158 <Compile Include="Automaton\Scanner.cs" />
160 159 <Compile Include="Automaton\IndexedAlphabetBase.cs" />
161 160 <Compile Include="Automaton\IAlphabetBuilder.cs" />
162 161 <Compile Include="Automaton\RegularExpressions\AltToken.cs" />
163 162 <Compile Include="Automaton\RegularExpressions\BinaryToken.cs" />
164 163 <Compile Include="Automaton\RegularExpressions\CatToken.cs" />
165 164 <Compile Include="Automaton\DFAConst.cs" />
166 165 <Compile Include="Automaton\RegularExpressions\Grammar.cs" />
167 166 <Compile Include="Automaton\RegularExpressions\StarToken.cs" />
168 167 <Compile Include="Automaton\RegularExpressions\SymbolToken.cs" />
169 168 <Compile Include="Automaton\RegularExpressions\EmptyToken.cs" />
170 169 <Compile Include="Automaton\RegularExpressions\EndToken.cs" />
171 170 <Compile Include="Automaton\RegularExpressions\Token.cs" />
172 171 <Compile Include="Automaton\RegularExpressions\IVisitor.cs" />
173 172 <Compile Include="Automaton\AutomatonTransition.cs" />
174 173 <Compile Include="Automaton\RegularExpressions\RegularDFABuilder.cs" />
175 174 <Compile Include="Formats\JSON\JSONElementContext.cs" />
176 175 <Compile Include="Formats\JSON\JSONElementType.cs" />
177 176 <Compile Include="Formats\JSON\JSONGrammar.cs" />
178 177 <Compile Include="Formats\JSON\JSONParser.cs" />
179 178 <Compile Include="Formats\JSON\JSONScanner.cs" />
180 179 <Compile Include="Formats\JSON\JsonTokenType.cs" />
181 180 <Compile Include="Formats\JSON\JSONWriter.cs" />
182 181 <Compile Include="Formats\JSON\JSONXmlReader.cs" />
183 182 <Compile Include="Formats\JSON\JSONXmlReaderOptions.cs" />
184 183 <Compile Include="Formats\JSON\StringTranslator.cs" />
185 184 <Compile Include="Automaton\MapAlphabet.cs" />
186 185 <Compile Include="Automaton\DummyAlphabet.cs" />
187 186 <Compile Include="Automaton\DFATransitionTable.cs" />
188 <Compile Include="Automaton\IDFATransitionTableBuilder.cs" />
189 <Compile Include="Automaton\IDFATransitionTable.cs" />
190 187 <Compile Include="Automaton\RegularExpressions\RegularDFADefinition.cs" />
191 188 <Compile Include="Formats\CharAlphabet.cs" />
192 189 <Compile Include="Formats\ByteAlphabet.cs" />
190 <Compile Include="Formats\RegularCharDFADefinition.cs" />
191 <Compile Include="Automaton\IDFATable.cs" />
192 <Compile Include="Automaton\IDFATableBuilder.cs" />
193 193 </ItemGroup>
194 194 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
195 195 <ItemGroup />
196 196 <ProjectExtensions>
197 197 <MonoDevelop>
198 198 <Properties>
199 199 <Policies>
200 200 <CSharpFormattingPolicy IndentSwitchBody="True" NamespaceBraceStyle="EndOfLine" ClassBraceStyle="EndOfLine" InterfaceBraceStyle="EndOfLine" StructBraceStyle="EndOfLine" EnumBraceStyle="EndOfLine" MethodBraceStyle="EndOfLine" ConstructorBraceStyle="EndOfLine" DestructorBraceStyle="EndOfLine" BeforeMethodDeclarationParentheses="False" BeforeMethodCallParentheses="False" BeforeConstructorDeclarationParentheses="False" NewLineBeforeConstructorInitializerColon="NewLine" NewLineAfterConstructorInitializerColon="SameLine" BeforeIndexerDeclarationBracket="False" BeforeDelegateDeclarationParentheses="False" NewParentheses="False" SpacesBeforeBrackets="False" inheritsSet="Mono" inheritsScope="text/x-csharp" scope="text/x-csharp" />
201 201 <TextStylePolicy FileWidth="120" EolMarker="Unix" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
202 202 <DotNetNamingPolicy DirectoryNamespaceAssociation="PrefixedHierarchical" ResourceNamePolicy="MSBuild" />
203 203 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
204 204 <XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
205 205 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
206 206 <NameConventionPolicy>
207 207 <Rules>
208 208 <NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
209 209 <NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
210 210 <NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
211 211 <RequiredPrefixes>
212 212 <String>I</String>
213 213 </RequiredPrefixes>
214 214 </NamingRule>
215 215 <NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
216 216 <RequiredSuffixes>
217 217 <String>Attribute</String>
218 218 </RequiredSuffixes>
219 219 </NamingRule>
220 220 <NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
221 221 <RequiredSuffixes>
222 222 <String>EventArgs</String>
223 223 </RequiredSuffixes>
224 224 </NamingRule>
225 225 <NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
226 226 <RequiredSuffixes>
227 227 <String>Exception</String>
228 228 </RequiredSuffixes>
229 229 </NamingRule>
230 230 <NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
231 231 <NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
232 232 <NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
233 233 <NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
234 234 <NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
235 235 <RequiredPrefixes>
236 236 <String>m_</String>
237 237 </RequiredPrefixes>
238 238 </NamingRule>
239 239 <NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True">
240 240 <RequiredPrefixes>
241 241 <String>_</String>
242 242 </RequiredPrefixes>
243 243 </NamingRule>
244 244 <NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
245 245 <RequiredPrefixes>
246 246 <String>m_</String>
247 247 </RequiredPrefixes>
248 248 </NamingRule>
249 249 <NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="AllUpper" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
250 250 <NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
251 251 <NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
252 252 <NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
253 253 <NamingRule Name="Parameters" AffectedEntity="Parameter, LocalVariable" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
254 254 <NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
255 255 <RequiredPrefixes>
256 256 <String>T</String>
257 257 </RequiredPrefixes>
258 258 </NamingRule>
259 259 </Rules>
260 260 </NameConventionPolicy>
261 261 </Policies>
262 262 </Properties>
263 263 </MonoDevelop>
264 264 </ProjectExtensions>
265 265 <ItemGroup>
266 266 <Folder Include="Components\" />
267 267 <Folder Include="Automaton\RegularExpressions\" />
268 268 <Folder Include="Formats\" />
269 269 <Folder Include="Formats\JSON\" />
270 270 </ItemGroup>
271 271 </Project> No newline at end of file
1 NO CONTENT: file was removed
1 NO CONTENT: file was removed
1 NO CONTENT: file was removed
General Comments 0
You need to be logged in to leave comments. Login now