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