DFATable.cs
348 lines
| 13.6 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r176 | using Implab; | ||
| using System; | ||||
| using System.Collections.Generic; | ||||
| using System.Linq; | ||||
|
cin
|
r181 | using System.Diagnostics; | ||
|
cin
|
r182 | using System.IO; | ||
| using System.CodeDom.Compiler; | ||||
| using System.CodeDom; | ||||
|
cin
|
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
|
r181 | m_stateCount = Math.Max(m_stateCount, s + 1); | ||
|
cin
|
r176 | m_initialState = s; | ||
| } | ||||
| public void MarkFinalState(int state) { | ||||
|
cin
|
r181 | m_stateCount = Math.Max(m_stateCount, state + 1); | ||
|
cin
|
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
|
r181 | m_symbolCount = Math.Max(m_symbolCount, item.edge + 1); | ||
|
cin
|
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
|
r180 | return m_transitions.Remove(item); | ||
|
cin
|
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
|
r182 | public void AddSymbol(int symbol) { | ||
| Safe.ArgumentAssert(symbol >= 0, "symbol"); | ||||
| m_symbolCount = Math.Max(symbol + 1, m_symbolCount); | ||||
| } | ||||
|
cin
|
r176 | public int[,] CreateTransitionTable() { | ||
| var table = new int[StateCount,AlphabetSize]; | ||||
| for (int i = 0; i < StateCount; i++) | ||||
|
cin
|
r181 | for (int j = 0; j < AlphabetSize; j++) | ||
|
cin
|
r178 | table[i, j] = AutomatonConst.UNREACHABLE_STATE; | ||
|
cin
|
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
|
r183 | protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) { | ||
| return new [] { new HashSet<int>(states) }; | ||||
|
cin
|
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
|
r183 | optimalStates.Add(new HashSet<int>(FinalStates)); | ||
|
cin
|
r176 | |||
| var state = new HashSet<int>( | ||||
| Enumerable | ||||
|
cin
|
r182 | .Range(0, m_stateCount) | ||
|
cin
|
r176 | .Where(i => !m_finalStates.Contains(i)) | ||
| ); | ||||
| optimalStates.Add(state); | ||||
| queue.Add(state); | ||||
| var rmap = m_transitions | ||||
| .GroupBy(t => t.s2) | ||||
|
cin
|
r180 | .ToDictionary( | ||
|
cin
|
r176 | g => g.Key, // s2 | ||
|
cin
|
r181 | g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key) | ||
|
cin
|
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
|
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
|
r182 | |||
| var tmp = optimalStates.ToArray(); | ||||
| foreach (var stateY in tmp) { | ||||
|
cin
|
r183 | var stateR1 = new HashSet<int>(stateY); | ||
| var stateR2 = new HashSet<int>(stateY); | ||||
|
cin
|
r176 | |||
|
cin
|
r183 | stateR1.IntersectWith(stateX); | ||
| stateR2.ExceptWith(stateX); | ||||
| if (stateR1.Count > 0 && stateR2.Count > 0) { | ||||
|
cin
|
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
|
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
|
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
|
r182 | var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First(); | ||
|
cin
|
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
|
r178 | if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT) | ||
|
cin
|
r176 | nextCls++; | ||
| // сохраняем DFAConst.UNCLASSIFIED_INPUT | ||||
|
cin
|
r181 | var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++; | ||
|
cin
|
r182 | optimalDFA.AddSymbol(cls); | ||
|
cin
|
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
|
r182 | protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { | ||
|
cin
|
r176 | Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); | ||
| Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); | ||||
|
cin
|
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
|
r176 | } | ||
|
cin
|
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
|
r176 | } | ||
| } | ||||