Branch data Line data Source code
1 : : // $Id: NFA.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include "NFA.h"
8 : : #include "EquivClass.h"
9 : :
10 : : static int nfa_state_id = 0;
11 : :
12 : 55051 : NFA_State::NFA_State(int arg_sym, EquivClass* ec)
13 : : {
14 : 55051 : sym = arg_sym;
15 : 55051 : ccl = 0;
16 : 55051 : accept = NO_ACCEPT;
17 : 55051 : mark = 0;
18 : 55051 : epsclosure = 0;
19 : 55051 : id = ++nfa_state_id;
20 : :
21 : : // Fix up equivalence classes based on this transition. Note that any
22 : : // character which has its own transition gets its own equivalence
23 : : // class. Thus only characters which are only in character classes
24 : : // have a chance at being in the same equivalence class. E.g. "a|b"
25 : : // puts 'a' and 'b' into two different equivalence classes. "[ab]"
26 : : // puts them in the same equivalence class (barring other differences
27 : : // elsewhere in the input).
28 : :
29 [ + + + - - : 55051 : if ( ec && sym != SYM_EPSILON /* no associated symbol */ )
+ ][ # # ]
30 : 18336 : ec->UniqueChar(sym);
31 : 55051 : }
32 : :
33 : 4279 : NFA_State::NFA_State(CCL* arg_ccl)
34 : : {
35 : 4279 : sym = SYM_CCL;
36 : 4279 : ccl = arg_ccl;
37 : 4279 : accept = NO_ACCEPT;
38 : 4279 : mark = 0;
39 : 4279 : id = ++nfa_state_id;
40 : 4279 : epsclosure = 0;
41 : 4279 : }
42 : :
43 : 442 : NFA_State::~NFA_State()
44 : : {
45 [ + + ][ # # ]: 1101 : for ( int i = 0; i < xtions.length(); ++i )
[ + + ]
46 : 659 : Unref(xtions[i]);
47 [ + - ][ # # ]: 442 : }
[ - + ]
48 : :
49 : 10998 : void NFA_State::AddXtionsTo(NFA_state_list* ns)
50 : : {
51 [ + + ]: 21996 : for ( int i = 0; i < xtions.length(); ++i )
52 : 10998 : ns->append(xtions[i]);
53 : 10998 : }
54 : :
55 : 2072 : NFA_State* NFA_State::DeepCopy()
56 : : {
57 [ + + ]: 2072 : if ( mark )
58 : 230 : return mark;
59 : :
60 [ + + ]: 1842 : NFA_State* copy = ccl ? new NFA_State(ccl) : new NFA_State(sym, 0);
61 : 1842 : SetMark(copy);
62 : :
63 [ + + ]: 3272 : for ( int i = 0; i < xtions.length(); ++i )
64 : 1430 : copy->AddXtion(xtions[i]->DeepCopy());
65 : :
66 : 2072 : return copy;
67 : : }
68 : :
69 : 2072 : void NFA_State::ClearMarks()
70 : : {
71 [ + + ]: 2072 : if ( mark )
72 : : {
73 : 1842 : SetMark(0);
74 [ + + ]: 3272 : for ( int i = 0; i < xtions.length(); ++i )
75 : 1430 : xtions[i]->ClearMarks();
76 : : }
77 : 2072 : }
78 : :
79 : 11442 : NFA_state_list* NFA_State::EpsilonClosure()
80 : : {
81 [ + + ]: 11442 : if ( epsclosure )
82 : 10783 : return epsclosure;
83 : :
84 : 659 : epsclosure = new NFA_state_list;
85 : :
86 : 659 : NFA_state_list states;
87 : 659 : states.append(this);
88 : 659 : SetMark(this);
89 : :
90 : : int i;
91 [ + + ]: 14876 : for ( i = 0; i < states.length(); ++i )
92 : : {
93 : 14217 : NFA_State* ns = states[i];
94 [ + + ]: 14217 : if ( ns->TransSym() == SYM_EPSILON )
95 : : {
96 : 9318 : NFA_state_list* x = ns->Transitions();
97 [ + + ]: 22882 : for ( int j = 0; j < x->length(); ++j )
98 : : {
99 : 13564 : NFA_State* nxt = (*x)[j];
100 [ + + ]: 13564 : if ( ! nxt->Mark() )
101 : : {
102 : 13558 : states.append(nxt);
103 : 13558 : nxt->SetMark(nxt);
104 : : }
105 : : }
106 : :
107 [ + + ]: 9318 : if ( ns->Accept() != NO_ACCEPT )
108 : 9318 : epsclosure->append(ns);
109 : : }
110 : :
111 : : else
112 : : // Non-epsilon transition - keep it.
113 : 4899 : epsclosure->append(ns);
114 : : }
115 : :
116 : : // Clear out markers.
117 [ + + ]: 14876 : for ( i = 0; i < states.length(); ++i )
118 : 14217 : states[i]->SetMark(0);
119 : :
120 : : // Make it fit.
121 : 659 : epsclosure->resize(0);
122 : :
123 : 11442 : return epsclosure;
124 : : }
125 : :
126 : 0 : void NFA_State::Describe(ODesc* d) const
127 : : {
128 : 0 : d->Add("NFA state");
129 : 0 : }
130 : :
131 : 0 : void NFA_State::Dump(FILE* f)
132 : : {
133 [ # # ]: 0 : if ( mark )
134 : 0 : return;
135 : :
136 : 0 : fprintf(f, "NFA state %d, sym = %d, accept = %d:\n", id, sym, accept);
137 : :
138 [ # # ]: 0 : for ( int i = 0; i < xtions.length(); ++i )
139 : 0 : fprintf(f, "\ttransition to %d\n", xtions[i]->ID());
140 : :
141 : 0 : SetMark(this);
142 [ # # ]: 0 : for ( int i = 0; i < xtions.length(); ++i )
143 : 0 : xtions[i]->Dump(f);
144 : : }
145 : :
146 : 0 : unsigned int NFA_State::TotalMemoryAllocation() const
147 : : {
148 : : return padded_sizeof(*this)
149 : : + xtions.MemoryAllocation() - padded_sizeof(xtions)
150 [ # # ]: 0 : + (epsclosure ? epsclosure->MemoryAllocation() : 0);
151 : : }
152 : :
153 : 24784 : NFA_Machine::NFA_Machine(NFA_State* first, NFA_State* final)
154 : : {
155 : 24784 : first_state = first;
156 [ + + ][ # # ]: 24784 : final_state = final ? final : first;
157 : 24784 : eol = bol = 0;
158 : 24784 : }
159 : :
160 : 19590 : NFA_Machine::~NFA_Machine()
161 : : {
162 : 19590 : Unref(first_state);
163 [ + - ][ # # ]: 19590 : }
[ # # ]
164 : :
165 : 4490 : void NFA_Machine::InsertEpsilon()
166 : : {
167 : 4490 : NFA_State* eps = new EpsilonState();
168 : 4490 : eps->AddXtion(first_state);
169 : 4490 : first_state = eps;
170 : 4490 : }
171 : :
172 : 26383 : void NFA_Machine::AppendEpsilon()
173 : : {
174 : 26383 : AppendState(new EpsilonState());
175 : 26383 : }
176 : :
177 : 444 : void NFA_Machine::AddAccept(int accept_val)
178 : : {
179 : : // Hang the accepting number off an epsilon state. If it is associated
180 : : // with a state that has a non-epsilon out-transition, then the state
181 : : // will accept BEFORE it makes that transition, i.e., one character
182 : : // too soon.
183 : :
184 [ + + ]: 444 : if ( final_state->TransSym() != SYM_EPSILON )
185 : 96 : AppendState(new EpsilonState());
186 : :
187 : 444 : final_state->SetAccept(accept_val);
188 : 444 : }
189 : :
190 : 212 : void NFA_Machine::LinkCopies(int n)
191 : : {
192 [ + + ]: 212 : if ( n <= 0 )
193 : 170 : return;
194 : :
195 : : // Make all the copies before doing any appending, otherwise
196 : : // subsequent DuplicateMachine()'s will include the extra
197 : : // copies!
198 : 42 : NFA_Machine** copies = new NFA_Machine*[n];
199 : :
200 : : int i;
201 [ + + ]: 176 : for ( i = 0; i < n; ++i )
202 : 134 : copies[i] = DuplicateMachine();
203 : :
204 [ + + ]: 176 : for ( i = 0; i < n; ++i )
205 : 134 : AppendMachine(copies[i]);
206 : :
207 [ + - ]: 212 : delete [] copies;
208 : : }
209 : :
210 : 642 : NFA_Machine* NFA_Machine::DuplicateMachine()
211 : : {
212 : 642 : NFA_State* new_first_state = first_state->DeepCopy();
213 : 642 : NFA_Machine* new_m = new NFA_Machine(new_first_state, final_state->Mark());
214 : 642 : first_state->ClearMarks();
215 : :
216 : 642 : return new_m;
217 : : }
218 : :
219 : 31233 : void NFA_Machine::AppendState(NFA_State* s)
220 : : {
221 : 31233 : final_state->AddXtion(s);
222 : 31233 : final_state = s;
223 : 31233 : }
224 : :
225 : 19586 : void NFA_Machine::AppendMachine(NFA_Machine* m)
226 : : {
227 : 19586 : AppendEpsilon();
228 : 19586 : final_state->AddXtion(m->FirstState());
229 : 19586 : final_state = m->FinalState();
230 : :
231 : 19586 : Ref(m->FirstState()); // so states stay around after the following
232 : 19586 : Unref(m);
233 : 19586 : }
234 : :
235 : 4490 : void NFA_Machine::MakeOptional()
236 : : {
237 : 4490 : InsertEpsilon();
238 : 4490 : AppendEpsilon();
239 : 4490 : first_state->AddXtion(final_state);
240 : 4490 : Ref(final_state);
241 : 4490 : }
242 : :
243 : 2307 : void NFA_Machine::MakePositiveClosure()
244 : : {
245 : 2307 : AppendEpsilon();
246 : 2307 : final_state->AddXtion(first_state);
247 : 2307 : Ref(first_state);
248 : 2307 : }
249 : :
250 : 188 : void NFA_Machine::MakeRepl(int lower, int upper)
251 : : {
252 : 188 : NFA_Machine* dup = 0;
253 [ + + ][ + + ]: 188 : if ( upper > lower || upper == NO_UPPER_BOUND )
254 : 182 : dup = DuplicateMachine();
255 : :
256 : 188 : LinkCopies(lower - 1);
257 : :
258 [ + + ]: 188 : if ( upper == NO_UPPER_BOUND )
259 : : {
260 : 12 : dup->MakeClosure();
261 : 12 : AppendMachine(dup);
262 : 12 : return;
263 : : }
264 : :
265 [ + + ]: 684 : while ( upper > lower )
266 : : {
267 : : NFA_Machine* dup2;
268 [ + + ]: 496 : if ( --upper == lower )
269 : : // Don't need "dup" for any further copies
270 : 170 : dup2 = dup;
271 : : else
272 : 326 : dup2 = dup->DuplicateMachine();
273 : :
274 : 496 : dup2->MakeOptional();
275 : 496 : AppendMachine(dup2);
276 : : }
277 : : }
278 : :
279 : 0 : void NFA_Machine::Describe(ODesc* d) const
280 : : {
281 : 0 : d->Add("NFA machine");
282 : 0 : }
283 : :
284 : 0 : void NFA_Machine::Dump(FILE* f)
285 : : {
286 : 0 : first_state->Dump(f);
287 : 0 : first_state->ClearMarks();
288 : 0 : }
289 : :
290 : 0 : void NFA_Machine::DumpStats(FILE* f)
291 : : {
292 : 0 : fprintf(f, "highest NFA state ID is %d\n", nfa_state_id);
293 : 0 : }
294 : :
295 : 2377 : NFA_Machine* make_alternate(NFA_Machine* m1, NFA_Machine* m2)
296 : : {
297 [ - + ]: 2377 : if ( ! m1 )
298 : 0 : return m2;
299 [ - + ]: 2377 : if ( ! m2 )
300 : 0 : return m1;
301 : :
302 : 2377 : NFA_State* first = new EpsilonState();
303 : 2377 : NFA_State* last = new EpsilonState();
304 : :
305 : 2377 : first->AddXtion(m1->FirstState());
306 : 2377 : first->AddXtion(m2->FirstState());
307 : :
308 : 2377 : m1->AppendState(last);
309 : 2377 : m2->AppendState(last);
310 : 2377 : Ref(last);
311 : :
312 : 2377 : return new NFA_Machine(first, last);
313 : : }
314 : :
315 : :
316 : 1082 : NFA_state_list* epsilon_closure(NFA_state_list* states)
317 : : {
318 : : // We just keep one of this as it may get quite large.
319 [ + + ][ + - ]: 1084 : static IntSet closuremap;
[ # # ]
320 : 1082 : closuremap.Clear();
321 : :
322 : 1082 : NFA_state_list* closure = new NFA_state_list;
323 : :
324 [ + + ]: 12524 : for ( int i = 0; i < states->length(); ++i )
325 : : {
326 : 11442 : NFA_state_list* stateclosure = (*states)[i]->EpsilonClosure();
327 : :
328 [ + + ]: 47651 : for ( int j = 0; j < stateclosure->length(); ++j )
329 : : {
330 : 36209 : NFA_State* ns = (*stateclosure)[j];
331 [ + + ]: 36209 : if ( ! closuremap.Contains(ns->ID()) )
332 : : {
333 : 35933 : closuremap.Insert(ns->ID());
334 : 35933 : closure->sortedinsert(ns, NFA_state_cmp_neg);
335 : : }
336 : : }
337 : : }
338 : :
339 : : // Make it fit.
340 : 1082 : closure->resize(0);
341 : :
342 [ + - ]: 1082 : delete states;
343 : :
344 : 1082 : return closure;
345 : : }
346 : :
347 : 82094 : int NFA_state_cmp_neg(const void* v1, const void* v2)
348 : : {
349 : 82094 : const NFA_State* n1 = (const NFA_State*) v1;
350 : 82094 : const NFA_State* n2 = (const NFA_State*) v2;
351 : :
352 [ + + ]: 82094 : if ( n1->ID() < n2->ID() )
353 : 32894 : return -1;
354 [ - + ]: 49200 : else if ( n1->ID() == n2->ID() )
355 : 0 : return 0;
356 : : else
357 : 82094 : return 1;
358 [ + - ][ + - ]: 6 : }
|
