RegularExpressionVisitor.cs
212 lines
| 6.8 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r289 | using Implab; | ||
| using System; | ||||
| using System.Collections.Generic; | ||||
| using System.Diagnostics; | ||||
| using System.Linq; | ||||
| namespace Implab.Automaton.RegularExpressions { | ||||
| /// <summary> | ||||
| /// Используется для построения ДКА по регулярному выражению, сначала обходит | ||||
| /// регулярное выражение и вычисляет followpos, затем используется метод | ||||
| /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата. | ||||
| /// </summary> | ||||
| public class RegularExpressionVisitor : IVisitor { | ||||
| int m_idx; | ||||
| Token m_root; | ||||
| HashSet<int> m_firstpos; | ||||
| HashSet<int> m_lastpos; | ||||
| readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>(); | ||||
| readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>(); | ||||
| readonly HashSet<int> m_ends = new HashSet<int>(); | ||||
| readonly IDFATableBuilder m_builder; | ||||
| readonly IAlphabetBuilder<HashSet<int>> m_states = new MapAlphabet<HashSet<int>>( | ||||
| false, | ||||
| new CustomEqualityComparer<HashSet<int>>( | ||||
| (x, y) => x.SetEquals(y), | ||||
| x => x.Sum(n => n.GetHashCode()) | ||||
| ) | ||||
| ); | ||||
| public RegularExpressionVisitor(IDFATableBuilder builder) { | ||||
| Safe.ArgumentNotNull(builder, "builder"); | ||||
| m_builder = builder; | ||||
| } | ||||
| HashSet<int> Followpos(int pos) { | ||||
| HashSet<int> set; | ||||
| return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>(); | ||||
| } | ||||
| bool Nullable(object n) { | ||||
| if (n is EmptyToken || n is StarToken) | ||||
| return true; | ||||
| var altToken = n as AltToken; | ||||
| if (altToken != null) | ||||
| return Nullable(altToken.Left) || Nullable(altToken.Right); | ||||
| var catToken = n as CatToken; | ||||
| if (catToken != null) | ||||
| return Nullable(catToken.Left) && Nullable(catToken.Right); | ||||
| return false; | ||||
| } | ||||
| protected int Index { | ||||
| get { return m_idx; } | ||||
| } | ||||
| public void Visit(AltToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| var firtspos = new HashSet<int>(); | ||||
| var lastpos = new HashSet<int>(); | ||||
| token.Left.Accept(this); | ||||
| firtspos.UnionWith(m_firstpos); | ||||
| lastpos.UnionWith(m_lastpos); | ||||
| token.Right.Accept(this); | ||||
| firtspos.UnionWith(m_firstpos); | ||||
| lastpos.UnionWith(m_lastpos); | ||||
| m_firstpos = firtspos; | ||||
| m_lastpos = lastpos; | ||||
| } | ||||
| public void Visit(StarToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| token.Token.Accept(this); | ||||
| foreach (var i in m_lastpos) | ||||
| Followpos(i).UnionWith(m_firstpos); | ||||
| } | ||||
| public void Visit(CatToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| var firtspos = new HashSet<int>(); | ||||
| var lastpos = new HashSet<int>(); | ||||
| token.Left.Accept(this); | ||||
| firtspos.UnionWith(m_firstpos); | ||||
| var leftLastpos = m_lastpos; | ||||
| token.Right.Accept(this); | ||||
| lastpos.UnionWith(m_lastpos); | ||||
| var rightFirstpos = m_firstpos; | ||||
| if (Nullable(token.Left)) | ||||
| firtspos.UnionWith(rightFirstpos); | ||||
| if (Nullable(token.Right)) | ||||
| lastpos.UnionWith(leftLastpos); | ||||
| m_firstpos = firtspos; | ||||
| m_lastpos = lastpos; | ||||
| foreach (var i in leftLastpos) | ||||
| Followpos(i).UnionWith(rightFirstpos); | ||||
| } | ||||
| public void Visit(EmptyToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| } | ||||
| public void Visit(SymbolToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| m_idx++; | ||||
| m_indexes[m_idx] = token.Value; | ||||
| m_firstpos = new HashSet<int>(new[] { m_idx }); | ||||
| m_lastpos = new HashSet<int>(new[] { m_idx }); | ||||
| } | ||||
| public virtual void Visit(EndToken token) { | ||||
| if (m_root == null) | ||||
| m_root = token; | ||||
| m_idx++; | ||||
| m_indexes[m_idx] = AutomatonConst.UnclassifiedInput; | ||||
| m_firstpos = new HashSet<int>(new[] { m_idx }); | ||||
| m_lastpos = new HashSet<int>(new[] { m_idx }); | ||||
| Followpos(m_idx); | ||||
| m_ends.Add(m_idx); | ||||
| } | ||||
| public void BuildDFA() { | ||||
| AddState(m_firstpos); | ||||
| SetInitialState(m_firstpos); | ||||
| if(IsFinal(m_firstpos)) | ||||
| MarkFinalState(m_firstpos); | ||||
| var inputMax = m_indexes.Values.Max(); | ||||
| var queue = new Queue<HashSet<int>>(); | ||||
| queue.Enqueue(m_firstpos); | ||||
| while (queue.Count > 0) { | ||||
| var s1 = queue.Dequeue(); | ||||
| for (int a = 0; a <= inputMax; a++) { | ||||
| var s2 = new HashSet<int>(); | ||||
| foreach (var p in s1) { | ||||
| if (m_indexes[p] == a) { | ||||
| s2.UnionWith(Followpos(p)); | ||||
| } | ||||
| } | ||||
| if (s2.Count > 0) { | ||||
| if (!HasState(s2)) { | ||||
| AddState(s2); | ||||
| if (IsFinal(s2)) | ||||
| MarkFinalState(s2); | ||||
| queue.Enqueue(s2); | ||||
| } | ||||
| DefineTransition(s1, s2, a); | ||||
| } | ||||
| } | ||||
| } | ||||
| } | ||||
| protected bool HasState(HashSet<int> state) { | ||||
| return m_states.Contains(state); | ||||
| } | ||||
| protected void AddState(HashSet<int> state) { | ||||
| Debug.Assert(!HasState(state)); | ||||
| m_states.DefineSymbol(state); | ||||
| } | ||||
| protected int Translate(HashSet<int> state) { | ||||
| Debug.Assert(HasState(state)); | ||||
| return m_states.Translate(state); | ||||
| } | ||||
| protected virtual void SetInitialState(HashSet<int> state) { | ||||
| m_builder.SetInitialState(Translate(state)); | ||||
| } | ||||
| protected virtual void MarkFinalState(HashSet<int> state) { | ||||
| m_builder.MarkFinalState(Translate(state)); | ||||
| } | ||||
| protected virtual void DefineTransition(HashSet<int> s1, HashSet<int> s2, int ch) { | ||||
| m_builder.Add(new AutomatonTransition(Translate(s1), Translate(s2), ch)); | ||||
| } | ||||
| bool IsFinal(IEnumerable<int> state) { | ||||
| Debug.Assert(state != null); | ||||
| return state.Any(m_ends.Contains); | ||||
| } | ||||
| } | ||||
| } | ||||