1
2
3
4
5
6 using System;
7 using System.Collections;
8
9 namespace System.RegularExpressions
10 {
11 public List<NfaState*> EpsilonClosure(const List<NfaState*>& states)
12 {
13 List<NfaState*> stack;
14 for (NfaState* state : states)
15 {
16 stack.Add(state);
17 }
18 List<NfaState*> epsilonClosure = states;
19 while (!stack.IsEmpty())
20 {
21 NfaState* s = stack.Back();
22 stack.RemoveLast();
23 List<NfaState*> u = s->Next(eps);
24 for (NfaState* v : u)
25 {
26 if (Find(epsilonClosure.CBegin(), epsilonClosure.CEnd(), v) == epsilonClosure.CEnd())
27 {
28 epsilonClosure.Add(v);
29 stack.Add(v);
30 }
31 }
32 }
33 return epsilonClosure;
34 }
35 public List<NfaState*> EpsilonClosure(NfaState* state)
36 {
37 List<NfaState*> states(1, state);
38 return EpsilonClosure(states);
39 }
40 public List<NfaState*> Move(const List<NfaState*>& states, uchar c)
41 {
42 List<NfaState*> next;
43 for (NfaState* state : states)
44 {
45 List<NfaState*> n = state->Next(c);
46 for (NfaState* s : n)
47 {
48 if (Find(next.CBegin(), next.CEnd(), s) == next.CEnd())
49 {
50 next.Add(s);
51 }
52 }
53 }
54 return next;
55 }
56 public bool Match(Nfa& nfa, const ustring& s)
57 {
58 List<NfaState*> states = EpsilonClosure(nfa.Start());
59 for (uchar c : s)
60 {
61 states = EpsilonClosure(Move(states, c));
62 }
63 for (NfaState* state : states)
64 {
65 if (state->Accept()) return true;
66 }
67 return false;
68 }
69