implab/ImplabNet Commit - r162:0526412bbb26

DFA refactoring

cin -

r162:0526412bbb26 ref20160224

parent child

Context file:

r162:0526412bbb26

Expand all files

Implab/Automaton/AutomatonTransition.cs created 644 +33 0

			@@ -0,0 +1,33
		1	using System;
		2
		3	namespace Implab.Automaton {
		4	struct AutomatonTransition : IEquatable<AutomatonTransition> {
		5	public readonly int s1;
		6	public readonly int s2;
		7	public readonly int edge;
		8
		9	public AutomatonTransition(int s1, int s2, int edge) {
		10	this.s1 = s1;
		11	this.s2 = s2;
		12	this.edge = edge;
		13	}
		14
		15
		16	#region IEquatable implementation
		17	public bool Equals(AutomatonTransition other) {
		18	return other.s1 == s1 && other.s2 == s2 && other.edge == edge ;
		19	}
		20	#endregion
		21
		22	public override bool Equals(object obj) {
		23	if (obj is AutomatonTransition)
		24	return Equals((AutomatonTransition)obj);
		25	return base.Equals(obj);
		26	}
		27
		28	public override int GetHashCode() {
		29	return s1 + s2 + edge;
		30	}
		31	}
		32	}
		33

Implab/Automaton/ByteAlphabet.cs created 644 +23 0

			@@ -0,0 +1,23
		1	using System;
		2
		3	namespace Implab.Automaton {
		4	public class ByteAlphabet : IndexedAlphabetBase<byte> {
		5	public ByteAlphabet() : base(byte.MaxValue + 1){
		6	}
		7
		8	#region implemented abstract members of IndexedAlphabetBase
		9
		10	public override int GetSymbolIndex(byte symbol) {
		11	return (int)symbol;
		12	}
		13
		14	public override System.Collections.Generic.IEnumerable<byte> InputSymbols {
		15	get {
		16	throw new NotImplementedException();
		17	}
		18	}
		19
		20	#endregion
		21	}
		22	}
		23

Implab/Automaton/CDFADefinition.cs created 644 +22 0

			@@ -0,0 +1,22
		1	namespace Implab.Automaton {
		2	public class CDFADefinition : DFADefinition {
		3	readonly CharAlphabet m_alphabet;
		4
		5	public CharAlphabet Alphabet {
		6	get { return m_alphabet; }
		7	}
		8
		9	public CDFADefinition(CharAlphabet alphabet): base(alphabet.Count) {
		10	m_alphabet = alphabet;
		11	}
		12
		13	public CDFADefinition Optimize() {
		14
		15	return (CDFADefinition)Optimize(alphabet => new CDFADefinition((CharAlphabet)alphabet), m_alphabet, new CharAlphabet());
		16	}
		17
		18	public void PrintDFA() {
		19	PrintDFA(m_alphabet);
		20	}
		21	}
		22	}

Implab/Automaton/CharAlphabet.cs created 644 +23 0

			@@ -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).Select(x => (char)x); }
		21	}
		22	}
		23	}

Implab/Automaton/DFAConst.cs created 644 +10 0

			@@ -0,0 +1,10
		1	using System;
		2
		3	namespace Implab.Automaton {
		4	public static class DFAConst {
		5	public const int UNREACHABLE_STATE = -1;
		6
		7	public const int UNCLASSIFIED_INPUT = 0;
		8	}
		9	}
		10

