# HG changeset patch
# User cin
# Date 1455894437 -10800
# Node ID 2a8466f0cb8aacae858116af47493d1126bfeecc
# Parent  5802131432e41edeb1de28fa005c6f5911a71555
DFA refactoring

diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Implab.csproj
--- a/Implab/Implab.csproj	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Implab.csproj	Fri Feb 19 18:07:17 2016 +0300
@@ -7,9 +7,6 @@
     <OutputType>Library</OutputType>
     <RootNamespace>Implab</RootNamespace>
     <AssemblyName>Implab</AssemblyName>
-    <ProductVersion>8.0.30703</ProductVersion>
-    <SchemaVersion>2.0</SchemaVersion>
-    <ReleaseVersion>0.2</ReleaseVersion>
     <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
@@ -184,6 +181,8 @@
     <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" />
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <ItemGroup />
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/DFADefinition.cs
--- a/Implab/Parsing/DFADefinition.cs	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Parsing/DFADefinition.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -5,28 +5,20 @@
 using System.Linq;
 
 namespace Implab.Parsing {
-    public class DFADefinition : IDFADefinition {
-        readonly List<DFAStateDescriptior> m_states;
+    public class DFADefinition<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
+        readonly List<DFAStateDescriptior<TTag>> m_states;
         
         public const int INITIAL_STATE = 1;
         public const int UNREACHEBLE_STATE = 0;
 
-        DFAStateDescriptior[] m_statesArray;
+        DFAStateDescriptior<TTag>[] m_statesArray;
         readonly int m_alpabetSize;
 
         public DFADefinition(int alphabetSize) {
-            m_states = new List<DFAStateDescriptior>();
+            m_states = new List<DFAStateDescriptior<TTag>>();
             m_alpabetSize = alphabetSize;
         
-            m_states.Add(new DFAStateDescriptior());
-        }
-
-        public DFAStateDescriptior[] States {
-            get {
-                if (m_statesArray == null)
-                    m_statesArray = m_states.ToArray();
-                return m_statesArray;
-            }
+            m_states.Add(new DFAStateDescriptior<TTag>());
         }
 
         public bool InitialStateIsFinal {
@@ -37,7 +29,7 @@
 
         public int AddState() {
             var index = m_states.Count;
-            m_states.Add(new DFAStateDescriptior {
+            m_states.Add(new DFAStateDescriptior<TTag> {
                 final = false,
                 transitions = new int[AlphabetSize]
             });
@@ -46,10 +38,10 @@
             return index;
         }
 
-        public int AddState(int[] tag) {
+        public int AddState(TTag[] tag) {
             var index = m_states.Count;
             bool final = tag != null && tag.Length != 0;
-            m_states.Add(new DFAStateDescriptior {
+            m_states.Add(new DFAStateDescriptior<TTag> {
                 final = final,
                 transitions = new int[AlphabetSize],
                 tag = final ? tag : null
@@ -58,15 +50,41 @@
             return index;
         }
 
-        public void DefineTransition(int s1,int s2, int symbol) {
-            Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
-            Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
-            Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
+        public void DefineTransition(TState s1, TState s2, TInput symbol) {
+            int is1 = StateAlphabet.Translate(s1);
+            int is2 = StateAlphabet.Translate(s2);
+            int isym = InputAlphabet.Translate(symbol);
 
-            m_states[s1].transitions[symbol] = s2;
+            Safe.ArgumentAssert(is1 != 0, "s1");
+            Safe.ArgumentAssert(is2 != 0, "s2");
+            Safe.ArgumentAssert(isym != 0, "symbol");
+
+            m_states[is1].transitions[isym] = is2;
         }
 
-        protected IDFADefinition Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
+        #region IDFADefinition implementation
+
+        public DFAStateDescriptior<TTag>[] GetTransitionTable() {
+            if (m_statesArray == null)
+                m_statesArray = m_states.ToArray();
+            return m_statesArray;
+        }
+
+        public IAlphabet<TInput> InputAlphabet {
+            get {
+                throw new NotImplementedException();
+            }
+        }
+
+        public IAlphabet<TState> StateAlphabet {
+            get {
+                throw new NotImplementedException();
+            }
+        }
+
+        #endregion
+
+        protected IDFADefinition<> Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
             Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
             Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
 
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/DFAStateDescriptor.cs
--- a/Implab/Parsing/DFAStateDescriptor.cs	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Parsing/DFAStateDescriptor.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -5,9 +5,9 @@
 using System.Threading.Tasks;
 
 namespace Implab.Parsing {
-    public struct DFAStateDescriptior {
+    public struct DFAStateDescriptior<TTag> {
         public bool final;
-        public int[] tag;
+        public TTag[] tag;
         public int[] transitions;
     }
 }
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/IAlphabet.cs
--- a/Implab/Parsing/IAlphabet.cs	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Parsing/IAlphabet.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -12,43 +12,31 @@
     /// <remarks>
     /// <para>Алфавит является сюрьективным отображением множества символов в множество индексов, это позволяет сократить размер таблицы переходов автомата
     /// для входных символов, которые для него не различимы.</para>
-    /// <para>Далее символами алфавита будем называть классы исходных символов.</para>
     /// </remarks>
     /// <typeparam name="TSymbol">Тип символов.</typeparam>
     public interface IAlphabet<TSymbol> {
         /// <summary>
-        /// Количество символов в алфавите.
+        /// Количество классов символов в алфавите.
         /// </summary>
         int Count { get; }
-        /// <summary>
-        /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
-        /// возвращается ранее сопоставленный с символом класс.
-        /// </summary>
-        /// <param name="symbol">Символ для добавления.</param>
-        /// <returns>Индекс класса, который попоставлен с символом.</returns>
-        int DefineSymbol(TSymbol symbol);
+
         /// <summary>
-        /// Доабвляем класс символов. Множеству указанных исходных символов 
-        /// будет сопоставлен символ в алфавите.
-        /// </summary>
-        /// <param name="symbols">Множестов исходных символов</param>
-        /// <returns>Идентификатор символа алфавита.</returns>
-        int DefineClass(IEnumerable<TSymbol> symbols);
-        /// <summary>
-        /// Создает карту обратного сопоставления символа алфавита и сопоставленным
+        /// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
         /// ему исходным символам.
         /// </summary>
         /// <returns></returns>
         List<TSymbol>[] CreateReverseMap();
+
         /// <summary>
         /// Создает новый алфавит на основе текущего, горппируя его сиволы в более
         /// крупные непересекающиеся классы символов.
         /// </summary>
         /// <param name="newAlphabet">Новый, пустой алфавит, в котором быдут определены классы.</param>
         /// <param name="classes">Множество классов символов текущего алфавита.</param>
-        /// <returns>Карта для перехода символов текущего
-        /// алфавита к символам нового.</returns>
-        int[] Reclassify(IAlphabet<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
+        /// <returns>Карта для перехода классов текущего
+        /// алфавита к классам нового.</returns>
+        /// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
+        int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
 
         /// <summary>
         /// Преобразует входной символ в индекс символа из алфавита.
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/IAlphabetBuilder.cs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Parsing/IAlphabetBuilder.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -0,0 +1,25 @@
+using System;
+using System.Collections.Generic;
+
+namespace Implab.Parsing {
+    public interface IAlphabetBuilder<TSymbol> : IAlphabet<TSymbol> {
+        /// <summary>
+        /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
+        /// возвращается ранее сопоставленный с символом класс.
+        /// </summary>
+        /// <param name="symbol">Символ для добавления.</param>
+        /// <returns>Индекс класса, который попоставлен с символом.</returns>
+        int DefineSymbol(TSymbol symbol);
+        /// <summary>
+        /// Доабвляем класс символов. Множеству указанных исходных символов 
+        /// будет сопоставлен символ в алфавите.
+        /// </summary>
+        /// <param name="symbols">Множестов исходных символов</param>
+        /// <returns>Идентификатор символа алфавита.</returns>
+        int DefineClass(IEnumerable<TSymbol> symbols);
+
+
+
+    }
+}
+
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/IDFADefinition.cs
--- a/Implab/Parsing/IDFADefinition.cs	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Parsing/IDFADefinition.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -6,34 +6,56 @@
 
 namespace Implab.Parsing {
     /// <summary>
-    /// Интерфейс для определения ДКА, позволяет добавить состояния и определить переходы.
+    /// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
     /// </summary>
-    public interface IDFADefinition {
+    /// <example>
+    /// class MyAutomaton {
+    ///     int m_current;
+    ///     readonly DFAStateDescriptor<string>[] m_automaton;
+    ///     readonly IAlphabet<MyCommands> m_commands;
+    /// 
+    ///     public MyAutomaton(IDFADefinition&lt;MyCommands,MyStates,string&gt; definition) {
+    ///         m_current = definition.StateAlphabet.Translate(MyStates.Initial);
+    ///         m_automaton = definition.GetTransitionTable();
+    ///         m_commands = definition.InputAlphabet;
+    ///     }
+    /// 
+    ///     // defined a method which will move the automaton to the next state
+    ///     public void Move(MyCommands cmd) {
+    ///         // use transition map to determine the next state
+    ///         var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
+    /// 
+    ///         // validate that we aren't in the unreachable state
+    ///         if (next == DFAConst.UNREACHABLE_STATE)
+    ///             throw new InvalidOperationException("The specified command is invalid");
+    /// 
+    ///         // if everything is ok
+    ///         m_current = next;
+    ///     }
+    /// }
+    /// </example>
+    public interface IDFADefinition<TInput, TState, TTag> {
         /// <summary>
-        /// Добавляет состояние в автомат.
-        /// </summary>
-        /// <returns>Индекс добавленного состояния.</returns>
-        int AddState();
-        /// <summary>
-        /// Добавляет конечное состояние с указанными метками, если метки не заданы, то
-        /// добавленное состояние не будет конечным.
+        /// Алфавит входных символов
         /// </summary>
-        /// <param name="tags">Метки состояния.</param>
-        /// <returns>Индекс добавленного состояния.</returns>
-        int AddState(int[] tags);
+        /// <value>The input alphabet.</value>
+        IAlphabet<TInput> InputAlphabet {
+            get;
+        }
+
         /// <summary>
-        /// Определяет переход между состояниями.
+        /// Алфавит состояний автомата
         /// </summary>
-        /// <param name="s1">Исходное состояние.</param>
-        /// <param name="s2">Конечное состояние.</param>
-        /// <param name="input">Входной символ.</param>
-        void DefineTransition(int s1, int s2, int input);
+        /// <value>The state alphabet.</value>
+        IAlphabet<TState> StateAlphabet {
+            get;
+        }
+
         /// <summary>
-        /// Размер входного алфавита. 
+        /// Таблица переходов состояний автомата
         /// </summary>
-        /// <remarks>
-        /// Размер входного алфавита определяет количество возможных выходов из одного состояния. <see cref="IAlphabet{TSymbol}.Count"/> 
-        /// </remarks>
-        int AlphabetSize { get; }
+        /// <returns>The transition table.</returns>
+        DFAStateDescriptior<TTag>[] GetTransitionTable();
+
     }
 }
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Parsing/IDFADefinitionBuilder.cs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Parsing/IDFADefinitionBuilder.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -0,0 +1,9 @@
+using System;
+
+namespace Implab.Parsing {
+    public interface IDFADefinitionBuilder<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
+
+
+    }
+}
+
diff -r 5802131432e4 -r 2a8466f0cb8a Implab/Safe.cs
--- a/Implab/Safe.cs	Thu Feb 18 19:38:54 2016 +0300
+++ b/Implab/Safe.cs	Fri Feb 19 18:07:17 2016 +0300
@@ -9,6 +9,11 @@
 {
     public static class Safe
     {
+        public static void ArgumentAssert(bool condition, string paramName) {
+            if (!condition)
+                throw new ArgumentException("The parameter is invalid", paramName);
+        }
+
         public static void ArgumentMatch(string value, string paramName, Regex rx) {
             if (rx == null)
                 throw new ArgumentNullException("rx");