implab/ImplabNet Commit - r161:2a8466f0cb8a

DFA refactoring

cin -

r161:2a8466f0cb8a v2

parent child

Context file:

r161:2a8466f0cb8a

Collapse all files

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

@@ -0,0 +1,25
	1	using System;
	2	using System.Collections.Generic;
	3
	4	namespace Implab.Parsing {
	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/Parsing/IDFADefinitionBuilder.cs created 644 +9 0

@@ -0,0 +1,9
	1	using System;
	2
	3	namespace Implab.Parsing {
	4	public interface IDFADefinitionBuilder<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
	5
	6
	7	}
	8	}
	9

Implab/Implab.csproj +2 -3

             <?xml version="1.0" encoding="utf-8"?>
             <Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
               <PropertyGroup>
                 <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
                 <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
                 <ProjectGuid>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</ProjectGuid>
                 <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' ">
                 <DebugSymbols>true</DebugSymbols>
                 <DebugType>full</DebugType>
                 <Optimize>false</Optimize>
                 <OutputPath>bin\Debug</OutputPath>
                 <DefineConstants>TRACE;DEBUG;</DefineConstants>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <ConsolePause>false</ConsolePause>
                 <RunCodeAnalysis>true</RunCodeAnalysis>
               </PropertyGroup>
               <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
                 <DebugType>full</DebugType>
                 <Optimize>true</Optimize>
                 <OutputPath>bin\Release</OutputPath>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <ConsolePause>false</ConsolePause>
               </PropertyGroup>
               <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug 4.5|AnyCPU' ">
                 <DebugSymbols>true</DebugSymbols>
                 <DebugType>full</DebugType>
                 <Optimize>false</Optimize>
                 <OutputPath>bin\Debug</OutputPath>
                 <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <RunCodeAnalysis>true</RunCodeAnalysis>
                 <ConsolePause>false</ConsolePause>
               </PropertyGroup>
               <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release 4.5|AnyCPU' ">
                 <Optimize>true</Optimize>
                 <OutputPath>bin\Release</OutputPath>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <ConsolePause>false</ConsolePause>
                 <DefineConstants>NET_4_5</DefineConstants>
               </PropertyGroup>
               <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'DebugMono|AnyCPU' ">
                 <DebugSymbols>true</DebugSymbols>
                 <DebugType>full</DebugType>
                 <Optimize>false</Optimize>
                 <OutputPath>bin\Debug</OutputPath>
                 <DefineConstants>TRACE;DEBUG;NET_4_5;MONO</DefineConstants>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <RunCodeAnalysis>true</RunCodeAnalysis>
                 <ConsolePause>false</ConsolePause>
               </PropertyGroup>
               <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'ReleaseMono|AnyCPU' ">
                 <Optimize>true</Optimize>
                 <OutputPath>bin\Release</OutputPath>
                 <DefineConstants>NET_4_5;MONO;</DefineConstants>
                 <ErrorReport>prompt</ErrorReport>
                 <WarningLevel>4</WarningLevel>
                 <ConsolePause>false</ConsolePause>
               </PropertyGroup>
               <ItemGroup>
                 <Reference Include="System" />
                 <Reference Include="System.Xml" />
                 <Reference Include="mscorlib" />
               </ItemGroup>
               <ItemGroup>
                 <Compile Include="CustomEqualityComparer.cs" />
                 <Compile Include="Diagnostics\ConsoleTraceListener.cs" />
                 <Compile Include="Diagnostics\EventText.cs" />
                 <Compile Include="Diagnostics\LogChannel.cs" />
                 <Compile Include="Diagnostics\LogicalOperation.cs" />
                 <Compile Include="Diagnostics\TextFileListener.cs" />
                 <Compile Include="Diagnostics\TraceLog.cs" />
                 <Compile Include="Diagnostics\TraceEvent.cs" />
                 <Compile Include="Diagnostics\TraceEventType.cs" />
                 <Compile Include="ICancellable.cs" />
                 <Compile Include="IProgressHandler.cs" />
                 <Compile Include="IProgressNotifier.cs" />
                 <Compile Include="IPromiseT.cs" />
                 <Compile Include="IPromise.cs" />
                 <Compile Include="IServiceLocator.cs" />
                 <Compile Include="ITaskController.cs" />
                 <Compile Include="JSON\JSONElementContext.cs" />
                 <Compile Include="JSON\JSONElementType.cs" />
                 <Compile Include="JSON\JSONGrammar.cs" />
                 <Compile Include="JSON\JSONParser.cs" />
                 <Compile Include="JSON\JSONScanner.cs" />
                 <Compile Include="JSON\JsonTokenType.cs" />
                 <Compile Include="JSON\JSONWriter.cs" />
                 <Compile Include="JSON\JSONXmlReader.cs" />
                 <Compile Include="JSON\JSONXmlReaderOptions.cs" />
                 <Compile Include="JSON\StringTranslator.cs" />
                 <Compile Include="Parallels\DispatchPool.cs" />
                 <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="Safe.cs" />
                 <Compile Include="ValueEventArgs.cs" />
                 <Compile Include="PromiseExtensions.cs" />
                 <Compile Include="SyncContextPromise.cs" />
                 <Compile Include="Diagnostics\OperationContext.cs" />
                 <Compile Include="Diagnostics\TraceContext.cs" />
                 <Compile Include="Diagnostics\LogEventArgs.cs" />
                 <Compile Include="Diagnostics\LogEventArgsT.cs" />
                 <Compile Include="Diagnostics\Extensions.cs" />
                 <Compile Include="PromiseEventType.cs" />
                 <Compile Include="Parallels\AsyncQueue.cs" />
                 <Compile Include="PromiseT.cs" />
                 <Compile Include="IDeferred.cs" />
                 <Compile Include="IDeferredT.cs" />
                 <Compile Include="Promise.cs" />
                 <Compile Include="PromiseTransientException.cs" />
                 <Compile Include="Parallels\Signal.cs" />
                 <Compile Include="Parallels\SharedLock.cs" />
                 <Compile Include="Diagnostics\ILogWriter.cs" />
                 <Compile Include="Diagnostics\ListenerBase.cs" />
                 <Compile Include="Parallels\BlockingQueue.cs" />
                 <Compile Include="AbstractEvent.cs" />
                 <Compile Include="AbstractPromise.cs" />
                 <Compile Include="AbstractPromiseT.cs" />
                 <Compile Include="FuncTask.cs" />
                 <Compile Include="FuncTaskBase.cs" />
                 <Compile Include="FuncTaskT.cs" />
                 <Compile Include="ActionChainTaskBase.cs" />
                 <Compile Include="ActionChainTask.cs" />
                 <Compile Include="ActionChainTaskT.cs" />
                 <Compile Include="FuncChainTaskBase.cs" />
                 <Compile Include="FuncChainTask.cs" />
                 <Compile Include="FuncChainTaskT.cs" />
                 <Compile Include="ActionTaskBase.cs" />
                 <Compile Include="ActionTask.cs" />
                 <Compile Include="ActionTaskT.cs" />
                 <Compile Include="ICancellationToken.cs" />
                 <Compile Include="SuccessPromise.cs" />
                 <Compile Include="SuccessPromiseT.cs" />
                 <Compile Include="PromiseAwaiterT.cs" />
                 <Compile Include="PromiseAwaiter.cs" />
                 <Compile Include="Components\ComponentContainer.cs" />
                 <Compile Include="Components\Disposable.cs" />
                 <Compile Include="Components\DisposablePool.cs" />
                 <Compile Include="Components\ObjectPool.cs" />
                 <Compile Include="Components\ServiceLocator.cs" />
                 <Compile Include="Components\IInitializable.cs" />
                 <Compile Include="TaskController.cs" />
                 <Compile Include="Components\App.cs" />
                 <Compile Include="Components\IRunnable.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" />
               </ItemGroup>
               <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
               <ItemGroup />
               <ProjectExtensions>
                 <MonoDevelop>
                   <Properties>
                     <Policies>
                       <CSharpFormattingPolicy IndentSwitchBody="True" NamespaceBraceStyle="EndOfLine" ClassBraceStyle="EndOfLine" InterfaceBraceStyle="EndOfLine" StructBraceStyle="EndOfLine" EnumBraceStyle="EndOfLine" MethodBraceStyle="EndOfLine" ConstructorBraceStyle="EndOfLine" DestructorBraceStyle="EndOfLine" BeforeMethodDeclarationParentheses="False" BeforeMethodCallParentheses="False" BeforeConstructorDeclarationParentheses="False" NewLineBeforeConstructorInitializerColon="NewLine" NewLineAfterConstructorInitializerColon="SameLine" BeforeIndexerDeclarationBracket="False" BeforeDelegateDeclarationParentheses="False" NewParentheses="False" SpacesBeforeBrackets="False" inheritsSet="Mono" inheritsScope="text/x-csharp" scope="text/x-csharp" />
                       <TextStylePolicy FileWidth="120" EolMarker="Unix" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
                       <DotNetNamingPolicy DirectoryNamespaceAssociation="PrefixedHierarchical" ResourceNamePolicy="MSBuild" />
                       <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
                       <XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
                       <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
                       <NameConventionPolicy>
                         <Rules>
                           <NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
                             <RequiredPrefixes>
                               <String>I</String>
                             </RequiredPrefixes>
                           </NamingRule>
                           <NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
                             <RequiredSuffixes>
                               <String>Attribute</String>
                             </RequiredSuffixes>
                           </NamingRule>
                           <NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
                             <RequiredSuffixes>
                               <String>EventArgs</String>
                             </RequiredSuffixes>
                           </NamingRule>
                           <NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
                             <RequiredSuffixes>
                               <String>Exception</String>
                             </RequiredSuffixes>
                           </NamingRule>
                           <NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
                           <NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
                           <NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
                             <RequiredPrefixes>
                               <String>m_</String>
                             </RequiredPrefixes>
                           </NamingRule>
                           <NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True">
                             <RequiredPrefixes>
                               <String>_</String>
                             </RequiredPrefixes>
                           </NamingRule>
                           <NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
                             <RequiredPrefixes>
                               <String>m_</String>
                             </RequiredPrefixes>
                           </NamingRule>
                           <NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="AllUpper" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Parameters" AffectedEntity="Parameter, LocalVariable" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
                           <NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
                             <RequiredPrefixes>
                               <String>T</String>
                             </RequiredPrefixes>
                           </NamingRule>
                         </Rules>
                       </NameConventionPolicy>
                     </Policies>
                   </Properties>
                 </MonoDevelop>
               </ProjectExtensions>
               <ItemGroup>
                 <Folder Include="Components\" />
               </ItemGroup>
             </Project>