Implab/Automaton/DFADefinition.cs created 644 +213 0

			@@ -0,0 +1,213
		1	using Implab;
		2	using System;
		3	using System.Collections.Generic;
		4	using System.Linq;
		5
		6	namespace Implab.Automaton {
		7	public class DFADefinition<TInput, TState, TTag> : IDFADefinitionBuilder<TTag>, IDFADefinition<TInput, TState, TTag> {
		8	DFAStateDescriptior<TTag>[] m_dfaTable;
		9	readonly IAlphabet<TInput> m_inputAlphabet;
		10	readonly IAlphabet<TState> m_stateAlphabet;
		11
		12	readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
		13	readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
		14
		15	public DFADefinition(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
		16	Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
		17	Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
		18
		19	m_inputAlphabet = inputAlphabet;
		20	m_stateAlphabet = stateAlphabet;
		21	}
		22
		23	public void DefineTransition(int s1, int s2, int symbol) {
		24	Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count-1, "s1");
		25	Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count-1, "s2");
		26	Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count-1, "symbol");
		27
		28	m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
		29	}
		30
		31
		32	#region IDFADefinition implementation
		33
		34	public DFAStateDescriptior<TTag>[] GetTransitionTable() {
		35	if (m_dfaTable == null) {
		36	m_dfaTable = new DFAStateDescriptior<TTag>[m_stateAlphabet.Count];
		37
		38	foreach (var pair in m_finalStates) {
		39	var idx = pair.Key;
		40
		41	m_dfaTable[idx].final = true;
		42	m_dfaTable[idx].tag = m_dfaTable[idx].tag != null ?
		43	m_dfaTable[idx].tag.Concat(pair.Value).Distinct().ToArray() :
		44	pair.Value;
		45	}
		46
		47	foreach (var t in m_transitions) {
		48	if (m_dfaTable[t.s1].transitions == null) {
		49	m_dfaTable[t.s1].transitions = new int[m_inputAlphabet.Count];
		50	for (int i = 0; i < m_dfaTable[t.s1].transitions.Length; i++)
		51	m_dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
		52	}
		53
		54	m_dfaTable[t.s1].transitions[t.edge] = t.s2;
		55	}
		56	}
		57	return m_dfaTable;
		58	}
		59
		60	public IAlphabet<TInput> InputAlphabet {
		61	get {
		62	return m_inputAlphabet;
		63	}
		64	}
		65
		66	public IAlphabet<TState> StateAlphabet {
		67	get {
		68	return m_stateAlphabet;
		69	}
		70	}
		71
		72	#endregion
		73
		74	#region IDFADefinitionBuilder
		75
		76	public void DefineTransition(int s1, int s2, int symbol) {
		77	Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count - 1, "s1");
		78	Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count - 1, "s2");
		79	Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count - 1, "symbol");
		80
		81	m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
		82	}
		83
		84	public void MarkFinalState(int state, params TTag[] tags) {
		85	m_finalStates[state] = tags;
		86	}
		87
		88
		89	#endregion
		90
		91	protected void Optimize(IDFADefinitionBuilder<TTag> optimalDFA,IAlphabetBuilder<TInput> optimalInputAlphabet, IAlphabetBuilder<TState> optimalStateAlphabet) {
		92	Safe.ArgumentNotNull(optimalDFA, "dfa");
		93	Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
		94	Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
		95
		96	var setComparer = new CustomEqualityComparer<HashSet<int>>(
		97	(x, y) => x.SetEquals(y),
		98	s => s.Sum(x => x.GetHashCode())
		99	);
		100
		101	var arrayComparer = new CustomEqualityComparer<TTag[]>(
		102	(x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
		103	a => a.Sum(x => x.GetHashCode())
		104	);
		105
		106	var optimalStates = new HashSet<HashSet<int>>(setComparer);
		107	var queue = new HashSet<HashSet<int>>(setComparer);
		108
		109	// получаем конечные состояния, сгруппированные по маркерам
		110	optimalStates.UnionWith(
		111	m_finalStates
		112	.GroupBy(pair => pair.Value, arrayComparer)
		113	.Select(
		114	g => new HashSet<int>(
		115	g.Select( pair => pair.Key)
		116	)
		117	)
		118	);
		119
		120	var state = new HashSet<int>(
		121	Enumerable
		122	.Range(0, m_stateAlphabet.Count - 1)
		123	.Where(i => !m_finalStates.ContainsKey(i))
		124	);
		125	optimalStates.Add(state);
		126	queue.Add(state);
		127
		128	var rmap = m_transitions
		129	.GroupBy(t => t.s2)
		130	.ToLookup(
		131	g => g.Key, // s2
		132	g => g.ToLookup(t => t.edge, t => t.s1)
		133	);
		134
		135	while (queue.Count > 0) {
		136	var stateA = queue.First();
		137	queue.Remove(stateA);
		138
		139	for (int c = 0; c < m_inputAlphabet.Count; c++) {
		140	var stateX = new HashSet<int>();
		141	foreach(var a in stateA)
		142	stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
		143
		144	foreach (var stateY in optimalStates.ToArray()) {
		145	if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
		146	var stateR1 = new HashSet<int>(stateY);
		147	var stateR2 = new HashSet<int>(stateY);
		148
		149	stateR1.IntersectWith(stateX);
		150	stateR2.ExceptWith(stateX);
		151
		152	optimalStates.Remove(stateY);
		153	optimalStates.Add(stateR1);
		154	optimalStates.Add(stateR2);
		155
		156	if (queue.Contains(stateY)) {
		157	queue.Remove(stateY);
		158	queue.Add(stateR1);
		159	queue.Add(stateR2);
		160	} else {
		161	queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
		162	}
		163	}
		164	}
		165	}
		166	}
		167
		168	// карта получения оптимального состояния по соотвествующему ему простому состоянию
		169	var statesMap = m_stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
		170
		171	// получаем минимальный алфавит
		172	// входные символы не различимы, если Move(s,a1) == Move(s,a2)
		173	var optimalAlphabet = m_transitions
		174	.GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
		175
		176	var alphabetMap = m_inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
		177
		178	var optimalTags = m_finalStates
		179	.GroupBy(pair => statesMap[pair.Key])
		180	.ToDictionary(
		181	g => g.Key,
		182	g => g.SelectMany(pair => pair.Value).ToArray()
		183	);
		184
		185	// построение автомата
		186	foreach (var pair in optimalTags)
		187	optimalDFA.MarkFinalState(pair.Key, pair.Value);
		188
		189	foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
		190	optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
		191	}
		192
		193	public void PrintDFA() {
		194
		195	var inputMap = InputAlphabet.CreateReverseMap();
		196	var stateMap = StateAlphabet.CreateReverseMap();
		197
		198	for (int i = 0; i < inputMap.Length; i++) {
		199	Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
		200	}
		201
		202	foreach(var t in m_transitions)
		203	Console.WriteLine(
		204	"S{0} -{1}-> S{2}{3}",
		205	stateMap[t.s1],
		206	String.Join(",", inputMap[t.edge]),
		207	stateMap[t.s2],
		208	m_finalStates.ContainsKey(t.s2) ? "$" : ""
		209	);
		210
		211	}
		212	}
		213	}

Implab/Automaton/DFAStateDescriptor.cs created 644 +13 0

			@@ -0,0 +1,13
		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 {
		8	public struct DFAStateDescriptior<TTag> {
		9	public bool final;
		10	public TTag[] tag;
		11	public int[] transitions;
		12	}
		13	}

Implab/Automaton/DFAutomaton.cs created 644 +61 0

			@@ -0,0 +1,61
		1	using Implab;
		2	using System;
		3	using System.Collections.Generic;
		4	using System.Diagnostics;
		5	using System.Linq;
		6	using System.Text;
		7	using System.Threading.Tasks;
		8
		9	namespace Implab.Automaton {
		10	public abstract class DFAutomaton<T> {
		11	protected struct ContextFrame {
		12	public DFAStateDescriptior[] states;
		13	public int current;
		14	public T info;
		15	}
		16
		17	public const int INITIAL_STATE = DFADefinition.INITIAL_STATE;
		18	public const int UNREACHEBLE_STATE = DFADefinition.UNREACHEBLE_STATE;
		19
		20	protected ContextFrame m_context;
		21	Stack<ContextFrame> m_contextStack = new Stack<ContextFrame>();
		22
		23	protected int Level {
		24	get { return m_contextStack.Count; }
		25	}
		26
		27	protected DFAutomaton(DFAStateDescriptior[] states, int startState, T info) {
		28	Safe.ArgumentNotNull(states, "states");
		29	Safe.ArgumentInRange(startState, 0, states.Length - 1, "startState");
		30
		31	m_context.states = states;
		32	m_context.current = startState;
		33	m_context.info = info;
		34	}
		35
		36	protected void Switch(DFAStateDescriptior[] states, int current, T info) {
		37	Debug.Assert(states != null);
		38	Debug.Assert(current >= 0 && current < states.Length);
		39	m_contextStack.Push(m_context);
		40	m_context.states = states;
		41	m_context.current = current;
		42	m_context.info = info;
		43	}
		44
		45	protected void Restore() {
		46	Debug.Assert(m_contextStack.Count > 0);
		47
		48	m_context = m_contextStack.Pop();
		49	}
		50
		51	protected void Move(int input) {
		52	Debug.Assert(input > 0 && input < m_context.states[m_context.current].transitions.Length);
		53	m_context.current = m_context.states[m_context.current].transitions[input];
		54	}
		55
		56	protected bool CanMove(int input) {
		57	Debug.Assert(input > 0 && input < m_context.states[m_context.current].transitions.Length);
		58	return m_context.states[m_context.current].transitions[input] != UNREACHEBLE_STATE;
		59	}
		60	}
		61	}

