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