##// END OF EJS Templates
implab » ImplabNet
RSS
Almost complete DFA refactoring
cin -
r164:ec35731ae299 ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -0,0 +1,251
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Linq;
5
6 namespace Implab.Automaton {
7 public class DFATransitionTable<TTag> : IDFATransitionTableBuilder<TTag> {
8 DFAStateDescriptior<TTag>[] m_dfaTable;
9
10 int m_stateCount;
11 int m_symbolCount;
12 int m_initialState;
13
14 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16
17
18 #region IDFADefinition implementation
19
20 public DFAStateDescriptior<TTag>[] GetTransitionTable() {
21 if (m_dfaTable == null) {
22 if (m_stateCount <= 0)
23 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
24 if (m_symbolCount <= 0)
25 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
26
27 m_dfaTable = ConstructTransitionTable();
28 }
29 return m_dfaTable;
30 }
31
32 public bool IsFinalState(int s) {
33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
34
35 return m_finalStates.ContainsKey(s);
36 }
37
38 public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
39 get {
40 return m_finalStates;
41 }
42 }
43
44 public int StateCount {
45 get { return m_stateCount; }
46 }
47
48 public int AlphabetSize {
49 get { return m_symbolCount; }
50 }
51
52 public int InitialState {
53 get { return m_initialState; }
54 }
55
56 #endregion
57
58 protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
59 var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
60
61 foreach (var pair in m_finalStates) {
62 var idx = pair.Key;
63
64 dfaTable[idx].final = true;
65 dfaTable[idx].tag = pair.Value;
66 }
67
68 foreach (var t in m_transitions) {
69 if (dfaTable[t.s1].transitions == null) {
70 dfaTable[t.s1].transitions = new int[m_symbolCount];
71 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
72 dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
73 }
74
75 dfaTable[t.s1].transitions[t.edge] = t.s2;
76 }
77 }
78
79 #region IDFADefinitionBuilder
80
81 public void DefineTransition(int s1, int s2, int symbol) {
82 if (m_dfaTable != null)
83 throw new InvalidOperationException("The transition table is already built");
84
85 Safe.ArgumentAssert(s1 > 0, "s1");
86 Safe.ArgumentAssert(s2 > 0, "s2");
87 Safe.ArgumentAssert(symbol >= 0, "symbol");
88
89 m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
90 m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
91
92 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
93 }
94
95 public void MarkFinalState(int state, params TTag[] tags) {
96 if (m_dfaTable != null)
97 throw new InvalidOperationException("The transition table is already built");
98
99 m_finalStates[state] = tags;
100 }
101
102 public void SetInitialState(int s) {
103 Safe.ArgumentAssert(s >= 0, "s");
104 m_initialState = s;
105 }
106
107
108 #endregion
109
110 protected void Optimize<TInput, TState>(
111 IDFATransitionTableBuilder<TTag> optimalDFA,
112 IAlphabet<TInput> inputAlphabet,
113 IAlphabetBuilder<TInput> optimalInputAlphabet,
114 IAlphabet<TState> stateAlphabet,
115 IAlphabetBuilder<TState> optimalStateAlphabet
116 ) {
117 Safe.ArgumentNotNull(optimalDFA, "dfa");
118 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
119 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
120 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
121 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
122
123 if (inputAlphabet.Count != m_symbolCount)
124 throw new InvalidOperationException("The input symbols aphabet mismatch");
125 if (stateAlphabet.Count != m_stateCount)
126 throw new InvalidOperationException("The states alphabet mismatch");
127
128 var setComparer = new CustomEqualityComparer<HashSet<int>>(
129 (x, y) => x.SetEquals(y),
130 s => s.Sum(x => x.GetHashCode())
131 );
132
133 var arrayComparer = new CustomEqualityComparer<TTag[]>(
134 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
135 a => a.Sum(x => x.GetHashCode())
136 );
137
138 var optimalStates = new HashSet<HashSet<int>>(setComparer);
139 var queue = new HashSet<HashSet<int>>(setComparer);
140
141 // получаем конечные состояния, сгруппированные по маркерам
142 optimalStates.UnionWith(
143 m_finalStates
144 .GroupBy(pair => pair.Value, arrayComparer)
145 .Select(
146 g => new HashSet<int>(
147 g.Select( pair => pair.Key)
148 )
149 )
150 );
151
152 var state = new HashSet<int>(
153 Enumerable
154 .Range(0, m_stateCount - 1)
155 .Where(i => !m_finalStates.ContainsKey(i))
156 );
157 optimalStates.Add(state);
158 queue.Add(state);
159
160 var rmap = m_transitions
161 .GroupBy(t => t.s2)
162 .ToLookup(
163 g => g.Key, // s2
164 g => g.ToLookup(t => t.edge, t => t.s1)
165 );
166
167 while (queue.Count > 0) {
168 var stateA = queue.First();
169 queue.Remove(stateA);
170
171 for (int c = 0; c < m_symbolCount; c++) {
172 var stateX = new HashSet<int>();
173 foreach(var a in stateA)
174 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
175
176 foreach (var stateY in optimalStates.ToArray()) {
177 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
178 var stateR1 = new HashSet<int>(stateY);
179 var stateR2 = new HashSet<int>(stateY);
180
181 stateR1.IntersectWith(stateX);
182 stateR2.ExceptWith(stateX);
183
184 optimalStates.Remove(stateY);
185 optimalStates.Add(stateR1);
186 optimalStates.Add(stateR2);
187
188 if (queue.Contains(stateY)) {
189 queue.Remove(stateY);
190 queue.Add(stateR1);
191 queue.Add(stateR2);
192 } else {
193 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
194 }
195 }
196 }
197 }
198 }
199
200 // карта получения оптимального состояния по соотвествующему ему простому состоянию
201 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
202
203 // получаем минимальный алфавит
204 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
205 var optimalAlphabet = m_transitions
206 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
207
208 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
209
210 var optimalTags = m_finalStates
211 .GroupBy(pair => statesMap[pair.Key])
212 .ToDictionary(
213 g => g.Key,
214 g => g.SelectMany(pair => pair.Value).ToArray()
215 );
216
217 // построение автомата
218 optimalDFA.SetInitialState(statesMap[m_initialState]);
219
220 foreach (var pair in optimalTags)
221 optimalDFA.MarkFinalState(pair.Key, pair.Value);
222
223 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
224 optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
225
226 }
227
228 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
229 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
230 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
231
232 var inputMap = inputAlphabet.CreateReverseMap();
233 var stateMap = stateAlphabet.CreateReverseMap();
234
235 for (int i = 0; i < inputMap.Length; i++)
236 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
237
238
239 foreach(var t in m_transitions)
240 Console.WriteLine(
241 "[{0}] -{{{1}}}-> [{2}]{3}",
242 stateMap[t.s1],
243 String.Join(",", inputMap[t.edge]),
244 stateMap[t.s2],
245 m_finalStates.ContainsKey(t.s2) ? "$" : ""
246 );
247
248 }
249
250 }
251 }
Show file before | Show file after | Hide comments
@@ -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 IDFATransitionTable<TTag> {
35 /// <summary>
36 /// Таблица переходов состояний автомата
37 /// </summary>
38 /// <returns>The transition table.</returns>
39 DFAStateDescriptior<TTag>[] 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<KeyValuePair<int,TTag[]>> FinalStates {
56 get;
57 }
58 }
59 }
Show file before | Show file after | Hide comments
@@ -0,0 +1,25
1 using System;
2
3 namespace Implab.Automaton {
4 public interface IDFATransitionTableBuilder<TTag> : IDFATransitionTable<TTag> {
5 /// <summary>
6 /// Marks the state as final and assings tags.
7 /// </summary>
8 /// <param name="state">State.</param>
9 /// <param name="tags">Tags.</param>
10 void MarkFinalState(int state, params TTag[] tags);
11
12 /// <summary>
13 /// Defines the transition from <paramref name="s1"/> to
14 /// <paramref name="s2"/> with input <paramref name="symbol"/>.
15 /// </summary>
16 /// <param name="s1">S1.</param>
17 /// <param name="s2">S2.</param>
18 /// <param name="symbol">Symbol.</param>
19 void DefineTransition(int s1, int s2, int symbol);
20
21 void SetInitialState(int s);
22
23 }
24 }
25
Show file before | Show file after | Hide comments
@@ -0,0 +1,46
1 using System;
2
3 namespace Implab.Automaton.RegularExpressions {
4 public class RegularDFADefinition<TInput, TTag> : DFATransitionTable<TTag>, IDFATransitionTable<TTag> {
5
6 readonly IAlphabet<TInput> m_alphabet;
7 readonly int m_initialState;
8
9 public RegularDFADefinition(IAlphabet<TInput> alphabet, int initialState) {
10 Safe.ArgumentNotNull(alphabet, "aplhabet");
11
12 m_alphabet = alphabet;
13 m_initialState = initialState;
14 }
15
16
17 public IAlphabet<TInput> InputAlphabet {
18 get {
19 return m_alphabet;
20 }
21 }
22
23 protected override DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
24 if (InputAlphabet.Count != m_alphabet.Count)
25 throw new InvalidOperationException("The alphabet doesn't match the transition table");
26
27 return base.ConstructTransitionTable();
28 }
29
30 /// <summary>
31 /// Optimize the specified alphabet.
32 /// </summary>
33 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
34 public RegularDFADefinition<TInput, TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
35 Safe.ArgumentNotNull(alphabet, "alphabet");
36
37 var optimalDFA = new RegularDFADefinition<TInput,TTag>(alphabet, m_initialState);
38
39 Optimize(optimalDFA, InputAlphabet, alphabet, new DummyAlphabet(StateCount), new MapAlphabet<int>());
40
41 }
42
43
44 }
45 }
46
Show file before | Show file after | Hide comments
@@ -0,0 +1,25
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4
5 namespace Implab.Automaton {
6 public class ByteAlphabet : IndexedAlphabetBase<byte> {
7 public ByteAlphabet() : base(byte.MaxValue + 1){
8 }
9
10 #region implemented abstract members of IndexedAlphabetBase
11
12 public override int GetSymbolIndex(byte symbol) {
13 return (int)symbol;
14 }
15
16 public IEnumerable<byte> InputSymbols {
17 get {
18 return Enumerable.Range(byte.MinValue, byte.MaxValue).Cast<byte>();
19 }
20 }
21
22 #endregion
23 }
24 }
25
Show file before | Show file after | Hide comments
@@ -0,0 +1,23
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Linq;
5 using System.Text;
6 using System.Threading.Tasks;
7
8 namespace Implab.Automaton {
9 public class CharAlphabet: IndexedAlphabetBase<char> {
10
11 public CharAlphabet()
12 : base(char.MaxValue + 1) {
13 }
14
15 public override int GetSymbolIndex(char symbol) {
16 return symbol;
17 }
18
19 public override IEnumerable<char> InputSymbols {
20 get { return Enumerable.Range(char.MinValue, char.MaxValue).Cast<char>(); }
21 }
22 }
23 }
Show file before | Show file after | Hide comments
@@ -1,13 +1,7
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.Automaton {
1 namespace Implab.Automaton {
8 2 public struct DFAStateDescriptior<TTag> {
9 3 public bool final;
10 4 public TTag[] tag;
11 5 public int[] transitions;
12 6 }
13 7 }
Show file before | Show file after | Hide comments
@@ -1,46 +1,56
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton {
6 /// <summary>
7 /// Dummy alphabet consists of integer numbers which are identical to their classes.
8 /// </summary>
6 9 public class DummyAlphabet : IAlphabet<int> {
7 10 readonly int m_size;
11
12 /// <summary>
13 /// Creates a new dummy alphabet with given size.
14 /// </summary>
15 /// <param name="size">The size of the alphabet, must be greater then zero.</param>
8 16 public DummyAlphabet(int size) {
9 17 Safe.ArgumentAssert(size > 0);
10 18 m_size = 0;
11 19 }
12 20
13 21 #region IAlphabet implementation
14 22
15 23 public List<int>[] CreateReverseMap() {
16 24 Enumerable.Range(0, m_size).ToArray();
17 25 }
18 26
19 27 public int[] Reclassify(IAlphabetBuilder<int> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
20 28 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
21 29 Safe.ArgumentNotNull(classes, "classes");
22 30 var map = new int[m_size];
23 31 foreach (var cls in classes) {
32 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
33 continue;
24 34 var newid = newAlphabet.DefineClass(cls);
25 35 foreach (var id in cls)
26 36 map[id] = newid;
27 37 }
28 38
29 39 return map;
30 40 }
31 41
32 42 public int Translate(int symobl) {
33 43 Safe.ArgumentInRange(symobl, 0, m_size, "symbol");
34 44 return symobl;
35 45 }
36 46
37 47 public int Count {
38 48 get {
39 49 return m_size;
40 50 }
41 51 }
42 52
43 53 #endregion
44 54 }
45 55 }
46 56
Show file before | Show file after | Hide comments
@@ -1,67 +1,70
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Diagnostics;
4 4 using System.Globalization;
5 5 using System.Linq;
6 6 using System.Diagnostics.CodeAnalysis;
7 7
8 8 namespace Implab.Automaton {
9 9 /// <summary>
10 10 /// Алфавит символами которого являются элементы перечислений.
11 11 /// </summary>
12 12 /// <typeparam name="T">Тип перечислений</typeparam>
13 13 public class EnumAlphabet<T> : IndexedAlphabetBase<T> where T : struct, IConvertible {
14 14 [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
15 static readonly T[] _symbols;
16 static readonly EnumAlphabet<T> _fullAlphabet;
15 static readonly Lazy<T[]> _symbols = new Lazy<T[]>(GetSymbols);
16
17 [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
18 static readonly Lazy<EnumAlphabet<T>> _fullAlphabet = new Lazy<EnumAlphabet<T>>(CreateEnumAlphabet);
19
20 static EnumAlphabet<T> CreateEnumAlphabet() {
21 var symbols = _symbols.Value;
17 22
18 [SuppressMessage("Microsoft.Design", "CA1065:DoNotRaiseExceptionsInUnexpectedLocations")]
19 static EnumAlphabet() {
23 if (
24 symbols[symbols.Length - 1].ToInt32(CultureInfo.InvariantCulture) >= symbols.Length
25 || symbols[0].ToInt32(CultureInfo.InvariantCulture) != 0
26 )
27 throw new InvalidOperationException("The specified enumeration must be zero-based and continuously numbered");
28
29 return new EnumAlphabet<T>(symbols.Select(x => x.ToInt32(CultureInfo.InvariantCulture)).ToArray());
30 }
31
32 static T[] GetSymbols() {
20 33 if (!typeof(T).IsEnum)
21 34 throw new InvalidOperationException("Invalid generic parameter, enumeration is required");
22 35
23 36 if (Enum.GetUnderlyingType(typeof(T)) != typeof(Int32))
24 37 throw new InvalidOperationException("Only enums based on Int32 are supported");
25 38
26 _symbols = ((T[])Enum.GetValues(typeof(T)))
39 return ((T[])Enum.GetValues(typeof(T)))
27 40 .OrderBy(x => x.ToInt32(CultureInfo.InvariantCulture))
28 41 .ToArray();
29
30 if (
31 _symbols[_symbols.Length - 1].ToInt32(CultureInfo.InvariantCulture) >= _symbols.Length
32 || _symbols[0].ToInt32(CultureInfo.InvariantCulture) != 0
33 )
34 throw new InvalidOperationException("The specified enumeration must be zero-based and continuously numbered");
35
36 _fullAlphabet = new EnumAlphabet<T>(_symbols.Select(x => x.ToInt32(CultureInfo.InvariantCulture)).ToArray());
37 42 }
38 43
39
40
41 44 public static EnumAlphabet<T> FullAlphabet {
42 45 get {
43 return _fullAlphabet;
46 return _fullAlphabet.Value;
44 47 }
45 48 }
46 49
47 50
48 51 public EnumAlphabet()
49 : base(_symbols.Length) {
52 : base(_symbols.Value.Length) {
50 53 }
51 54
52 55 public EnumAlphabet(int[] map)
53 56 : base(map) {
54 Debug.Assert(map.Length == _symbols.Length);
57 Debug.Assert(map.Length == _symbols.Value.Length);
55 58 }
56 59
57 60
58 61 public override int GetSymbolIndex(T symbol) {
59 62 return symbol.ToInt32(CultureInfo.InvariantCulture);
60 63 }
61 64
62 65 public override IEnumerable<T> InputSymbols {
63 get { return _symbols; }
66 get { return _symbols.Value; }
64 67 }
65 68
66 69 }
67 70 }
Show file before | Show file after | Hide comments
@@ -1,25 +1,22
1 1
2 2 using System.Collections.Generic;
3 3
4 4 namespace Implab.Automaton {
5 5 public interface IAlphabetBuilder<TSymbol> : IAlphabet<TSymbol> {
6 6 /// <summary>
7 7 /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
8 8 /// возвращается ранее сопоставленный с символом класс.
9 9 /// </summary>
10 10 /// <param name="symbol">Символ для добавления.</param>
11 11 /// <returns>Индекс класса, который попоставлен с символом.</returns>
12 12 int DefineSymbol(TSymbol symbol);
13 13 /// <summary>
14 14 /// Доабвляем класс символов. Множеству указанных исходных символов
15 15 /// будет сопоставлен символ в алфавите.
16 16 /// </summary>
17 17 /// <param name="symbols">Множестов исходных символов</param>
18 18 /// <returns>Идентификатор символа алфавита.</returns>
19 19 int DefineClass(IEnumerable<TSymbol> symbols);
20
21
22
23 20 }
24 21 }
25 22
Show file before | Show file after | Hide comments
@@ -1,105 +1,103
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 {
8 8 /// <summary>
9 9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
10 10 /// </summary>
11 11 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
12 public const int UNCLASSIFIED = 0;
13
14 12 int m_nextId = 1;
15 13 readonly int[] m_map;
16 14
17 15 public int Count {
18 16 get { return m_nextId; }
19 17 }
20 18
21 19 protected IndexedAlphabetBase(int mapSize) {
22 20 m_map = new int[mapSize];
23 21 }
24 22
25 23 protected IndexedAlphabetBase(int[] map) {
26 24 Debug.Assert(map != null);
27 25
28 26 m_map = map;
29 27 m_nextId = map.Max() + 1;
30 28 }
31 29
32 30 public int DefineSymbol(T symbol) {
33 31 var index = GetSymbolIndex(symbol);
34 if (m_map[index] == UNCLASSIFIED)
32 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
35 33 m_map[index] = m_nextId++;
36 34 return m_map[index];
37 35 }
38 36
39 37 public int DefineClass(IEnumerable<T> symbols) {
40 38 Safe.ArgumentNotNull(symbols, "symbols");
41 39 symbols = symbols.Distinct();
42 40
43 41 foreach (var symbol in symbols) {
44 42 var index = GetSymbolIndex(symbol);
45 if (m_map[index] == UNCLASSIFIED)
43 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
46 44 m_map[GetSymbolIndex(symbol)] = m_nextId;
47 45 else
48 46 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
49 47 }
50 48 return m_nextId++;
51 49 }
52 50
53 51 public List<T>[] CreateReverseMap() {
54 52 return
55 Enumerable.Range(UNCLASSIFIED, Count)
53 Enumerable.Range(0, Count)
56 54 .Select(
57 55 i => InputSymbols
58 .Where(x => i != UNCLASSIFIED && m_map[GetSymbolIndex(x)] == i)
56 .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
59 57 .ToList()
60 58 )
61 59 .ToArray();
62 60 }
63 61
64 62 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
65 63 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
66 64 Safe.ArgumentNotNull(classes, "classes");
67 65 var reverseMap = CreateReverseMap();
68 66
69 67 var translationMap = new int[Count];
70 68
71 69 foreach (var scl in classes) {
72 70 // skip if the supper class contains the unclassified element
73 if (scl.Contains(UNCLASSIFIED))
71 if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
74 72 continue;
75 73 var range = new List<T>();
76 74 foreach (var cl in scl) {
77 75 if (cl < 0 || cl >= reverseMap.Length)
78 76 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
79 77 range.AddRange(reverseMap[cl]);
80 78 }
81 79 var newClass = newAlphabet.DefineClass(range);
82 80 foreach (var cl in scl)
83 81 translationMap[cl] = newClass;
84 82 }
85 83
86 84 return translationMap;
87 85 }
88 86
89 87 public virtual int Translate(T symbol) {
90 88 return m_map[GetSymbolIndex(symbol)];
91 89 }
92 90
93 91 public abstract int GetSymbolIndex(T symbol);
94 92
95 93 public abstract IEnumerable<T> InputSymbols { get; }
96 94
97 95 /// <summary>
98 96 /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
99 97 /// </summary>
100 98 /// <returns>The translation map.</returns>
101 99 public int[] GetTranslationMap() {
102 100 return m_map;
103 101 }
104 102 }
105 103 }
Show file before | Show file after | Hide comments
@@ -1,103 +1,109
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton {
6 6 public class MapAlphabet<T> : IAlphabetBuilder<T> {
7 7 readonly Dictionary<T,int> m_map;
8 int m_nextCls;
8 int m_nextCls = 1;
9
10 public MapAlphabet() {
11 m_map = new Dictionary<T, int>();
12 }
9 13
10 14 public MapAlphabet(IEqualityComparer<T> comparer) {
11 15 m_map = new Dictionary<T, int>(comparer);
12 m_nextCls = 1;
13 16 }
14 17
15 18 #region IAlphabetBuilder implementation
16 19
17 20 public int DefineSymbol(T symbol) {
18 21 int cls;
19 22 if (m_map.TryGetValue(symbol, out cls))
20 23 return cls;
21 24
22 25 cls = m_nextCls++;
23 26
24 27 m_map.Add(symbol, cls);
25 28
26 29 return cls;
27 30 }
28 31
29 32 public int DefineClass(IEnumerable<T> symbols) {
30 33 Safe.ArgumentNotNull(symbols, "symbols");
31 34 symbols = symbols.Distinct();
32 35
33 36 foreach (var symbol in symbols) {
34 37 if (!m_map.Contains(symbol))
35 38 m_map.Add(symbol, m_nextCls);
36 39 else
37 40 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
38 41 }
39 42 return m_nextCls++;
40 43 }
41 44
42 45 #endregion
43 46
44 47 #region IAlphabet implementation
45 48
46 49 public List<T>[] CreateReverseMap() {
47 50 var empty = new List<T>();
48 51 var rmap = new List<T>[m_nextCls];
49 52
50 53 for (int i = 0; i < rmap.Length; i++)
51 54 rmap[i] = empty;
52 55
53 56 foreach (var pair in m_map) {
54 57 var symbols = rmap[pair.Value];
55 58 if (symbols == null) {
56 59 symbols = new List<T>();
57 60 rmap[pair.Value] = symbols;
58 61 }
59 62
60 63 symbols.Add(pair.Key);
61 64 }
62 65
63 66 return rmap;
64 67 }
65 68
66 69 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
67 70 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
68 71 Safe.ArgumentNotNull(classes, "classes");
69 72
70 73 var rmap = CreateReverseMap();
71 74 var map = new int[rmap.Length];
72 75
73 76 foreach (var cls in classes) {
77 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
78 continue;
79
74 80 var symbols = new List<T>();
75 81 foreach (var id in cls) {
76 82 if (id < 0 || id >= rmap.Length)
77 83 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", id));
78 84 if (rmap[id] != null)
79 85 symbols.AddRange(rmap[id]);
80 86 }
81 87
82 88 var newId = newAlphabet.DefineClass(symbols);
83 89
84 90 foreach (var id in cls)
85 91 map[id] = newId;
86 92 }
87 93 }
88 94
89 95 public int Translate(T symobl) {
90 96 int cls;
91 97 return m_map.TryGetValue(symobl, out cls) ? cls : DFAConst.UNCLASSIFIED_INPUT;
92 98 }
93 99
94 100 public int Count {
95 101 get {
96 102 return m_nextCls;
97 103 }
98 104 }
99 105
100 106 #endregion
101 107 }
102 108 }
103 109
Show file before | Show file after | Hide comments
@@ -1,93 +1,95
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 5 using System.Text;
6 6 using System.Threading.Tasks;
7 7
8 8 namespace Implab.Automaton.RegularExpressions {
9 9 /// <summary>
10 10 /// Базовый абстрактный класс. Грамматика, позволяет формулировать выражения над алфавитом типа <c>char</c>.
11 11 /// </summary>
12 12 public abstract class Grammar<TSymbol, TTag> {
13 13
14 14 public abstract IAlphabetBuilder<TSymbol> Alphabet {
15 15 get;
16 16 }
17 17
18 18 public SymbolToken<TTag> UnclassifiedToken() {
19 19 return new SymbolToken<TTag>(DFAConst.UNCLASSIFIED_INPUT);
20 20 }
21 21
22 22 public void DefineAlphabet(IEnumerable<TSymbol> alphabet) {
23 23 Safe.ArgumentNotNull(alphabet, "alphabet");
24 24
25 25 foreach (var ch in alphabet)
26 26 Alphabet.DefineSymbol(ch);
27 27 }
28 28
29 29 public Token<TTag> SymbolToken(TSymbol symbol) {
30 30 return Token<TTag>.New(TranslateOrAdd(symbol));
31 31 }
32 32
33 33 public Token<TTag> SymbolToken(IEnumerable<TSymbol> symbols) {
34 34 Safe.ArgumentNotNull(symbols, "symbols");
35 35
36 36 return Token<TTag>.New(TranslateOrAdd(symbols).ToArray());
37 37 }
38 38
39 39 public Token<TTag> SymbolSetToken(params TSymbol[] set) {
40 40 return SymbolToken(set);
41 41 }
42 42
43 43 int TranslateOrAdd(TSymbol ch) {
44 44 var t = Alphabet.Translate(ch);
45 45 if (t == DFAConst.UNCLASSIFIED_INPUT)
46 46 t = Alphabet.DefineSymbol(ch);
47 47 return t;
48 48 }
49 49
50 50 IEnumerable<int> TranslateOrAdd(IEnumerable<TSymbol> symbols) {
51 51 return symbols.Distinct().Select(TranslateOrAdd);
52 52 }
53 53
54 54 int TranslateOrDie(TSymbol ch) {
55 55 var t = Alphabet.Translate(ch);
56 56 if (t == DFAConst.UNCLASSIFIED_INPUT)
57 57 throw new ApplicationException(String.Format("Symbol '{0}' is UNCLASSIFIED", ch));
58 58 return t;
59 59 }
60 60
61 61 IEnumerable<int> TranslateOrDie(IEnumerable<TSymbol> symbols) {
62 62 return symbols.Distinct().Select(TranslateOrDie);
63 63 }
64 64
65 65 public Token<TTag> SymbolTokenExcept(IEnumerable<TSymbol> symbols) {
66 66 Safe.ArgumentNotNull(symbols, "symbols");
67 67
68 68 return Token<TTag>.New( Enumerable.Range(0, Alphabet.Count).Except(TranslateOrDie(symbols)).ToArray() );
69 69 }
70 70
71 71 protected CDFADefinition BuildDFA(Token<TTag> lang) {
72 72 Safe.ArgumentNotNull(lang, "lang");
73 73
74 var dfa = new CDFADefinition(Alphabet);
74 var dfa = new RegularDFADefinition<TSymbol, TTag>(Alphabet, 0);
75
76 var table = new DFATransitionTable<TTag>();
75 77
76 78 var builder = new RegularDFABuilder<TTag>();
77 79
78 80 lang.Accept( builder );
79 81
80 builder.BuildDFA(dfa);
81 if (dfa.InitialStateIsFinal)
82 var initialState = builder.BuildDFA(table);
83 if (table.IsFinalState(initialState))
82 84 throw new ApplicationException("The specified language contains empty token");
83 85
84 86 return dfa.Optimize();
85 87 }
86 88
87 89
88 90
89 91 //protected abstract TGrammar CreateInstance();
90 92 }
91 93
92 94
93 95 }
Show file before | Show file after | Hide comments
@@ -1,179 +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 14 int m_idx = 0;
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 29 if (m_followpos.TryGetValue(pos, out set))
30 30 return set;
31 31 return m_followpos[pos] = new HashSet<int>();
32 32 }
33 33
34 34 bool Nullable(object n) {
35 35 if (n is EmptyToken<TTag> || n is StarToken<TTag>)
36 36 return true;
37 37 if (n is AltToken<TTag>)
38 38 return Nullable(((AltToken<TTag>)n).Left) || Nullable(((AltToken<TTag>)n).Right);
39 39 if (n is CatToken<TTag>)
40 40 return Nullable(((CatToken<TTag>)n).Left) && Nullable(((CatToken<TTag>)n).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(IDFADefinitionBuilder<TTag> dfa) {
125 public void BuildDFA(IDFATransitionTableBuilder<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 dfa.SetInitialState(initialState);
134 135
135 136 var tags = GetStateTags(m_firstpos);
136 137 if (tags != null && tags.Length > 0)
137 138 dfa.MarkFinalState(initialState, tags);
138 139
139 140 var inputMax = m_indexes.Values.Max();
140 141 var queue = new Queue<HashSet<int>>();
141 142
142 143 queue.Enqueue(m_firstpos);
143 144
144 145 while (queue.Count > 0) {
145 146 var state = queue.Dequeue();
146 147 var s1 = states.Translate(state);
147 148 Debug.Assert(s1 != DFAConst.UNCLASSIFIED_INPUT);
148 149
149 150 for (int a = 0; a <= inputMax; a++) {
150 151 var next = new HashSet<int>();
151 152 foreach (var p in state) {
152 153 if (m_indexes[p] == a) {
153 154 next.UnionWith(Followpos(p));
154 155 }
155 156 }
156 157 if (next.Count > 0) {
157 158 int s2 = states.Translate(next);
158 159 if (s2 == DFAConst.UNCLASSIFIED_INPUT) {
159 160 s2 = states.DefineSymbol(next);
160 161
161 162 tags = GetStateTags(next);
162 163 if (tags != null && tags.Length > 0)
163 164 dfa.MarkFinalState(s2, tags);
164 165
165 166 queue.Enqueue(next);
166 167 }
167 168 dfa.DefineTransition(s1, s2, a);
168 169 }
169 170 }
170 171 }
171 172 }
172 173
173 174 TTag[] GetStateTags(IEnumerable<int> state) {
174 175 Debug.Assert(state != null);
175 176 return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray();
176 177 }
177 178
178 179 }
179 180 }
Show file before | Show file after | Hide comments
@@ -1,259 +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 public int initialState;
20 21 }
21 22
22 23 Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>();
23 24
24 25 DFAStateDescriptior<TTag>[] m_states;
25 26 int[] m_alphabetMap;
27 int m_initialState;
26 28
27 29 protected DFAStateDescriptior<TTag> m_currentState;
28 30 int m_previewCode;
29 31
30 32 protected int m_tokenLen = 0;
31 33 protected int m_tokenOffset;
32 34
33 35 protected char[] m_buffer;
34 36 protected int m_bufferSize;
35 37 protected int m_pointer;
36 38
37 39 TextReader m_reader;
38 40 bool m_disposeReader;
39 41 int m_chunkSize = 1024; // 1k
40 42 int m_limit = 10 * 1024 * 1024; // 10Mb
41 43
42 protected Scanner(DFAStateDescriptior<TTag>[] states, int[] alphabet) {
44 protected Scanner(DFAStateDescriptior<TTag>[] states, int[] alphabet, int initialState) {
43 45 Safe.ArgumentNotEmpty(states, "states");
44 46 Safe.ArgumentNotNull(alphabet, "alphabet");
45 47
46 48 m_states = states;
47 49 m_alphabetMap = alphabet;
50 m_initialState = initialState;
48 51
49 52 Feed(new char[0]);
50 53 }
51 54
52 55 /// <summary>
53 56 /// Заполняет входными данными буффер.
54 57 /// </summary>
55 58 /// <param name="data">Данные для обработки.</param>
56 59 /// <remarks>Копирование данных не происходит, переданный массив используется в
57 60 /// качестве входного буффера.</remarks>
58 61 public void Feed(char[] data) {
59 62 Safe.ArgumentNotNull(data, "data");
60 63
61 64 Feed(data, data.Length);
62 65 }
63 66
64 67 /// <summary>
65 68 /// Заполняет буффур чтения входными данными.
66 69 /// </summary>
67 70 /// <param name="data">Данные для обработки.</param>
68 71 /// <param name="length">Длина данных для обработки.</param>
69 72 /// <remarks>Копирование данных не происходит, переданный массив используется в
70 73 /// качестве входного буффера.</remarks>
71 74 public void Feed(char[] data, int length) {
72 75 Safe.ArgumentNotNull(data, "data");
73 76 Safe.ArgumentInRange(length, 0, data.Length, "length");
74 77 AssertNotDisposed();
75 78
76 79 m_pointer = -1;
77 80 m_buffer = data;
78 81 m_bufferSize = length;
79 82 Shift();
80 83 }
81 84
82 85 public void Feed(TextReader reader, bool dispose) {
83 86 Safe.ArgumentNotNull(reader, "reader");
84 87 AssertNotDisposed();
85 88
86 89 if (m_reader != null && m_disposeReader)
87 90 m_reader.Dispose();
88 91
89 92 m_reader = reader;
90 93 m_disposeReader = dispose;
91 94 m_pointer = -1;
92 95 m_buffer = new char[m_chunkSize];
93 96 m_bufferSize = 0;
94 97 Shift();
95 98 }
96 99
97 100 /// <summary>
98 101 /// Получает текущий токен в виде строки.
99 102 /// </summary>
100 103 /// <returns></returns>
101 104 protected string GetTokenValue() {
102 105 return new String(m_buffer, m_tokenOffset, m_tokenLen);
103 106 }
104 107
105 108 /// <summary>
106 109 /// Метки текущего токена, которые были назначены в регулярном выражении.
107 110 /// </summary>
108 111 protected TTag[] TokenTags {
109 112 get {
110 113 return m_currentState.tag;
111 114 }
112 115 }
113 116
114 117 /// <summary>
115 118 /// Признак конца данных
116 119 /// </summary>
117 120 public bool EOF {
118 121 get {
119 122 return m_pointer >= m_bufferSize;
120 123 }
121 124 }
122 125
123 126 /// <summary>
124 127 /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена,
125 128 /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в
126 129 /// котором находится токен.
127 130 /// </summary>
128 131 /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns>
129 132 protected bool ReadTokenInternal() {
130 133 if (m_pointer >= m_bufferSize)
131 134 return false;
132 135
133 m_currentState = m_states[DFADefinition.INITIAL_STATE];
136 m_currentState = m_states[m_initialState];
134 137 m_tokenLen = 0;
135 138 m_tokenOffset = m_pointer;
136 139 int nextState;
137 140 do {
138 141 nextState = m_currentState.transitions[m_previewCode];
139 142 if (nextState == DFAConst.UNREACHABLE_STATE) {
140 143 if (m_currentState.final)
141 144 return true;
142 145 else
143 146 throw new ParserException(
144 147 String.Format(
145 148 "Unexpected symbol '{0}', at pos {1}",
146 149 m_buffer[m_pointer],
147 150 Position
148 151 )
149 152 );
150 153 } else {
151 154 m_currentState = m_states[nextState];
152 155 m_tokenLen++;
153 156 }
154 157
155 158 } while (Shift());
156 159
157 160 // END OF DATA
158 161 if (!m_currentState.final)
159 162 throw new ParserException("Unexpected end of data");
160 163
161 164 return true;
162 165 }
163 166
164 167
165 168 bool Shift() {
166 169 m_pointer++;
167 170
168 171 if (m_pointer >= m_bufferSize) {
169 172 if (!ReadNextChunk())
170 173 return false;
171 174 }
172 175
173 176 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
174 177
175 178 return true;
176 179 }
177 180
178 181 bool ReadNextChunk() {
179 182 if (m_reader == null)
180 183 return false;
181 184
182 185 // extend buffer if nesessary
183 186 if (m_pointer + m_chunkSize > m_buffer.Length) {
184 187 // trim unused buffer head
185 188 var size = m_tokenLen + m_chunkSize;
186 189 if (size >= m_limit)
187 190 throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit));
188 191 var temp = new char[size];
189 192 Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen);
190 193 m_pointer -= m_tokenOffset;
191 194 m_bufferSize -= m_tokenOffset;
192 195 m_tokenOffset = 0;
193 196 m_buffer = temp;
194 197 }
195 198
196 199 var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize);
197 200 if (read == 0)
198 201 return false;
199 202
200 203 m_bufferSize += read;
201 204
202 205 return true;
203 206 }
204 207
205 208 /// <summary>
206 209 /// Позиция сканнера во входном буфере
207 210 /// </summary>
208 211 public int Position {
209 212 get {
210 213 return m_pointer + 1;
211 214 }
212 215 }
213 216
214 217 /// <summary>
215 218 /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей
216 219 /// группировки.
217 220 /// </summary>
218 221 /// <param name="states">Таблица состояний нового ДКА</param>
219 222 /// <param name="alphabet">Таблица входных символов для нового ДКА</param>
220 protected void Switch(DFAStateDescriptior<TTag>[] states, int[] alphabet) {
223 protected void Switch(DFAStateDescriptior<TTag>[] states, int[] alphabet, int initialState) {
221 224 Safe.ArgumentNotNull(states, "dfa");
222 225
223 226 m_defs.Push(new ScannerConfig {
224 227 states = m_states,
225 alphabetMap = m_alphabetMap
228 alphabetMap = m_alphabetMap,
229 initialState = m_initialState
226 230 });
227 231
228 232 m_states = states;
229 233 m_alphabetMap = alphabet;
234 m_initialState = initialState;
230 235
231 236 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
232 237 }
233 238
234 239 /// <summary>
235 240 /// Восстанавливает предыдущей ДКА сканнера.
236 241 /// </summary>
237 242 protected void Restore() {
238 243 if (m_defs.Count == 0)
239 244 throw new InvalidOperationException();
240 245 var prev = m_defs.Pop();
241 246 m_states = prev.states;
242 247 m_alphabetMap = prev.alphabetMap;
248 m_initialState = prev.initialState;
243 249 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
244 250 }
245 251
246 252 protected override void Dispose(bool disposing) {
247 253 if (disposing) {
248 254 if (m_reader != null && m_disposeReader)
249 255 m_reader.Dispose();
250 256 m_buffer = null;
251 257 m_bufferSize = 0;
252 258 m_pointer = 0;
253 259 m_tokenLen = 0;
254 260 m_tokenOffset = 0;
255 261 }
256 262 base.Dispose(disposing);
257 263 }
258 264 }
259 265 }
Show file before | Show file after | Hide comments
@@ -1,269 +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 <ReleaseVersion>0.2</ReleaseVersion>
12 <ProductVersion>8.0.30703</ProductVersion>
13 <SchemaVersion>2.0</SchemaVersion>
11 14 </PropertyGroup>
12 15 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
13 16 <DebugSymbols>true</DebugSymbols>
14 17 <DebugType>full</DebugType>
15 18 <Optimize>false</Optimize>
16 19 <OutputPath>bin\Debug</OutputPath>
17 20 <DefineConstants>TRACE;DEBUG;</DefineConstants>
18 21 <ErrorReport>prompt</ErrorReport>
19 22 <WarningLevel>4</WarningLevel>
20 23 <ConsolePause>false</ConsolePause>
21 24 <RunCodeAnalysis>true</RunCodeAnalysis>
22 25 </PropertyGroup>
23 26 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
24 27 <DebugType>full</DebugType>
25 28 <Optimize>true</Optimize>
26 29 <OutputPath>bin\Release</OutputPath>
27 30 <ErrorReport>prompt</ErrorReport>
28 31 <WarningLevel>4</WarningLevel>
29 32 <ConsolePause>false</ConsolePause>
30 33 </PropertyGroup>
31 34 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug 4.5|AnyCPU' ">
32 35 <DebugSymbols>true</DebugSymbols>
33 36 <DebugType>full</DebugType>
34 37 <Optimize>false</Optimize>
35 38 <OutputPath>bin\Debug</OutputPath>
36 39 <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants>
37 40 <ErrorReport>prompt</ErrorReport>
38 41 <WarningLevel>4</WarningLevel>
39 42 <RunCodeAnalysis>true</RunCodeAnalysis>
40 43 <ConsolePause>false</ConsolePause>
41 44 </PropertyGroup>
42 45 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release 4.5|AnyCPU' ">
43 46 <Optimize>true</Optimize>
44 47 <OutputPath>bin\Release</OutputPath>
45 48 <ErrorReport>prompt</ErrorReport>
46 49 <WarningLevel>4</WarningLevel>
47 50 <ConsolePause>false</ConsolePause>
48 51 <DefineConstants>NET_4_5</DefineConstants>
49 52 </PropertyGroup>
50 53 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'DebugMono|AnyCPU' ">
51 54 <DebugSymbols>true</DebugSymbols>
52 55 <DebugType>full</DebugType>
53 56 <Optimize>false</Optimize>
54 57 <OutputPath>bin\Debug</OutputPath>
55 58 <DefineConstants>TRACE;DEBUG;NET_4_5;MONO</DefineConstants>
56 59 <ErrorReport>prompt</ErrorReport>
57 60 <WarningLevel>4</WarningLevel>
58 61 <RunCodeAnalysis>true</RunCodeAnalysis>
59 62 <ConsolePause>false</ConsolePause>
60 63 </PropertyGroup>
61 64 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'ReleaseMono|AnyCPU' ">
62 65 <Optimize>true</Optimize>
63 66 <OutputPath>bin\Release</OutputPath>
64 67 <DefineConstants>NET_4_5;MONO;</DefineConstants>
65 68 <ErrorReport>prompt</ErrorReport>
66 69 <WarningLevel>4</WarningLevel>
67 70 <ConsolePause>false</ConsolePause>
68 71 </PropertyGroup>
69 72 <ItemGroup>
70 73 <Reference Include="System" />
71 74 <Reference Include="System.Xml" />
72 75 <Reference Include="mscorlib" />
73 76 </ItemGroup>
74 77 <ItemGroup>
75 78 <Compile Include="CustomEqualityComparer.cs" />
76 79 <Compile Include="Diagnostics\ConsoleTraceListener.cs" />
77 80 <Compile Include="Diagnostics\EventText.cs" />
78 81 <Compile Include="Diagnostics\LogChannel.cs" />
79 82 <Compile Include="Diagnostics\LogicalOperation.cs" />
80 83 <Compile Include="Diagnostics\TextFileListener.cs" />
81 84 <Compile Include="Diagnostics\TraceLog.cs" />
82 85 <Compile Include="Diagnostics\TraceEvent.cs" />
83 86 <Compile Include="Diagnostics\TraceEventType.cs" />
84 87 <Compile Include="ICancellable.cs" />
85 88 <Compile Include="IProgressHandler.cs" />
86 89 <Compile Include="IProgressNotifier.cs" />
87 90 <Compile Include="IPromiseT.cs" />
88 91 <Compile Include="IPromise.cs" />
89 92 <Compile Include="IServiceLocator.cs" />
90 93 <Compile Include="ITaskController.cs" />
91 94 <Compile Include="Parallels\DispatchPool.cs" />
92 95 <Compile Include="Parallels\ArrayTraits.cs" />
93 96 <Compile Include="Parallels\MTQueue.cs" />
94 97 <Compile Include="Parallels\WorkerPool.cs" />
95 98 <Compile Include="ProgressInitEventArgs.cs" />
96 99 <Compile Include="Properties\AssemblyInfo.cs" />
97 100 <Compile Include="Parallels\AsyncPool.cs" />
98 101 <Compile Include="Safe.cs" />
99 102 <Compile Include="ValueEventArgs.cs" />
100 103 <Compile Include="PromiseExtensions.cs" />
101 104 <Compile Include="SyncContextPromise.cs" />
102 105 <Compile Include="Diagnostics\OperationContext.cs" />
103 106 <Compile Include="Diagnostics\TraceContext.cs" />
104 107 <Compile Include="Diagnostics\LogEventArgs.cs" />
105 108 <Compile Include="Diagnostics\LogEventArgsT.cs" />
106 109 <Compile Include="Diagnostics\Extensions.cs" />
107 110 <Compile Include="PromiseEventType.cs" />
108 111 <Compile Include="Parallels\AsyncQueue.cs" />
109 112 <Compile Include="PromiseT.cs" />
110 113 <Compile Include="IDeferred.cs" />
111 114 <Compile Include="IDeferredT.cs" />
112 115 <Compile Include="Promise.cs" />
113 116 <Compile Include="PromiseTransientException.cs" />
114 117 <Compile Include="Parallels\Signal.cs" />
115 118 <Compile Include="Parallels\SharedLock.cs" />
116 119 <Compile Include="Diagnostics\ILogWriter.cs" />
117 120 <Compile Include="Diagnostics\ListenerBase.cs" />
118 121 <Compile Include="Parallels\BlockingQueue.cs" />
119 122 <Compile Include="AbstractEvent.cs" />
120 123 <Compile Include="AbstractPromise.cs" />
121 124 <Compile Include="AbstractPromiseT.cs" />
122 125 <Compile Include="FuncTask.cs" />
123 126 <Compile Include="FuncTaskBase.cs" />
124 127 <Compile Include="FuncTaskT.cs" />
125 128 <Compile Include="ActionChainTaskBase.cs" />
126 129 <Compile Include="ActionChainTask.cs" />
127 130 <Compile Include="ActionChainTaskT.cs" />
128 131 <Compile Include="FuncChainTaskBase.cs" />
129 132 <Compile Include="FuncChainTask.cs" />
130 133 <Compile Include="FuncChainTaskT.cs" />
131 134 <Compile Include="ActionTaskBase.cs" />
132 135 <Compile Include="ActionTask.cs" />
133 136 <Compile Include="ActionTaskT.cs" />
134 137 <Compile Include="ICancellationToken.cs" />
135 138 <Compile Include="SuccessPromise.cs" />
136 139 <Compile Include="SuccessPromiseT.cs" />
137 140 <Compile Include="PromiseAwaiterT.cs" />
138 141 <Compile Include="PromiseAwaiter.cs" />
139 142 <Compile Include="Components\ComponentContainer.cs" />
140 143 <Compile Include="Components\Disposable.cs" />
141 144 <Compile Include="Components\DisposablePool.cs" />
142 145 <Compile Include="Components\ObjectPool.cs" />
143 146 <Compile Include="Components\ServiceLocator.cs" />
144 147 <Compile Include="Components\IInitializable.cs" />
145 148 <Compile Include="TaskController.cs" />
146 149 <Compile Include="Components\App.cs" />
147 150 <Compile Include="Components\IRunnable.cs" />
148 151 <Compile Include="Components\ExecutionState.cs" />
149 152 <Compile Include="Components\RunnableComponent.cs" />
150 153 <Compile Include="Components\IFactory.cs" />
151 <Compile Include="Automaton\CDFADefinition.cs" />
152 154 <Compile Include="Automaton\DFAStateDescriptor.cs" />
153 155 <Compile Include="Automaton\DFAutomaton.cs" />
154 <Compile Include="Automaton\EDFADefinition.cs" />
155 156 <Compile Include="Automaton\EnumAlphabet.cs" />
156 157 <Compile Include="Automaton\IAlphabet.cs" />
157 <Compile Include="Automaton\IDFADefinition.cs" />
158 158 <Compile Include="Automaton\ParserException.cs" />
159 159 <Compile Include="Automaton\Scanner.cs" />
160 <Compile Include="Automaton\DFADefinition.cs" />
161 160 <Compile Include="Automaton\IndexedAlphabetBase.cs" />
162 <Compile Include="Automaton\CharAlphabet.cs" />
163 161 <Compile Include="Automaton\IAlphabetBuilder.cs" />
164 <Compile Include="Automaton\IDFADefinitionBuilder.cs" />
165 162 <Compile Include="Automaton\RegularExpressions\AltToken.cs" />
166 163 <Compile Include="Automaton\RegularExpressions\BinaryToken.cs" />
167 164 <Compile Include="Automaton\RegularExpressions\CatToken.cs" />
168 165 <Compile Include="Automaton\DFAConst.cs" />
169 166 <Compile Include="Automaton\RegularExpressions\Grammar.cs" />
170 167 <Compile Include="Automaton\RegularExpressions\StarToken.cs" />
171 168 <Compile Include="Automaton\RegularExpressions\SymbolToken.cs" />
172 169 <Compile Include="Automaton\RegularExpressions\EmptyToken.cs" />
173 170 <Compile Include="Automaton\RegularExpressions\EndToken.cs" />
174 171 <Compile Include="Automaton\RegularExpressions\Token.cs" />
175 172 <Compile Include="Automaton\RegularExpressions\IVisitor.cs" />
176 173 <Compile Include="Automaton\AutomatonTransition.cs" />
177 <Compile Include="Automaton\ByteAlphabet.cs" />
178 174 <Compile Include="Automaton\RegularExpressions\RegularDFABuilder.cs" />
179 175 <Compile Include="Formats\JSON\JSONElementContext.cs" />
180 176 <Compile Include="Formats\JSON\JSONElementType.cs" />
181 177 <Compile Include="Formats\JSON\JSONGrammar.cs" />
182 178 <Compile Include="Formats\JSON\JSONParser.cs" />
183 179 <Compile Include="Formats\JSON\JSONScanner.cs" />
184 180 <Compile Include="Formats\JSON\JsonTokenType.cs" />
185 181 <Compile Include="Formats\JSON\JSONWriter.cs" />
186 182 <Compile Include="Formats\JSON\JSONXmlReader.cs" />
187 183 <Compile Include="Formats\JSON\JSONXmlReaderOptions.cs" />
188 184 <Compile Include="Formats\JSON\StringTranslator.cs" />
189 185 <Compile Include="Automaton\MapAlphabet.cs" />
190 186 <Compile Include="Automaton\DummyAlphabet.cs" />
187 <Compile Include="Automaton\DFATransitionTable.cs" />
188 <Compile Include="Automaton\IDFATransitionTableBuilder.cs" />
189 <Compile Include="Automaton\IDFATransitionTable.cs" />
190 <Compile Include="Automaton\RegularExpressions\RegularDFADefinition.cs" />
191 <Compile Include="Formats\CharAlphabet.cs" />
192 <Compile Include="Formats\ByteAlphabet.cs" />
191 193 </ItemGroup>
192 194 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
193 195 <ItemGroup />
194 196 <ProjectExtensions>
195 197 <MonoDevelop>
196 198 <Properties>
197 199 <Policies>
198 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" />
199 201 <TextStylePolicy FileWidth="120" EolMarker="Unix" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
200 202 <DotNetNamingPolicy DirectoryNamespaceAssociation="PrefixedHierarchical" ResourceNamePolicy="MSBuild" />
201 203 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
202 204 <XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
203 205 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
204 206 <NameConventionPolicy>
205 207 <Rules>
206 208 <NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
207 209 <NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
208 210 <NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
209 211 <RequiredPrefixes>
210 212 <String>I</String>
211 213 </RequiredPrefixes>
212 214 </NamingRule>
213 215 <NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
214 216 <RequiredSuffixes>
215 217 <String>Attribute</String>
216 218 </RequiredSuffixes>
217 219 </NamingRule>
218 220 <NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
219 221 <RequiredSuffixes>
220 222 <String>EventArgs</String>
221 223 </RequiredSuffixes>
222 224 </NamingRule>
223 225 <NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
224 226 <RequiredSuffixes>
225 227 <String>Exception</String>
226 228 </RequiredSuffixes>
227 229 </NamingRule>
228 230 <NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
229 231 <NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
230 232 <NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
231 233 <NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
232 234 <NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
233 235 <RequiredPrefixes>
234 236 <String>m_</String>
235 237 </RequiredPrefixes>
236 238 </NamingRule>
237 239 <NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True">
238 240 <RequiredPrefixes>
239 241 <String>_</String>
240 242 </RequiredPrefixes>
241 243 </NamingRule>
242 244 <NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
243 245 <RequiredPrefixes>
244 246 <String>m_</String>
245 247 </RequiredPrefixes>
246 248 </NamingRule>
247 249 <NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="AllUpper" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
248 250 <NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
249 251 <NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
250 252 <NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
251 253 <NamingRule Name="Parameters" AffectedEntity="Parameter, LocalVariable" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
252 254 <NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
253 255 <RequiredPrefixes>
254 256 <String>T</String>
255 257 </RequiredPrefixes>
256 258 </NamingRule>
257 259 </Rules>
258 260 </NameConventionPolicy>
259 261 </Policies>
260 262 </Properties>
261 263 </MonoDevelop>
262 264 </ProjectExtensions>
263 265 <ItemGroup>
264 266 <Folder Include="Components\" />
265 267 <Folder Include="Automaton\RegularExpressions\" />
266 268 <Folder Include="Formats\" />
267 269 <Folder Include="Formats\JSON\" />
268 270 </ItemGroup>
269 271 </Project> No newline at end of file
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
Show file before | Show file after | Hide comments
1 NO CONTENT: file was removed
General Comments 0
You need to be logged in to leave comments. Login now