##// END OF EJS Templates
implab » ImplabNet
RSS
fixed promise chaining behavior, the error handler doesn't handle result or cancellation handlers exceptions these exceptions are propagated to the next handlers.
fixed promise chaining behavior, the error handler doesn't handle result or cancellation handlers exceptions these exceptions are propagated to the next handlers.
cin - - Load All Authors

File last commit:

r183:4f82e0f161c3 ref20160224
r196:40d7fed4a09e default
Show More
DFATable.cs
348 lines | 13.6 KiB | text/x-csharp | CSharpLexer
/ Implab / Automaton / DFATable.cs
History | Source | Raw |Copy content |Copy permalink
cin
rewritten the text scanner
 r176 using Implab;
using System;
using System.Collections.Generic;
using System.Linq;
cin
minor fixes and debug
 r181 using System.Diagnostics;
cin
pretty print DFA, the minimization is still buggy
 r182 using System.IO;
using System.CodeDom.Compiler;
using System.CodeDom;
cin
rewritten the text scanner
 r176
namespace Implab.Automaton {
public class DFATable : IDFATableBuilder {
int m_stateCount;
int m_symbolCount;
int m_initialState;
readonly HashSet<int> m_finalStates = new HashSet<int>();
readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
#region IDFADefinition implementation
public bool IsFinalState(int s) {
Safe.ArgumentInRange(s, 0, m_stateCount, "s");
return m_finalStates.Contains(s);
}
public IEnumerable<int> FinalStates {
get {
return m_finalStates;
}
}
public int StateCount {
get { return m_stateCount; }
}
public int AlphabetSize {
get { return m_symbolCount; }
}
public int InitialState {
get { return m_initialState; }
}
#endregion
public void SetInitialState(int s) {
Safe.ArgumentAssert(s >= 0, "s");
cin
minor fixes and debug
 r181 m_stateCount = Math.Max(m_stateCount, s + 1);
cin
rewritten the text scanner
 r176 m_initialState = s;
}
public void MarkFinalState(int state) {
cin
minor fixes and debug
 r181 m_stateCount = Math.Max(m_stateCount, state + 1);
cin
rewritten the text scanner
 r176 m_finalStates.Add(state);
}
public void Add(AutomatonTransition item) {
Safe.ArgumentAssert(item.s1 >= 0, "item");
Safe.ArgumentAssert(item.s2 >= 0, "item");
Safe.ArgumentAssert(item.edge >= 0, "item");
m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
cin
minor fixes and debug
 r181 m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
cin
rewritten the text scanner
 r176
m_transitions.Add(item);
}
public void Clear() {
m_stateCount = 0;
m_symbolCount = 0;
m_finalStates.Clear();
m_transitions.Clear();
}
public bool Contains(AutomatonTransition item) {
return m_transitions.Contains(item);
}
public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
m_transitions.CopyTo(array, arrayIndex);
}
public bool Remove(AutomatonTransition item) {
cin
refactoring complete, JSONParser rewritten
 r180 return m_transitions.Remove(item);
cin
rewritten the text scanner
 r176 }
public int Count {
get {
return m_transitions.Count;
}
}
public bool IsReadOnly {
get {
return false;
}
}
public IEnumerator<AutomatonTransition> GetEnumerator() {
return m_transitions.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
return GetEnumerator();
}
cin
pretty print DFA, the minimization is still buggy
 r182 public void AddSymbol(int symbol) {
Safe.ArgumentAssert(symbol >= 0, "symbol");
m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
}
cin
rewritten the text scanner
 r176 public int[,] CreateTransitionTable() {
var table = new int[StateCount,AlphabetSize];
for (int i = 0; i < StateCount; i++)
cin
minor fixes and debug
 r181 for (int j = 0; j < AlphabetSize; j++)
cin
working on JSON parser
 r178 table[i, j] = AutomatonConst.UNREACHABLE_STATE;
cin
rewritten the text scanner
 r176
foreach (var t in this)
table[t.s1,t.edge] = t.s2;
return table;
}
public bool[] CreateFinalStateTable() {
var table = new bool[StateCount];
foreach (var s in FinalStates)
table[s] = true;
return table;
}
/// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
/// <remarks>
/// В процессе построения минимального автомата требуется разделить множество состояний,
/// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
/// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
/// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
/// </remarks>
/// <returns>The final states.</returns>
cin
fixed DFA optimization, JSON is fully functional
 r183 protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
return new [] { new HashSet<int>(states) };
cin
rewritten the text scanner
 r176 }
