##// END OF EJS Templates
implab » ImplabNet
RSS
rewritten the text scanner
rewritten the text scanner
cin - - Load All Authors

File last commit:

r176:0c3c69fe225b ref20160224
r176:0c3c69fe225b ref20160224
Show More
DFATable.cs
313 lines | 12.1 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;
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");
m_initialState = s;
}
public void MarkFinalState(int state) {
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);
m_symbolCount = Math.Max(m_symbolCount, item.edge);
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) {
m_transitions.Remove(item);
}
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();
}
public int[,] CreateTransitionTable() {
var table = new int[StateCount,AlphabetSize];
for (int i = 0; i < StateCount; i++)
for (int j = 0; i < AlphabetSize; j++)
table[i, j] = DFAConst.UNREACHABLE_STATE;
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>
protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
return new HashSet<int>[] { m_finalStates };
}
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);
// получаем конечные состояния, сгруппированные по маркерам
optimalStates.UnionWith(
GroupFinalStates()
);
var state = new HashSet<int>(
Enumerable
.Range(0, m_stateCount - 1)
.Where(i => !m_finalStates.Contains(i))
);
optimalStates.Add(state);
queue.Add(state);
var rmap = m_transitions
.GroupBy(t => t.s2)
.ToLookup(
g => g.Key, // s2
g => g.ToLookup(t => t.edge, t => t.s1)
);
while (queue.Count > 0) {
var stateA = queue.First();
queue.Remove(stateA);
for (int c = 0; c < m_symbolCount; c++) {
var stateX = new HashSet<int>();
foreach(var a in stateA)
stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
foreach (var stateY in optimalStates.ToArray()) {
if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
var stateR1 = new HashSet<int>(stateY);
var stateR2 = new HashSet<int>(stateY);
stateR1.IntersectWith(stateX);
stateR2.ExceptWith(stateX);
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);
}
}
}
}
}
// карта получения оптимального состояния по соотвествующему ему простому состоянию
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
var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
var s2 = res.Length > 0 ? res[0] : -1;
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) {
if (nextCls == DFAConst.UNCLASSIFIED_INPUT)
nextCls++;
// сохраняем DFAConst.UNCLASSIFIED_INPUT
var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
foreach (var a in item)
alphabetMap[a] = cls;
nextCls++;
}
// построение автомата
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);
}
protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
foreach(var t in m_transitions)
Console.WriteLine(
"[{0}] -{{{1}}}-> [{2}]{3}",
String.Join(",", stateAlphabet.GetSymbols(t.s1)),
String.Join("", inputAlphabet.GetSymbols(t.edge)),
String.Join(",", stateAlphabet.GetSymbols(t.s2)),
m_finalStates.Contains(t.s2) ? "$" : ""
);
}
}
}