1
2
3
4
5
6 using System;
7 using System.Collections;
8
9 namespace System.RegularExpressions
10 {
11 public class NfaEdge
12 {
13 public NfaEdge(Symbol* symbol_, NfaState* next_) : symbol(symbol_), next(next_)
14 {
15 }
16 public inline Symbol* GetSymbol() const
17 {
18 return symbol;
19 }
20 public inline NfaState* Next() const
21 {
22 return next;
23 }
24 private Symbol* symbol;
25 private NfaState* next;
26 }
27
28 public class NfaState
29 {
30 public NfaState() : accept(false), edges()
31 {
32 }
33 public inline bool Accept() const
34 {
35 return accept;
36 }
37 public void SetAccept(bool accept_)
38 {
39 accept = accept_;
40 }
41 public inline 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
70 public class Nfa
71 {
72 public Nfa() : start(null), end(null)
73 {
74 }
75 public Nfa(NfaState* start_, NfaState* end_) : start(start_), end(end_)
76 {
77 }
78 public inline NfaState* Start() const
79 {
80 return start;
81 }
82 public void SetStart(NfaState* start_)
83 {
84 start = start_;
85 }
86 public inline NfaState* End() const
87 {
88 return end;
89 }
90 public void SetEnd(NfaState* end_)
91 {
92 end = end_;
93 }
94 private NfaState* start;
95 private NfaState* end;
96 }
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
107 public Nfa Cat(const Nfa& left, const Nfa& right)
108 {
109 Nfa cat(left);
110 NfaState* leftEnd = cat.End();
111 leftEnd->SetAccept(false);
112 NfaState* rightStart = right.Start();
113 leftEnd->SetEdges(rightStart->Edges());
114 cat.SetEnd(right.End());
115 return cat;
116 }
117
118 public Nfa Alt(Context& context, const Nfa& left, const Nfa& right)
119 {
120 NfaState* leftStart = left.Start();
121 NfaState* leftEnd = left.End();
122 NfaState* rightStart = right.Start();
123 NfaState* rightEnd = right.End();
124 NfaState* start = context.MakeNfaState();
125 NfaState* end = context.MakeNfaState();
126 end->SetAccept(true);
127 start->AddEdge(NfaEdge(context.MakeEpsilon(), leftStart));
128 start->AddEdge(NfaEdge(context.MakeEpsilon(), rightStart));
129 Nfa alt;
130 alt.SetStart(start);
131 leftEnd->SetAccept(false);
132 leftEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
133 rightEnd->SetAccept(false);
134 rightEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
135 alt.SetEnd(end);
136 return alt;
137 }
138
139 public Nfa Kleene(Context& context, const Nfa& nfa)
140 {
141 Nfa kleene;
142 NfaState* start = context.MakeNfaState();
143 NfaState* end = context.MakeNfaState();
144 end->SetAccept(true);
145 start->AddEdge(NfaEdge(context.MakeEpsilon(), end));
146 kleene.SetStart(start);
147 NfaState* nfaStart = nfa.Start();
148 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
149 NfaState* nfaEnd = nfa.End();
150 nfaEnd->SetAccept(false);
151 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
152 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
153 kleene.SetEnd(end);
154 return kleene;
155 }
156
157 public Nfa Pos(Context& context, const Nfa& nfa)
158 {
159 Nfa pos;
160 NfaState* start = context.MakeNfaState();
161 NfaState* end = context.MakeNfaState();
162 end->SetAccept(true);
163 pos.SetStart(start);
164 NfaState* nfaStart = nfa.Start();
165 start->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
166 NfaState* nfaEnd = nfa.End();
167 nfaEnd->SetAccept(false);
168 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), end));
169 nfaEnd->AddEdge(NfaEdge(context.MakeEpsilon(), nfaStart));
170 pos.SetEnd(end);
171 return pos;
172 }
173
174 public Nfa Opt(Context& context, const Nfa& nfa)
175 {
176 Nfa opt(nfa);
177 opt.Start()->AddEdge(NfaEdge(context.MakeEpsilon(), opt.End()));
178 return opt;
179 }
180