# HG changeset patch
# User cin
# Date 2016-02-19 15:07:17
# Node ID 2a8466f0cb8aacae858116af47493d1126bfeecc
# Parent 5802131432e41edeb1de28fa005c6f5911a71555
DFA refactoring
diff --git a/Implab/Implab.csproj b/Implab/Implab.csproj
--- a/Implab/Implab.csproj
+++ b/Implab/Implab.csproj
@@ -7,9 +7,6 @@
Library
Implab
Implab
- 8.0.30703
- 2.0
- 0.2
v4.5
@@ -184,6 +181,8 @@
+
+
diff --git a/Implab/Parsing/DFADefinition.cs b/Implab/Parsing/DFADefinition.cs
--- a/Implab/Parsing/DFADefinition.cs
+++ b/Implab/Parsing/DFADefinition.cs
@@ -5,28 +5,20 @@ using System.Diagnostics;
using System.Linq;
namespace Implab.Parsing {
- public class DFADefinition : IDFADefinition {
- readonly List m_states;
+ public class DFADefinition : IDFADefinition {
+ readonly List> m_states;
public const int INITIAL_STATE = 1;
public const int UNREACHEBLE_STATE = 0;
- DFAStateDescriptior[] m_statesArray;
+ DFAStateDescriptior[] m_statesArray;
readonly int m_alpabetSize;
public DFADefinition(int alphabetSize) {
- m_states = new List();
+ m_states = new List>();
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());
}
public bool InitialStateIsFinal {
@@ -37,7 +29,7 @@ namespace Implab.Parsing {
public int AddState() {
var index = m_states.Count;
- m_states.Add(new DFAStateDescriptior {
+ m_states.Add(new DFAStateDescriptior {
final = false,
transitions = new int[AlphabetSize]
});
@@ -46,10 +38,10 @@ namespace Implab.Parsing {
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 {
final = final,
transitions = new int[AlphabetSize],
tag = final ? tag : null
@@ -58,15 +50,41 @@ namespace Implab.Parsing {
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(Func, IDFADefinition> dfaFactory,IAlphabet sourceAlphabet, IAlphabet minimalAlphabet) {
+ #region IDFADefinition implementation
+
+ public DFAStateDescriptior[] GetTransitionTable() {
+ if (m_statesArray == null)
+ m_statesArray = m_states.ToArray();
+ return m_statesArray;
+ }
+
+ public IAlphabet InputAlphabet {
+ get {
+ throw new NotImplementedException();
+ }
+ }
+
+ public IAlphabet StateAlphabet {
+ get {
+ throw new NotImplementedException();
+ }
+ }
+
+ #endregion
+
+ protected IDFADefinition<> Optimize(Func, IDFADefinition> dfaFactory,IAlphabet sourceAlphabet, IAlphabet minimalAlphabet) {
Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
diff --git a/Implab/Parsing/DFAStateDescriptor.cs b/Implab/Parsing/DFAStateDescriptor.cs
--- a/Implab/Parsing/DFAStateDescriptor.cs
+++ b/Implab/Parsing/DFAStateDescriptor.cs
@@ -5,9 +5,9 @@ using System.Text;
using System.Threading.Tasks;
namespace Implab.Parsing {
- public struct DFAStateDescriptior {
+ public struct DFAStateDescriptior {
public bool final;
- public int[] tag;
+ public TTag[] tag;
public int[] transitions;
}
}
diff --git a/Implab/Parsing/IAlphabet.cs b/Implab/Parsing/IAlphabet.cs
--- a/Implab/Parsing/IAlphabet.cs
+++ b/Implab/Parsing/IAlphabet.cs
@@ -12,43 +12,31 @@ namespace Implab.Parsing {
///
/// Алфавит является сюрьективным отображением множества символов в множество индексов, это позволяет сократить размер таблицы переходов автомата
/// для входных символов, которые для него не различимы.
- /// Далее символами алфавита будем называть классы исходных символов.
///
/// Тип символов.
public interface IAlphabet {
///
- /// Количество символов в алфавите.
+ /// Количество классов символов в алфавите.
///
int Count { get; }
- ///
- /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
- /// возвращается ранее сопоставленный с символом класс.
- ///
- /// Символ для добавления.
- /// Индекс класса, который попоставлен с символом.
- int DefineSymbol(TSymbol symbol);
+
///
- /// Доабвляем класс символов. Множеству указанных исходных символов
- /// будет сопоставлен символ в алфавите.
- ///
- /// Множестов исходных символов
- /// Идентификатор символа алфавита.
- int DefineClass(IEnumerable symbols);
- ///
- /// Создает карту обратного сопоставления символа алфавита и сопоставленным
+ /// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
/// ему исходным символам.
///
///
List[] CreateReverseMap();
+
///
/// Создает новый алфавит на основе текущего, горппируя его сиволы в более
/// крупные непересекающиеся классы символов.
///
/// Новый, пустой алфавит, в котором быдут определены классы.
/// Множество классов символов текущего алфавита.
- /// Карта для перехода символов текущего
- /// алфавита к символам нового.
- int[] Reclassify(IAlphabet newAlphabet, IEnumerable> classes);
+ /// Карта для перехода классов текущего
+ /// алфавита к классам нового.
+ /// Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.
+ int[] Reclassify(IAlphabetBuilder newAlphabet, IEnumerable> classes);
///
/// Преобразует входной символ в индекс символа из алфавита.
diff --git a/Implab/Parsing/IAlphabetBuilder.cs b/Implab/Parsing/IAlphabetBuilder.cs
new file mode 100644
--- /dev/null
+++ b/Implab/Parsing/IAlphabetBuilder.cs
@@ -0,0 +1,25 @@
+using System;
+using System.Collections.Generic;
+
+namespace Implab.Parsing {
+ public interface IAlphabetBuilder : IAlphabet {
+ ///
+ /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
+ /// возвращается ранее сопоставленный с символом класс.
+ ///
+ /// Символ для добавления.
+ /// Индекс класса, который попоставлен с символом.
+ int DefineSymbol(TSymbol symbol);
+ ///
+ /// Доабвляем класс символов. Множеству указанных исходных символов
+ /// будет сопоставлен символ в алфавите.
+ ///
+ /// Множестов исходных символов
+ /// Идентификатор символа алфавита.
+ int DefineClass(IEnumerable symbols);
+
+
+
+ }
+}
+
diff --git a/Implab/Parsing/IDFADefinition.cs b/Implab/Parsing/IDFADefinition.cs
--- a/Implab/Parsing/IDFADefinition.cs
+++ b/Implab/Parsing/IDFADefinition.cs
@@ -6,34 +6,56 @@ using System.Threading.Tasks;
namespace Implab.Parsing {
///
- /// Интерфейс для определения ДКА, позволяет добавить состояния и определить переходы.
+ /// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
///
- public interface IDFADefinition {
+ ///
+ /// class MyAutomaton {
+ /// int m_current;
+ /// readonly DFAStateDescriptor[] m_automaton;
+ /// readonly IAlphabet m_commands;
+ ///
+ /// public MyAutomaton(IDFADefinition<MyCommands,MyStates,string> definition) {
+ /// m_current = definition.StateAlphabet.Translate(MyStates.Initial);
+ /// m_automaton = definition.GetTransitionTable();
+ /// m_commands = definition.InputAlphabet;
+ /// }
+ ///
+ /// // defined a method which will move the automaton to the next state
+ /// public void Move(MyCommands cmd) {
+ /// // use transition map to determine the next state
+ /// var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
+ ///
+ /// // validate that we aren't in the unreachable state
+ /// if (next == DFAConst.UNREACHABLE_STATE)
+ /// throw new InvalidOperationException("The specified command is invalid");
+ ///
+ /// // if everything is ok
+ /// m_current = next;
+ /// }
+ /// }
+ ///
+ public interface IDFADefinition {
///
- /// Добавляет состояние в автомат.
- ///
- /// Индекс добавленного состояния.
- int AddState();
- ///
- /// Добавляет конечное состояние с указанными метками, если метки не заданы, то
- /// добавленное состояние не будет конечным.
+ /// Алфавит входных символов
///
- /// Метки состояния.
- /// Индекс добавленного состояния.
- int AddState(int[] tags);
+ /// The input alphabet.
+ IAlphabet InputAlphabet {
+ get;
+ }
+
///
- /// Определяет переход между состояниями.
+ /// Алфавит состояний автомата
///
- /// Исходное состояние.
- /// Конечное состояние.
- /// Входной символ.
- void DefineTransition(int s1, int s2, int input);
+ /// The state alphabet.
+ IAlphabet StateAlphabet {
+ get;
+ }
+
///
- /// Размер входного алфавита.
+ /// Таблица переходов состояний автомата
///
- ///
- /// Размер входного алфавита определяет количество возможных выходов из одного состояния.
- ///
- int AlphabetSize { get; }
+ /// The transition table.
+ DFAStateDescriptior[] GetTransitionTable();
+
}
}
diff --git a/Implab/Parsing/IDFADefinitionBuilder.cs b/Implab/Parsing/IDFADefinitionBuilder.cs
new file mode 100644
--- /dev/null
+++ b/Implab/Parsing/IDFADefinitionBuilder.cs
@@ -0,0 +1,9 @@
+using System;
+
+namespace Implab.Parsing {
+ public interface IDFADefinitionBuilder : IDFADefinition {
+
+
+ }
+}
+
diff --git a/Implab/Safe.cs b/Implab/Safe.cs
--- a/Implab/Safe.cs
+++ b/Implab/Safe.cs
@@ -9,6 +9,11 @@ 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");