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>
  No newline at end of file

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 {
-                     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 {
                          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) {
-                         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");
                          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>
-                     int[] Reclassify(IAlphabet<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
+                     /// <returns>Карта для перехода классов текущего
+                     /// алфавита к классам нового.</returns>
+                     /// <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 +46 -24

		@@ -1,39 +1,61
1	1	using System;
2	2	using System.Collections.Generic;
3	3	using System.Linq;
4	4	using System.Text;
5	5	using System.Threading.Tasks;
6	6
7	7	namespace Implab.Parsing {
8	8	/// <summary>
9		/// Интерфейс для определения ДКА, позволяет добавить состояния и определить переходы.
10		/// </summary>
11		public interface IDFADefinition {
12		/// <summary>
13		/// Добавляет состояние в автомат.
14		/// </summary>
15		/// <returns>Индекс добавленного состояния.</returns>
16		int AddState();
17		/// <summary>
18		/// Добавляет конечное состояние с указанными метками, если метки не заданы, то
19		/// добавленное состояние не будет конечным.
	9	/// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
20	10	/// </summary>
21		/// <param name="tags">Метки состояния.</param>
22		/// <returns>Индекс добавленного состояния.</returns>
23		int AddState(int[] tags);
	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> {
24	38	/// <summary>
25		/// Определяет переход между состояниями.
	39	/// Алфавит входных символов
26	40	/// </summary>
27		/// <param name="s1">Исходное состояние.</param>
28		/// <param name="s2">Конечное состояние.</param>
29		/// <param name="input">Входной символ.</param>
30		void DefineTransition(int s1, int s2, int input);
	41	/// <value>The input alphabet.</value>
	42	IAlphabet<TInput> InputAlphabet {
	43	get;
	44	}
	45
31	46	/// <summary>
32		/// Размер входного алфавита.
	47	/// Алфавит состояний автомата
33	48	/// </summary>
34		/// <remarks>
35		/// Размер входного алфавита определяет количество возможных выходов из одного состояния. <see cref="IAlphabet{TSymbol}.Count"/>
36		/// </remarks>
37		int AlphabetSize { get; }
	49	/// <value>The state alphabet.</value>
	50	IAlphabet<TState> StateAlphabet {
	51	get;
	52	}
	53
	54	/// <summary>
	55	/// Таблица переходов состояний автомата
	56	/// </summary>
	57	/// <returns>The transition table.</returns>
	58	DFAStateDescriptior<TTag>[] GetTransitionTable();
	59
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