usr.bin/lex/nfa.c

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