diff --git a/Implab/Automaton/DFAStateDescriptor.cs b/Implab/Automaton/DFAStateDescriptor.cs deleted file mode 100644 --- a/Implab/Automaton/DFAStateDescriptor.cs +++ /dev/null @@ -1,26 +0,0 @@ -namespace Implab.Automaton { - public struct DFAStateDescriptor { - public readonly bool final; - public readonly int[] transitions; - - - public DFAStateDescriptor(int[] transitions, bool final) { - this.transitions = transitions; - this.final = final; - } - - public DFAStateDescriptor(int[] transitions) : this(transitions, false) { - } - - public DFAStateDescriptor(int size, bool final) { - Safe.ArgumentInRange(size, 0, int.MaxValue, "size"); - - this.final = final; - - transitions = new int[size]; - - for (int i = 0; i < size; i++) - transitions[i] = DFAConst.UNREACHABLE_STATE; - } - } -} diff --git a/Implab/Automaton/DFATable.cs b/Implab/Automaton/DFATable.cs --- a/Implab/Automaton/DFATable.cs +++ b/Implab/Automaton/DFATable.cs @@ -1,305 +1,313 @@ -using Implab; -using System; -using System.Collections.Generic; -using System.Linq; - -namespace Implab.Automaton { - public class DFATable : IDFATableBuilder { - int m_stateCount; - int m_symbolCount; - int m_initialState; - - readonly HashSet m_finalStates = new HashSet(); - readonly HashSet m_transitions = new HashSet(); - - - #region IDFADefinition implementation - - public bool IsFinalState(int s) { - Safe.ArgumentInRange(s, 0, m_stateCount, "s"); - - return m_finalStates.Contains(s); - } - - public IEnumerable FinalStates { - get { - return m_finalStates; - } - } - - public int StateCount { - get { return m_stateCount; } - } - - public int AlphabetSize { - get { return m_symbolCount; } - } - - public int InitialState { - get { return m_initialState; } - } - - #endregion - - public void SetInitialState(int s) { - Safe.ArgumentAssert(s >= 0, "s"); - m_initialState = s; - } - - public void MarkFinalState(int state) { - m_finalStates.Add(state); - } - - public void Add(AutomatonTransition item) { - Safe.ArgumentAssert(item.s1 >= 0, "item"); - Safe.ArgumentAssert(item.s2 >= 0, "item"); - Safe.ArgumentAssert(item.edge >= 0, "item"); - - m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); - m_symbolCount = Math.Max(m_symbolCount, item.edge); - - m_transitions.Add(item); - } - - public void Clear() { - m_stateCount = 0; - m_symbolCount = 0; - m_finalStates.Clear(); - m_transitions.Clear(); - } - - public bool Contains(AutomatonTransition item) { - return m_transitions.Contains(item); - } - - public void CopyTo(AutomatonTransition[] array, int arrayIndex) { - m_transitions.CopyTo(array, arrayIndex); - } - - public bool Remove(AutomatonTransition item) { - m_transitions.Remove(item); - } - - public int Count { - get { - return m_transitions.Count; - } - } - - public bool IsReadOnly { - get { - return false; - } - } - - public IEnumerator GetEnumerator() { - return m_transitions.GetEnumerator(); - } - - System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { - return GetEnumerator(); - } - - public DFAStateDescriptor[] CreateTransitionTable() { - var table = new DFAStateDescriptor[StateCount]; - - foreach (var t in this) { - if (table[t.s1].transitions == null) - table[t.s1] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s1)); - if (table[t.s2].transitions == null) - table[t.s2] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s2)); - table[t.s1].transitions[t.edge] = t.s2; - } - - return table; - } - - /// Формирует множества конечных состояний перед началом работы алгоритма минимизации. - /// - /// В процессе построения минимального автомата требуется разделить множество состояний, - /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества - /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, - /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. - /// - /// The final states. - protected virtual IEnumerable> GroupFinalStates() { - return new HashSet[] { m_finalStates }; - } - - protected void Optimize( - IDFATableBuilder optimalDFA, - IDictionary alphabetMap, - IDictionary stateMap - ) { - Safe.ArgumentNotNull(optimalDFA, "dfa"); - Safe.ArgumentNotNull(alphabetMap, "alphabetMap"); - Safe.ArgumentNotNull(stateMap, "stateMap"); - - - var setComparer = new CustomEqualityComparer>( - (x, y) => x.SetEquals(y), - s => s.Sum(x => x.GetHashCode()) - ); - - var optimalStates = new HashSet>(setComparer); - var queue = new HashSet>(setComparer); - - // получаем конечные состояния, сгруппированные по маркерам - optimalStates.UnionWith( - GroupFinalStates() - ); - - var state = new HashSet( - Enumerable - .Range(0, m_stateCount - 1) - .Where(i => !m_finalStates.Contains(i)) - ); - - optimalStates.Add(state); - queue.Add(state); - - var rmap = m_transitions - .GroupBy(t => t.s2) - .ToLookup( - g => g.Key, // s2 - g => g.ToLookup(t => t.edge, t => t.s1) - ); - - while (queue.Count > 0) { - var stateA = queue.First(); - queue.Remove(stateA); - - for (int c = 0; c < m_symbolCount; c++) { - var stateX = new HashSet(); - foreach(var a in stateA) - stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a' - - foreach (var stateY in optimalStates.ToArray()) { - if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { - var stateR1 = new HashSet(stateY); - var stateR2 = new HashSet(stateY); - - stateR1.IntersectWith(stateX); - stateR2.ExceptWith(stateX); - - optimalStates.Remove(stateY); - optimalStates.Add(stateR1); - optimalStates.Add(stateR2); - - if (queue.Contains(stateY)) { - queue.Remove(stateY); - queue.Add(stateR1); - queue.Add(stateR2); - } else { - queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2); - } - } - } - } - } - - // карта получения оптимального состояния по соотвествующему ему простому состоянию - var nextState = 0; - foreach (var item in optimalStates) { - var id = nextState++; - foreach (var s in item) - stateMap[s] = id; - } - - // получаем минимальный алфавит - // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s - // для этого используем алгоритм кластеризации, сначала - // считаем, что все символы не различимы - - var minClasses = new HashSet>(setComparer); - var alphaQueue = new Queue>(); - alphaQueue.Enqueue(new HashSet(Enumerable.Range(0,AlphabetSize))); - - // для всех состояний, будем проверять каждый класс на различимость, - // т.е. символы различимы, если они приводят к разным состояниям - for (int s = 0 ; s < optimalStates.Count; s++) { - var newQueue = new Queue>(); - - foreach (var A in alphaQueue) { - // классы из одного символа делить бесполезно, переводим их сразу в - // результирующий алфавит - if (A.Count == 1) { - minClasses.Add(A); - continue; - } - - // различаем классы символов, которые переводят в различные оптимальные состояния - // optimalState -> alphaClass - var classes = new Dictionary>(); - - foreach (var term in A) { - // ищем все переходы класса по символу term - var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray(); - - var s2 = res.Length > 0 ? res[0] : -1; - - HashSet a2; - if (!classes.TryGetValue(s2, out a2)) { - a2 = new HashSet(); - newQueue.Enqueue(a2); - classes[s2] = a2; - } - a2.Add(term); - } - } - - if (newQueue.Count == 0) - break; - alphaQueue = newQueue; - } - - // после окончания работы алгоритма в очереди останутся минимальные различимые классы - // входных символов - foreach (var A in alphaQueue) - minClasses.Add(A); - - // построение отображения алфавитов входных символов. - // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь - // специальное значение, тогда сохраним минимальный класс, - // содержащий этот символ на томже месте. - - var nextCls = 0; - foreach (var item in minClasses) { - if (nextCls == DFAConst.UNCLASSIFIED_INPUT) - nextCls++; - - // сохраняем DFAConst.UNCLASSIFIED_INPUT - var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls; - - foreach (var a in item) - alphabetMap[a] = cls; - - nextCls++; - } - - // построение автомата - optimalDFA.SetInitialState(stateMap[m_initialState]); - - foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct()) - optimalDFA.MarkFinalState(sf); - - foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct()) - optimalDFA.Add(t); - } - - protected void PrintDFA(IAlphabet inputAlphabet, IAlphabet stateAlphabet) { - Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); - Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); - - foreach(var t in m_transitions) - Console.WriteLine( - "[{0}] -{{{1}}}-> [{2}]{3}", - String.Join(",", stateAlphabet.GetSymbols(t.s1)), - String.Join("", inputAlphabet.GetSymbols(t.edge)), - String.Join(",", stateAlphabet.GetSymbols(t.s2)), - m_finalStates.Contains(t.s2) ? "$" : "" - ); - } - - } -} +using Implab; +using System; +using System.Collections.Generic; +using System.Linq; + +namespace Implab.Automaton { + public class DFATable : IDFATableBuilder { + int m_stateCount; + int m_symbolCount; + int m_initialState; + + readonly HashSet m_finalStates = new HashSet(); + readonly HashSet m_transitions = new HashSet(); + + + #region IDFADefinition implementation + + public bool IsFinalState(int s) { + Safe.ArgumentInRange(s, 0, m_stateCount, "s"); + + return m_finalStates.Contains(s); + } + + public IEnumerable FinalStates { + get { + return m_finalStates; + } + } + + public int StateCount { + get { return m_stateCount; } + } + + public int AlphabetSize { + get { return m_symbolCount; } + } + + public int InitialState { + get { return m_initialState; } + } + + #endregion + + public void SetInitialState(int s) { + Safe.ArgumentAssert(s >= 0, "s"); + m_initialState = s; + } + + public void MarkFinalState(int state) { + m_finalStates.Add(state); + } + + public void Add(AutomatonTransition item) { + Safe.ArgumentAssert(item.s1 >= 0, "item"); + Safe.ArgumentAssert(item.s2 >= 0, "item"); + Safe.ArgumentAssert(item.edge >= 0, "item"); + + m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); + m_symbolCount = Math.Max(m_symbolCount, item.edge); + + m_transitions.Add(item); + } + + public void Clear() { + m_stateCount = 0; + m_symbolCount = 0; + m_finalStates.Clear(); + m_transitions.Clear(); + } + + public bool Contains(AutomatonTransition item) { + return m_transitions.Contains(item); + } + + public void CopyTo(AutomatonTransition[] array, int arrayIndex) { + m_transitions.CopyTo(array, arrayIndex); + } + + public bool Remove(AutomatonTransition item) { + m_transitions.Remove(item); + } + + public int Count { + get { + return m_transitions.Count; + } + } + + public bool IsReadOnly { + get { + return false; + } + } + + public IEnumerator GetEnumerator() { + return m_transitions.GetEnumerator(); + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { + return GetEnumerator(); + } + + public int[,] CreateTransitionTable() { + var table = new int[StateCount,AlphabetSize]; + + for (int i = 0; i < StateCount; i++) + for (int j = 0; i < AlphabetSize; j++) + table[i, j] = DFAConst.UNREACHABLE_STATE; + + foreach (var t in this) + table[t.s1,t.edge] = t.s2; + + return table; + } + + public bool[] CreateFinalStateTable() { + var table = new bool[StateCount]; + + foreach (var s in FinalStates) + table[s] = true; + + return table; + } + + /// Формирует множества конечных состояний перед началом работы алгоритма минимизации. + /// + /// В процессе построения минимального автомата требуется разделить множество состояний, + /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества + /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, + /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. + /// + /// The final states. + protected virtual IEnumerable> GroupFinalStates() { + return new HashSet[] { m_finalStates }; + } + + protected void Optimize( + IDFATableBuilder optimalDFA, + IDictionary alphabetMap, + IDictionary stateMap + ) { + Safe.ArgumentNotNull(optimalDFA, "dfa"); + Safe.ArgumentNotNull(alphabetMap, "alphabetMap"); + Safe.ArgumentNotNull(stateMap, "stateMap"); + + + var setComparer = new CustomEqualityComparer>( + (x, y) => x.SetEquals(y), + s => s.Sum(x => x.GetHashCode()) + ); + + var optimalStates = new HashSet>(setComparer); + var queue = new HashSet>(setComparer); + + // получаем конечные состояния, сгруппированные по маркерам + optimalStates.UnionWith( + GroupFinalStates() + ); + + var state = new HashSet( + Enumerable + .Range(0, m_stateCount - 1) + .Where(i => !m_finalStates.Contains(i)) + ); + + optimalStates.Add(state); + queue.Add(state); + + var rmap = m_transitions + .GroupBy(t => t.s2) + .ToLookup( + g => g.Key, // s2 + g => g.ToLookup(t => t.edge, t => t.s1) + ); + + while (queue.Count > 0) { + var stateA = queue.First(); + queue.Remove(stateA); + + for (int c = 0; c < m_symbolCount; c++) { + var stateX = new HashSet(); + foreach(var a in stateA) + stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a' + + foreach (var stateY in optimalStates.ToArray()) { + if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { + var stateR1 = new HashSet(stateY); + var stateR2 = new HashSet(stateY); + + stateR1.IntersectWith(stateX); + stateR2.ExceptWith(stateX); + + optimalStates.Remove(stateY); + optimalStates.Add(stateR1); + optimalStates.Add(stateR2); + + if (queue.Contains(stateY)) { + queue.Remove(stateY); + queue.Add(stateR1); + queue.Add(stateR2); + } else { + queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2); + } + } + } + } + } + + // карта получения оптимального состояния по соотвествующему ему простому состоянию + var nextState = 0; + foreach (var item in optimalStates) { + var id = nextState++; + foreach (var s in item) + stateMap[s] = id; + } + + // получаем минимальный алфавит + // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s + // для этого используем алгоритм кластеризации, сначала + // считаем, что все символы не различимы + + var minClasses = new HashSet>(setComparer); + var alphaQueue = new Queue>(); + alphaQueue.Enqueue(new HashSet(Enumerable.Range(0,AlphabetSize))); + + // для всех состояний, будем проверять каждый класс на различимость, + // т.е. символы различимы, если они приводят к разным состояниям + for (int s = 0 ; s < optimalStates.Count; s++) { + var newQueue = new Queue>(); + + foreach (var A in alphaQueue) { + // классы из одного символа делить бесполезно, переводим их сразу в + // результирующий алфавит + if (A.Count == 1) { + minClasses.Add(A); + continue; + } + + // различаем классы символов, которые переводят в различные оптимальные состояния + // optimalState -> alphaClass + var classes = new Dictionary>(); + + foreach (var term in A) { + // ищем все переходы класса по символу term + var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray(); + + var s2 = res.Length > 0 ? res[0] : -1; + + HashSet a2; + if (!classes.TryGetValue(s2, out a2)) { + a2 = new HashSet(); + newQueue.Enqueue(a2); + classes[s2] = a2; + } + a2.Add(term); + } + } + + if (newQueue.Count == 0) + break; + alphaQueue = newQueue; + } + + // после окончания работы алгоритма в очереди останутся минимальные различимые классы + // входных символов + foreach (var A in alphaQueue) + minClasses.Add(A); + + // построение отображения алфавитов входных символов. + // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь + // специальное значение, тогда сохраним минимальный класс, + // содержащий этот символ на томже месте. + + var nextCls = 0; + foreach (var item in minClasses) { + if (nextCls == DFAConst.UNCLASSIFIED_INPUT) + nextCls++; + + // сохраняем DFAConst.UNCLASSIFIED_INPUT + var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls; + + foreach (var a in item) + alphabetMap[a] = cls; + + nextCls++; + } + + // построение автомата + optimalDFA.SetInitialState(stateMap[m_initialState]); + + foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct()) + optimalDFA.MarkFinalState(sf); + + foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct()) + optimalDFA.Add(t); + } + + protected void PrintDFA(IAlphabet inputAlphabet, IAlphabet stateAlphabet) { + Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); + Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); + + foreach(var t in m_transitions) + Console.WriteLine( + "[{0}] -{{{1}}}-> [{2}]{3}", + String.Join(",", stateAlphabet.GetSymbols(t.s1)), + String.Join("", inputAlphabet.GetSymbols(t.edge)), + String.Join(",", stateAlphabet.GetSymbols(t.s2)), + m_finalStates.Contains(t.s2) ? "$" : "" + ); + } + + } +} diff --git a/Implab/Automaton/IndexedAlphabetBase.cs b/Implab/Automaton/IndexedAlphabetBase.cs --- a/Implab/Automaton/IndexedAlphabetBase.cs +++ b/Implab/Automaton/IndexedAlphabetBase.cs @@ -13,82 +13,38 @@ namespace Implab.Automaton { /// to the input alphabet of the automaton. It's assumed that the index to the symbol match /// is well known and documented. /// - public abstract class IndexedAlphabetBase : IAlphabetBuilder { - int m_nextId = 1; - readonly int[] m_map; - - protected IndexedAlphabetBase(int mapSize) { - m_map = new int[mapSize]; - } - - protected IndexedAlphabetBase(int[] map) { - Debug.Assert(map != null && map.Length > 0); - Debug.Assert(map.All(x => x >= 0)); - - m_map = map; - m_nextId = map.Max() + 1; - } - - public int DefineSymbol(T symbol) { - var index = GetSymbolIndex(symbol); - if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT) - m_map[index] = m_nextId++; - return m_map[index]; - } - - public int DefineSymbol(T symbol, int cls) { - var index = GetSymbolIndex(symbol); - m_map[index] = cls; - m_nextId = Math.Max(cls + 1, m_nextId); - return cls; - } + public abstract class IndexedAlphabetBase : MapAlphabet { - public int DefineClass(IEnumerable symbols) { - return DefineClass(symbols, m_nextId); - } - - public int DefineClass(IEnumerable symbols, int cls) { - Safe.ArgumentNotNull(symbols, "symbols"); - symbols = symbols.Distinct(); - - foreach (var symbol in symbols) - m_map[GetSymbolIndex(symbol)] = cls; - - m_nextId = Math.Max(cls + 1, m_nextId); - - return cls; - } - - public virtual int Translate(T symbol) { - return m_map[GetSymbolIndex(symbol)]; - } - - public int Count { - get { return m_nextId; } - } - - public bool Contains(T symbol) { - return true; - } - - public IEnumerable GetSymbols(int cls) { - for (var i = 0; i < m_map.Length; i++) - if (m_map[i] == cls) - yield return GetSymbolByIndex(i); + protected IndexedAlphabetBase() :base(true, null) { } public abstract int GetSymbolIndex(T symbol); - public abstract T GetSymbolByIndex(int index); - - public abstract IEnumerable InputSymbols { get; } - /// /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion. /// + /// + /// The map is continous and start from the symbol with zero code. The last symbol + /// in the map is the last classified symbol in the alphabet, i.e. the map can be + /// shorter then the whole alphabet. + /// /// The translation map. public int[] GetTranslationMap() { - return m_map; + Dictionary map = new Dictionary(); + + int max; + foreach (var p in Mappings) { + var index = GetSymbolIndex(p.Key); + max = Math.Max(max, index); + map[index] = p.Value; + } + + var result = new int[max + 1]; + + for (int i = 0; i < result.Length; i++) + map.TryGetValue(i, out result[i]); + + return result; } } } diff --git a/Implab/Automaton/MapAlphabet.cs b/Implab/Automaton/MapAlphabet.cs --- a/Implab/Automaton/MapAlphabet.cs +++ b/Implab/Automaton/MapAlphabet.cs @@ -69,9 +69,16 @@ namespace Implab.Automaton { public IEnumerable GetSymbols(int cls) { + Safe.ArgumentAssert(cls > 0, "cls"); return m_map.Where(p => p.Value == cls).Select(p => p.Key); } #endregion + + public IEnumerable> Mappings { + get { + return m_map; + } + } } } diff --git a/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs b/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs deleted file mode 100644 --- a/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs +++ /dev/null @@ -1,23 +0,0 @@ -using System; - -namespace Implab.Automaton.RegularExpressions { - public struct DFAStateDescriptor { - public readonly bool final; - - public readonly int[] transitions; - - public readonly T[] tags; - - public DFAStateDescriptor(int size, bool final, T[] tags) { - Safe.ArgumentAssert(size >= 0, "size"); - this.final = final; - this.tags = tags; - - transitions = new int[size]; - - for (int i = 0; i < size; i++) - transitions[i] = DFAConst.UNREACHABLE_STATE; - } - } -} - diff --git a/Implab/Automaton/RegularExpressions/Grammar.cs b/Implab/Automaton/RegularExpressions/Grammar.cs --- a/Implab/Automaton/RegularExpressions/Grammar.cs +++ b/Implab/Automaton/RegularExpressions/Grammar.cs @@ -66,9 +66,9 @@ namespace Implab.Automaton.RegularExpres return Token.New( Enumerable.Range(0, AlphabetBuilder.Count).Except(TranslateOrDie(symbols)).ToArray() ); } - protected abstract IAlphabetBuilder CreateAlphabet(); + protected abstract IndexedAlphabetBase CreateAlphabet(); - protected RegularDFA BuildDFA(Token regexp) { + protected ScannerContext BuildScannerContext(Token regexp) { var dfa = new RegularDFA(AlphabetBuilder); @@ -80,7 +80,16 @@ namespace Implab.Automaton.RegularExpres if (dfa.IsFinalState(dfa.InitialState)) throw new ApplicationException("The specified language contains empty token"); - return dfa.Optimize(CreateAlphabet()); + var ab = CreateAlphabet(); + var optimal = dfa.Optimize(ab); + + return new ScannerContext( + optimal.CreateTransitionTable(), + optimal.CreateFinalStateTable(), + optimal.CreateTagTable(), + optimal.InitialState, + ab.GetTranslationMap() + ); } } diff --git a/Implab/Automaton/RegularExpressions/RegularDFA.cs b/Implab/Automaton/RegularExpressions/RegularDFA.cs --- a/Implab/Automaton/RegularExpressions/RegularDFA.cs +++ b/Implab/Automaton/RegularExpressions/RegularDFA.cs @@ -36,16 +36,11 @@ namespace Implab.Automaton.RegularExpres return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0]; } - public new DFAStateDescriptor[] CreateTransitionTable() { - var table = new DFAStateDescriptor[StateCount]; + public TTag[][] CreateTagTable() { + var table = new TTag[StateCount][]; - foreach (var t in this) { - if (table[t.s1].transitions == null) - table[t.s1] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s1), GetStateTag(t.s1)); - if (table[t.s2].transitions == null) - table[t.s2] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s2), GetStateTag(t.s2)); - table[t.s1].transitions[t.edge] = t.s2; - } + foreach (var pair in m_tags) + table[pair.Key] = pair.Value; return table; } diff --git a/Implab/Automaton/Scanner.cs b/Implab/Automaton/Scanner.cs deleted file mode 100644 --- a/Implab/Automaton/Scanner.cs +++ /dev/null @@ -1,255 +0,0 @@ -using Implab; -using System; -using System.Collections.Generic; -using System.IO; -using Implab.Components; -using Implab.Automaton.RegularExpressions; - -namespace Implab.Automaton { - /// - /// Базовый класс для разбора потока входных символов на токены. - /// - /// - /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два - /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения - /// конца токена и допустимости текущего символа. - /// - public abstract class Scanner : Disposable { - protected struct ScannerConfig { - public readonly DFAStateDescriptor[] states; - public readonly int[] alphabet; - public readonly int initialState; - - public ScannerConfig(DFAStateDescriptor[] states, int[] alphabet, int initialState) { - this.initialState = initialState; - this.alphabet = alphabet; - this.states = states; - } - } - - Stack m_defs = new Stack(); - - ScannerConfig m_config; - - protected DFAStateDescriptor 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; - } - - /// - /// Заполняет входными данными буффер. - /// - /// Данные для обработки. - /// Копирование данных не происходит, переданный массив используется в - /// качестве входного буффера. - public void Feed(char[] data) { - Safe.ArgumentNotNull(data, "data"); - - Feed(data, data.Length); - } - - /// - /// Заполняет буффур чтения входными данными. - /// - /// Данные для обработки. - /// Длина данных для обработки. - /// Копирование данных не происходит, переданный массив используется в - /// качестве входного буффера. - 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(); - } - - /// - /// Получает текущий токен в виде строки. - /// - /// - protected string GetTokenValue() { - return new String(m_buffer, m_tokenOffset, m_tokenLen); - } - - /// - /// Метки текущего токена, которые были назначены в регулярном выражении. - /// - protected TTag[] TokenTags { - get { - return m_currentState.tags; - } - } - - /// - /// Признак конца данных - /// - public bool EOF { - get { - return m_pointer >= m_bufferSize; - } - } - - /// - /// Читает следующий токен, при этом указывает на начало токена, - /// на длину токена, - массив символов, в - /// котором находится токен. - /// - /// false - достигнут конец данных, токен не прочитан. - 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; - } - - /// - /// Позиция сканнера во входном буфере - /// - public int Position { - get { - return m_pointer + 1; - } - } - - /// - /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей - /// группировки. - /// - /// - 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]]; - } - - /// - /// Восстанавливает предыдущей ДКА сканнера. - /// - 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); - } - } -} diff --git a/Implab/Formats/BufferScanner.cs b/Implab/Formats/BufferScanner.cs deleted file mode 100644 --- a/Implab/Formats/BufferScanner.cs +++ /dev/null @@ -1,62 +0,0 @@ -using System; -using Implab.Automaton.RegularExpressions; -using Implab.Automaton; -using System.Diagnostics; - -namespace Implab.Formats { - public struct BufferScanner { - readonly DFAStateDescriptor[] m_dfa; - int m_state; - int m_pos; - - public BufferScanner(DFAStateDescriptor[] dfa, int initialState) { - m_dfa = dfa; - m_state = initialState; - } - - public int Position { - get { return m_pos; } - } - - /// - /// Scan this instance. - /// - /// true - additional data required - 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 symbol" - ) - ); - } - m_pos++; - m_state = next; - } - - return true; - } - - public void Eof() { - if (!m_dfa[m_state].final) - throw new ParserException( - String.Format( - "Unexpected EOF" - ) - ); - } - - public TTag[] GetTokenTags() { - return m_dfa[m_state].tags; - } - } -} - diff --git a/Implab/Formats/ByteAlphabet.cs b/Implab/Formats/ByteAlphabet.cs --- a/Implab/Formats/ByteAlphabet.cs +++ b/Implab/Formats/ByteAlphabet.cs @@ -4,7 +4,7 @@ using Implab.Automaton; namespace Implab.Formats { public class ByteAlphabet : IndexedAlphabetBase { - public ByteAlphabet() : base(byte.MaxValue + 1){ + public ByteAlphabet() { } #region implemented abstract members of IndexedAlphabetBase @@ -13,10 +13,6 @@ namespace Implab.Formats { return (int)symbol; } - public override byte GetSymbolByIndex(int index) { - return (byte)index; - } - public IEnumerable InputSymbols { get { return Enumerable.Range(byte.MinValue, byte.MaxValue).Cast(); diff --git a/Implab/Formats/CharAlphabet.cs b/Implab/Formats/CharAlphabet.cs --- a/Implab/Formats/CharAlphabet.cs +++ b/Implab/Formats/CharAlphabet.cs @@ -5,19 +5,14 @@ using Implab.Automaton; namespace Implab.Formats { public class CharAlphabet: IndexedAlphabetBase { - public CharAlphabet() - : base(char.MaxValue + 1) { + public CharAlphabet() { } public override int GetSymbolIndex(char symbol) { return symbol; } - public override char GetSymbolByIndex(int index) { - return (char)index; - } - - public override IEnumerable InputSymbols { + public IEnumerable InputSymbols { get { return Enumerable.Range(char.MinValue, char.MaxValue).Cast(); } } } diff --git a/Implab/Formats/JSON/JSONGrammar.cs b/Implab/Formats/JSON/JSONGrammar.cs --- a/Implab/Formats/JSON/JSONGrammar.cs +++ b/Implab/Formats/JSON/JSONGrammar.cs @@ -20,14 +20,7 @@ namespace Implab.Formats.JSON { StringBound, EscapedChar, UnescapedChar, - EscapedUnicode, - - Minus, - Plus, - Sign, - Integer, - Dot, - Exp + EscapedUnicode } static Lazy _instance = new Lazy(); @@ -36,8 +29,8 @@ namespace Implab.Formats.JSON { get { return _instance.Value; } } - readonly RegularDFA m_jsonDFA; - readonly RegularDFA m_stringDFA; + readonly ScannerContext m_jsonDFA; + readonly ScannerContext m_stringDFA; public JSONGrammar() { DefineAlphabet(Enumerable.Range(0, 0x20).Select(x => (char)x)); @@ -88,17 +81,17 @@ namespace Implab.Formats.JSON { .Or(unescaped.Closure().Tag(TokenType.UnescapedChar)); - m_jsonDFA = BuildDFA(jsonExpression); - m_stringDFA = BuildDFA(jsonStringExpression); + m_jsonDFA = BuildScannerContext(jsonExpression); + m_stringDFA = BuildScannerContext(jsonStringExpression); } - public RegularDFA JsonDFA { + public ScannerContext JsonDFA { get { return m_jsonDFA; } } - public RegularDFA JsonStringDFA { + public ScannerContext JsonStringDFA { get { return m_stringDFA; } diff --git a/Implab/Formats/JSON/JSONScanner.cs b/Implab/Formats/JSON/JSONScanner.cs --- a/Implab/Formats/JSON/JSONScanner.cs +++ b/Implab/Formats/JSON/JSONScanner.cs @@ -1,25 +1,37 @@ using System; using System.Globalization; using Implab.Automaton; +using System.Text; +using Implab.Components; +using System.IO; +using Implab.Automaton.RegularExpressions; namespace Implab.Formats.JSON { /// /// Сканнер (лексер), разбивающий поток символов на токены JSON. /// - public class JSONScanner : Scanner { - char[] m_stringBuffer; - DFAStateDescriptior<>[] m_stringDFA; - int[] m_stringAlphabet; + public class JSONScanner : Disposable { + readonly StringBuilder m_builder = new StringBuilder(); + + readonly ScannerContext m_jsonScanner = JSONGrammar.Instance.JsonDFA; + readonly ScannerContext m_stringScanner = JSONGrammar.Instance.JsonStringDFA; + + + readonly TextScanner m_scanner; /// /// Создает новый экземпляр сканнера /// - public JSONScanner() - : base(JSONGrammar.Instance.JsonDFA.GetTransitionTable(), JSONGrammar.Instance.JsonDFA.Alphabet.GetTranslationMap()) { - m_stringBuffer = new char[1024]; - var dfa = JSONGrammar.Instance.JsonStringDFA; - m_stringAlphabet = dfa.Alphabet.GetTranslationMap(); - m_stringDFA = dfa.States; + public JSONScanner(string text) { + Safe.ArgumentNotEmpty(text, "text"); + + m_scanner = new StringScanner(text); + } + + public JSONScanner(TextReader reader, int bufferMax, int chunkSize) { + Safe.ArgumentNotNull(reader, "reader"); + + m_scanner = new ReaderScanner(reader); } /// @@ -31,19 +43,20 @@ namespace Implab.Formats.JSON { /// В случе если токен не распознается, возникает исключение. Значения токенов обрабатываются, т.е. /// в строках обрабатываются экранированные символы, числа становтся типа double. public bool ReadToken(out object tokenValue, out JsonTokenType tokenType) { - if (ReadTokenInternal()) { - switch ((JSONGrammar.TokenType)m_currentState.tag[0]) { + JSONGrammar.TokenType[] tag; + if (m_jsonScanner.Execute(m_scanner, out tag)) { + switch (tag[0]) { case JSONGrammar.TokenType.StringBound: tokenValue = ReadString(); tokenType = JsonTokenType.String; break; case JSONGrammar.TokenType.Number: - tokenValue = Double.Parse(new String(m_buffer, m_tokenOffset, m_tokenLen), CultureInfo.InvariantCulture); + tokenValue = Double.Parse(m_scanner.GetTokenValue(), CultureInfo.InvariantCulture); tokenType = JsonTokenType.Number; break; default: - tokenType = (JsonTokenType)m_currentState.tag[0]; - tokenValue = new String(m_buffer, m_tokenOffset, m_tokenLen); + tokenType = (JsonTokenType)tag[0]; + tokenValue = m_scanner.GetTokenValue(); break; } return true; @@ -55,26 +68,26 @@ namespace Implab.Formats.JSON { string ReadString() { int pos = 0; - Switch(m_stringDFA, m_stringAlphabet); - while (ReadTokenInternal()) { - switch ((JSONGrammar.TokenType)m_currentState.tag[0]) { + char[] buf = new char[6]; // the buffer for unescaping chars + + JSONGrammar.TokenType[] tag; + m_builder.Clear(); + + while (m_stringScanner.Execute(m_scanner, out tag)) { + switch (tag[0]) { case JSONGrammar.TokenType.StringBound: - Restore(); - return new String(m_stringBuffer, 0, pos); + return m_builder.ToString(); case JSONGrammar.TokenType.UnescapedChar: - EnsureStringBufferSize(pos + m_tokenLen); - Array.Copy(m_buffer, m_tokenOffset, m_stringBuffer, pos, m_tokenLen); - pos += m_tokenLen; + m_scanner.CopyTokenTo(m_builder); break; - case JSONGrammar.TokenType.EscapedUnicode: - EnsureStringBufferSize(pos + 1); - m_stringBuffer[pos] = StringTranslator.TranslateHexUnicode(m_buffer, m_tokenOffset + 2); + case JSONGrammar.TokenType.EscapedUnicode: // \xXXXX - unicode escape sequence + m_scanner.CopyTokenTo(buf, 0); + m_builder.Append(StringTranslator.TranslateHexUnicode(buf, 2)); pos++; break; - case JSONGrammar.TokenType.EscapedChar: - EnsureStringBufferSize(pos + 1); - m_stringBuffer[pos] = StringTranslator.TranslateEscapedChar(m_buffer[m_tokenOffset + 1]); - pos++; + case JSONGrammar.TokenType.EscapedChar: // \t - escape sequence + m_scanner.CopyTokenTo(buf, 0); + m_builder.Append(StringTranslator.TranslateEscapedChar(buf[1])); break; default: break; @@ -84,13 +97,5 @@ namespace Implab.Formats.JSON { throw new ParserException("Unexpected end of data"); } - - void EnsureStringBufferSize(int size) { - if (size > m_stringBuffer.Length) { - var newBuffer = new char[size]; - m_stringBuffer.CopyTo(newBuffer, 0); - m_stringBuffer = newBuffer; - } - } } } diff --git a/Implab/Formats/JSON/StringTranslator.cs b/Implab/Formats/JSON/StringTranslator.cs --- a/Implab/Formats/JSON/StringTranslator.cs +++ b/Implab/Formats/JSON/StringTranslator.cs @@ -1,5 +1,5 @@ using Implab; -using Implab.Parsing; +using Implab.Formats; using System; using System.Collections.Generic; using System.Diagnostics; @@ -7,11 +7,11 @@ using System.Linq; using System.Text; using System.Threading.Tasks; -namespace Implab.JSON { +namespace Implab.Formats.JSON { /// /// Класс для преобразования экранированной строки JSON /// - public class StringTranslator : Scanner { + public class StringTranslator : TextScanner { static readonly char[] _escMap; static readonly int[] _hexMap; @@ -34,8 +34,7 @@ namespace Implab.JSON { } - public StringTranslator() - : base(JSONGrammar.Instance.JsonStringDFA.States, JSONGrammar.Instance.JsonStringDFA.Alphabet.GetTranslationMap()) { + public StringTranslator() { } public string Translate(string data) { @@ -59,7 +58,7 @@ namespace Implab.JSON { int pos = 0; while (ReadTokenInternal()) { - switch ((JSONGrammar.TokenType)TokenTags[0]) { + switch ((JSONGrammar.TokenType)Tags[0]) { case JSONGrammar.TokenType.UnescapedChar: Array.Copy(m_buffer,m_tokenOffset,translated,pos,m_tokenLen); pos += m_tokenLen; diff --git a/Implab/Formats/ReaderScanner.cs b/Implab/Formats/ReaderScanner.cs new file mode 100644 --- /dev/null +++ b/Implab/Formats/ReaderScanner.cs @@ -0,0 +1,30 @@ +using System; +using System.IO; + +namespace Implab.Formats { + public class ReaderScanner: TextScanner { + const int CHUNK_SIZE = 1024; + const int BUFFER_MAX = CHUNK_SIZE*1024; + + readonly TextReader m_reader; + + public ReaderScanner(TextReader reader, int limit, int chunk) : base(limit, chunk) { + Safe.ArgumentNotNull(reader, "reader"); + m_reader = reader; + } + + public ReaderScanner(TextReader reader) : this(reader, BUFFER_MAX, CHUNK_SIZE) { + } + + protected override int Read(char[] buffer, int offset, int size) { + return m_reader.Read(buffer, offset, size); + } + + protected override void Dispose(bool disposing) { + if (disposing) + Safe.Dispose(m_reader); + base.Dispose(disposing); + } + } +} + diff --git a/Implab/Formats/ScannerContext.cs b/Implab/Formats/ScannerContext.cs new file mode 100644 --- /dev/null +++ b/Implab/Formats/ScannerContext.cs @@ -0,0 +1,24 @@ +using System; + +namespace Implab.Formats { + public class ScannerContext { + public int[,] Dfa { get; private set; } + public bool[] Final { get; private set; } + public TTag[][] Tags { get; private set; } + public int State { get; private set; } + public int[] Alphabet { get; private set; } + + public ScannerContext(int[,] dfa, bool[] final, TTag[][] tags, int state, int[] alphabet) { + Dfa = dfa; + Final = final; + Tags = tags; + State = state; + Alphabet = alphabet; + } + + public bool Execute(TextScanner scanner, out TTag[] tag) { + return scanner.ReadToken(Dfa, Final, Tags, State, Alphabet, out tag); + } + } +} + diff --git a/Implab/Formats/StringScanner.cs b/Implab/Formats/StringScanner.cs new file mode 100644 --- /dev/null +++ b/Implab/Formats/StringScanner.cs @@ -0,0 +1,26 @@ +using System; + +namespace Implab.Formats { + public class StringScanner: TextScanner { + const int CHUNK_SIZE = 1024; + + readonly string m_text; + int m_pos; + + public StringScanner(string text) : base(text.Length, text.Length < CHUNK_SIZE ? text.Length : CHUNK_SIZE) { + m_text = text; + Feed(); + } + + protected override int Read(char[] buffer, int offset, int size) { + var actual = size + m_pos > m_text.Length ? m_text.Length - m_pos : size; + + m_text.CopyTo(m_pos,buffer,offset, actual); + + m_pos += actual; + + return actual; + } + } +} + diff --git a/Implab/Formats/TextScanner.cs b/Implab/Formats/TextScanner.cs --- a/Implab/Formats/TextScanner.cs +++ b/Implab/Formats/TextScanner.cs @@ -3,50 +3,146 @@ using Implab.Components; using Implab.Automaton.RegularExpressions; using System.Diagnostics; using Implab.Automaton; +using System.IO; +using System.Text; namespace Implab.Formats { - public abstract class TextScanner : Disposable { + public abstract class TextScanner : Disposable { + readonly int m_bufferMax; + readonly int m_chunkSize; - int m_maxSymbol; - int[] m_symbolMap; - - readonly char[] m_buffer; + char[] m_buffer; int m_bufferOffset; int m_bufferSize; + int m_tokenOffset; int m_tokenLength; - TTag[] m_tags; + /// + /// Initializes a new instance of the class. + /// + /// Buffer max. + /// Chunk size. + protected TextScanner(int bufferMax, int chunkSize) { + Debug.Assert(m_chunkSize <= m_bufferMax); + + m_bufferMax = bufferMax; + m_chunkSize = chunkSize; + } - protected bool ReadTokenInternal(DFAStateDescriptor[] dfa, int state) { - Debug.Assert(dfa != null); + /// + /// Initializes a new instance of the class. + /// + /// Buffer. + protected TextScanner(char[] buffer) { + if (buffer != null) { + m_buffer = buffer; + m_bufferSize = buffer.Length; + } + } + + /// + /// (hungry) Reads the next token. + /// + /// true, if token internal was read, false if there is no more tokens in the stream. + /// The transition map for the automaton + /// Final states of the automaton. + /// Tags. + /// The initial state for the automaton. + internal bool ReadToken(int[,] dfa, int[] final, TTag[][] tags, int state, int[] alphabet, out TTag[] tag) { + Safe.ArgumentNotNull(); + m_tokenLength = 0; + + var maxSymbol = alphabet.Length - 1; do { - for (var pos = m_bufferOffset; pos < m_bufferSize; pos++) { + // after the next chunk is read the offset in the buffer may change + int pos = m_bufferOffset + m_tokenLength; + + while(pos < m_bufferSize) { var ch = m_buffer[pos]; - state = dfa[state].transitions[m_symbolMap[ch > m_maxSymbol ? m_maxSymbol : ch]]; + + state = dfa[state,ch > maxSymbol ? DFAConst.UNCLASSIFIED_INPUT : alphabet[ch]]; if (state == DFAConst.UNREACHABLE_STATE) break; + + pos++; } - } while (Feed()); + + m_tokenLength = pos - m_bufferOffset; + } while (state != DFAConst.UNREACHABLE_STATE && Feed()); + + m_tokenOffset = m_bufferOffset; + m_bufferOffset += m_tokenLength; - if (dfa[state].final) { + if (final[state]) { + tag = tags[state]; + return true; + } else { + if (m_bufferOffset == m_bufferSize) { + if (m_tokenLength == 0) //EOF + return false; + + throw new ParserException(); + } + throw new ParserException(String.Format("Unexpected symbol '{0}'", m_buffer[m_bufferOffset])); + + } + } - } - + protected void Feed(char[] buffer, int offset, int length) { + m_buffer = buffer; + m_bufferOffset = offset; + m_bufferSize = offset + length; } - bool Feed() { + protected bool Feed() { + if (m_chunkSize <= 0) + return false; + + if (m_buffer != null) { + var free = m_buffer.Length - m_bufferSize; + + if (free < m_chunkSize) { + free += m_chunkSize; + var used = m_bufferSize - m_bufferOffset; + var size = used + free; + + if (size > m_bufferMax) + throw new ParserException(String.Format("The buffer limit ({0} Kb) is reached"), m_bufferMax/1024); + + var temp = new char[size]; + var read = Read(temp, used, m_chunkSize); + if (read == 0) + return false; + + Array.Copy(m_buffer, m_bufferOffset, temp, 0, used); + + m_bufferOffset = 0; + m_bufferSize = used + read; + m_buffer = temp; + } + } else { + Debug.Assert(m_bufferOffset == 0); + m_buffer = new char[m_chunkSize]; + m_bufferSize = Read(m_buffer, 0, m_chunkSize); + return (m_bufferSize != 0); + } } protected abstract int Read(char[] buffer, int offset, int size); - protected TTag[] Tags { - get { - return m_tags; - } + public string GetTokenValue() { + return new String(m_buffer, m_tokenOffset, m_tokenLength); } + public void CopyTokenTo(char[] buffer, int offset) { + m_buffer.CopyTo(buffer, offset); + } + + public void CopyTokenTo(StringBuilder sb) { + sb.Append(m_buffer, m_tokenOffset, m_tokenLength); + } } } diff --git a/Implab/Implab.csproj b/Implab/Implab.csproj --- a/Implab/Implab.csproj +++ b/Implab/Implab.csproj @@ -151,11 +151,9 @@ - - @@ -190,9 +188,10 @@ - - + + +