Implab/Automaton/EDFADefinition.cs created 644 +29 0

			@@ -0,0 +1,29
		1	using Implab;
		2	using System;
		3
		4	namespace Implab.Parsing {
		5	public class EDFADefinition<T> : DFADefinition where T : struct, IConvertible {
		6	readonly EnumAlphabet<T> m_alphabet;
		7
		8	public EnumAlphabet<T> Alphabet {
		9	get { return m_alphabet; }
		10	}
		11
		12	public EDFADefinition(EnumAlphabet<T> alphabet) : base(alphabet.Count) {
		13	m_alphabet = alphabet;
		14	}
		15
		16	public void DefineTransition(int s1, int s2, T input) {
		17	DefineTransition(s1, s2, m_alphabet.Translate(input));
		18	}
		19
		20	public EDFADefinition<T> Optimize() {
		21
		22	return (EDFADefinition<T>)Optimize(alphabet => new EDFADefinition<T>((EnumAlphabet<T>)alphabet), m_alphabet, new EnumAlphabet<T>());
		23	}
		24
		25	public void PrintDFA() {
		26	PrintDFA(m_alphabet);
		27	}
		28	}
		29	}

Implab/Automaton/EnumAlphabet.cs created 644 +67 0

			@@ -0,0 +1,67
		1	using System;
		2	using System.Collections.Generic;
		3	using System.Diagnostics;
		4	using System.Globalization;
		5	using System.Linq;
		6	using System.Diagnostics.CodeAnalysis;
		7
		8	namespace Implab.Automaton {
		9	/// <summary>
		10	/// Алфавит символами которого являются элементы перечислений.
		11	/// </summary>
		12	/// <typeparam name="T">Тип перечислений</typeparam>
		13	public class EnumAlphabet<T> : IndexedAlphabetBase<T> where T : struct, IConvertible {
		14	[SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
		15	static readonly T[] _symbols;
		16	static readonly EnumAlphabet<T> _fullAlphabet;
		17
		18	[SuppressMessage("Microsoft.Design", "CA1065:DoNotRaiseExceptionsInUnexpectedLocations")]
		19	static EnumAlphabet() {
		20	if (!typeof(T).IsEnum)
		21	throw new InvalidOperationException("Invalid generic parameter, enumeration is required");
		22
		23	if (Enum.GetUnderlyingType(typeof(T)) != typeof(Int32))
		24	throw new InvalidOperationException("Only enums based on Int32 are supported");
		25
		26	_symbols = ((T[])Enum.GetValues(typeof(T)))
		27	.OrderBy(x => x.ToInt32(CultureInfo.InvariantCulture))
		28	.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	}
		38
		39
		40
		41	public static EnumAlphabet<T> FullAlphabet {
		42	get {
		43	return _fullAlphabet;
		44	}
		45	}
		46
		47
		48	public EnumAlphabet()
		49	: base(_symbols.Length) {
		50	}
		51
		52	public EnumAlphabet(int[] map)
		53	: base(map) {
		54	Debug.Assert(map.Length == _symbols.Length);
		55	}
		56
		57
		58	public override int GetSymbolIndex(T symbol) {
		59	return symbol.ToInt32(CultureInfo.InvariantCulture);
		60	}
		61
		62	public override IEnumerable<T> InputSymbols {
		63	get { return _symbols; }
		64	}
		65
		66	}
		67	}

Implab/Automaton/IAlphabet.cs created 644 +48 0

			@@ -0,0 +1,48
		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 {
		8	/// <summary>
		9	/// Алфавит. Множество символов, которые разбиты на классы, при этом классы имеют непрерывную нумерацию,
		10	/// что позволяет использовать их в качестве индексов массивов.
		11	/// </summary>
		12	/// <remarks>
		13	/// <para>Алфавит является сюрьективным отображением множества символов в множество индексов, это позволяет сократить размер таблицы переходов автомата
		14	/// для входных символов, которые для него не различимы.</para>
		15	/// </remarks>
		16	/// <typeparam name="TSymbol">Тип символов.</typeparam>
		17	public interface IAlphabet<TSymbol> {
		18	/// <summary>
		19	/// Количество классов символов в алфавите.
		20	/// </summary>
		21	int Count { get; }
		22
		23	/// <summary>
		24	/// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
		25	/// ему исходным символам.
		26	/// </summary>
		27	/// <returns></returns>
		28	List<TSymbol>[] CreateReverseMap();
		29
		30	/// <summary>
		31	/// Создает новый алфавит на основе текущего, горппируя его сиволы в более
		32	/// крупные непересекающиеся классы символов.
		33	/// </summary>
		34	/// <param name="newAlphabet">Новый, пустой алфавит, в котором быдут определены классы.</param>
		35	/// <param name="classes">Множество классов символов текущего алфавита.</param>
		36	/// <returns>Карта для перехода классов текущего
		37	/// алфавита к классам нового.</returns>
		38	/// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
		39	int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<IEnumerable<int>> classes);
		40
		41	/// <summary>
		42	/// Преобразует входной символ в индекс символа из алфавита.
		43	/// </summary>
		44	/// <param name="symobl">Исходный символ</param>
		45	/// <returns>Индекс в алфавите</returns>
		46	int Translate(TSymbol symobl);
		47	}
		48	}

Implab/Automaton/IAlphabetBuilder.cs created 644 +25 0

			@@ -0,0 +1,25
		1
		2	using System.Collections.Generic;
		3
		4	namespace Implab.Automaton {
		5	public interface IAlphabetBuilder<TSymbol> : IAlphabet<TSymbol> {
		6	/// <summary>
		7	/// Добавляет новый символ в алфавит, если символ уже был добавлен, то
		8	/// возвращается ранее сопоставленный с символом класс.
		9	/// </summary>
		10	/// <param name="symbol">Символ для добавления.</param>
		11	/// <returns>Индекс класса, который попоставлен с символом.</returns>
		12	int DefineSymbol(TSymbol symbol);
		13	/// <summary>
		14	/// Доабвляем класс символов. Множеству указанных исходных символов
		15	/// будет сопоставлен символ в алфавите.
		16	/// </summary>
		17	/// <param name="symbols">Множестов исходных символов</param>
		18	/// <returns>Идентификатор символа алфавита.</returns>
		19	int DefineClass(IEnumerable<TSymbol> symbols);
		20
		21
		22
		23	}
		24	}
		25

