Mercurial > pub > ImplabNet

comparison Implab/Automaton/Scanner.cs @ 162:0526412bbb26 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DFA refactoring
author cin
date Wed, 24 Feb 2016 08:39:53 +0300
parents
children ec35731ae299
comparison
equal deleted inserted replaced
161:2a8466f0cb8a 162:0526412bbb26
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.IO;
5 using Implab.Components;
6
7 namespace Implab.Automaton {
8 /// <summary>
9 /// Базовый класс для разбора потока входных символов на токены.
10 /// </summary>
11 /// <remarks>
12 /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два
13 /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения
14 /// конца токена и допустимости текущего символа.
15 /// </remarks>
16 public abstract class Scanner<TTag> : Disposable {
17 struct ScannerConfig {
18 public DFAStateDescriptior<TTag>[] states;
19 public int[] alphabetMap;
20 }
21
22 Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>();
23
24 DFAStateDescriptior<TTag>[] m_states;
25 int[] m_alphabetMap;
26
27 protected DFAStateDescriptior<TTag> m_currentState;
28 int m_previewCode;
29
30 protected int m_tokenLen = 0;
31 protected int m_tokenOffset;
32
33 protected char[] m_buffer;
34 protected int m_bufferSize;
35 protected int m_pointer;
36
37 TextReader m_reader;
38 bool m_disposeReader;
39 int m_chunkSize = 1024; // 1k
40 int m_limit = 10 * 1024 * 1024; // 10Mb
41
42 protected Scanner(DFAStateDescriptior<TTag>[] states, int[] alphabet) {
43 Safe.ArgumentNotEmpty(states, "states");
44 Safe.ArgumentNotNull(alphabet, "alphabet");
45
46 m_states = states;
47 m_alphabetMap = alphabet;
48
49 Feed(new char[0]);
50 }
51
52 /// <summary>
53 /// Заполняет входными данными буффер.
54 /// </summary>
55 /// <param name="data">Данные для обработки.</param>
56 /// <remarks>Копирование данных не происходит, переданный массив используется в
57 /// качестве входного буффера.</remarks>
58 public void Feed(char[] data) {
59 Safe.ArgumentNotNull(data, "data");
60
61 Feed(data, data.Length);
62 }
63
64 /// <summary>
65 /// Заполняет буффур чтения входными данными.
66 /// </summary>
67 /// <param name="data">Данные для обработки.</param>
68 /// <param name="length">Длина данных для обработки.</param>
69 /// <remarks>Копирование данных не происходит, переданный массив используется в
70 /// качестве входного буффера.</remarks>
71 public void Feed(char[] data, int length) {
72 Safe.ArgumentNotNull(data, "data");
73 Safe.ArgumentInRange(length, 0, data.Length, "length");
74 AssertNotDisposed();
75
76 m_pointer = -1;
77 m_buffer = data;
78 m_bufferSize = length;
79 Shift();
80 }
81
82 public void Feed(TextReader reader, bool dispose) {
83 Safe.ArgumentNotNull(reader, "reader");
84 AssertNotDisposed();
85
86 if (m_reader != null && m_disposeReader)
87 m_reader.Dispose();
88
89 m_reader = reader;
90 m_disposeReader = dispose;
91 m_pointer = -1;
92 m_buffer = new char[m_chunkSize];
93 m_bufferSize = 0;
94 Shift();
95 }
96
97 /// <summary>
98 /// Получает текущий токен в виде строки.
99 /// </summary>
100 /// <returns></returns>
101 protected string GetTokenValue() {
102 return new String(m_buffer, m_tokenOffset, m_tokenLen);
103 }
104
105 /// <summary>
106 /// Метки текущего токена, которые были назначены в регулярном выражении.
107 /// </summary>
108 protected TTag[] TokenTags {
109 get {
110 return m_currentState.tag;
111 }
112 }
113
114 /// <summary>
115 /// Признак конца данных
116 /// </summary>
117 public bool EOF {
118 get {
119 return m_pointer >= m_bufferSize;
120 }
121 }
122
123 /// <summary>
124 /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена,
125 /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в
126 /// котором находится токен.
127 /// </summary>
128 /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns>
129 protected bool ReadTokenInternal() {
130 if (m_pointer >= m_bufferSize)
131 return false;
132
133 m_currentState = m_states[DFADefinition.INITIAL_STATE];
134 m_tokenLen = 0;
135 m_tokenOffset = m_pointer;
136 int nextState;
137 do {
138 nextState = m_currentState.transitions[m_previewCode];
139 if (nextState == DFAConst.UNREACHABLE_STATE) {
140 if (m_currentState.final)
141 return true;
142 else
143 throw new ParserException(
144 String.Format(
145 "Unexpected symbol '{0}', at pos {1}",
146 m_buffer[m_pointer],
147 Position
148 )
149 );
150 } else {
151 m_currentState = m_states[nextState];
152 m_tokenLen++;
153 }
154
155 } while (Shift());
156
157 // END OF DATA
158 if (!m_currentState.final)
159 throw new ParserException("Unexpected end of data");
160
161 return true;
162 }
163
164
165 bool Shift() {
166 m_pointer++;
167
168 if (m_pointer >= m_bufferSize) {
169 if (!ReadNextChunk())
170 return false;
171 }
172
173 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
174
175 return true;
176 }
177
178 bool ReadNextChunk() {
179 if (m_reader == null)
180 return false;
181
182 // extend buffer if nesessary
183 if (m_pointer + m_chunkSize > m_buffer.Length) {
184 // trim unused buffer head
185 var size = m_tokenLen + m_chunkSize;
186 if (size >= m_limit)
187 throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit));
188 var temp = new char[size];
189 Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen);
190 m_pointer -= m_tokenOffset;
191 m_bufferSize -= m_tokenOffset;
192 m_tokenOffset = 0;
193 m_buffer = temp;
194 }
195
196 var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize);
197 if (read == 0)
198 return false;
199
200 m_bufferSize += read;
201
202 return true;
203 }
204
205 /// <summary>
206 /// Позиция сканнера во входном буфере
207 /// </summary>
208 public int Position {
209 get {
210 return m_pointer + 1;
211 }
212 }
213
214 /// <summary>
215 /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей
216 /// группировки.
217 /// </summary>
218 /// <param name="states">Таблица состояний нового ДКА</param>
219 /// <param name="alphabet">Таблица входных символов для нового ДКА</param>
220 protected void Switch(DFAStateDescriptior<TTag>[] states, int[] alphabet) {
221 Safe.ArgumentNotNull(states, "dfa");
222
223 m_defs.Push(new ScannerConfig {
224 states = m_states,
225 alphabetMap = m_alphabetMap
226 });
227
228 m_states = states;
229 m_alphabetMap = alphabet;
230
231 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
232 }
233
234 /// <summary>
235 /// Восстанавливает предыдущей ДКА сканнера.
236 /// </summary>
237 protected void Restore() {
238 if (m_defs.Count == 0)
239 throw new InvalidOperationException();
240 var prev = m_defs.Pop();
241 m_states = prev.states;
242 m_alphabetMap = prev.alphabetMap;
243 m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
244 }
245
246 protected override void Dispose(bool disposing) {
247 if (disposing) {
248 if (m_reader != null && m_disposeReader)
249 m_reader.Dispose();
250 m_buffer = null;
251 m_bufferSize = 0;
252 m_pointer = 0;
253 m_tokenLen = 0;
254 m_tokenOffset = 0;
255 }
256 base.Dispose(disposing);
257 }
258 }
259 }