1 using System;
2 using System.Collections;
3
4
5
6
7
8 namespace System.RegularExpressions
9 {
10 public class NfaEdge
11 {
12 public NfaEdge(Symbol* symbol_, NfaState* next_) :
13 symbol(symbol_), next(next_)
14 {
15 }
16 public Symbol* GetSymbol() const
17 {
18 return symbol;
19 }
20 public NfaState* Next() const
21 {
22 return next;
23 }
24 private Symbol* symbol;
25 private NfaState* next;
26 }
27 public class NfaState
28 {
29 public NfaState() :
30 accept(false), edges()
31 {
32 }
33 public bool Accept() const
34 {
35 return accept;
36 }
37 public void SetAccept(bool accept_)
38 {
39 accept = accept_;
40 }
41 public const List<NfaEdge>& Edges() const
42 {
43 return edges;
44 }
45 public void SetEdges(const List<NfaEdge>& edges_)
46 {
47 edges = edges_;
48 }
49 public void AddEdge(const NfaEdge& edge)
50 {
51 edges.Add(edge);
52 }
53 public List<NfaState*> Next(uchar c) const
54 {
55 List<NfaState*> next;
56 for (const NfaEdge& edge : edges)
57 {
58 Symbol* symbol = edge.GetSymbol();
59 if (symbol->Match(c))
60 {
61 next.Add(edge.Next());
62 }
63 }
64 return next;
65 }
66 private bool accept;
67 private List<NfaEdge> edges;
68 }
69 public class Nfa
70 {
71 public Nfa() :
72 start(null), end(null)
73 {
74 }
75 public Nfa(NfaState* start_, NfaState* end_) :
76 start(start_), end(end_)
77 {
78 }
79 public NfaState* Start() const
80 {
81 return start;
82 }
83 public void SetStart(NfaState* start_)
84 {
85 start = start_;
86 }
87 public NfaState* End() const
88 {
89 return end;
90 }
91 public void SetEnd(NfaState* end_)
92 {
93 end = end_;
94 }
95 private NfaState* start;
96 private NfaState* end;
97 }
98 public Nfa MakeNfa(Context& context, Symbol* symbol)
99 {
100 NfaState* start = context.MakeNfaState();
101 NfaState* end = context.MakeNfaState();
102 end->SetAccept(true);
103 start->AddEdge(NfaEdge(symbol, end));
104 return Nfa(start, end);
105 }
106 public Nfa Cat(const Nfa& left, const Nfa& right)
107 {
108 Nfa cat(left);
109 NfaState* leftEnd = cat.End();
110 leftEnd->SetAccept(false);
111 NfaState* rightStart = right.Start();
112 leftEnd->SetEdges(rightStart->Edges());
113 cat.SetEnd(right.End());
114 return cat;
115 }
116 public Nfa Alt(Context& context, const Nfa& left, const Nfa& right)
117 {
118 NfaState* leftStart = left.Start();
119 NfaState* leftEnd = left.End();
120 NfaState* rightStart = right.Start();
121 NfaState* rightEnd = right.End();
122 NfaState* start = context.MakeNfaState();
123 NfaState* end = context.MakeNfaState();
124 end->SetAccept(true);
125 start->AddEdge(NfaEdge(context.MakeEpsilon(), leftStart));
126 start->AddEdge(NfaEdge(context.MakeEpsilon(), rightStart));
127 Nfa alt;
128 alt.SetStart(start);
129 leftEnd->SetAccept(false);
130 leftEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
131 rightEnd->SetAccept(false);
132 rightEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
133 alt.SetEnd(end);
134 return alt;
135 }
136 public Nfa Kleene(Context& context, const Nfa& nfa)
137 {
138 Nfa kleene;
139 NfaState* start = context.MakeNfaState();
140 NfaState* end = context.MakeNfaState();
141 end->SetAccept(true);
142 start->AddEdge(NfaEdge(context.MakeEpsilon(), end));
143 kleene.SetStart(start);
144 NfaState* nfaStart = nfa.Start();
145 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
146 NfaState* nfaEnd = nfa.End();
147 nfaEnd->SetAccept(false);
148 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
149 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
150 kleene.SetEnd(end);
151 return kleene;
152 }
153 public Nfa Pos(Context& context, const Nfa& nfa)
154 {
155 Nfa pos;
156 NfaState* start = context.MakeNfaState();
157 NfaState* end = context.MakeNfaState();
158 end->SetAccept(true);
159 pos.SetStart(start);
160 NfaState* nfaStart = nfa.Start();
161 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
162 NfaState* nfaEnd = nfa.End();
163 nfaEnd->SetAccept(false);
164 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
165 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
166 pos.SetEnd(end);
167 return pos;
168 }
169 public Nfa Opt(Context& context, const Nfa& nfa)
170 {
171 Nfa opt(nfa);
172 opt.Start()->AddEdge(NfaEdge(context.MakeEpsilon(), opt.End()));
173 return opt;
174 }
175 }