Implab/Parsing/DFADefinition.cs +40 -22

             using Implab;
             using System;
             using System.Collections.Generic;
             using System.Diagnostics;
             using System.Linq;
             namespace Implab.Parsing {
-                public class DFADefinition : IDFADefinition {
+                public class DFADefinition<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
-                    readonly List<DFAStateDescriptior> m_states;
+                    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());
+                        m_states.Add(new DFAStateDescriptior<TTag>());
-                    public DFAStateDescriptior[] States {
-                        get {
-                            if (m_statesArray == null)
-                                m_statesArray = m_states.ToArray();
-                            return m_statesArray;
                     }
                     public bool InitialStateIsFinal {
                         get {
                             return m_states[INITIAL_STATE].final;
                         }
                     }
                     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]
                         });
                         m_statesArray = null;
                         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
                         });
                         m_statesArray = null;
                         return index;
                     }
-                    public void DefineTransition(int s1,int s2, int symbol) {
+                    public void DefineTransition(TState s1, TState s2, TInput symbol) {
-                        Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
+                        int is1 = StateAlphabet.Translate(s1);
-                        Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
+                        int is2 = StateAlphabet.Translate(s2);
-                        Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
+                        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");
                         var setComparer = new CustomEqualityComparer<HashSet<int>>(
                             (x, y) => x.SetEquals(y),
                             (s) => s.Sum(x => x.GetHashCode())
                         );
                         var arrayComparer = new CustomEqualityComparer<int[]>(
                             (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
                             (a) => a.Sum(x => x.GetHashCode())
                         );
                         var optimalStates = new HashSet<HashSet<int>>(setComparer);
                         var queue = new HashSet<HashSet<int>>(setComparer);
                         foreach (var g in Enumerable
                             .Range(INITIAL_STATE, m_states.Count-1)
                             .Select(i => new {
                                 index = i,
                                 descriptor = m_states[i]
                             })
                             .Where(x => x.descriptor.final)
                             .GroupBy(x => x.descriptor.tag, arrayComparer)
                         ) {
                             optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
                         }
                         var state = new HashSet<int>(
                             Enumerable
                                 .Range(INITIAL_STATE, m_states.Count - 1)
                                 .Where(i => !m_states[i].final)
                         );
                         optimalStates.Add(state);
                         queue.Add(state);
                         while (queue.Count > 0) {
                             var stateA = queue.First();
                             queue.Remove(stateA);
                             for (int c = 0; c < AlphabetSize; c++) {
                                 var stateX = new HashSet<int>();
                                 for(int s = 1; s < m_states.Count; s++) {
                                     if (stateA.Contains(m_states[s].transitions[c]))
                                         stateX.Add(s);
                                 }
                                 foreach (var stateY in optimalStates.ToArray()) {
                                     if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
                                         var stateR1 = new HashSet<int>(stateY);
                                         var stateR2 = new HashSet<int>(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 initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
                         // карта получения оптимального состояния по соотвествующему ему простому состоянию
                         int[] reveseOptimalMap = new int[m_states.Count];
                         // карта с индексами оптимальных состояний
                         HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
                         {
                             optimalMap[0] = new HashSet<int>(); // unreachable state
                             optimalMap[1] = initialState; // initial state
                             foreach (var ss in initialState)
                                 reveseOptimalMap[ss] = 1;
                             int i = 2;
                             foreach (var s in optimalStates) {
                                 if (s.SetEquals(initialState))
                                     continue;
                                 optimalMap[i] = s;
                                 foreach (var ss in s)
                                     reveseOptimalMap[ss] = i;
                                 i++;
                             }
                         }
                         // получаем минимальный алфавит
                         var minClasses = new HashSet<HashSet<int>>(setComparer);
                         var alphaQueue = new Queue<HashSet<int>>();
                         alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
                         for (int s = 1 ; s < optimalMap.Length; s++) {
                             var newQueue = new Queue<HashSet<int>>();
                             foreach (var A in alphaQueue) {
                                 if (A.Count == 1) {
                                     minClasses.Add(A);
                                     continue;
                                 }
                                 // различаем классы символов, которые переводят в различные оптимальные состояния
                                 // optimalState -> alphaClass
                                 var classes = new Dictionary<int, HashSet<int>>();
                                 foreach (var term in A) {
                                     // ищем все переходы класса по символу term
                                     var s2 = reveseOptimalMap[
                                                  optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // первое допустимое элементарное состояние, если есть
                                              ];
                                     HashSet<int> A2;
                                     if (!classes.TryGetValue(s2, out A2)) {
                                         A2 = new HashSet<int>();
                                         newQueue.Enqueue(A2);
                                         classes[s2] = A2;
                                     }
                                     A2.Add(term);
                                 }
                             }
                             if (newQueue.Count == 0)
                                 break;
                             alphaQueue = newQueue;
                         }
                         foreach (var A in alphaQueue)
                             minClasses.Add(A);
                         var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
                         // построение автомата
                         var minimalDFA = dfaFactory(minimalAlphabet);
                         var states = new int[ optimalMap.Length ];
                         states[0] = UNREACHEBLE_STATE;
                         for(var s = INITIAL_STATE; s < states.Length; s++) {
                             var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
                             if (tags.Length > 0)
                                 states[s] = minimalDFA.AddState(tags);
                             else
                                 states[s] = minimalDFA.AddState();
                         }
                         Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
                         for (int s1 = 1; s1 < m_states.Count;  s1++) {
                             for (int c = 0; c < AlphabetSize; c++) {
                                 var s2 = m_states[s1].transitions[c];
                                 if (s2 != UNREACHEBLE_STATE) {
                                     minimalDFA.DefineTransition(
                                         reveseOptimalMap[s1],
                                         reveseOptimalMap[s2],
                                         alphabetMap[c]
                                     );
                                 }
                             }
                         }
                         return minimalDFA;
                     }
                     public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
                         var reverseMap = alphabet.CreateReverseMap();
                         for (int i = 1; i < reverseMap.Length; i++) {
                             Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
                         }
                         for (int i = 1; i < m_states.Count; i++) {
                             var s = m_states[i];
                             for (int c = 0; c < AlphabetSize; c++)
                                 if (s.transitions[c] != UNREACHEBLE_STATE)
                                     Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
                         }
                     }
                     public int AlphabetSize {
                         get {
                             return m_alpabetSize;
                         }
                     }
                 }
             }

Implab/Parsing/DFAStateDescriptor.cs +2 -2

             using System;
             using System.Collections.Generic;
             using System.Linq;
             using System.Text;
             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;
                 }
             }

Implab/Parsing/IAlphabet.cs +8 -20

             using System;
             using System.Collections.Generic;
             using System.Linq;
             using System.Text;
             using System.Threading.Tasks;
             namespace Implab.Parsing {
                 /// <summary>
                 /// Алфавит. Множество символов, которые разбиты на классы, при этом классы имеют непрерывную нумерацию,
                 /// что позволяет использовать их в качестве индексов массивов.
                 /// </summary>
                 /// <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>Карта для перехода классов текущего
-                    /// алфавита к символам нового.</returns>
+                    /// алфавита к классам нового.</returns>
-                    int[] Reclassify(IAlphabet<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
+                    /// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
+                    int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
                     /// <summary>
                     /// Преобразует входной символ в индекс символа из алфавита.
                     /// </summary>
                     /// <param name="symobl">Исходный символ</param>
                     /// <returns>Индекс в алфавите</returns>
                     int Translate(TSymbol symobl);
                 }
             }

Implab/Parsing/IDFADefinition.cs +44 -22

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

Implab/Safe.cs +5 0

             using System;
             using System.Collections.Generic;
             using System.Linq;
             using System.Text;
             using System.Text.RegularExpressions;
             using System.Diagnostics;
             namespace Implab
             {
                 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");
                         if (!rx.IsMatch(value))
                             throw new ArgumentException(String.Format("The prameter value must match {0}", rx), paramName);
                     }
                     public static void ArgumentNotEmpty(string value, string paramName) {
                         if (String.IsNullOrEmpty(value))
                             throw new ArgumentException("The parameter can't be empty", paramName);
                     }
                     public static void ArgumentNotEmpty<T>(T[] value, string paramName) {
                         if (value == null || value.Length == 0)
                             throw new ArgumentException("The array must be not emty", paramName);
                     }
                     public static void ArgumentNotNull(object value, string paramName) {
                         if (value == null)
                             throw new ArgumentNullException(paramName);
                     }
                     public static void ArgumentInRange(int value, int min, int max, string paramName) {
                         if (value < min || value > max)
                             throw new ArgumentOutOfRangeException(paramName);
                     }
                     public static void Dispose(params IDisposable[] objects) {
                         foreach (var d in objects)
                             if (d != null)
                                 d.Dispose();
                     }
                     public static void Dispose(params object[] objects) {
                         foreach (var obj in objects) {
                             var d = obj as IDisposable;
                             if (d != null)
                                 d.Dispose();
                         }
                     }
                     public static void Dispose(object obj) {
                         var d = obj as IDisposable;
                         if (d != null)
                             d.Dispose();
                     }
                     [DebuggerStepThrough]
                     public static IPromise<T> WrapPromise<T>(Func<T> action) {
                         ArgumentNotNull(action, "action");
                         var p = new Promise<T>();
                         try {
                             p.Resolve(action());
                         } catch (Exception err) {
                             p.Reject(err);
                         }
                         return p;
                     }
                     [DebuggerStepThrough]
                     public static IPromise WrapPromise(Action action) {
                         ArgumentNotNull(action, "action");
                         var p = new Promise();
                         try {
                             action();
                             p.Resolve();
                         } catch (Exception err) {
                             p.Reject(err);
                         }
                         return p;
                     }
                     [DebuggerStepThrough]
                     public static IPromise InvokePromise(Func<IPromise> action) {
                         ArgumentNotNull(action, "action");
                         try {
                             var p = action();
                             if (p == null) {
                                 var d = new Promise();
                                 d.Reject(new Exception("The action returned null"));
                                 p = d;
                             }
                             return p;
                         } catch (Exception err) {
                             var p = new Promise();
                             p.Reject(err);
                             return p;
                         }
                     }
                     [DebuggerStepThrough]
                     public static IPromise<T> InvokePromise<T>(Func<IPromise<T>> action) {
                         ArgumentNotNull(action, "action");
                         try {
                             return action() ?? Promise<T>.FromException(new Exception("The action returned null"));
                         } catch (Exception err) {
                             return Promise<T>.FromException(err);
                         }
                     }
                 }
             }

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