Mercurial > pub > ImplabNet
changeset 161:2a8466f0cb8a v2
DFA refactoring
| author | cin |
|---|---|
| date | Fri, 19 Feb 2016 18:07:17 +0300 |
| parents | 5802131432e4 |
| children | 0526412bbb26 1c2a16d071a7 |
| files | Implab/Implab.csproj Implab/Parsing/DFADefinition.cs Implab/Parsing/DFAStateDescriptor.cs Implab/Parsing/IAlphabet.cs Implab/Parsing/IAlphabetBuilder.cs Implab/Parsing/IDFADefinition.cs Implab/Parsing/IDFADefinitionBuilder.cs Implab/Safe.cs |
| diffstat | 8 files changed, 135 insertions(+), 69 deletions(-) [+] |
line wrap: on
line diff
--- 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 />
--- 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");
--- 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; } }
--- 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> /// Преобразует входной символ в индекс символа из алфавита.
--- /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); + + + + } +} +
--- 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<MyCommands,MyStates,string> 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(); + } }
--- /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> { + + + } +} +
--- 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");