Implab/Automaton/IDFADefinition.cs created 644 +56 0

			@@ -0,0 +1,56
		1
		2	namespace Implab.Automaton {
		3	/// <summary>
		4	/// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
		5	/// </summary>
		6	/// <example>
		7	/// class MyAutomaton {
		8	/// int m_current;
		9	/// readonly DFAStateDescriptor<string>[] m_automaton;
		10	/// readonly IAlphabet<MyCommands> m_commands;
		11	///
		12	/// public MyAutomaton(IDFADefinition<MyCommands,MyStates,string> definition) {
		13	/// m_current = definition.StateAlphabet.Translate(MyStates.Initial);
		14	/// m_automaton = definition.GetTransitionTable();
		15	/// m_commands = definition.InputAlphabet;
		16	/// }
		17	///
		18	/// // defined a method which will move the automaton to the next state
		19	/// public void Move(MyCommands cmd) {
		20	/// // use transition map to determine the next state
		21	/// var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
		22	///
		23	/// // validate that we aren't in the unreachable state
		24	/// if (next == DFAConst.UNREACHABLE_STATE)
		25	/// throw new InvalidOperationException("The specified command is invalid");
		26	///
		27	/// // if everything is ok
		28	/// m_current = next;
		29	/// }
		30	/// }
		31	/// </example>
		32	public interface IDFADefinition<TInput, TState, TTag> {
		33	/// <summary>
		34	/// Алфавит входных символов
		35	/// </summary>
		36	/// <value>The input alphabet.</value>
		37	IAlphabet<TInput> InputAlphabet {
		38	get;
		39	}
		40
		41	/// <summary>
		42	/// Алфавит состояний автомата
		43	/// </summary>
		44	/// <value>The state alphabet.</value>
		45	IAlphabet<TState> StateAlphabet {
		46	get;
		47	}
		48
		49	/// <summary>
		50	/// Таблица переходов состояний автомата
		51	/// </summary>
		52	/// <returns>The transition table.</returns>
		53	DFAStateDescriptior<TTag>[] GetTransitionTable();
		54
		55	}
		56	}

Implab/Automaton/IDFADefinitionBuilder.cs created 644 +23 0

			@@ -0,0 +1,23
		1	using System;
		2
		3	namespace Implab.Automaton {
		4	public interface IDFADefinitionBuilder<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	}
		22	}
		23

Implab/Automaton/IndexedAlphabetBase.cs created 644 +105 0

			@@ -0,0 +1,105
		1	using Implab;
		2	using System;
		3	using System.Collections.Generic;
		4	using System.Diagnostics;
		5	using System.Linq;
		6
		7	namespace Implab.Automaton {
		8	/// <summary>
		9	/// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
		10	/// </summary>
		11	public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
		12	public const int UNCLASSIFIED = 0;
		13
		14	int m_nextId = 1;
		15	readonly int[] m_map;
		16
		17	public int Count {
		18	get { return m_nextId; }
		19	}
		20
		21	protected IndexedAlphabetBase(int mapSize) {
		22	m_map = new int[mapSize];
		23	}
		24
		25	protected IndexedAlphabetBase(int[] map) {
		26	Debug.Assert(map != null);
		27
		28	m_map = map;
		29	m_nextId = map.Max() + 1;
		30	}
		31
		32	public int DefineSymbol(T symbol) {
		33	var index = GetSymbolIndex(symbol);
		34	if (m_map[index] == UNCLASSIFIED)
		35	m_map[index] = m_nextId++;
		36	return m_map[index];
		37	}
		38
		39	public int DefineClass(IEnumerable<T> symbols) {
		40	Safe.ArgumentNotNull(symbols, "symbols");
		41	symbols = symbols.Distinct();
		42
		43	foreach (var symbol in symbols) {
		44	var index = GetSymbolIndex(symbol);
		45	if (m_map[index] == UNCLASSIFIED)
		46	m_map[GetSymbolIndex(symbol)] = m_nextId;
		47	else
		48	throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
		49	}
		50	return m_nextId++;
		51	}
		52
		53	public List<T>[] CreateReverseMap() {
		54	return
		55	Enumerable.Range(UNCLASSIFIED, Count)
		56	.Select(
		57	i => InputSymbols
		58	.Where(x => i != UNCLASSIFIED && m_map[GetSymbolIndex(x)] == i)
		59	.ToList()
		60	)
		61	.ToArray();
		62	}
		63
		64	public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
		65	Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
		66	Safe.ArgumentNotNull(classes, "classes");
		67	var reverseMap = CreateReverseMap();
		68
		69	var translationMap = new int[Count];
		70
		71	foreach (var scl in classes) {
		72	// skip if the supper class contains the unclassified element
		73	if (scl.Contains(UNCLASSIFIED))
		74	continue;
		75	var range = new List<T>();
		76	foreach (var cl in scl) {
		77	if (cl < 0 \|\| cl >= reverseMap.Length)
		78	throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
		79	range.AddRange(reverseMap[cl]);
		80	}
		81	var newClass = newAlphabet.DefineClass(range);
		82	foreach (var cl in scl)
		83	translationMap[cl] = newClass;
		84	}
		85
		86	return translationMap;
		87	}
		88
		89	public virtual int Translate(T symbol) {
		90	return m_map[GetSymbolIndex(symbol)];
		91	}
		92
		93	public abstract int GetSymbolIndex(T symbol);
		94
		95	public abstract IEnumerable<T> InputSymbols { get; }
		96
		97	/// <summary>
		98	/// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
		99	/// </summary>
		100	/// <returns>The translation map.</returns>
		101	public int[] GetTranslationMap() {
		102	return m_map;
		103	}
		104	}
		105	}

Implab/Automaton/ParserException.cs created 644 +17 0

			@@ -0,0 +1,17
		1	using System;
		2	using System.Collections.Generic;
		3	using System.Linq;
		4	using System.Text;
		5
		6	namespace Implab.Automaton {
		7	[Serializable]
		8	public class ParserException : Exception {
		9	public ParserException() { }
		10	public ParserException(string message) : base(message) { }
		11	public ParserException(string message, Exception inner) : base(message, inner) { }
		12	protected ParserException(
		13	System.Runtime.Serialization.SerializationInfo info,
		14	System.Runtime.Serialization.StreamingContext context)
		15	: base(info, context) { }
		16	}
		17	}

