Mercurial > pub > ImplabNet
changeset 174:983df35b3ca1 ref20160224
sync
| author | cin |
|---|---|
| date | Fri, 18 Mar 2016 18:10:30 +0300 |
| parents | ecfece82ca11 |
| children | 96a89dcb4060 |
| files | Implab/Automaton/Scanner.cs Implab/Formats/BufferScanner.cs Implab/Formats/TextScanner.cs |
| diffstat | 3 files changed, 295 insertions(+), 387 deletions(-) [+] |
line wrap: on
line diff
--- a/Implab/Automaton/Scanner.cs Tue Mar 15 02:11:06 2016 +0300 +++ b/Implab/Automaton/Scanner.cs Fri Mar 18 18:10:30 2016 +0300 @@ -1,255 +1,255 @@ -using Implab; -using System; -using System.Collections.Generic; -using System.IO; -using Implab.Components; -using Implab.Automaton.RegularExpressions; - -namespace Implab.Automaton { - /// <summary> - /// Базовый класс для разбора потока входных символов на токены. - /// </summary> - /// <remarks> - /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два - /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения - /// конца токена и допустимости текущего символа. - /// </remarks> - public abstract class Scanner<TTag> : Disposable { - protected struct ScannerConfig { - public readonly DFAStateDescriptor<TTag>[] states; - public readonly int[] alphabet; - public readonly int initialState; - - public ScannerConfig(DFAStateDescriptor<TTag>[] states, int[] alphabet, int initialState) { - this.initialState = initialState; - this.alphabet = alphabet; - this.states = states; - } - } - - Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>(); - - ScannerConfig m_config; - - protected DFAStateDescriptor<TTag> m_currentState; - int m_previewCode; - - protected int m_tokenLen; - protected int m_tokenOffset; - - protected char[] m_buffer; - protected int m_bufferSize; - protected int m_pointer; - - TextReader m_reader; - bool m_disposeReader; - int m_chunkSize = 1024; // 1k - int m_limit = 10 * 1024 * 1024; // 10Mb - - protected Scanner(ScannerConfig config) { - Safe.ArgumentNotEmpty(config.states, "config.states"); - Safe.ArgumentNotNull(config.alphabet, "config.alphabet"); - - m_config = config; - } - - /// <summary> - /// Заполняет входными данными буффер. - /// </summary> - /// <param name="data">Данные для обработки.</param> - /// <remarks>Копирование данных не происходит, переданный массив используется в - /// качестве входного буффера.</remarks> - public void Feed(char[] data) { - Safe.ArgumentNotNull(data, "data"); - - Feed(data, data.Length); - } - - /// <summary> - /// Заполняет буффур чтения входными данными. - /// </summary> - /// <param name="data">Данные для обработки.</param> - /// <param name="length">Длина данных для обработки.</param> - /// <remarks>Копирование данных не происходит, переданный массив используется в - /// качестве входного буффера.</remarks> - public void Feed(char[] data, int length) { - Safe.ArgumentNotNull(data, "data"); - Safe.ArgumentInRange(length, 0, data.Length, "length"); - AssertNotDisposed(); - - m_pointer = -1; - m_buffer = data; - m_bufferSize = length; - Shift(); - } - - public void Feed(TextReader reader, bool dispose) { - Safe.ArgumentNotNull(reader, "reader"); - AssertNotDisposed(); - - if (m_reader != null && m_disposeReader) - m_reader.Dispose(); - - m_reader = reader; - m_disposeReader = dispose; - m_pointer = -1; - m_buffer = new char[m_chunkSize]; - m_bufferSize = 0; - Shift(); - } - - /// <summary> - /// Получает текущий токен в виде строки. - /// </summary> - /// <returns></returns> - protected string GetTokenValue() { - return new String(m_buffer, m_tokenOffset, m_tokenLen); - } - - /// <summary> - /// Метки текущего токена, которые были назначены в регулярном выражении. - /// </summary> - protected TTag[] TokenTags { - get { - return m_currentState.tags; - } - } - - /// <summary> - /// Признак конца данных - /// </summary> - public bool EOF { - get { - return m_pointer >= m_bufferSize; - } - } - - /// <summary> - /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена, - /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в - /// котором находится токен. - /// </summary> - /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns> - protected bool ReadTokenInternal() { - if (m_pointer >= m_bufferSize) - return false; - - m_currentState = m_config.states[m_config.initialState]; - m_tokenLen = 0; - m_tokenOffset = m_pointer; - int nextState; - do { - nextState = m_currentState.transitions[m_previewCode]; - if (nextState == DFAConst.UNREACHABLE_STATE) { - if (m_currentState.final) - return true; - - throw new ParserException( - String.Format( - "Unexpected symbol '{0}', at pos {1}", - m_buffer[m_pointer], - Position - ) - ); - } - m_currentState = m_config.states[nextState]; - m_tokenLen++; - - } while (Shift()); - - // END OF DATA - if (!m_currentState.final) - throw new ParserException("Unexpected end of data"); - - return true; - } - - - bool Shift() { - m_pointer++; - - if (m_pointer >= m_bufferSize) { - if (!ReadNextChunk()) - return false; - } - - m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; - - return true; - } - - bool ReadNextChunk() { - if (m_reader == null) - return false; - - // extend buffer if nesessary - if (m_pointer + m_chunkSize > m_buffer.Length) { - // trim unused buffer head - var size = m_tokenLen + m_chunkSize; - if (size >= m_limit) - throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit)); - var temp = new char[size]; - Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen); - m_pointer -= m_tokenOffset; - m_bufferSize -= m_tokenOffset; - m_tokenOffset = 0; - m_buffer = temp; - } - - var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize); - if (read == 0) - return false; - - m_bufferSize += read; - - return true; - } - - /// <summary> - /// Позиция сканнера во входном буфере - /// </summary> - public int Position { - get { - return m_pointer + 1; - } - } - - /// <summary> - /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей - /// группировки. - /// </summary> - /// <param name = "config"></param> - protected void Switch(ScannerConfig config) { - Safe.ArgumentNotNull(config.states, "config.states"); - - m_defs.Push(m_config); - m_config = config; - - m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; - } - - /// <summary> - /// Восстанавливает предыдущей ДКА сканнера. - /// </summary> - protected void Restore() { - if (m_defs.Count == 0) - throw new InvalidOperationException(); - m_config = m_defs.Pop(); - - m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; - } - - protected override void Dispose(bool disposing) { - if (disposing) { - if (m_reader != null && m_disposeReader) - m_reader.Dispose(); - m_buffer = null; - m_bufferSize = 0; - m_pointer = 0; - m_tokenLen = 0; - m_tokenOffset = 0; - } - base.Dispose(disposing); - } - } -} +using Implab; +using System; +using System.Collections.Generic; +using System.IO; +using Implab.Components; +using Implab.Automaton.RegularExpressions; + +namespace Implab.Automaton { + /// <summary> + /// Базовый класс для разбора потока входных символов на токены. + /// </summary> + /// <remarks> + /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два + /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения + /// конца токена и допустимости текущего символа. + /// </remarks> + public abstract class Scanner<TTag> : Disposable { + protected struct ScannerConfig { + public readonly DFAStateDescriptor<TTag>[] states; + public readonly int[] alphabet; + public readonly int initialState; + + public ScannerConfig(DFAStateDescriptor<TTag>[] states, int[] alphabet, int initialState) { + this.initialState = initialState; + this.alphabet = alphabet; + this.states = states; + } + } + + Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>(); + + ScannerConfig m_config; + + protected DFAStateDescriptor<TTag> m_currentState; + int m_previewCode; + + protected int m_tokenLen; + protected int m_tokenOffset; + + protected char[] m_buffer; + protected int m_bufferSize; + protected int m_pointer; + + TextReader m_reader; + bool m_disposeReader; + int m_chunkSize = 1024; // 1k + int m_limit = 10 * 1024 * 1024; // 10Mb + + protected Scanner(ScannerConfig config) { + Safe.ArgumentNotEmpty(config.states, "config.states"); + Safe.ArgumentNotNull(config.alphabet, "config.alphabet"); + + m_config = config; + } + + /// <summary> + /// Заполняет входными данными буффер. + /// </summary> + /// <param name="data">Данные для обработки.</param> + /// <remarks>Копирование данных не происходит, переданный массив используется в + /// качестве входного буффера.</remarks> + public void Feed(char[] data) { + Safe.ArgumentNotNull(data, "data"); + + Feed(data, data.Length); + } + + /// <summary> + /// Заполняет буффур чтения входными данными. + /// </summary> + /// <param name="data">Данные для обработки.</param> + /// <param name="length">Длина данных для обработки.</param> + /// <remarks>Копирование данных не происходит, переданный массив используется в + /// качестве входного буффера.</remarks> + public void Feed(char[] data, int length) { + Safe.ArgumentNotNull(data, "data"); + Safe.ArgumentInRange(length, 0, data.Length, "length"); + AssertNotDisposed(); + + m_pointer = -1; + m_buffer = data; + m_bufferSize = length; + Shift(); + } + + public void Feed(TextReader reader, bool dispose) { + Safe.ArgumentNotNull(reader, "reader"); + AssertNotDisposed(); + + if (m_reader != null && m_disposeReader) + m_reader.Dispose(); + + m_reader = reader; + m_disposeReader = dispose; + m_pointer = -1; + m_buffer = new char[m_chunkSize]; + m_bufferSize = 0; + Shift(); + } + + /// <summary> + /// Получает текущий токен в виде строки. + /// </summary> + /// <returns></returns> + protected string GetTokenValue() { + return new String(m_buffer, m_tokenOffset, m_tokenLen); + } + + /// <summary> + /// Метки текущего токена, которые были назначены в регулярном выражении. + /// </summary> + protected TTag[] TokenTags { + get { + return m_currentState.tags; + } + } + + /// <summary> + /// Признак конца данных + /// </summary> + public bool EOF { + get { + return m_pointer >= m_bufferSize; + } + } + + /// <summary> + /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена, + /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в + /// котором находится токен. + /// </summary> + /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns> + protected bool ReadTokenInternal() { + if (m_pointer >= m_bufferSize) + return false; + + m_currentState = m_config.states[m_config.initialState]; + m_tokenLen = 0; + m_tokenOffset = m_pointer; + int nextState; + do { + nextState = m_currentState.transitions[m_previewCode]; + if (nextState == DFAConst.UNREACHABLE_STATE) { + if (m_currentState.final) + return true; + + throw new ParserException( + String.Format( + "Unexpected symbol '{0}', at pos {1}", + m_buffer[m_pointer], + Position + ) + ); + } + m_currentState = m_config.states[nextState]; + m_tokenLen++; + + } while (Shift()); + + // END OF DATA + if (!m_currentState.final) + throw new ParserException("Unexpected end of data"); + + return true; + } + + + bool Shift() { + m_pointer++; + + if (m_pointer >= m_bufferSize) { + if (!ReadNextChunk()) + return false; + } + + m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; + + return true; + } + + bool ReadNextChunk() { + if (m_reader == null) + return false; + + // extend buffer if nesessary + if (m_pointer + m_chunkSize > m_buffer.Length) { + // trim unused buffer head + var size = m_tokenLen + m_chunkSize; + if (size >= m_limit) + throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit)); + var temp = new char[size]; + Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen); + m_pointer -= m_tokenOffset; + m_bufferSize -= m_tokenOffset; + m_tokenOffset = 0; + m_buffer = temp; + } + + var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize); + if (read == 0) + return false; + + m_bufferSize += read; + + return true; + } + + /// <summary> + /// Позиция сканнера во входном буфере + /// </summary> + public int Position { + get { + return m_pointer + 1; + } + } + + /// <summary> + /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей + /// группировки. + /// </summary> + /// <param name = "config"></param> + protected void Switch(ScannerConfig config) { + Safe.ArgumentNotNull(config.states, "config.states"); + + m_defs.Push(m_config); + m_config = config; + + m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; + } + + /// <summary> + /// Восстанавливает предыдущей ДКА сканнера. + /// </summary> + protected void Restore() { + if (m_defs.Count == 0) + throw new InvalidOperationException(); + m_config = m_defs.Pop(); + + m_previewCode = m_config.alphabet[m_buffer[m_pointer]]; + } + + protected override void Dispose(bool disposing) { + if (disposing) { + if (m_reader != null && m_disposeReader) + m_reader.Dispose(); + m_buffer = null; + m_bufferSize = 0; + m_pointer = 0; + m_tokenLen = 0; + m_tokenOffset = 0; + } + base.Dispose(disposing); + } + } +}
--- a/Implab/Formats/BufferScanner.cs Tue Mar 15 02:11:06 2016 +0300 +++ b/Implab/Formats/BufferScanner.cs Fri Mar 18 18:10:30 2016 +0300 @@ -1,125 +1,45 @@ using System; using Implab.Automaton.RegularExpressions; using Implab.Automaton; +using System.Diagnostics; namespace Implab.Formats { public struct BufferScanner<TTag> { - char[] m_buffer; - int m_offset; - int m_position; - int m_hi; - - readonly int m_chunk; - readonly int m_limit; - readonly DFAStateDescriptor<TTag>[] m_dfa; int m_state; + int m_pos; - public BufferScanner(DFAStateDescriptor<TTag>[] dfa, int initialState, int chunk, int limit) { + public BufferScanner(DFAStateDescriptor<TTag>[] dfa, int initialState) { m_dfa = dfa; m_state = initialState; - m_chunk = chunk; - m_limit = limit; - m_buffer = null; - m_offset = 0; - m_position = 0; - m_hi = 0; - } - - public char[] Buffer { - get { - return m_buffer; - } - } - - public int HiMark { - get { - return m_hi; - } } public int Position { - get { - return m_position; - } - } - - public int Length { - get { - return m_hi - m_position; - } - } - - public int TokenOffset { - get { - return m_offset; - } - } - - public int TokenLength { - get { - return m_position - m_offset; - } - } - - public void Init(char[] buffer, int position, int length) { - m_buffer = buffer; - m_position = position; - m_offset = position; - m_hi = position + length; - } - - public int Extend() { - // free space - var free = m_buffer.Length - m_hi; - - // if the buffer have enough free space - if (free > 0) - return free; - - // effective size of the buffer - var size = m_buffer.Length - m_offset; - - // calculate the new size - int grow = Math.Min(m_limit - size, m_chunk); - if (grow <= 0) - throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit)); - - var temp = new char[size + grow]; - Array.Copy(m_buffer, m_offset, temp, 0, m_hi - m_offset); - m_position -= m_offset; - m_hi -= m_offset; - m_offset = 0; - m_buffer = temp; - - return free + grow; - } - - public void RaiseMark(int size) { - m_hi += size; + get { return m_pos; } } /// <summary> /// Scan this instance. /// </summary> /// <returns><c>true</c> - additional data required</returns> - public bool Scan() { - while (m_position < m_hi) { - var ch = m_buffer[m_position]; - var next = m_dfa[m_state].transitions[(int)ch]; + public bool Scan(int[] buffer, int position, int length) { + var hi = position + length; + m_pos = position; + + while (position < hi) { + var next = m_dfa[m_state].transitions[buffer[position]]; if (next == DFAConst.UNREACHABLE_STATE) { if (m_dfa[m_state].final) return false; throw new ParserException( String.Format( - "Unexpected token '{0}'", - new string(m_buffer, m_offset, m_position - m_offset) + "Unexpected symbol" ) ); } + m_pos++; m_state = next; - m_position++; } return true; @@ -129,8 +49,7 @@ if (!m_dfa[m_state].final) throw new ParserException( String.Format( - "Unexpected token '{0}'", - new string(m_buffer, m_offset, m_position - m_offset) + "Unexpected EOF" ) ); }
--- a/Implab/Formats/TextScanner.cs Tue Mar 15 02:11:06 2016 +0300 +++ b/Implab/Formats/TextScanner.cs Fri Mar 18 18:10:30 2016 +0300 @@ -4,11 +4,11 @@ namespace Implab.Formats { public abstract class TextScanner<TTag> : Disposable { - char[] m_buffer; - int m_offset; - int m_length; - int m_tokenOffset; + readonly int[] m_buffer; + int m_bufferOffset; + int m_dataLength; int m_tokenLength; + TTag[] m_tags; BufferScanner<TTag> m_scanner; @@ -17,29 +17,36 @@ if (EOF) return false; - // create a new scanner from template (scanners are structs) + // create a new scanner from template (scanners are value types) var inst = m_scanner; - // initialize the scanner - inst.Init(m_buffer, m_offset, m_length); + m_tokenLength = 0; + + while (inst.Scan(m_buffer, m_bufferOffset, m_dataLength)) { + m_tokenLength += m_dataLength; + + var actual = Read(m_buffer, 0, m_buffer.Length); + + m_bufferOffset = 0; + m_dataLength = actual; - // do work - while (inst.Scan()) - Feed(ref inst); + if (actual == 0) { + inst.Eof(); + break; + } + } + + var len = inst.Position - m_bufferOffset; + m_tokenLength += len; + m_dataLength -= len; + m_bufferOffset = inst.Position; // save result; - m_buffer = inst.Buffer; - m_length = inst.Length; - m_offset = inst.Position; - m_tokenOffset = inst.TokenOffset; - m_tokenLength = inst.TokenLength; - + m_tags = inst.GetTokenTags(); } - protected string GetToken() { - return new String(m_buffer, m_tokenOffset, m_tokenLength); - } + protected abstract int Read(int[] buffer, int offset, int size); protected TTag[] Tags { get { @@ -47,26 +54,8 @@ } } - /// <summary> - /// Feed the specified scanner. - /// </summary> - /// <param name="scanner">Scanner.</param> - /// <example> - /// protected override void Feed(ref BufferScanner<TTag> scanner) { - /// var size = scanner.Extend(); - /// var actual = m_reader.Read(scanner.Buffer, scanner.HiMark, size); - /// if (actual == 0) { - /// m_eof = true; - /// scanner.Eof(); - /// } else { - /// scanner.RaiseHiMark(actual); - /// } - /// } - /// </example> - protected abstract void Feed(ref BufferScanner<TTag> scanner); - public abstract bool EOF { get; } - + } }