RegularDFA.cs
91 lines
| 3.1 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r177 | using System.Collections.Generic; | ||
|
cin
|
r172 | using System.Linq; | ||
| namespace Implab.Automaton.RegularExpressions { | ||||
|
cin
|
r179 | public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> { | ||
|
cin
|
r172 | |||
| readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>(); | ||||
| readonly IAlphabet<TInput> m_alphabet; | ||||
|
cin
|
r179 | public RegularDFA(IAlphabet<TInput> alphabet) { | ||
|
cin
|
r172 | Safe.ArgumentNotNull(alphabet, "aplhabet"); | ||
| m_alphabet = alphabet; | ||||
| } | ||||
| public IAlphabet<TInput> InputAlphabet { | ||||
| get { | ||||
| return m_alphabet; | ||||
| } | ||||
| } | ||||
| public void MarkFinalState(int s, TTag[] tags) { | ||||
| MarkFinalState(s); | ||||
| SetStateTag(s, tags); | ||||
| } | ||||
| public void SetStateTag(int s, TTag[] tags) { | ||||
| Safe.ArgumentNotNull(tags, "tags"); | ||||
| m_tags[s] = tags; | ||||
| } | ||||
| public TTag[] GetStateTag(int s) { | ||||
| TTag[] tags; | ||||
| return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0]; | ||||
| } | ||||
|
cin
|
r176 | public TTag[][] CreateTagTable() { | ||
| var table = new TTag[StateCount][]; | ||||
|
cin
|
r172 | |||
|
cin
|
r176 | foreach (var pair in m_tags) | ||
| table[pair.Key] = pair.Value; | ||||
|
cin
|
r172 | |||
| return table; | ||||
| } | ||||
| /// <summary> | ||||
| /// Optimize the specified alphabet. | ||||
| /// </summary> | ||||
| /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param> | ||||
|
cin
|
r179 | public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) { | ||
|
cin
|
r172 | Safe.ArgumentNotNull(alphabet, "alphabet"); | ||
|
cin
|
r179 | var dfa = new RegularDFA<TInput, TTag>(alphabet); | ||
|
cin
|
r172 | |||
| var alphaMap = new Dictionary<int,int>(); | ||||
| var stateMap = new Dictionary<int,int>(); | ||||
| Optimize(dfa, alphaMap, stateMap); | ||||
| // mark tags in the new DFA | ||||
| foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value )) | ||||
| dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray()); | ||||
| // make the alphabet for the new DFA | ||||
|
cin
|
r181 | // skip all unclassified symbols | ||
| foreach (var pair in alphaMap.Where(x => x.Value != 0)) | ||||
|
cin
|
r172 | alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value); | ||
| return dfa; | ||||
| } | ||||
|
cin
|
r183 | protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) { | ||
|
cin
|
r172 | var arrayComparer = new CustomEqualityComparer<TTag[]>( | ||
| (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)), | ||||
| x => x.Sum(it => x.GetHashCode()) | ||||
| ); | ||||
|
cin
|
r183 | return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g)); | ||
|
cin
|
r172 | } | ||
|
cin
|
r182 | public override string ToString() { | ||
| var states = new MapAlphabet<string>(false, null); | ||||
| for (int i = 0; i < StateCount; i++) | ||||
| states.DefineSymbol(string.Format("s{0}", i), i); | ||||
| return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize); | ||||
| } | ||||
|
cin
|
r172 | } | ||
| } | ||||