Implab/Automaton/RegularExpressions/AltToken.cs created 644 +17 0

			@@ -0,0 +1,17
		1	using System;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	public class AltToken<TTag>: BinaryToken<TTag> {
		5	public AltToken(Token<TTag> left, Token<TTag> right)
		6	: base(left, right) {
		7	}
		8
		9	public override void Accept(IVisitor<TTag> visitor) {
		10	Safe.ArgumentNotNull(visitor, "visitor");
		11	visitor.Visit(this);
		12	}
		13	public override string ToString() {
		14	return String.Format(Right is BinaryToken<TTag> ? "{0}\|({1})" : "{0}\|{1}", Left, Right);
		15	}
		16	}
		17	}

Implab/Automaton/RegularExpressions/BinaryToken.cs created 644 +21 0

			@@ -0,0 +1,21
		1	using Implab;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	public abstract class BinaryToken<TTag> : Token<TTag> {
		5	readonly Token<TTag> m_left;
		6	readonly Token<TTag> m_right;
		7
		8	public Token<TTag> Left {
		9	get { return m_left; }
		10	}
		11
		12	public Token<TTag> Right {
		13	get { return m_right; }
		14	}
		15
		16	protected BinaryToken(Token<TTag> left, Token<TTag> right) {
		17	Safe.ArgumentNotNull(m_left = left, "left");
		18	Safe.ArgumentNotNull(m_right = right, "right");
		19	}
		20	}
		21	}

Implab/Automaton/RegularExpressions/CatToken.cs created 644 +22 0

			@@ -0,0 +1,22
		1	using System;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	public class CatToken<TTag> : BinaryToken<TTag> {
		5	public CatToken(Token<TTag> left, Token<TTag> right)
		6	: base(left, right) {
		7	}
		8
		9	public override void Accept(IVisitor<TTag> visitor) {
		10	Safe.ArgumentNotNull(visitor, "visitor");
		11	visitor.Visit(this);
		12	}
		13
		14	public override string ToString() {
		15	return String.Format("{0}{1}", FormatToken(Left), FormatToken(Right));
		16	}
		17
		18	static string FormatToken(Token<TTag> token) {
		19	return String.Format(token is AltToken<TTag> ? "({0})" : "{0}", token);
		20	}
		21	}
		22	}

Implab/Automaton/RegularExpressions/DFABuilder.cs created 644 +181 0

			@@ -0,0 +1,181
		1	using Implab;
		2	using System;
		3	using System.Collections.Generic;
		4	using System.Diagnostics;
		5	using System.Linq;
		6
		7	namespace Implab.Automaton.RegularExpressions {
		8	/// <summary>
		9	/// Используется для построения ДКА по регулярному выражению, сначала обходит
		10	/// регулярное выражение и вычисляет followpos, затем используется метод
		11	/// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
		12	/// </summary>
		13	public class DFABuilder<TTag> : IVisitor<TTag> {
		14	int m_idx = 0;
		15	Token<TTag> m_root;
		16	HashSet<int> m_firstpos;
		17	HashSet<int> m_lastpos;
		18
		19	readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
		20	readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
		21	readonly Dictionary<int, TTag> m_ends = new Dictionary<int, TTag>();
		22
		23	public Dictionary<int, HashSet<int>> FollowposMap {
		24	get { return m_followpos; }
		25	}
		26
		27	public HashSet<int> Followpos(int pos) {
		28	HashSet<int> set;
		29	if (m_followpos.TryGetValue(pos, out set))
		30	return set;
		31	return m_followpos[pos] = new HashSet<int>();
		32	}
		33
		34	bool Nullable(object n) {
		35	if (n is EmptyToken<TTag> \|\| n is StarToken<TTag>)
		36	return true;
		37	if (n is AltToken<TTag>)
		38	return Nullable(((AltToken<TTag>)n).Left) \|\| Nullable(((AltToken<TTag>)n).Right);
		39	if (n is CatToken<TTag>)
		40	return Nullable(((CatToken<TTag>)n).Left) && Nullable(((CatToken<TTag>)n).Right);
		41	return false;
		42	}
		43
		44
		45	public void Visit(AltToken<TTag> token) {
		46	if (m_root == null)
		47	m_root = token;
		48	var firtspos = new HashSet<int>();
		49	var lastpos = new HashSet<int>();
		50
		51	token.Left.Accept(this);
		52	firtspos.UnionWith(m_firstpos);
		53	lastpos.UnionWith(m_lastpos);
		54
		55	token.Right.Accept(this);
		56	firtspos.UnionWith(m_firstpos);
		57	lastpos.UnionWith(m_lastpos);
		58
		59	m_firstpos = firtspos;
		60	m_lastpos = lastpos;
		61	}
		62
		63	public void Visit(StarToken<TTag> token) {
		64	if (m_root == null)
		65	m_root = token;
		66	token.Token.Accept(this);
		67
		68	foreach (var i in m_lastpos)
		69	Followpos(i).UnionWith(m_firstpos);
		70	}
		71
		72	public void Visit(CatToken<TTag> token) {
		73	if (m_root == null)
		74	m_root = token;
		75
		76	var firtspos = new HashSet<int>();
		77	var lastpos = new HashSet<int>();
		78	token.Left.Accept(this);
		79	firtspos.UnionWith(m_firstpos);
		80	var leftLastpos = m_lastpos;
		81
		82	token.Right.Accept(this);
		83	lastpos.UnionWith(m_lastpos);
		84	var rightFirstpos = m_firstpos;
		85
		86	if (Nullable(token.Left))
		87	firtspos.UnionWith(rightFirstpos);
		88
		89	if (Nullable(token.Right))
		90	lastpos.UnionWith(leftLastpos);
		91
		92	m_firstpos = firtspos;
		93	m_lastpos = lastpos;
		94
		95	foreach (var i in leftLastpos)
		96	Followpos(i).UnionWith(rightFirstpos);
		97
		98	}
		99
		100	public void Visit(EmptyToken<TTag> token) {
		101	if (m_root == null)
		102	m_root = token;
		103	}
		104
		105	public void Visit(SymbolToken<TTag> token) {
		106	if (m_root == null)
		107	m_root = token;
		108	m_idx++;
		109	m_indexes[m_idx] = token.Value;
		110	m_firstpos = new HashSet<int>(new[] { m_idx });
		111	m_lastpos = new HashSet<int>(new[] { m_idx });
		112	}
		113
		114	public void Visit(EndToken<TTag> token) {
		115	if (m_root == null)
		116	m_root = token;
		117	m_idx++;
		118	m_indexes[m_idx] = DFAConst.UNCLASSIFIED_INPUT;
		119	m_firstpos = new HashSet<int>(new[] { m_idx });
		120	m_lastpos = new HashSet<int>(new[] { m_idx });
		121	Followpos(m_idx);
		122	m_ends.Add(m_idx, token.Tag);
		123	}
		124
		125	public void BuildDFA(IDFADefinitionBuilder<TTag> dfa, IAlphabetBuilder<int> states) {
		126	Safe.ArgumentNotNull(dfa,"dfa");
		127
		128	var stateMap = new Dictionary<HashSet<int>, int>(new CustomEqualityComparer<HashSet<int>>(
		129	(x, y) => x.SetEquals(y),
		130	x => x.Sum(n => n.GetHashCode())
		131	));
		132
		133	int nextState = 0;
		134
		135	int initialState = states.DefineSymbol(nextState++);
		136	stateMap[m_firstpos] = initialState;
		137
		138	var tags = GetStateTags(m_firstpos);
		139	if (tags != null && tags.Length > 0)
		140	dfa.MarkFinalState(initialState, tags);
		141
		142	var inputMax = m_indexes.Values.Max();
		143	var queue = new Queue<HashSet<int>>();
		144
		145	queue.Enqueue(m_firstpos);
		146
		147	while (queue.Count > 0) {
		148	var state = queue.Dequeue();
		149	var s1 = stateMap[state];
		150
		151	for (int a = 0; a <= inputMax; a++) {
		152	var next = new HashSet<int>();
		153	foreach (var p in state) {
		154	if (m_indexes[p] == a) {
		155	next.UnionWith(Followpos(p));
		156	}
		157	}
		158	if (next.Count > 0) {
		159	int s2;
		160	if (!stateMap.TryGetValue(next, out s2)) {
		161	s2 = states.DefineSymbol(nextState++);
		162	stateMap[next] = s2;
		163	tags = GetStateTags(next);
		164	if (tags != null && tags.Length > 0)
		165	dfa.MarkFinalState(s2, tags);
		166
		167	queue.Enqueue(next);
		168	}
		169	dfa.DefineTransition(s1, s2, a);
		170	}
		171	}
		172	}
		173	}
		174
		175	TTag[] GetStateTags(IEnumerable<int> state) {
		176	Debug.Assert(state != null);
		177	return state.Where(m_ends.ContainsKey).Select(pos => m_ends[pos]).ToArray();
		178	}
		179
		180	}
		181	}

