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 with or without 15 * modification are permitted provided that: (1) source distributions retain 16 * this entire copyright notice and comment, and (2) distributions including 17 * binaries display the following acknowledgement: ``This product includes 18 * software developed by the University of California, Berkeley and its 19 * contributors'' in the documentation or other materials provided with the 20 * distribution and in all advertising materials mentioning features or use 21 * of this software. Neither the name of the University nor the names of 22 * its contributors may be used to endorse or promote products derived from 23 * this software without 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: /projects/cvsroot/src/router/flex/nfa.c,v 1.1.1.1 2001/04/08 23:53:37 mhuang Exp $ */ 30 31#include "flexdef.h" 32 33 34/* declare functions that have forward references */ 35 36int dupmachine PROTO((int)); 37void 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 45void add_accept( mach, accepting_number ) 46int 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 77int copysingl( singl, num ) 78int 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 93void dumpnfa( state1 ) 94int 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 148int dupmachine( mach ) 149int 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 198void finish_rule( mach, variable_trail_rule, headcnt, trailcnt ) 199int 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. But don't do it for continued actions, 268 * as that'll result in multiple YY_RULE_SETUP's. 269 */ 270 if ( ! continued_action ) 271 add_action( "YY_RULE_SETUP\n" ); 272 273 line_directive_out( (FILE *) 0, 1 ); 274 } 275 276 277/* link_machines - connect two machines together 278 * 279 * synopsis 280 * 281 * new = link_machines( first, last ); 282 * 283 * new - a machine constructed by connecting first to last 284 * first - the machine whose successor is to be last 285 * last - the machine whose predecessor is to be first 286 * 287 * note: this routine concatenates the machine first with the machine 288 * last to produce a machine new which will pattern-match first first 289 * and then last, and will fail if either of the sub-patterns fails. 290 * FIRST is set to new by the operation. last is unmolested. 291 */ 292 293int link_machines( first, last ) 294int first, last; 295 { 296 if ( first == NIL ) 297 return last; 298 299 else if ( last == NIL ) 300 return first; 301 302 else 303 { 304 mkxtion( finalst[first], last ); 305 finalst[first] = finalst[last]; 306 lastst[first] = MAX( lastst[first], lastst[last] ); 307 firstst[first] = MIN( firstst[first], firstst[last] ); 308 309 return first; 310 } 311 } 312 313 314/* mark_beginning_as_normal - mark each "beginning" state in a machine 315 * as being a "normal" (i.e., not trailing context- 316 * associated) states 317 * 318 * The "beginning" states are the epsilon closure of the first state 319 */ 320 321void mark_beginning_as_normal( mach ) 322register int mach; 323 { 324 switch ( state_type[mach] ) 325 { 326 case STATE_NORMAL: 327 /* Oh, we've already visited here. */ 328 return; 329 330 case STATE_TRAILING_CONTEXT: 331 state_type[mach] = STATE_NORMAL; 332 333 if ( transchar[mach] == SYM_EPSILON ) 334 { 335 if ( trans1[mach] != NO_TRANSITION ) 336 mark_beginning_as_normal( 337 trans1[mach] ); 338 339 if ( trans2[mach] != NO_TRANSITION ) 340 mark_beginning_as_normal( 341 trans2[mach] ); 342 } 343 break; 344 345 default: 346 flexerror( 347 _( "bad state type in mark_beginning_as_normal()" ) ); 348 break; 349 } 350 } 351 352 353/* mkbranch - make a machine that branches to two machines 354 * 355 * synopsis 356 * 357 * branch = mkbranch( first, second ); 358 * 359 * branch - a machine which matches either first's pattern or second's 360 * first, second - machines whose patterns are to be or'ed (the | operator) 361 * 362 * Note that first and second are NEITHER destroyed by the operation. Also, 363 * the resulting machine CANNOT be used with any other "mk" operation except 364 * more mkbranch's. Compare with mkor() 365 */ 366 367int mkbranch( first, second ) 368int first, second; 369 { 370 int eps; 371 372 if ( first == NO_TRANSITION ) 373 return second; 374 375 else if ( second == NO_TRANSITION ) 376 return first; 377 378 eps = mkstate( SYM_EPSILON ); 379 380 mkxtion( eps, first ); 381 mkxtion( eps, second ); 382 383 return eps; 384 } 385 386 387/* mkclos - convert a machine into a closure 388 * 389 * synopsis 390 * new = mkclos( state ); 391 * 392 * new - a new state which matches the closure of "state" 393 */ 394 395int mkclos( state ) 396int state; 397 { 398 return mkopt( mkposcl( state ) ); 399 } 400 401 402/* mkopt - make a machine optional 403 * 404 * synopsis 405 * 406 * new = mkopt( mach ); 407 * 408 * new - a machine which optionally matches whatever mach matched 409 * mach - the machine to make optional 410 * 411 * notes: 412 * 1. mach must be the last machine created 413 * 2. mach is destroyed by the call 414 */ 415 416int mkopt( mach ) 417int mach; 418 { 419 int eps; 420 421 if ( ! SUPER_FREE_EPSILON(finalst[mach]) ) 422 { 423 eps = mkstate( SYM_EPSILON ); 424 mach = link_machines( mach, eps ); 425 } 426 427 /* Can't skimp on the following if FREE_EPSILON(mach) is true because 428 * some state interior to "mach" might point back to the beginning 429 * for a closure. 430 */ 431 eps = mkstate( SYM_EPSILON ); 432 mach = link_machines( eps, mach ); 433 434 mkxtion( mach, finalst[mach] ); 435 436 return mach; 437 } 438 439 440/* mkor - make a machine that matches either one of two machines 441 * 442 * synopsis 443 * 444 * new = mkor( first, second ); 445 * 446 * new - a machine which matches either first's pattern or second's 447 * first, second - machines whose patterns are to be or'ed (the | operator) 448 * 449 * note that first and second are both destroyed by the operation 450 * the code is rather convoluted because an attempt is made to minimize 451 * the number of epsilon states needed 452 */ 453 454int mkor( first, second ) 455int first, second; 456 { 457 int eps, orend; 458 459 if ( first == NIL ) 460 return second; 461 462 else if ( second == NIL ) 463 return first; 464 465 else 466 { 467 /* See comment in mkopt() about why we can't use the first 468 * state of "first" or "second" if they satisfy "FREE_EPSILON". 469 */ 470 eps = mkstate( SYM_EPSILON ); 471 472 first = link_machines( eps, first ); 473 474 mkxtion( first, second ); 475 476 if ( SUPER_FREE_EPSILON(finalst[first]) && 477 accptnum[finalst[first]] == NIL ) 478 { 479 orend = finalst[first]; 480 mkxtion( finalst[second], orend ); 481 } 482 483 else if ( SUPER_FREE_EPSILON(finalst[second]) && 484 accptnum[finalst[second]] == NIL ) 485 { 486 orend = finalst[second]; 487 mkxtion( finalst[first], orend ); 488 } 489 490 else 491 { 492 eps = mkstate( SYM_EPSILON ); 493 494 first = link_machines( first, eps ); 495 orend = finalst[first]; 496 497 mkxtion( finalst[second], orend ); 498 } 499 } 500 501 finalst[first] = orend; 502 return first; 503 } 504 505 506/* mkposcl - convert a machine into a positive closure 507 * 508 * synopsis 509 * new = mkposcl( state ); 510 * 511 * new - a machine matching the positive closure of "state" 512 */ 513 514int mkposcl( state ) 515int state; 516 { 517 int eps; 518 519 if ( SUPER_FREE_EPSILON(finalst[state]) ) 520 { 521 mkxtion( finalst[state], state ); 522 return state; 523 } 524 525 else 526 { 527 eps = mkstate( SYM_EPSILON ); 528 mkxtion( eps, state ); 529 return link_machines( state, eps ); 530 } 531 } 532 533 534/* mkrep - make a replicated machine 535 * 536 * synopsis 537 * new = mkrep( mach, lb, ub ); 538 * 539 * new - a machine that matches whatever "mach" matched from "lb" 540 * number of times to "ub" number of times 541 * 542 * note 543 * if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach" 544 */ 545 546int mkrep( mach, lb, ub ) 547int mach, lb, ub; 548 { 549 int base_mach, tail, copy, i; 550 551 base_mach = copysingl( mach, lb - 1 ); 552 553 if ( ub == INFINITY ) 554 { 555 copy = dupmachine( mach ); 556 mach = link_machines( mach, 557 link_machines( base_mach, mkclos( copy ) ) ); 558 } 559 560 else 561 { 562 tail = mkstate( SYM_EPSILON ); 563 564 for ( i = lb; i < ub; ++i ) 565 { 566 copy = dupmachine( mach ); 567 tail = mkopt( link_machines( copy, tail ) ); 568 } 569 570 mach = link_machines( mach, link_machines( base_mach, tail ) ); 571 } 572 573 return mach; 574 } 575 576 577/* mkstate - create a state with a transition on a given symbol 578 * 579 * synopsis 580 * 581 * state = mkstate( sym ); 582 * 583 * state - a new state matching sym 584 * sym - the symbol the new state is to have an out-transition on 585 * 586 * note that this routine makes new states in ascending order through the 587 * state array (and increments LASTNFA accordingly). The routine DUPMACHINE 588 * relies on machines being made in ascending order and that they are 589 * CONTIGUOUS. Change it and you will have to rewrite DUPMACHINE (kludge 590 * that it admittedly is) 591 */ 592 593int mkstate( sym ) 594int sym; 595 { 596 if ( ++lastnfa >= current_mns ) 597 { 598 if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS ) 599 lerrif( 600 _( "input rules are too complicated (>= %d NFA states)" ), 601 current_mns ); 602 603 ++num_reallocs; 604 605 firstst = reallocate_integer_array( firstst, current_mns ); 606 lastst = reallocate_integer_array( lastst, current_mns ); 607 finalst = reallocate_integer_array( finalst, current_mns ); 608 transchar = reallocate_integer_array( transchar, current_mns ); 609 trans1 = reallocate_integer_array( trans1, current_mns ); 610 trans2 = reallocate_integer_array( trans2, current_mns ); 611 accptnum = reallocate_integer_array( accptnum, current_mns ); 612 assoc_rule = 613 reallocate_integer_array( assoc_rule, current_mns ); 614 state_type = 615 reallocate_integer_array( state_type, current_mns ); 616 } 617 618 firstst[lastnfa] = lastnfa; 619 finalst[lastnfa] = lastnfa; 620 lastst[lastnfa] = lastnfa; 621 transchar[lastnfa] = sym; 622 trans1[lastnfa] = NO_TRANSITION; 623 trans2[lastnfa] = NO_TRANSITION; 624 accptnum[lastnfa] = NIL; 625 assoc_rule[lastnfa] = num_rules; 626 state_type[lastnfa] = current_state_type; 627 628 /* Fix up equivalence classes base on this transition. Note that any 629 * character which has its own transition gets its own equivalence 630 * class. Thus only characters which are only in character classes 631 * have a chance at being in the same equivalence class. E.g. "a|b" 632 * puts 'a' and 'b' into two different equivalence classes. "[ab]" 633 * puts them in the same equivalence class (barring other differences 634 * elsewhere in the input). 635 */ 636 637 if ( sym < 0 ) 638 { 639 /* We don't have to update the equivalence classes since 640 * that was already done when the ccl was created for the 641 * first time. 642 */ 643 } 644 645 else if ( sym == SYM_EPSILON ) 646 ++numeps; 647 648 else 649 { 650 check_char( sym ); 651 652 if ( useecs ) 653 /* Map NUL's to csize. */ 654 mkechar( sym ? sym : csize, nextecm, ecgroup ); 655 } 656 657 return lastnfa; 658 } 659 660 661/* mkxtion - make a transition from one state to another 662 * 663 * synopsis 664 * 665 * mkxtion( statefrom, stateto ); 666 * 667 * statefrom - the state from which the transition is to be made 668 * stateto - the state to which the transition is to be made 669 */ 670 671void mkxtion( statefrom, stateto ) 672int statefrom, stateto; 673 { 674 if ( trans1[statefrom] == NO_TRANSITION ) 675 trans1[statefrom] = stateto; 676 677 else if ( (transchar[statefrom] != SYM_EPSILON) || 678 (trans2[statefrom] != NO_TRANSITION) ) 679 flexfatal( _( "found too many transitions in mkxtion()" ) ); 680 681 else 682 { /* second out-transition for an epsilon state */ 683 ++eps2; 684 trans2[statefrom] = stateto; 685 } 686 } 687 688/* new_rule - initialize for a new rule */ 689 690void new_rule() 691 { 692 if ( ++num_rules >= current_max_rules ) 693 { 694 ++num_reallocs; 695 current_max_rules += MAX_RULES_INCREMENT; 696 rule_type = reallocate_integer_array( rule_type, 697 current_max_rules ); 698 rule_linenum = reallocate_integer_array( rule_linenum, 699 current_max_rules ); 700 rule_useful = reallocate_integer_array( rule_useful, 701 current_max_rules ); 702 } 703 704 if ( num_rules > MAX_RULE ) 705 lerrif( _( "too many rules (> %d)!" ), MAX_RULE ); 706 707 rule_linenum[num_rules] = linenum; 708 rule_useful[num_rules] = false; 709 } 710