1 /* nfa - NFA construction routines */
2
3 /*-
4 * Copyright (c) 1990 The Regents of the University of California.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Vern Paxson.
9 *
10 * The United States Government has rights in this work pursuant
11 * to contract no. DE-AC03-76SF00098 between the United States
12 * Department of Energy and the University of California.
13 *
14 * Redistribution and use in source and binary forms are permitted provided
15 * that: (1) source distributions retain this entire copyright notice and
16 * comment, and (2) distributions including binaries display the following
17 * acknowledgement: ``This product includes software developed by the
18 * University of California, Berkeley and its contributors'' in the
19 * documentation or other materials provided with the distribution and in
20 * all advertising materials mentioning features or use of this software.
21 * Neither the name of the University nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
23 * specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27 */
28
29 /* $Header: /home/daffy/u0/vern/flex/RCS/nfa.c,v 2.13 93/12/07 10:18:28 vern Exp $ */
30
31 #include "flexdef.h"
32
33
34 /* declare functions that have forward references */
35
36 int dupmachine PROTO((int));
37 void mkxtion PROTO((int, int));
38
39
40 /* add_accept - add an accepting state to a machine
41 *
42 * accepting_number becomes mach's accepting number.
43 */
44
add_accept(mach,accepting_number)45 void add_accept( mach, accepting_number )
46 int mach, accepting_number;
47 {
48 /* Hang the accepting number off an epsilon state. if it is associated
49 * with a state that has a non-epsilon out-transition, then the state
50 * will accept BEFORE it makes that transition, i.e., one character
51 * too soon.
52 */
53
54 if ( transchar[finalst[mach]] == SYM_EPSILON )
55 accptnum[finalst[mach]] = accepting_number;
56
57 else
58 {
59 int astate = mkstate( SYM_EPSILON );
60 accptnum[astate] = accepting_number;
61 (void) link_machines( mach, astate );
62 }
63 }
64
65
66 /* copysingl - make a given number of copies of a singleton machine
67 *
68 * synopsis
69 *
70 * newsng = copysingl( singl, num );
71 *
72 * newsng - a new singleton composed of num copies of singl
73 * singl - a singleton machine
74 * num - the number of copies of singl to be present in newsng
75 */
76
copysingl(singl,num)77 int copysingl( singl, num )
78 int singl, num;
79 {
80 int copy, i;
81
82 copy = mkstate( SYM_EPSILON );
83
84 for ( i = 1; i <= num; ++i )
85 copy = link_machines( copy, dupmachine( singl ) );
86
87 return copy;
88 }
89
90
91 /* dumpnfa - debugging routine to write out an nfa */
92
dumpnfa(state1)93 void dumpnfa( state1 )
94 int state1;
95
96 {
97 int sym, tsp1, tsp2, anum, ns;
98
99 fprintf( stderr,
100 "\n\n********** beginning dump of nfa with start state %d\n",
101 state1 );
102
103 /* We probably should loop starting at firstst[state1] and going to
104 * lastst[state1], but they're not maintained properly when we "or"
105 * all of the rules together. So we use our knowledge that the machine
106 * starts at state 1 and ends at lastnfa.
107 */
108
109 /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
110 for ( ns = 1; ns <= lastnfa; ++ns )
111 {
112 fprintf( stderr, "state # %4d\t", ns );
113
114 sym = transchar[ns];
115 tsp1 = trans1[ns];
116 tsp2 = trans2[ns];
117 anum = accptnum[ns];
118
119 fprintf( stderr, "%3d: %4d, %4d", sym, tsp1, tsp2 );
120
121 if ( anum != NIL )
122 fprintf( stderr, " [%d]", anum );
123
124 fprintf( stderr, "\n" );
125 }
126
127 fprintf( stderr, "********** end of dump\n" );
128 }
129
130
131 /* dupmachine - make a duplicate of a given machine
132 *
133 * synopsis
134 *
135 * copy = dupmachine( mach );
136 *
137 * copy - holds duplicate of mach
138 * mach - machine to be duplicated
139 *
140 * note that the copy of mach is NOT an exact duplicate; rather, all the
141 * transition states values are adjusted so that the copy is self-contained,
142 * as the original should have been.
143 *
144 * also note that the original MUST be contiguous, with its low and high
145 * states accessible by the arrays firstst and lastst
146 */
147
dupmachine(mach)148 int dupmachine( mach )
149 int mach;
150 {
151 int i, init, state_offset;
152 int state = 0;
153 int last = lastst[mach];
154
155 for ( i = firstst[mach]; i <= last; ++i )
156 {
157 state = mkstate( transchar[i] );
158
159 if ( trans1[i] != NO_TRANSITION )
160 {
161 mkxtion( finalst[state], trans1[i] + state - i );
162
163 if ( transchar[i] == SYM_EPSILON &&
164 trans2[i] != NO_TRANSITION )
165 mkxtion( finalst[state],
166 trans2[i] + state - i );
167 }
168
169 accptnum[state] = accptnum[i];
170 }
171
172 if ( state == 0 )
173 flexfatal( "empty machine in dupmachine()" );
174
175 state_offset = state - i + 1;
176
177 init = mach + state_offset;
178 firstst[init] = firstst[mach] + state_offset;
179 finalst[init] = finalst[mach] + state_offset;
180 lastst[init] = lastst[mach] + state_offset;
181
182 return init;
183 }
184
185
186 /* finish_rule - finish up the processing for a rule
187 *
188 * An accepting number is added to the given machine. If variable_trail_rule
189 * is true then the rule has trailing context and both the head and trail
190 * are variable size. Otherwise if headcnt or trailcnt is non-zero then
191 * the machine recognizes a pattern with trailing context and headcnt is
192 * the number of characters in the matched part of the pattern, or zero
193 * if the matched part has variable length. trailcnt is the number of
194 * trailing context characters in the pattern, or zero if the trailing
195 * context has variable length.
196 */
197
finish_rule(mach,variable_trail_rule,headcnt,trailcnt)198 void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
199 int mach, variable_trail_rule, headcnt, trailcnt;
200 {
201 char action_text[MAXLINE];
202
203 add_accept( mach, num_rules );
204
205 /* We did this in new_rule(), but it often gets the wrong
206 * number because we do it before we start parsing the current rule.
207 */
208 rule_linenum[num_rules] = linenum;
209
210 /* If this is a continued action, then the line-number has already
211 * been updated, giving us the wrong number.
212 */
213 if ( continued_action )
214 --rule_linenum[num_rules];
215
216 sprintf( action_text, "case %d:\n", num_rules );
217 add_action( action_text );
218
219 if ( variable_trail_rule )
220 {
221 rule_type[num_rules] = RULE_VARIABLE;
222
223 if ( performance_report > 0 )
224 fprintf( stderr,
225 "Variable trailing context rule at line %d\n",
226 rule_linenum[num_rules] );
227
228 variable_trailing_context_rules = true;
229 }
230
231 else
232 {
233 rule_type[num_rules] = RULE_NORMAL;
234
235 if ( headcnt > 0 || trailcnt > 0 )
236 {
237 /* Do trailing context magic to not match the trailing
238 * characters.
239 */
240 char *scanner_cp = "yy_c_buf_p = yy_cp";
241 char *scanner_bp = "yy_bp";
242
243 add_action(
244 "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
245
246 if ( headcnt > 0 )
247 {
248 sprintf( action_text, "%s = %s + %d;\n",
249 scanner_cp, scanner_bp, headcnt );
250 add_action( action_text );
251 }
252
253 else
254 {
255 sprintf( action_text, "%s -= %d;\n",
256 scanner_cp, trailcnt );
257 add_action( action_text );
258 }
259
260 add_action(
261 "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
262 }
263 }
264
265 /* Okay, in the action code at this point yytext and yyleng have
266 * their proper final values for this rule, so here's the point
267 * to do any user action.
268 */
269 add_action( "YY_USER_ACTION\n" );
270
271 line_directive_out( (FILE *) 0 );
272 }
273
274
275 /* link_machines - connect two machines together
276 *
277 * synopsis
278 *
279 * new = link_machines( first, last );
280 *
281 * new - a machine constructed by connecting first to last
282 * first - the machine whose successor is to be last
283 * last - the machine whose predecessor is to be first
284 *
285 * note: this routine concatenates the machine first with the machine
286 * last to produce a machine new which will pattern-match first first
287 * and then last, and will fail if either of the sub-patterns fails.
288 * FIRST is set to new by the operation. last is unmolested.
289 */
290
link_machines(first,last)291 int link_machines( first, last )
292 int first, last;
293 {
294 if ( first == NIL )
295 return last;
296
297 else if ( last == NIL )
298 return first;
299
300 else
301 {
302 mkxtion( finalst[first], last );
303 finalst[first] = finalst[last];
304 lastst[first] = MAX( lastst[first], lastst[last] );
305 firstst[first] = MIN( firstst[first], firstst[last] );
306
307 return first;
308 }
309 }
310
311
312 /* mark_beginning_as_normal - mark each "beginning" state in a machine
313 * as being a "normal" (i.e., not trailing context-
314 * associated) states
315 *
316 * The "beginning" states are the epsilon closure of the first state
317 */
318
mark_beginning_as_normal(mach)319 void mark_beginning_as_normal( mach )
320 register int mach;
321 {
322 switch ( state_type[mach] )
323 {
324 case STATE_NORMAL:
325 /* Oh, we've already visited here. */
326 return;
327
328 case STATE_TRAILING_CONTEXT:
329 state_type[mach] = STATE_NORMAL;
330
331 if ( transchar[mach] == SYM_EPSILON )
332 {
333 if ( trans1[mach] != NO_TRANSITION )
334 mark_beginning_as_normal(
335 trans1[mach] );
336
337 if ( trans2[mach] != NO_TRANSITION )
338 mark_beginning_as_normal(
339 trans2[mach] );
340 }
341 break;
342
343 default:
344 flexerror(
345 "bad state type in mark_beginning_as_normal()" );
346 break;
347 }
348 }
349
350
351 /* mkbranch - make a machine that branches to two machines
352 *
353 * synopsis
354 *
355 * branch = mkbranch( first, second );
356 *
357 * branch - a machine which matches either first's pattern or second's
358 * first, second - machines whose patterns are to be or'ed (the | operator)
359 *
360 * Note that first and second are NEITHER destroyed by the operation. Also,
361 * the resulting machine CANNOT be used with any other "mk" operation except
362 * more mkbranch's. Compare with mkor()
363 */
364
mkbranch(first,second)365 int mkbranch( first, second )
366 int first, second;
367 {
368 int eps;
369
370 if ( first == NO_TRANSITION )
371 return second;
372
373 else if ( second == NO_TRANSITION )
374 return first;
375
376 eps = mkstate( SYM_EPSILON );
377
378 mkxtion( eps, first );
379 mkxtion( eps, second );
380
381 return eps;
382 }
383
384
385 /* mkclos - convert a machine into a closure
386 *
387 * synopsis
388 * new = mkclos( state );
389 *
390 * new - a new state which matches the closure of "state"
391 */
392
mkclos(state)393 int mkclos( state )
394 int state;
395 {
396 return mkopt( mkposcl( state ) );
397 }
398
399
400 /* mkopt - make a machine optional
401 *
402 * synopsis
403 *
404 * new = mkopt( mach );
405 *
406 * new - a machine which optionally matches whatever mach matched
407 * mach - the machine to make optional
408 *
409 * notes:
410 * 1. mach must be the last machine created
411 * 2. mach is destroyed by the call
412 */
413
mkopt(mach)414 int mkopt( mach )
415 int mach;
416 {
417 int eps;
418
419 if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
420 {
421 eps = mkstate( SYM_EPSILON );
422 mach = link_machines( mach, eps );
423 }
424
425 /* Can't skimp on the following if FREE_EPSILON(mach) is true because
426 * some state interior to "mach" might point back to the beginning
427 * for a closure.
428 */
429 eps = mkstate( SYM_EPSILON );
430 mach = link_machines( eps, mach );
431
432 mkxtion( mach, finalst[mach] );
433
434 return mach;
435 }
436
437
438 /* mkor - make a machine that matches either one of two machines
439 *
440 * synopsis
441 *
442 * new = mkor( first, second );
443 *
444 * new - a machine which matches either first's pattern or second's
445 * first, second - machines whose patterns are to be or'ed (the | operator)
446 *
447 * note that first and second are both destroyed by the operation
448 * the code is rather convoluted because an attempt is made to minimize
449 * the number of epsilon states needed
450 */
451
mkor(first,second)452 int mkor( first, second )
453 int first, second;
454 {
455 int eps, orend;
456
457 if ( first == NIL )
458 return second;
459
460 else if ( second == NIL )
461 return first;
462
463 else
464 {
465 /* See comment in mkopt() about why we can't use the first
466 * state of "first" or "second" if they satisfy "FREE_EPSILON".
467 */
468 eps = mkstate( SYM_EPSILON );
469
470 first = link_machines( eps, first );
471
472 mkxtion( first, second );
473
474 if ( SUPER_FREE_EPSILON(finalst[first]) &&
475 accptnum[finalst[first]] == NIL )
476 {
477 orend = finalst[first];
478 mkxtion( finalst[second], orend );
479 }
480
481 else if ( SUPER_FREE_EPSILON(finalst[second]) &&
482 accptnum[finalst[second]] == NIL )
483 {
484 orend = finalst[second];
485 mkxtion( finalst[first], orend );
486 }
487
488 else
489 {
490 eps = mkstate( SYM_EPSILON );
491
492 first = link_machines( first, eps );
493 orend = finalst[first];
494
495 mkxtion( finalst[second], orend );
496 }
497 }
498
499 finalst[first] = orend;
500 return first;
501 }
502
503
504 /* mkposcl - convert a machine into a positive closure
505 *
506 * synopsis
507 * new = mkposcl( state );
508 *
509 * new - a machine matching the positive closure of "state"
510 */
511
mkposcl(state)512 int mkposcl( state )
513 int state;
514 {
515 int eps;
516
517 if ( SUPER_FREE_EPSILON(finalst[state]) )
518 {
519 mkxtion( finalst[state], state );
520 return state;
521 }
522
523 else
524 {
525 eps = mkstate( SYM_EPSILON );
526 mkxtion( eps, state );
527 return link_machines( state, eps );
528 }
529 }
530
531
532 /* mkrep - make a replicated machine
533 *
534 * synopsis
535 * new = mkrep( mach, lb, ub );
536 *
537 * new - a machine that matches whatever "mach" matched from "lb"
538 * number of times to "ub" number of times
539 *
540 * note
541 * if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
542 */
543
mkrep(mach,lb,ub)544 int mkrep( mach, lb, ub )
545 int mach, lb, ub;
546 {
547 int base_mach, tail, copy, i;
548
549 base_mach = copysingl( mach, lb - 1 );
550
551 if ( ub == INFINITY )
552 {
553 copy = dupmachine( mach );
554 mach = link_machines( mach,
555 link_machines( base_mach, mkclos( copy ) ) );
556 }
557
558 else
559 {
560 tail = mkstate( SYM_EPSILON );
561
562 for ( i = lb; i < ub; ++i )
563 {
564 copy = dupmachine( mach );
565 tail = mkopt( link_machines( copy, tail ) );
566 }
567
568 mach = link_machines( mach, link_machines( base_mach, tail ) );
569 }
570
571 return mach;
572 }
573
574
575 /* mkstate - create a state with a transition on a given symbol
576 *
577 * synopsis
578 *
579 * state = mkstate( sym );
580 *
581 * state - a new state matching sym
582 * sym - the symbol the new state is to have an out-transition on
583 *
584 * note that this routine makes new states in ascending order through the
585 * state array (and increments LASTNFA accordingly). The routine DUPMACHINE
586 * relies on machines being made in ascending order and that they are
587 * CONTIGUOUS. Change it and you will have to rewrite DUPMACHINE (kludge
588 * that it admittedly is)
589 */
590
mkstate(sym)591 int mkstate( sym )
592 int sym;
593 {
594 if ( ++lastnfa >= current_mns )
595 {
596 if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
597 lerrif(
598 "input rules are too complicated (>= %d NFA states)",
599 current_mns );
600
601 ++num_reallocs;
602
603 firstst = reallocate_integer_array( firstst, current_mns );
604 lastst = reallocate_integer_array( lastst, current_mns );
605 finalst = reallocate_integer_array( finalst, current_mns );
606 transchar = reallocate_integer_array( transchar, current_mns );
607 trans1 = reallocate_integer_array( trans1, current_mns );
608 trans2 = reallocate_integer_array( trans2, current_mns );
609 accptnum = reallocate_integer_array( accptnum, current_mns );
610 assoc_rule =
611 reallocate_integer_array( assoc_rule, current_mns );
612 state_type =
613 reallocate_integer_array( state_type, current_mns );
614 }
615
616 firstst[lastnfa] = lastnfa;
617 finalst[lastnfa] = lastnfa;
618 lastst[lastnfa] = lastnfa;
619 transchar[lastnfa] = sym;
620 trans1[lastnfa] = NO_TRANSITION;
621 trans2[lastnfa] = NO_TRANSITION;
622 accptnum[lastnfa] = NIL;
623 assoc_rule[lastnfa] = num_rules;
624 state_type[lastnfa] = current_state_type;
625
626 /* Fix up equivalence classes base on this transition. Note that any
627 * character which has its own transition gets its own equivalence
628 * class. Thus only characters which are only in character classes
629 * have a chance at being in the same equivalence class. E.g. "a|b"
630 * puts 'a' and 'b' into two different equivalence classes. "[ab]"
631 * puts them in the same equivalence class (barring other differences
632 * elsewhere in the input).
633 */
634
635 if ( sym < 0 )
636 {
637 /* We don't have to update the equivalence classes since
638 * that was already done when the ccl was created for the
639 * first time.
640 */
641 }
642
643 else if ( sym == SYM_EPSILON )
644 ++numeps;
645
646 else
647 {
648 check_char( sym );
649
650 if ( useecs )
651 /* Map NUL's to csize. */
652 mkechar( sym ? sym : csize, nextecm, ecgroup );
653 }
654
655 return lastnfa;
656 }
657
658
659 /* mkxtion - make a transition from one state to another
660 *
661 * synopsis
662 *
663 * mkxtion( statefrom, stateto );
664 *
665 * statefrom - the state from which the transition is to be made
666 * stateto - the state to which the transition is to be made
667 */
668
mkxtion(statefrom,stateto)669 void mkxtion( statefrom, stateto )
670 int statefrom, stateto;
671 {
672 if ( trans1[statefrom] == NO_TRANSITION )
673 trans1[statefrom] = stateto;
674
675 else if ( (transchar[statefrom] != SYM_EPSILON) ||
676 (trans2[statefrom] != NO_TRANSITION) )
677 flexfatal( "found too many transitions in mkxtion()" );
678
679 else
680 { /* second out-transition for an epsilon state */
681 ++eps2;
682 trans2[statefrom] = stateto;
683 }
684 }
685
686 /* new_rule - initialize for a new rule */
687
new_rule()688 void new_rule()
689 {
690 if ( ++num_rules >= current_max_rules )
691 {
692 ++num_reallocs;
693 current_max_rules += MAX_RULES_INCREMENT;
694 rule_type = reallocate_integer_array( rule_type,
695 current_max_rules );
696 rule_linenum = reallocate_integer_array( rule_linenum,
697 current_max_rules );
698 rule_useful = reallocate_integer_array( rule_useful,
699 current_max_rules );
700 }
701
702 if ( num_rules > MAX_RULE )
703 lerrif( "too many rules (> %d)!", MAX_RULE );
704
705 rule_linenum[num_rules] = linenum;
706 rule_useful[num_rules] = false;
707 }
708