Implab/Automaton/RegularExpressions/EmptyToken.cs created 644 +13 0

			@@ -0,0 +1,13
		1	using Implab;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	public class EmptyToken<TTag> : Token<TTag> {
		5	public override void Accept(IVisitor<TTag> visitor) {
		6	Safe.ArgumentNotNull(visitor, "visitor");
		7	visitor.Visit(this);
		8	}
		9	public override string ToString() {
		10	return "$";
		11	}
		12	}
		13	}

Implab/Automaton/RegularExpressions/EndToken.cs created 644 +32 0

			@@ -0,0 +1,32
		1	using Implab;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	/// <summary>
		5	/// Конечный символ расширенного регулярного выражения, при построении ДКА
		6	/// используется для определения конечных состояний.
		7	/// </summary>
		8	public class EndToken<TTag>: Token<TTag> {
		9
		10	TTag m_tag;
		11
		12	public EndToken(TTag tag) {
		13	m_tag = tag;
		14	}
		15
		16	public EndToken()
		17	: this(0) {
		18	}
		19
		20	public TTag Tag {
		21	get { return m_tag; }
		22	}
		23
		24	public override void Accept(IVisitor<TTag> visitor) {
		25	Safe.ArgumentNotNull(visitor, "visitor");
		26	visitor.Visit(this);
		27	}
		28	public override string ToString() {
		29	return "#";
		30	}
		31	}
		32	}

Implab/Automaton/RegularExpressions/Grammar.cs created 644 +108 0

			@@ -0,0 +1,108
		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.RegularExpressions {
		9	/// <summary>
		10	/// Базовый абстрактный класс. Грамматика, позволяет формулировать выражения над алфавитом типа <c>char</c>.
		11	/// </summary>
		12	/// <typeparam name="TGrammar"></typeparam>
		13	public abstract class Grammar<TGrammar> where TGrammar: Grammar<TGrammar>, new() {
		14	static TGrammar _instance;
		15
		16	public static TGrammar Instance{
		17	get {
		18	if (_instance == null)
		19	_instance = new TGrammar();
		20	return _instance;
		21	}
		22	}
		23
		24	readonly CharAlphabet m_alphabet = new CharAlphabet();
		25
		26	public CharAlphabet Alphabet {
		27	get { return m_alphabet; }
		28	}
		29
		30	public SymbolToken UnclassifiedToken() {
		31	return new SymbolToken(CharAlphabet.UNCLASSIFIED);
		32	}
		33
		34	public void DefineAlphabet(IEnumerable<char> alphabet) {
		35	Safe.ArgumentNotNull(alphabet, "alphabet");
		36
		37	foreach (var ch in alphabet)
		38	m_alphabet.DefineSymbol(ch);
		39	}
		40	public Token SymbolRangeToken(char start, char end) {
		41	return SymbolToken(Enumerable.Range(start, end - start + 1).Select(x => (char)x));
		42	}
		43
		44	public Token SymbolToken(char symbol) {
		45	return Token.New(TranslateOrAdd(symbol));
		46	}
		47
		48	public Token SymbolToken(IEnumerable<char> symbols) {
		49	Safe.ArgumentNotNull(symbols, "symbols");
		50
		51	return Token.New(TranslateOrAdd(symbols).ToArray());
		52	}
		53
		54	public Token SymbolSetToken(params char[] set) {
		55	return SymbolToken(set);
		56	}
		57
		58	int TranslateOrAdd(char ch) {
		59	var t = m_alphabet.Translate(ch);
		60	if (t == CharAlphabet.UNCLASSIFIED)
		61	t = m_alphabet.DefineSymbol(ch);
		62	return t;
		63	}
		64
		65	IEnumerable<int> TranslateOrAdd(IEnumerable<char> symbols) {
		66	return symbols.Distinct().Select(TranslateOrAdd);
		67	}
		68
		69	int TranslateOrDie(char ch) {
		70	var t = m_alphabet.Translate(ch);
		71	if (t == CharAlphabet.UNCLASSIFIED)
		72	throw new ApplicationException(String.Format("Symbol '{0}' is UNCLASSIFIED", ch));
		73	return t;
		74	}
		75
		76	IEnumerable<int> TranslateOrDie(IEnumerable<char> symbols) {
		77	return symbols.Distinct().Select(TranslateOrDie);
		78	}
		79
		80	public Token SymbolTokenExcept(IEnumerable<char> symbols) {
		81	Safe.ArgumentNotNull(symbols, "symbols");
		82
		83	return Token.New( Enumerable.Range(0, m_alphabet.Count).Except(TranslateOrDie(symbols)).ToArray());
		84	}
		85
		86	protected CDFADefinition BuildDFA(Token lang) {
		87	Safe.ArgumentNotNull(lang, "lang");
		88
		89	var dfa = new CDFADefinition(m_alphabet);
		90
		91	var builder = new DFABuilder();
		92
		93	lang.Accept( builder );
		94
		95	builder.BuildDFA(dfa);
		96	if (dfa.InitialStateIsFinal)
		97	throw new ApplicationException("The specified language contains empty token");
		98
		99	return dfa.Optimize();
		100	}
		101
		102
		103
		104	//protected abstract TGrammar CreateInstance();
		105	}
		106
		107
		108	}

