contrib/flex/src/nfa.c

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