##// END OF EJS Templates
implab » ImplabNet
RSS
DFA refactoring
cin -
r161:2a8466f0cb8a v2
parent child
Show More
Show file before | Show file after | Hide comments
@@ -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
Show file before | Show file after | Hide comments
@@ -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
Show file before | Show file after | Hide comments
@@ -7,9 +7,6
7 7 <OutputType>Library</OutputType>
8 8 <RootNamespace>Implab</RootNamespace>
9 9 <AssemblyName>Implab</AssemblyName>
10 <ProductVersion>8.0.30703</ProductVersion>
11 <SchemaVersion>2.0</SchemaVersion>
12 <ReleaseVersion>0.2</ReleaseVersion>
13 10 <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
14 11 </PropertyGroup>
15 12 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
@@ -184,6 +181,8
184 181 <Compile Include="Parsing\DFADefinition.cs" />
185 182 <Compile Include="Parsing\IndexedAlphabetBase.cs" />
186 183 <Compile Include="Parsing\CharAlphabet.cs" />
184 <Compile Include="Parsing\IAlphabetBuilder.cs" />
185 <Compile Include="Parsing\IDFADefinitionBuilder.cs" />
187 186 </ItemGroup>
188 187 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
189 188 <ItemGroup />
Show file before | Show file after | Hide comments
@@ -5,28 +5,20 using System.Diagnostics;
5 5 using System.Linq;
6 6
7 7 namespace Implab.Parsing {
8 public class DFADefinition : IDFADefinition {
9 readonly List<DFAStateDescriptior> m_states;
8 public class DFADefinition<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
9 readonly List<DFAStateDescriptior<TTag>> m_states;
10 10
11 11 public const int INITIAL_STATE = 1;
12 12 public const int UNREACHEBLE_STATE = 0;
13 13
14 DFAStateDescriptior[] m_statesArray;
14 DFAStateDescriptior<TTag>[] m_statesArray;
15 15 readonly int m_alpabetSize;
16 16
17 17 public DFADefinition(int alphabetSize) {
18 m_states = new List<DFAStateDescriptior>();
18 m_states = new List<DFAStateDescriptior<TTag>>();
19 19 m_alpabetSize = alphabetSize;
20 20
21 m_states.Add(new DFAStateDescriptior());
22 }
23
24 public DFAStateDescriptior[] States {
25 get {
26 if (m_statesArray == null)
27 m_statesArray = m_states.ToArray();
28 return m_statesArray;
29 }
21 m_states.Add(new DFAStateDescriptior<TTag>());
30 22 }
31 23
32 24 public bool InitialStateIsFinal {
@@ -37,7 +29,7 namespace Implab.Parsing {
37 29
38 30 public int AddState() {
39 31 var index = m_states.Count;
40 m_states.Add(new DFAStateDescriptior {
32 m_states.Add(new DFAStateDescriptior<TTag> {
41 33 final = false,
42 34 transitions = new int[AlphabetSize]
43 35 });
@@ -46,10 +38,10 namespace Implab.Parsing {
46 38 return index;
47 39 }
48 40
49 public int AddState(int[] tag) {
41 public int AddState(TTag[] tag) {
50 42 var index = m_states.Count;
51 43 bool final = tag != null && tag.Length != 0;
52 m_states.Add(new DFAStateDescriptior {
44 m_states.Add(new DFAStateDescriptior<TTag> {
53 45 final = final,
54 46 transitions = new int[AlphabetSize],
55 47 tag = final ? tag : null
@@ -58,15 +50,41 namespace Implab.Parsing {
58 50 return index;
59 51 }
60 52
61 public void DefineTransition(int s1,int s2, int symbol) {
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
53 public void DefineTransition(TState s1, TState s2, TInput symbol) {
54 int is1 = StateAlphabet.Translate(s1);
55 int is2 = StateAlphabet.Translate(s2);
56 int isym = InputAlphabet.Translate(symbol);
65 57
66 m_states[s1].transitions[symbol] = s2;
58 Safe.ArgumentAssert(is1 != 0, "s1");
59 Safe.ArgumentAssert(is2 != 0, "s2");
60 Safe.ArgumentAssert(isym != 0, "symbol");
61
62 m_states[is1].transitions[isym] = is2;
67 63 }
68 64
69 protected IDFADefinition Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
65 #region IDFADefinition implementation
66
67 public DFAStateDescriptior<TTag>[] GetTransitionTable() {
68 if (m_statesArray == null)
69 m_statesArray = m_states.ToArray();
70 return m_statesArray;
71 }
72
73 public IAlphabet<TInput> InputAlphabet {
74 get {
75 throw new NotImplementedException();
76 }
77 }
78
79 public IAlphabet<TState> StateAlphabet {
80 get {
81 throw new NotImplementedException();
82 }
83 }
84
85 #endregion
86
87 protected IDFADefinition<> Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
70 88 Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
71 89 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
72 90
Show file before | Show file after | Hide comments
@@ -5,9 +5,9 using System.Text;
5 5 using System.Threading.Tasks;
6 6
7 7 namespace Implab.Parsing {
8 public struct DFAStateDescriptior {
8 public struct DFAStateDescriptior<TTag> {
9 9 public bool final;
10 public int[] tag;
10 public TTag[] tag;
11 11 public int[] transitions;
12 12 }
13 13 }
Show file before | Show file after | Hide comments
@@ -12,43 +12,31 namespace Implab.Parsing {
12 12 /// <remarks>
13 13 /// <para>Алфавит является сюрьективным отображением множества символов в множество индексов, это позволяет сократить размер таблицы переходов автомата
14 14 /// для входных символов, которые для него не различимы.</para>
15 /// <para>Далее символами алфавита будем называть классы исходных символов.</para>
16 15 /// </remarks>
17 16 /// <typeparam name="TSymbol">Тип символов.</typeparam>
18 17 public interface IAlphabet<TSymbol> {
19 18 /// <summary>
20 /// Количество символов в алфавите.
19 /// Количество классов символов в алфавите.
21 20 /// </summary>
22 21 int Count { get; }
23 /// <summary>
24 /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
25 /// возвращается ранее сопоставленный с символом класс.
26 /// </summary>
27 /// <param name="symbol">Символ для добавления.</param>
28 /// <returns>Индекс класса, который попоставлен с символом.</returns>
29 int DefineSymbol(TSymbol symbol);
22
30 23 /// <summary>
31 /// Доабвляем класс символов. Множеству указанных исходных символов
32 /// будет сопоставлен символ в алфавите.
33 /// </summary>
34 /// <param name="symbols">Множестов исходных символов</param>
35 /// <returns>Идентификатор символа алфавита.</returns>
36 int DefineClass(IEnumerable<TSymbol> symbols);
37 /// <summary>
38 /// Создает карту обратного сопоставления символа алфавита и сопоставленным
24 /// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
39 25 /// ему исходным символам.
40 26 /// </summary>
41 27 /// <returns></returns>
42 28 List<TSymbol>[] CreateReverseMap();
29
43 30 /// <summary>
44 31 /// Создает новый алфавит на основе текущего, горппируя его сиволы в более
45 32 /// крупные непересекающиеся классы символов.
46 33 /// </summary>
47 34 /// <param name="newAlphabet">Новый, пустой алфавит, в котором быдут определены классы.</param>
48 35 /// <param name="classes">Множество классов символов текущего алфавита.</param>
49 /// <returns>Карта для перехода символов текущего
50 /// алфавита к символам нового.</returns>
51 int[] Reclassify(IAlphabet<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
36 /// <returns>Карта для перехода классов текущего
37 /// алфавита к классам нового.</returns>
38 /// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
39 int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<ICollection<int>> classes);
52 40
53 41 /// <summary>
54 42 /// Преобразует входной символ в индекс символа из алфавита.
Show file before | Show file after | Hide comments
@@ -6,34 +6,56 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&lt;MyCommands,MyStates,string&gt; 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 }
Show file before | Show file after | Hide comments
@@ -9,6 +9,11 namespace Implab
9 9 {
10 10 public static class Safe
11 11 {
12 public static void ArgumentAssert(bool condition, string paramName) {
13 if (!condition)
14 throw new ArgumentException("The parameter is invalid", paramName);
15 }
16
12 17 public static void ArgumentMatch(string value, string paramName, Regex rx) {
13 18 if (rx == null)
14 19 throw new ArgumentNullException("rx");
General Comments 0
You need to be logged in to leave comments. Login now