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