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 public string ToString() const
25 {
26 string s = symbol->ToString();
27 s.Append(" -> ").Append(ToString(next->Id()));
28 return s;
29 }
30 private Symbol* symbol;
31 private NfaState* next;
32 }
33 public class NfaState
34 {
35 public NfaState(int id_) :
36 id(id_), accept(false), edges()
37 {
38 }
39 public bool Accept() const
40 {
41 return accept;
42 }
43 public void SetAccept(bool accept_)
44 {
45 accept = accept_;
46 }
47 public const List<NfaEdge>& Edges() const
48 {
49 return edges;
50 }
51 public void SetEdges(const List<NfaEdge>& edges_)
52 {
53 edges = edges_;
54 }
55 public void AddEdge(const NfaEdge& edge)
56 {
57 edges.Add(edge);
58 }
59 public List<NfaState*> Next(uchar c) const
60 {
61 List<NfaState*> next;
62 for (const NfaEdge& edge : edges)
63 {
64 Symbol* symbol = edge.GetSymbol();
65 if (symbol->Match(c))
66 {
67 next.Add(edge.Next());
68 }
69 }
70 return next;
71 }
72 public void Dump()
73 {
74 string acceptStr;
75 if (accept)
76 {
77 acceptStr = " (accepting)";
78 }
79 Console.Out() << "state " << id << acceptStr << ":" << endl();
80 for (int i = 0; i < edges.Count(); ++i;)
81 {
82 const NfaEdge& edge = edges[i];
83 Console.Out() << " " << edge.ToString() << endl();
84 }
85 }
86 public nothrow int Id() const
87 {
88 return id;
89 }
90 private int id;
91 private bool accept;
92 private List<NfaEdge> edges;
93 }
94 public class Nfa
95 {
96 public Nfa() :
97 start(null), end(null)
98 {
99 }
100 public Nfa(NfaState* start_, NfaState* end_) :
101 start(start_), end(end_)
102 {
103 }
104 public NfaState* Start() const
105 {
106 return start;
107 }
108 public void SetStart(NfaState* start_)
109 {
110 start = start_;
111 }
112 public NfaState* End() const
113 {
114 return end;
115 }
116 public void SetEnd(NfaState* end_)
117 {
118 end = end_;
119 }
120 public void Dump()
121 {
122 Console.Out() << "NFA(" << start->Id() << ", " << end->Id() << ")" << endl();
123 }
124 private NfaState* start;
125 private NfaState* end;
126 }
127 public Nfa MakeNfa(Context& context, Symbol* symbol)
128 {
129 NfaState* start = context.MakeNfaState();
130 NfaState* end = context.MakeNfaState();
131 end->SetAccept(true);
132 start->AddEdge(NfaEdge(symbol, end));
133 return Nfa(start, end);
134 }
135 public Nfa Cat(const Nfa& left, const Nfa& right)
136 {
137 Nfa cat(left);
138 NfaState* leftEnd = cat.End();
139 leftEnd->SetAccept(false);
140 NfaState* rightStart = right.Start();
141 leftEnd->SetEdges(rightStart->Edges());
142 cat.SetEnd(right.End());
143 return cat;
144 }
145 public Nfa Alt(Context& context, const Nfa& left, const Nfa& right)
146 {
147 NfaState* leftStart = left.Start();
148 NfaState* leftEnd = left.End();
149 NfaState* rightStart = right.Start();
150 NfaState* rightEnd = right.End();
151 NfaState* start = context.MakeNfaState();
152 NfaState* end = context.MakeNfaState();
153 end->SetAccept(true);
154 start->AddEdge(NfaEdge(context.MakeEpsilon(), leftStart));
155 start->AddEdge(NfaEdge(context.MakeEpsilon(), rightStart));
156 Nfa alt;
157 alt.SetStart(start);
158 leftEnd->SetAccept(false);
159 leftEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
160 rightEnd->SetAccept(false);
161 rightEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
162 alt.SetEnd(end);
163 return alt;
164 }
165 public Nfa Kleene(Context& context, const Nfa& nfa)
166 {
167 Nfa kleene;
168 NfaState* start = context.MakeNfaState();
169 NfaState* end = context.MakeNfaState();
170 end->SetAccept(true);
171 start->AddEdge(NfaEdge(context.MakeEpsilon(), end));
172 kleene.SetStart(start);
173 NfaState* nfaStart = nfa.Start();
174 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
175 NfaState* nfaEnd = nfa.End();
176 nfaEnd->SetAccept(false);
177 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
178 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
179 kleene.SetEnd(end);
180 return kleene;
181 }
182 public Nfa Pos(Context& context, const Nfa& nfa)
183 {
184 Nfa pos;
185 NfaState* start = context.MakeNfaState();
186 NfaState* end = context.MakeNfaState();
187 end->SetAccept(true);
188 pos.SetStart(start);
189 NfaState* nfaStart = nfa.Start();
190 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
191 NfaState* nfaEnd = nfa.End();
192 nfaEnd->SetAccept(false);
193 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
194 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
195 pos.SetEnd(end);
196 return pos;
197 }
198 public Nfa Opt(Context& context, const Nfa& nfa)
199 {
200 Nfa opt(nfa);
201 opt.Start()->AddEdge(NfaEdge(context.MakeEpsilon(), opt.End()));
202 return opt;
203 }
204 }