protected void Optimize(
IDFATableBuilder optimalDFA,
IDictionary<int,int> alphabetMap,
IDictionary<int,int> stateMap
) {
Safe.ArgumentNotNull(optimalDFA, "dfa");
Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
Safe.ArgumentNotNull(stateMap, "stateMap");
var setComparer = new CustomEqualityComparer<HashSet<int>>(
(x, y) => x.SetEquals(y),
s => s.Sum(x => x.GetHashCode())
);
var optimalStates = new HashSet<HashSet<int>>(setComparer);
var queue = new HashSet<HashSet<int>>(setComparer);
cin
fixed DFA optimization, JSON is fully functional
 r183 optimalStates.Add(new HashSet<int>(FinalStates));
cin
rewritten the text scanner
 r176
var state = new HashSet<int>(
Enumerable
cin
pretty print DFA, the minimization is still buggy
 r182 .Range(0, m_stateCount)
cin
rewritten the text scanner
 r176 .Where(i => !m_finalStates.Contains(i))
);
optimalStates.Add(state);
queue.Add(state);
var rmap = m_transitions
.GroupBy(t => t.s2)
cin
refactoring complete, JSONParser rewritten
 r180 .ToDictionary(
cin
rewritten the text scanner
 r176 g => g.Key, // s2
cin
minor fixes and debug
 r181 g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
cin
rewritten the text scanner
 r176 );
while (queue.Count > 0) {
var stateA = queue.First();
queue.Remove(stateA);
for (int c = 0; c < m_symbolCount; c++) {
var stateX = new HashSet<int>();
cin
fixed DFA optimization, JSON is fully functional
 r183 foreach(var a in stateA.Where(rmap.ContainsKey))
stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
cin
pretty print DFA, the minimization is still buggy
 r182
var tmp = optimalStates.ToArray();
foreach (var stateY in tmp) {
cin
fixed DFA optimization, JSON is fully functional
 r183 var stateR1 = new HashSet<int>(stateY);
var stateR2 = new HashSet<int>(stateY);
cin
rewritten the text scanner
 r176
cin
fixed DFA optimization, JSON is fully functional
 r183 stateR1.IntersectWith(stateX);
stateR2.ExceptWith(stateX);
if (stateR1.Count > 0 && stateR2.Count > 0) {
cin
rewritten the text scanner
 r176
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);
}
}
}
}
}
cin
fixed DFA optimization, JSON is fully functional
 r183 // дополнительно разбиваем конечные состояния
foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
optimalStates.Remove(final);
foreach (var split in SplitFinalStates(final))
optimalStates.Add(split);
}
cin
rewritten the text scanner
 r176 // карта получения оптимального состояния по соотвествующему ему простому состоянию
var nextState = 0;
foreach (var item in optimalStates) {
var id = nextState++;
foreach (var s in item)
stateMap[s] = id;
}
// получаем минимальный алфавит
// входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
// для этого используем алгоритм кластеризации, сначала
// считаем, что все символы не различимы
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 = 0 ; s < optimalStates.Count; 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
cin
pretty print DFA, the minimization is still buggy
 r182 var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
cin
rewritten the text scanner
 r176
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);
// построение отображения алфавитов входных символов.
// поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
// специальное значение, тогда сохраним минимальный класс,
// содержащий этот символ на томже месте.
var nextCls = 0;
foreach (var item in minClasses) {
cin
working on JSON parser
 r178 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
cin
rewritten the text scanner
 r176 nextCls++;
// сохраняем DFAConst.UNCLASSIFIED_INPUT
cin
minor fixes and debug
 r181 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
cin
pretty print DFA, the minimization is still buggy
 r182 optimalDFA.AddSymbol(cls);
cin
rewritten the text scanner
 r176
foreach (var a in item)
alphabetMap[a] = cls;
}
// построение автомата
optimalDFA.SetInitialState(stateMap[m_initialState]);
foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
optimalDFA.MarkFinalState(sf);
foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
optimalDFA.Add(t);
}
cin
pretty print DFA, the minimization is still buggy
 r182 protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
cin
rewritten the text scanner
 r176 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
cin
pretty print DFA, the minimization is still buggy
 r182 var data = new List<string>();
data.Add("digraph dfa {");
foreach (var final in m_finalStates)
data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
foreach (var t in m_transitions)
data.Add(String.Format(
"{0} -> {2} [label={1}];",
String.Join("", stateAlphabet.GetSymbols(t.s1)),
ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
String.Join("", stateAlphabet.GetSymbols(t.s2))
));
data.Add("}");
return String.Join("\n", data);
cin
rewritten the text scanner
 r176 }
cin
pretty print DFA, the minimization is still buggy
 r182 static string ToLiteral(string input)
{
using (var writer = new StringWriter())
{
using (var provider = CodeDomProvider.CreateProvider("CSharp"))
{
provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
return writer.ToString();
}
}
}
cin
rewritten the text scanner
 r176 }
}