Implab/Automaton/RegularExpressions/IVisitor.cs created 644 +13 0

			@@ -0,0 +1,13
		1	namespace Implab.Automaton.RegularExpressions {
		2	/// <summary>
		3	/// Интерфейс обходчика синтаксического дерева регулярного выражения
		4	/// </summary>
		5	public interface IVisitor<TTag> {
		6	void Visit(AltToken<TTag> token);
		7	void Visit(StarToken<TTag> token);
		8	void Visit(CatToken<TTag> token);
		9	void Visit(EmptyToken<TTag> token);
		10	void Visit(EndToken<TTag> token);
		11	void Visit(SymbolToken<TTag> token);
		12	}
		13	}

Implab/Automaton/RegularExpressions/StarToken.cs created 644 +34 0

			@@ -0,0 +1,34
		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.RegularExpressions {
		9	/// <summary>
		10	/// Замыкание выражения с 0 и более повторов.
		11	/// </summary>
		12	public class StarToken<TTag>: Token<TTag> {
		13
		14	Token<TTag> m_token;
		15
		16	public Token<TTag> Token {
		17	get { return m_token; }
		18	}
		19
		20	public StarToken(Token<TTag> token) {
		21	Safe.ArgumentNotNull(token, "token");
		22	m_token = token;
		23	}
		24
		25	public override void Accept(IVisitor<TTag> visitor) {
		26	Safe.ArgumentNotNull(visitor, "visitor");
		27	visitor.Visit(this);
		28	}
		29
		30	public override string ToString() {
		31	return String.Format("({0})*", Token);
		32	}
		33	}
		34	}

Implab/Automaton/RegularExpressions/SymbolToken.cs created 644 +27 0

			@@ -0,0 +1,27
		1	using Implab;
		2
		3	namespace Implab.Automaton.RegularExpressions {
		4	/// <summary>
		5	/// Выражение, соответсвующее одному символу.
		6	/// </summary>
		7	public class SymbolToken<TTag> : Token<TTag> {
		8	int m_value;
		9
		10	public int Value {
		11	get { return m_value; }
		12	}
		13
		14	public SymbolToken(int value) {
		15	m_value = value;
		16	}
		17	public override void Accept(IVisitor<TTag> visitor) {
		18	Safe.ArgumentNotNull(visitor, "visitor");
		19
		20	visitor.Visit(this);
		21	}
		22
		23	public override string ToString() {
		24	return Value.ToString();
		25	}
		26	}
		27	}

Implab/Automaton/RegularExpressions/Token.cs created 644 +63 0

			@@ -0,0 +1,63
		1	using Implab;
		2	using System;
		3	using System.Linq;
		4
		5	namespace Implab.Automaton.RegularExpressions {
		6	public abstract class Token<TTag> {
		7	public abstract void Accept(IVisitor<TTag> visitor);
		8
		9	public Token<TTag> Extend() {
		10	return Cat(new EndToken<TTag>());
		11	}
		12
		13	public Token<TTag> Tag<T>(T tag) where T : IConvertible {
		14	return Cat(new EndToken<TTag>(tag));
		15	}
		16
		17	public Token<TTag> Cat(Token<TTag> right) {
		18	return new CatToken<TTag>(this, right);
		19	}
		20
		21	public Token<TTag> Or(Token<TTag> right) {
		22	return new AltToken<TTag>(this, right);
		23	}
		24
		25	public Token<TTag> Optional() {
		26	return Or(new EmptyToken<TTag>());
		27	}
		28
		29	public Token<TTag> EClosure() {
		30	return new StarToken<TTag>(this);
		31	}
		32
		33	public Token<TTag> Closure() {
		34	return Cat(new StarToken<TTag>(this));
		35	}
		36
		37	public Token<TTag> Repeat(int count) {
		38	Token<TTag> token = null;
		39
		40	for (int i = 0; i < count; i++)
		41	token = token != null ? token.Cat(this) : this;
		42	return token ?? new EmptyToken<TTag>();
		43	}
		44
		45	public Token<TTag> Repeat(int min, int max) {
		46	if (min > max \|\| min < 1)
		47	throw new ArgumentOutOfRangeException();
		48	var token = Repeat(min);
		49
		50	for (int i = min; i < max; i++)
		51	token = token.Cat( this.Optional() );
		52	return token;
		53	}
		54
		55	public static Token<TTag> New<T>(params T[] set) where T : struct, IConvertible {
		56	Safe.ArgumentNotNull(set, "set");
		57	Token<TTag> token = null;
		58	foreach(var c in set.Distinct())
		59	token = token == null ? new SymbolToken<TTag>(c) : token.Or(new SymbolToken<TTag>(c));
		60	return token;
		61	}
		62	}
		63	}

Implab/Automaton/Scanner.cs created 644 +259 0

			@@ -0,0 +1,259
		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	}

Implab/Implab.csproj +29 -25

                  <Compile Include="Parallels\ArrayTraits.cs" />
                  <Compile Include="Parallels\MTQueue.cs" />
                  <Compile Include="Parallels\WorkerPool.cs" />
