home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / flex254.zip / nfa.c < prev    next >
C/C++ Source or Header  |  1997-07-26  |  17KB  |  710 lines
  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: /home/daffy/u0/vern/flex/RCS/nfa.c,v 2.17 95/03/04 16:11:42 vern Exp $ */
  30.  
  31. #include "flexdef.h"
  32.  
  33.  
  34. /* declare functions that have forward references */
  35.  
  36. int dupmachine PROTO((int));
  37. void mkxtion PROTO((int, int));
  38.  
  39.  
  40. /* add_accept - add an accepting state to a machine
  41.  *
  42.  * accepting_number becomes mach's accepting number.
  43.  */
  44.  
  45. void add_accept( mach, accepting_number )
  46. int mach, accepting_number;
  47.     {
  48.     /* Hang the accepting number off an epsilon state.  if it is associated
  49.      * with a state that has a non-epsilon out-transition, then the state
  50.      * will accept BEFORE it makes that transition, i.e., one character
  51.      * too soon.
  52.      */
  53.  
  54.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  55.         accptnum[finalst[mach]] = accepting_number;
  56.  
  57.     else
  58.         {
  59.         int astate = mkstate( SYM_EPSILON );
  60.         accptnum[astate] = accepting_number;
  61.         (void) link_machines( mach, astate );
  62.         }
  63.     }
  64.  
  65.  
  66. /* copysingl - make a given number of copies of a singleton machine
  67.  *
  68.  * synopsis
  69.  *
  70.  *   newsng = copysingl( singl, num );
  71.  *
  72.  *     newsng - a new singleton composed of num copies of singl
  73.  *     singl  - a singleton machine
  74.  *     num    - the number of copies of singl to be present in newsng
  75.  */
  76.  
  77. int copysingl( singl, num )
  78. int singl, num;
  79.     {
  80.     int copy, i;
  81.  
  82.     copy = mkstate( SYM_EPSILON );
  83.  
  84.     for ( i = 1; i <= num; ++i )
  85.         copy = link_machines( copy, dupmachine( singl ) );
  86.  
  87.     return copy;
  88.     }
  89.  
  90.  
  91. /* dumpnfa - debugging routine to write out an nfa */
  92.  
  93. void dumpnfa( state1 )
  94. int state1;
  95.  
  96.     {
  97.     int sym, tsp1, tsp2, anum, ns;
  98.  
  99.     fprintf( stderr,
  100.     _( "\n\n********** beginning dump of nfa with start state %d\n" ),
  101.         state1 );
  102.  
  103.     /* We probably should loop starting at firstst[state1] and going to
  104.      * lastst[state1], but they're not maintained properly when we "or"
  105.      * all of the rules together.  So we use our knowledge that the machine
  106.      * starts at state 1 and ends at lastnfa.
  107.      */
  108.  
  109.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  110.     for ( ns = 1; ns <= lastnfa; ++ns )
  111.         {
  112.         fprintf( stderr, _( "state # %4d\t" ), ns );
  113.  
  114.         sym = transchar[ns];
  115.         tsp1 = trans1[ns];
  116.         tsp2 = trans2[ns];
  117.         anum = accptnum[ns];
  118.  
  119.         fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  120.  
  121.         if ( anum != NIL )
  122.             fprintf( stderr, "  [%d]", anum );
  123.  
  124.         fprintf( stderr, "\n" );
  125.         }
  126.  
  127.     fprintf( stderr, _( "********** end of dump\n" ) );
  128.     }
  129.  
  130.  
  131. /* dupmachine - make a duplicate of a given machine
  132.  *
  133.  * synopsis
  134.  *
  135.  *   copy = dupmachine( mach );
  136.  *
  137.  *     copy - holds duplicate of mach
  138.  *     mach - machine to be duplicated
  139.  *
  140.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  141.  * transition states values are adjusted so that the copy is self-contained,
  142.  * as the original should have been.
  143.  *
  144.  * also note that the original MUST be contiguous, with its low and high
  145.  * states accessible by the arrays firstst and lastst
  146.  */
  147.  
  148. int dupmachine( mach )
  149. int mach;
  150.     {
  151.     int i, init, state_offset;
  152.     int state = 0;
  153.     int last = lastst[mach];
  154.  
  155.     for ( i = firstst[mach]; i <= last; ++i )
  156.         {
  157.         state = mkstate( transchar[i] );
  158.  
  159.         if ( trans1[i] != NO_TRANSITION )
  160.             {
  161.             mkxtion( finalst[state], trans1[i] + state - i );
  162.  
  163.             if ( transchar[i] == SYM_EPSILON &&
  164.                  trans2[i] != NO_TRANSITION )
  165.                 mkxtion( finalst[state],
  166.                     trans2[i] + state - i );
  167.             }
  168.  
  169.         accptnum[state] = accptnum[i];
  170.         }
  171.  
  172.     if ( state == 0 )
  173.         flexfatal( _( "empty machine in dupmachine()" ) );
  174.  
  175.     state_offset = state - i + 1;
  176.  
  177.     init = mach + state_offset;
  178.     firstst[init] = firstst[mach] + state_offset;
  179.     finalst[init] = finalst[mach] + state_offset;
  180.     lastst[init] = lastst[mach] + state_offset;
  181.  
  182.     return init;
  183.     }
  184.  
  185.  
  186. /* finish_rule - finish up the processing for a rule
  187.  *
  188.  * An accepting number is added to the given machine.  If variable_trail_rule
  189.  * is true then the rule has trailing context and both the head and trail
  190.  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  191.  * the machine recognizes a pattern with trailing context and headcnt is
  192.  * the number of characters in the matched part of the pattern, or zero
  193.  * if the matched part has variable length.  trailcnt is the number of
  194.  * trailing context characters in the pattern, or zero if the trailing
  195.  * context has variable length.
  196.  */
  197.  
  198. void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  199. int mach, variable_trail_rule, headcnt, trailcnt;
  200.     {
  201.     char action_text[MAXLINE];
  202.  
  203.     add_accept( mach, num_rules );
  204.  
  205.     /* We did this in new_rule(), but it often gets the wrong
  206.      * number because we do it before we start parsing the current rule.
  207.      */
  208.     rule_linenum[num_rules] = linenum;
  209.  
  210.     /* If this is a continued action, then the line-number has already
  211.      * been updated, giving us the wrong number.
  212.      */
  213.     if ( continued_action )
  214.         --rule_linenum[num_rules];
  215.  
  216.     sprintf( action_text, "case %d:\n", num_rules );
  217.     add_action( action_text );
  218.  
  219.     if ( variable_trail_rule )
  220.         {
  221.         rule_type[num_rules] = RULE_VARIABLE;
  222.  
  223.         if ( performance_report > 0 )
  224.             fprintf( stderr,
  225.             _( "Variable trailing context rule at line %d\n" ),
  226.                 rule_linenum[num_rules] );
  227.  
  228.         variable_trailing_context_rules = true;
  229.         }
  230.  
  231.     else
  232.         {
  233.         rule_type[num_rules] = RULE_NORMAL;
  234.  
  235.         if ( headcnt > 0 || trailcnt > 0 )
  236.             {
  237.             /* Do trailing context magic to not match the trailing
  238.              * characters.
  239.              */
  240.             char *scanner_cp = "yy_c_buf_p = yy_cp";
  241.             char *scanner_bp = "yy_bp";
  242.  
  243.             add_action(
  244.     "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  245.  
  246.             if ( headcnt > 0 )
  247.                 {
  248.                 sprintf( action_text, "%s = %s + %d;\n",
  249.                 scanner_cp, scanner_bp, headcnt );
  250.                 add_action( action_text );
  251.                 }
  252.  
  253.             else
  254.                 {
  255.                 sprintf( action_text, "%s -= %d;\n",
  256.                     scanner_cp, trailcnt );
  257.                 add_action( action_text );
  258.                 }
  259.  
  260.             add_action(
  261.             "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  262.             }
  263.         }
  264.  
  265.     /* Okay, in the action code at this point yytext and yyleng have
  266.      * their proper final values for this rule, so here's the point
  267.      * to do any user action.  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.  
  293. int link_machines( first, last )
  294. int 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.  
  321. void mark_beginning_as_normal( mach )
  322. register 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.  
  367. int mkbranch( first, second )
  368. int 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.  
  395. int mkclos( state )
  396. int 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.  
  416. int mkopt( mach )
  417. int 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.  
  454. int mkor( first, second )
  455. int 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.  
  514. int mkposcl( state )
  515. int 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.  
  546. int mkrep( mach, lb, ub )
  547. int 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.  
  593. int mkstate( sym )
  594. int 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.  
  671. void mkxtion( statefrom, stateto )
  672. int 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.  
  690. void 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.