|
|
using Implab;
|
|
|
using System;
|
|
|
using System.Collections.Generic;
|
|
|
using System.Diagnostics;
|
|
|
using System.Linq;
|
|
|
|
|
|
namespace Implab.Parsing {
|
|
|
public class DFADefinition<TInput, TState, TTag> : IDFADefinition<TInput, TState, TTag> {
|
|
|
readonly List<DFAStateDescriptior<TTag>> m_states;
|
|
|
|
|
|
public const int INITIAL_STATE = 1;
|
|
|
public const int UNREACHEBLE_STATE = 0;
|
|
|
|
|
|
DFAStateDescriptior<TTag>[] m_statesArray;
|
|
|
readonly int m_alpabetSize;
|
|
|
|
|
|
public DFADefinition(int alphabetSize) {
|
|
|
m_states = new List<DFAStateDescriptior<TTag>>();
|
|
|
m_alpabetSize = alphabetSize;
|
|
|
|
|
|
m_states.Add(new DFAStateDescriptior<TTag>());
|
|
|
}
|
|
|
|
|
|
public bool InitialStateIsFinal {
|
|
|
get {
|
|
|
return m_states[INITIAL_STATE].final;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public int AddState() {
|
|
|
var index = m_states.Count;
|
|
|
m_states.Add(new DFAStateDescriptior<TTag> {
|
|
|
final = false,
|
|
|
transitions = new int[AlphabetSize]
|
|
|
});
|
|
|
m_statesArray = null;
|
|
|
|
|
|
return index;
|
|
|
}
|
|
|
|
|
|
public int AddState(TTag[] tag) {
|
|
|
var index = m_states.Count;
|
|
|
bool final = tag != null && tag.Length != 0;
|
|
|
m_states.Add(new DFAStateDescriptior<TTag> {
|
|
|
final = final,
|
|
|
transitions = new int[AlphabetSize],
|
|
|
tag = final ? tag : null
|
|
|
});
|
|
|
m_statesArray = null;
|
|
|
return index;
|
|
|
}
|
|
|
|
|
|
public void DefineTransition(TState s1, TState s2, TInput symbol) {
|
|
|
int is1 = StateAlphabet.Translate(s1);
|
|
|
int is2 = StateAlphabet.Translate(s2);
|
|
|
int isym = InputAlphabet.Translate(symbol);
|
|
|
|
|
|
Safe.ArgumentAssert(is1 != 0, "s1");
|
|
|
Safe.ArgumentAssert(is2 != 0, "s2");
|
|
|
Safe.ArgumentAssert(isym != 0, "symbol");
|
|
|
|
|
|
m_states[is1].transitions[isym] = is2;
|
|
|
}
|
|
|
|
|
|
#region IDFADefinition implementation
|
|
|
|
|
|
public DFAStateDescriptior<TTag>[] GetTransitionTable() {
|
|
|
if (m_statesArray == null)
|
|
|
m_statesArray = m_states.ToArray();
|
|
|
return m_statesArray;
|
|
|
}
|
|
|
|
|
|
public IAlphabet<TInput> InputAlphabet {
|
|
|
get {
|
|
|
throw new NotImplementedException();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public IAlphabet<TState> StateAlphabet {
|
|
|
get {
|
|
|
throw new NotImplementedException();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
|
|
|
protected IDFADefinition<> Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
|
|
|
Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
|
|
|
Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
|
|
|
|
|
|
var setComparer = new CustomEqualityComparer<HashSet<int>>(
|
|
|
(x, y) => x.SetEquals(y),
|
|
|
(s) => s.Sum(x => x.GetHashCode())
|
|
|
);
|
|
|
|
|
|
var arrayComparer = new CustomEqualityComparer<int[]>(
|
|
|
(x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
|
|
|
(a) => a.Sum(x => x.GetHashCode())
|
|
|
);
|
|
|
|
|
|
var optimalStates = new HashSet<HashSet<int>>(setComparer);
|
|
|
var queue = new HashSet<HashSet<int>>(setComparer);
|
|
|
|
|
|
foreach (var g in Enumerable
|
|
|
.Range(INITIAL_STATE, m_states.Count-1)
|
|
|
.Select(i => new {
|
|
|
index = i,
|
|
|
descriptor = m_states[i]
|
|
|
})
|
|
|
.Where(x => x.descriptor.final)
|
|
|
.GroupBy(x => x.descriptor.tag, arrayComparer)
|
|
|
) {
|
|
|
optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
|
|
|
}
|
|
|
|
|
|
var state = new HashSet<int>(
|
|
|
Enumerable
|
|
|
.Range(INITIAL_STATE, m_states.Count - 1)
|
|
|
.Where(i => !m_states[i].final)
|
|
|
);
|
|
|
optimalStates.Add(state);
|
|
|
queue.Add(state);
|
|
|
|
|
|
while (queue.Count > 0) {
|
|
|
var stateA = queue.First();
|
|
|
queue.Remove(stateA);
|
|
|
|
|
|
for (int c = 0; c < AlphabetSize; c++) {
|
|
|
var stateX = new HashSet<int>();
|
|
|
|
|
|
for(int s = 1; s < m_states.Count; s++) {
|
|
|
if (stateA.Contains(m_states[s].transitions[c]))
|
|
|
stateX.Add(s);
|
|
|
}
|
|
|
|
|
|
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 initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
|
|
|
|
|
|
// карта получения оптимального состояния по соотвествующему ему простому состоянию
|
|
|
int[] reveseOptimalMap = new int[m_states.Count];
|
|
|
// карта с индексами оптимальных состояний
|
|
|
HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
|
|
|
{
|
|
|
optimalMap[0] = new HashSet<int>(); // unreachable state
|
|
|
optimalMap[1] = initialState; // initial state
|
|
|
foreach (var ss in initialState)
|
|
|
reveseOptimalMap[ss] = 1;
|
|
|
|
|
|
int i = 2;
|
|
|
foreach (var s in optimalStates) {
|
|
|
if (s.SetEquals(initialState))
|
|
|
continue;
|
|
|
optimalMap[i] = s;
|
|
|
foreach (var ss in s)
|
|
|
reveseOptimalMap[ss] = i;
|
|
|
i++;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// получаем минимальный алфавит
|
|
|
|
|
|
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 = 1 ; s < optimalMap.Length; 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 s2 = reveseOptimalMap[
|
|
|
optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // первое допустимое элементарное состояние, если есть
|
|
|
];
|
|
|
|
|
|
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);
|
|
|
|
|
|
var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
|
|
|
|
|
|
// построение автомата
|
|
|
|
|
|
var minimalDFA = dfaFactory(minimalAlphabet);
|
|
|
|
|
|
var states = new int[ optimalMap.Length ];
|
|
|
states[0] = UNREACHEBLE_STATE;
|
|
|
|
|
|
for(var s = INITIAL_STATE; s < states.Length; s++) {
|
|
|
var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
|
|
|
if (tags.Length > 0)
|
|
|
states[s] = minimalDFA.AddState(tags);
|
|
|
else
|
|
|
states[s] = minimalDFA.AddState();
|
|
|
}
|
|
|
|
|
|
Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
|
|
|
|
|
|
for (int s1 = 1; s1 < m_states.Count; s1++) {
|
|
|
for (int c = 0; c < AlphabetSize; c++) {
|
|
|
var s2 = m_states[s1].transitions[c];
|
|
|
if (s2 != UNREACHEBLE_STATE) {
|
|
|
minimalDFA.DefineTransition(
|
|
|
reveseOptimalMap[s1],
|
|
|
reveseOptimalMap[s2],
|
|
|
alphabetMap[c]
|
|
|
);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return minimalDFA;
|
|
|
}
|
|
|
|
|
|
public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
|
|
|
|
|
|
var reverseMap = alphabet.CreateReverseMap();
|
|
|
|
|
|
for (int i = 1; i < reverseMap.Length; i++) {
|
|
|
Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i < m_states.Count; i++) {
|
|
|
var s = m_states[i];
|
|
|
for (int c = 0; c < AlphabetSize; c++)
|
|
|
if (s.transitions[c] != UNREACHEBLE_STATE)
|
|
|
Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public int AlphabetSize {
|
|
|
get {
|
|
|
return m_alpabetSize;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
