##// END OF EJS Templates
fixed: the error handler should not handle handlers errors
fixed: the error handler should not handle handlers errors

File last commit:

r178:d5c5db0335ee ref20160224
r197:86187b01c4e0 default
Show More
RegularExpressionVisitor.cs
212 lines | 6.8 KiB | text/x-csharp | CSharpLexer
cin
Working on text scanner
r172 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>
cin
working on JSON parser
r178 public class RegularExpressionVisitor : IVisitor {
cin
Working on text scanner
r172 int m_idx;
cin
refactoring
r177 Token m_root;
cin
Working on text scanner
r172 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>();
cin
refactoring
r177 readonly HashSet<int> m_ends = new HashSet<int>();
cin
Working on text scanner
r172
cin
working on JSON parser
r178 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;
cin
Working on text scanner
r172 }
cin
working on JSON parser
r178 HashSet<int> Followpos(int pos) {
cin
Working on text scanner
r172 HashSet<int> set;
return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
}
bool Nullable(object n) {
cin
refactoring
r177 if (n is EmptyToken || n is StarToken)
cin
Working on text scanner
r172 return true;
cin
refactoring
r177 var altToken = n as AltToken;
cin
Working on text scanner
r172 if (altToken != null)
return Nullable(altToken.Left) || Nullable(altToken.Right);
cin
refactoring
r177 var catToken = n as CatToken;
cin
Working on text scanner
r172 if (catToken != null)
return Nullable(catToken.Left) && Nullable(catToken.Right);
return false;
}
cin
working on JSON parser
r178 protected int Index {
get { return m_idx; }
}
cin
Working on text scanner
r172
cin
refactoring
r177 public void Visit(AltToken token) {
cin
Working on text scanner
r172 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;
}
cin
refactoring
r177 public void Visit(StarToken token) {
cin
Working on text scanner
r172 if (m_root == null)
m_root = token;
token.Token.Accept(this);
foreach (var i in m_lastpos)
Followpos(i).UnionWith(m_firstpos);
}
cin
refactoring
r177 public void Visit(CatToken token) {
cin
Working on text scanner
r172 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);
}
cin
refactoring
r177 public void Visit(EmptyToken token) {
cin
Working on text scanner
r172 if (m_root == null)
m_root = token;
}
cin
refactoring
r177 public void Visit(SymbolToken token) {
cin
Working on text scanner
r172 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 });
}
cin
working on JSON parser
r178 public virtual void Visit(EndToken token) {
cin
Working on text scanner
r172 if (m_root == null)
m_root = token;
m_idx++;
cin
working on JSON parser
r178 m_indexes[m_idx] = AutomatonConst.UNCLASSIFIED_INPUT;
cin
refactoring
r177 m_firstpos = new HashSet<int>(new[] { m_idx });
m_lastpos = new HashSet<int>(new[] { m_idx });
Followpos(m_idx);
m_ends.Add(m_idx);
cin
Working on text scanner
r172 }
cin
working on JSON parser
r178 public void BuildDFA() {
AddState(m_firstpos);
SetInitialState(m_firstpos);
cin
Working on text scanner
r172
cin
working on JSON parser
r178 if(IsFinal(m_firstpos))
MarkFinalState(m_firstpos);
cin
Working on text scanner
r172
var inputMax = m_indexes.Values.Max();
var queue = new Queue<HashSet<int>>();
queue.Enqueue(m_firstpos);
while (queue.Count > 0) {
cin
working on JSON parser
r178 var s1 = queue.Dequeue();
cin
Working on text scanner
r172
for (int a = 0; a <= inputMax; a++) {
cin
working on JSON parser
r178 var s2 = new HashSet<int>();
foreach (var p in s1) {
cin
Working on text scanner
r172 if (m_indexes[p] == a) {
cin
working on JSON parser
r178 s2.UnionWith(Followpos(p));
cin
Working on text scanner
r172 }
}
cin
working on JSON parser
r178 if (s2.Count > 0) {
if (!HasState(s2)) {
AddState(s2);
if (IsFinal(s2))
MarkFinalState(s2);
queue.Enqueue(s2);
}
cin
Working on text scanner
r172
cin
working on JSON parser
r178 DefineTransition(s1, s2, a);
cin
Working on text scanner
r172 }
cin
working on JSON parser
r178
cin
Working on text scanner
r172 }
}
}
cin
working on JSON parser
r178 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));
}
cin
refactoring
r177 bool IsFinal(IEnumerable<int> state) {
Debug.Assert(state != null);
return state.Any(m_ends.Contains);
}
cin
Working on text scanner
r172 }
}