Mercurial > pub > ImplabNet

changeset 170:181119ef3b39 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DFA refactoring, rx based dfa.
author cin
date Fri, 04 Mar 2016 01:56:31 +0300
parents 54270c2f29f2
children 0f70905b4652
files Implab/Automaton/RegularExpressions/EndToken.cs Implab/Automaton/RegularExpressions/IDFATable2.cs Implab/Automaton/RegularExpressions/RegularDFABuilder.cs Implab/Automaton/RegularExpressions/RegularDFADefinition.cs Implab/Implab.csproj
diffstat 5 files changed, 33 insertions(+), 17 deletions(-) [+]
line wrap: on
line diff
--- a/Implab/Automaton/RegularExpressions/EndToken.cs	Thu Mar 03 08:41:02 2016 +0300
+++ b/Implab/Automaton/RegularExpressions/EndToken.cs	Fri Mar 04 01:56:31 2016 +0300
@@ -14,7 +14,7 @@
         }
 
         public EndToken()
-            : this(0) {
+            : this(default(TTag)) {
         }
 
         public TTag Tag {
--- a/Implab/Automaton/RegularExpressions/IDFATable2.cs	Thu Mar 03 08:41:02 2016 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,9 +0,0 @@
-using System;
-
-namespace Implab.Automaton.RegularExpressions {
-    public interface IDFATable2<TTag> : IDFATable {
-        void MarkFinalState(int state, TTag[] tags);
-
-    }
-}
-
--- a/Implab/Automaton/RegularExpressions/RegularDFABuilder.cs	Thu Mar 03 08:41:02 2016 +0300
+++ b/Implab/Automaton/RegularExpressions/RegularDFABuilder.cs	Fri Mar 04 01:56:31 2016 +0300
@@ -122,7 +122,7 @@
             m_ends.Add(m_idx, token.Tag);
         }
 
-        public void BuildDFA(IDFATableBuilder<TTag> dfa) {
+        public void BuildDFA(IDFATableBuilder dfa) {
             Safe.ArgumentNotNull(dfa,"dfa");
 
             var states = new MapAlphabet<HashSet<int>>(new CustomEqualityComparer<HashSet<int>>(
@@ -165,7 +165,7 @@
                             
                             queue.Enqueue(next);
                         }
-                        dfa.DefineTransition(s1, s2, a);
+                        dfa.Add(new AutomatonTransition(s1, s2, a));
                     }
                 }
             }
--- a/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs	Thu Mar 03 08:41:02 2016 +0300
+++ b/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs	Fri Mar 04 01:56:31 2016 +0300
@@ -1,8 +1,11 @@
 using System;
+using System.Collections.Generic;
+using System.Linq;
 
 namespace Implab.Automaton.RegularExpressions {
     public class RegularDFADefinition<TInput, TTag> : DFATable {
 
+        readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
         readonly IAlphabet<TInput> m_alphabet;
 
         public RegularDFADefinition(IAlphabet<TInput> alphabet) {
@@ -25,16 +28,39 @@
             return base.ConstructTransitionTable();
         }
 
+        public void MarkFinalState(int s, TTag[] tags) {
+            MarkFinalState(s);
+            SetStateTag(s, tags);
+        }
+
+        public void SetStateTag(int s, TTag[] tags) {
+            Safe.ArgumentNotNull(tags, "tags");
+            m_tags[s] = tags;
+        }
+
+        public TTag[] GetStateTag(int s) {
+            TTag[] tags;
+            return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
+        }
+
         /// <summary>
         /// Optimize the specified alphabet.
         /// </summary>
-        /// <param name = "dfaTable"></param>
         /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
-        public void Optimize(IDFATableBuilder<TTag> dfaTable, IAlphabetBuilder<TInput> alphabet) {
+        public RegularDFADefinition<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
             Safe.ArgumentNotNull(alphabet, "alphabet");
-            Safe.ArgumentNotNull(dfaTable, "dfaTable");
+
+            var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
+
+            var states = new DummyAlphabet(StateCount);
+            var map = new MapAlphabet<int>();
 
-            Optimize(dfaTable, InputAlphabet, alphabet, new DummyAlphabet(StateCount), new MapAlphabet<int>()); 
+            Optimize(dfaTable, InputAlphabet, alphabet, states, map); 
+
+            foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => map.Translate(x.Key), x => x.Value ))
+                dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
+
+            return dfaTable;
         }
 
 
--- a/Implab/Implab.csproj	Thu Mar 03 08:41:02 2016 +0300
+++ b/Implab/Implab.csproj	Fri Mar 04 01:56:31 2016 +0300
@@ -190,7 +190,6 @@
     <Compile Include="Automaton\IDFATable.cs" />
     <Compile Include="Automaton\IDFATableBuilder.cs" />
     <Compile Include="Automaton\DFATable.cs" />
-    <Compile Include="Automaton\RegularExpressions\IDFATable2.cs" />
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <ItemGroup />