-                 <Compile Include="Parsing\AltToken.cs" />
-                 <Compile Include="Parsing\BinaryToken.cs" />
-                 <Compile Include="Parsing\CatToken.cs" />
-                 <Compile Include="Parsing\CDFADefinition.cs" />
-                 <Compile Include="Parsing\DFABuilder.cs" />
-                 <Compile Include="Parsing\DFAStateDescriptor.cs" />
-                 <Compile Include="Parsing\DFAutomaton.cs" />
-                 <Compile Include="Parsing\EDFADefinition.cs" />
-                 <Compile Include="Parsing\EmptyToken.cs" />
-                 <Compile Include="Parsing\EndToken.cs" />
-                 <Compile Include="Parsing\EnumAlphabet.cs" />
-                 <Compile Include="Parsing\Grammar.cs" />
-                 <Compile Include="Parsing\IAlphabet.cs" />
-                 <Compile Include="Parsing\IDFADefinition.cs" />
-                 <Compile Include="Parsing\IVisitor.cs" />
-                 <Compile Include="Parsing\ParserException.cs" />
-                 <Compile Include="Parsing\Scanner.cs" />
-                 <Compile Include="Parsing\StarToken.cs" />
-                 <Compile Include="Parsing\SymbolToken.cs" />
-                 <Compile Include="Parsing\Token.cs" />
                  <Compile Include="ProgressInitEventArgs.cs" />
                  <Compile Include="Properties\AssemblyInfo.cs" />
                  <Compile Include="Parallels\AsyncPool.cs" />
                  <Compile Include="Components\ExecutionState.cs" />
                  <Compile Include="Components\RunnableComponent.cs" />
                  <Compile Include="Components\IFactory.cs" />
-                 <Compile Include="Parsing\DFADefinition.cs" />
-                 <Compile Include="Parsing\IndexedAlphabetBase.cs" />
-                 <Compile Include="Parsing\CharAlphabet.cs" />
-                 <Compile Include="Parsing\IAlphabetBuilder.cs" />
-                 <Compile Include="Parsing\IDFADefinitionBuilder.cs" />
+                 <Compile Include="Automaton\CDFADefinition.cs" />
+                 <Compile Include="Automaton\DFAStateDescriptor.cs" />
+                 <Compile Include="Automaton\DFAutomaton.cs" />
+                 <Compile Include="Automaton\EDFADefinition.cs" />
+                 <Compile Include="Automaton\EnumAlphabet.cs" />
+                 <Compile Include="Automaton\IAlphabet.cs" />
+                 <Compile Include="Automaton\IDFADefinition.cs" />
+                 <Compile Include="Automaton\ParserException.cs" />
+                 <Compile Include="Automaton\Scanner.cs" />
+                 <Compile Include="Automaton\DFADefinition.cs" />
+                 <Compile Include="Automaton\IndexedAlphabetBase.cs" />
+                 <Compile Include="Automaton\CharAlphabet.cs" />
+                 <Compile Include="Automaton\IAlphabetBuilder.cs" />
+                 <Compile Include="Automaton\IDFADefinitionBuilder.cs" />
+                 <Compile Include="Automaton\RegularExpressions\AltToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\BinaryToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\CatToken.cs" />
+                 <Compile Include="Automaton\DFAConst.cs" />
+                 <Compile Include="Automaton\RegularExpressions\Grammar.cs" />
+                 <Compile Include="Automaton\RegularExpressions\StarToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\SymbolToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\EmptyToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\EndToken.cs" />
+                 <Compile Include="Automaton\RegularExpressions\Token.cs" />
+                 <Compile Include="Automaton\RegularExpressions\IVisitor.cs" />
+                 <Compile Include="Automaton\RegularExpressions\DFABuilder.cs" />
+                 <Compile Include="Automaton\AutomatonTransition.cs" />
+                 <Compile Include="Automaton\ByteAlphabet.cs" />
                </ItemGroup>
                <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
                <ItemGroup />
                </ProjectExtensions>
                <ItemGroup>
                  <Folder Include="Components\" />
+                 <Folder Include="Automaton\RegularExpressions\" />
                </ItemGroup>
              </Project>
  No newline at end of file

Implab/Parsing/AltToken.cs removed 0 -17

NO CONTENT: file was removed

Implab/Parsing/BinaryToken.cs removed 0 -26

NO CONTENT: file was removed

Implab/Parsing/CDFADefinition.cs removed 0 -22

NO CONTENT: file was removed

Implab/Parsing/CatToken.cs removed 0 -22

NO CONTENT: file was removed

Implab/Parsing/CharAlphabet.cs removed 0 -23

NO CONTENT: file was removed

Implab/Parsing/DFABuilder.cs removed 0 -180

NO CONTENT: file was removed

Implab/Parsing/DFADefinition.cs removed 0 -285

NO CONTENT: file was removed

Implab/Parsing/DFAStateDescriptor.cs removed 0 -13

NO CONTENT: file was removed

Implab/Parsing/DFAutomaton.cs removed 0 -61

NO CONTENT: file was removed

Implab/Parsing/EDFADefinition.cs removed 0 -29

NO CONTENT: file was removed

Implab/Parsing/EmptyToken.cs removed 0 -18

NO CONTENT: file was removed

Implab/Parsing/EndToken.cs removed 0 -37

NO CONTENT: file was removed

Implab/Parsing/EnumAlphabet.cs removed 0 -67

NO CONTENT: file was removed

Implab/Parsing/Grammar.cs removed 0 -108

NO CONTENT: file was removed

Implab/Parsing/IAlphabet.cs removed 0 -48

NO CONTENT: file was removed

Implab/Parsing/IAlphabetBuilder.cs removed 0 -25

NO CONTENT: file was removed

Implab/Parsing/IDFADefinition.cs removed 0 -61

NO CONTENT: file was removed

Implab/Parsing/IDFADefinitionBuilder.cs removed 0 -9

NO CONTENT: file was removed

Implab/Parsing/IVisitor.cs removed 0 -19

NO CONTENT: file was removed

Implab/Parsing/IndexedAlphabetBase.cs removed 0 -107

NO CONTENT: file was removed

Implab/Parsing/ParserException.cs removed 0 -17

NO CONTENT: file was removed

Implab/Parsing/Scanner.cs removed 0 -259

NO CONTENT: file was removed

Implab/Parsing/StarToken.cs removed 0 -34

NO CONTENT: file was removed

Implab/Parsing/SymbolToken.cs removed 0 -33

NO CONTENT: file was removed

Implab/Parsing/Token.cs removed 0 -67

NO CONTENT: file was removed

General Comments 0

Write
Preview

You need to be logged in to leave comments. Login now

No TODOs yet

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages