home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / FORTH / FLEX.ARC / NFA.C < prev    next >
C/C++ Source or Header  |  1988-10-09  |  14KB  |  576 lines
  1. /* nfa - NFA construction routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16.  
  17. /* add_accept - add an accepting state to a machine
  18.  *
  19.  * synopsis
  20.  *
  21.  *   add_accept( mach, headcnt, trailcnt );
  22.  *
  23.  * the global ACCNUM is incremented and the new value becomes mach's
  24.  * accepting number.  if headcnt or trailcnt is non-zero then the machine
  25.  * recognizes a pattern with trailing context.  headcnt is the number of
  26.  * characters in the matched part of the pattern, or zero if the matched
  27.  * part has variable length.  trailcnt is the number of trailing context
  28.  * characters in the pattern, or zero if the trailing context has variable
  29.  * length.
  30.  */
  31.  
  32. add_accept( mach, headcnt, trailcnt )
  33. int mach, headcnt, trailcnt;
  34.  
  35.     {
  36.     int astate;
  37.  
  38.     fprintf( temp_action_file, "case %d:\n", ++accnum );
  39.  
  40.     if ( headcnt > 0 || trailcnt > 0 )
  41.     { /* do trailing context magic to not match the trailing characters */
  42.     fprintf( temp_action_file,
  43.         "YY_DO_BEFORE_SCAN; /* undo effects of setting up yytext */\n" );
  44.  
  45.     if ( headcnt > 0 )
  46.         {
  47.         int head_offset = headcnt - 1;
  48.  
  49.         if ( fullspd || fulltbl )
  50.         /* with the fast skeleton, yy_c_buf_p points to the *next*
  51.          * character to scan, rather than the one that was last
  52.          * scanned
  53.          */
  54.         ++head_offset;
  55.  
  56.         if ( head_offset > 0 )
  57.         fprintf( temp_action_file, "yy_c_buf_p = yy_b_buf_p + %d;\n",
  58.              head_offset );
  59.  
  60.         else
  61.         fprintf( temp_action_file, "yy_c_buf_p = yy_b_buf_p;\n" );
  62.         }
  63.  
  64.     else
  65.         fprintf( temp_action_file, "yy_c_buf_p -= %d;\n", trailcnt );
  66.     
  67.     fprintf( temp_action_file, "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  68.     }
  69.  
  70.     line_directive_out( temp_action_file );
  71.  
  72.     /* hang the accepting number off an epsilon state.  if it is associated
  73.      * with a state that has a non-epsilon out-transition, then the state
  74.      * will accept BEFORE it makes that transition, i.e., one character
  75.      * too soon
  76.      */
  77.  
  78.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  79.     accptnum[finalst[mach]] = accnum;
  80.  
  81.     else
  82.     {
  83.     astate = mkstate( SYM_EPSILON );
  84.     accptnum[astate] = accnum;
  85.     mach = link_machines( mach, astate );
  86.     }
  87.     }
  88.  
  89.  
  90. /* copysingl - make a given number of copies of a singleton machine
  91.  *
  92.  * synopsis
  93.  *
  94.  *   newsng = copysingl( singl, num );
  95.  *
  96.  *     newsng - a new singleton composed of num copies of singl
  97.  *     singl  - a singleton machine
  98.  *     num    - the number of copies of singl to be present in newsng
  99.  */
  100.  
  101. int copysingl( singl, num )
  102. int singl, num;
  103.  
  104.     {
  105.     int copy, i;
  106.  
  107.     copy = mkstate( SYM_EPSILON );
  108.  
  109.     for ( i = 1; i <= num; ++i )
  110.     copy = link_machines( copy, dupmachine( singl ) );
  111.  
  112.     return ( copy );
  113.     }
  114.  
  115.  
  116. /* dumpnfa - debugging routine to write out an nfa
  117.  *
  118.  * synopsis
  119.  *    int state1;
  120.  *    dumpnfa( state1 );
  121.  */
  122.  
  123. dumpnfa( state1 )
  124. int state1;
  125.  
  126.     {
  127.     int sym, tsp1, tsp2, anum, ns;
  128.  
  129.     fprintf( stderr, "\n\n********** beginning dump of nfa with start state %d\n",
  130.          state1 );
  131.  
  132.     /* we probably should loop starting at firstst[state1] and going to
  133.      * lastst[state1], but they're not maintained properly when we "or"
  134.      * all of the rules together.  So we use our knowledge that the machine
  135.      * starts at state 1 and ends at lastnfa.
  136.      */
  137.  
  138.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  139.     for ( ns = 1; ns <= lastnfa; ++ns )
  140.     {
  141.     fprintf( stderr, "state # %4d\t", ns );
  142.  
  143.     sym = transchar[ns];
  144.     tsp1 = trans1[ns];
  145.     tsp2 = trans2[ns];
  146.     anum = accptnum[ns];
  147.  
  148.     fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  149.  
  150.     if ( anum != NIL )
  151.         fprintf( stderr, "  [%d]", anum );
  152.  
  153.     fprintf( stderr, "\n" );
  154.     }
  155.  
  156.     fprintf( stderr, "********** end of dump\n" );
  157.     }
  158.  
  159.  
  160. /* dupmachine - make a duplicate of a given machine
  161.  *
  162.  * synopsis
  163.  *
  164.  *   copy = dupmachine( mach );
  165.  *
  166.  *     copy - holds duplicate of mach
  167.  *     mach - machine to be duplicated
  168.  *
  169.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  170.  * transition states values are adjusted so that the copy is self-contained,
  171.  * as the original should have been.
  172.  *
  173.  * also note that the original MUST be contiguous, with its low and high
  174.  * states accessible by the arrays firstst and lastst
  175.  */
  176.  
  177. int dupmachine( mach )
  178. int mach;
  179.  
  180.     {
  181.     int i, state, init, last = lastst[mach], state_offset;
  182.  
  183.     for ( i = firstst[mach]; i <= last; ++i )
  184.     {
  185.     state = mkstate( transchar[i] );
  186.  
  187.     if ( trans1[i] != NO_TRANSITION )
  188.         {
  189.         mkxtion( finalst[state], trans1[i] + state - i );
  190.  
  191.         if ( transchar[i] == SYM_EPSILON && trans2[i] != NO_TRANSITION )
  192.         mkxtion( finalst[state], trans2[i] + state - i );
  193.         }
  194.  
  195.     accptnum[state] = accptnum[i];
  196.     }
  197.  
  198.     state_offset = state - i + 1;
  199.  
  200.     init = mach + state_offset;
  201.     firstst[init] = firstst[mach] + state_offset;
  202.     finalst[init] = finalst[mach] + state_offset;
  203.     lastst[init] = lastst[mach] + state_offset;
  204.  
  205.     return ( init );
  206.     }
  207.  
  208.  
  209. /* link_machines - connect two machines together
  210.  *
  211.  * synopsis
  212.  *
  213.  *   new = link_machines( first, last );
  214.  *
  215.  *     new    - a machine constructed by connecting first to last
  216.  *     first  - the machine whose successor is to be last
  217.  *     last   - the machine whose predecessor is to be first
  218.  *
  219.  * note: this routine concatenates the machine first with the machine
  220.  *  last to produce a machine new which will pattern-match first first
  221.  *  and then last, and will fail if either of the sub-patterns fails.
  222.  *  FIRST is set to new by the operation.  last is unmolested.
  223.  */
  224.  
  225. int link_machines( first, last )
  226. int first, last;
  227.  
  228.     {
  229.     if ( first == NIL )
  230.     return ( last );
  231.  
  232.     else if ( last == NIL )
  233.     return ( first );
  234.  
  235.     else
  236.     {
  237.     mkxtion( finalst[first], last );
  238.     finalst[first] = finalst[last];
  239.     lastst[first] = max( lastst[first], lastst[last] );
  240.     firstst[first] = min( firstst[first], firstst[last] );
  241.  
  242.     return ( first );
  243.     }
  244.     }
  245.  
  246.  
  247. /* mkbranch - make a machine that branches to two machines
  248.  *
  249.  * synopsis
  250.  *
  251.  *   branch = mkbranch( first, second );
  252.  *
  253.  *     branch - a machine which matches either first's pattern or second's
  254.  *     first, second - machines whose patterns are to be or'ed (the | operator)
  255.  *
  256.  * note that first and second are NEITHER destroyed by the operation.  Also,
  257.  * the resulting machine CANNOT be used with any other "mk" operation except
  258.  * more mkbranch's.  Compare with mkor()
  259.  */
  260.  
  261. int mkbranch( first, second )
  262. int first, second;
  263.  
  264.     {
  265.     int eps;
  266.  
  267.     if ( first == NO_TRANSITION )
  268.     return ( second );
  269.  
  270.     else if ( second == NO_TRANSITION )
  271.     return ( first );
  272.  
  273.     eps = mkstate( SYM_EPSILON );
  274.  
  275.     mkxtion( eps, first );
  276.     mkxtion( eps, second );
  277.  
  278.     return ( eps );
  279.     }
  280.  
  281.  
  282. /* mkclos - convert a machine into a closure
  283.  *
  284.  * synopsis
  285.  *   new = mkclos( state );
  286.  *
  287.  *     new - a new state which matches the closure of "state"
  288.  */
  289.  
  290. int mkclos( state )
  291. int state;
  292.  
  293.     {
  294.     return ( mkopt( mkposcl( state ) ) );
  295.     }
  296.  
  297.  
  298. /* mkopt - make a machine optional
  299.  *
  300.  * synopsis
  301.  *
  302.  *   new = mkopt( mach );
  303.  *
  304.  *     new  - a machine which optionally matches whatever mach matched
  305.  *     mach - the machine to make optional
  306.  *
  307.  * notes:
  308.  *     1. mach must be the last machine created
  309.  *     2. mach is destroyed by the call
  310.  */
  311.  
  312. int mkopt( mach )
  313. int mach;
  314.  
  315.     {
  316.     int eps;
  317.  
  318.     if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
  319.     {
  320.     eps = mkstate( SYM_EPSILON );
  321.     mach = link_machines( mach, eps );
  322.     }
  323.  
  324.     /* can't skimp on the following if FREE_EPSILON(mach) is true because
  325.      * some state interior to "mach" might point back to the beginning
  326.      * for a closure
  327.      */
  328.     eps = mkstate( SYM_EPSILON );
  329.     mach = link_machines( eps, mach );
  330.  
  331.     mkxtion( mach, finalst[mach] );
  332.  
  333.     return ( mach );
  334.     }
  335.  
  336.  
  337. /* mkor - make a machine that matches either one of two machines
  338.  *
  339.  * synopsis
  340.  *
  341.  *   new = mkor( first, second );
  342.  *
  343.  *     new - a machine which matches either first's pattern or second's
  344.  *     first, second - machines whose patterns are to be or'ed (the | operator)
  345.  *
  346.  * note that first and second are both destroyed by the operation
  347.  * the code is rather convoluted because an attempt is made to minimize
  348.  * the number of epsilon states needed
  349.  */
  350.  
  351. int mkor( first, second )
  352. int first, second;
  353.  
  354.     {
  355.     int eps, orend;
  356.  
  357.     if ( first == NIL )
  358.     return ( second );
  359.  
  360.     else if ( second == NIL )
  361.     return ( first );
  362.  
  363.     else
  364.     {
  365.     /* see comment in mkopt() about why we can't use the first state
  366.      * of "first" or "second" if they satisfy "FREE_EPSILON"
  367.      */
  368.     eps = mkstate( SYM_EPSILON );
  369.  
  370.     first = link_machines( eps, first );
  371.  
  372.     mkxtion( first, second );
  373.  
  374.     if ( SUPER_FREE_EPSILON(finalst[first]) &&
  375.          accptnum[finalst[first]] == NIL )
  376.         {
  377.         orend = finalst[first];
  378.         mkxtion( finalst[second], orend );
  379.         }
  380.  
  381.     else if ( SUPER_FREE_EPSILON(finalst[second]) &&
  382.           accptnum[finalst[second]] == NIL )
  383.         {
  384.         orend = finalst[second];
  385.         mkxtion( finalst[first], orend );
  386.         }
  387.  
  388.     else
  389.         {
  390.         eps = mkstate( SYM_EPSILON );
  391.  
  392.         first = link_machines( first, eps );
  393.         orend = finalst[first];
  394.  
  395.         mkxtion( finalst[second], orend );
  396.         }
  397.     }
  398.  
  399.     finalst[first] = orend;
  400.     return ( first );
  401.     }
  402.  
  403.  
  404. /* mkposcl - convert a machine into a positive closure
  405.  *
  406.  * synopsis
  407.  *   new = mkposcl( state );
  408.  *
  409.  *    new - a machine matching the positive closure of "state"
  410.  */
  411.  
  412. int mkposcl( state )
  413. int state;
  414.  
  415.     {
  416.     int eps;
  417.  
  418.     if ( SUPER_FREE_EPSILON(finalst[state]) )
  419.     {
  420.     mkxtion( finalst[state], state );
  421.     return ( state );
  422.     }
  423.  
  424.     else
  425.     {
  426.     eps = mkstate( SYM_EPSILON );
  427.     mkxtion( eps, state );
  428.     return ( link_machines( state, eps ) );
  429.     }
  430.     }
  431.  
  432.  
  433. /* mkrep - make a replicated machine
  434.  *
  435.  * synopsis
  436.  *   new = mkrep( mach, lb, ub );
  437.  *
  438.  *    new - a machine that matches whatever "mach" matched from "lb"
  439.  *          number of times to "ub" number of times
  440.  *
  441.  * note
  442.  *   if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
  443.  */
  444.  
  445. int mkrep( mach, lb, ub )
  446. int mach, lb, ub;
  447.  
  448.     {
  449.     int base, tail, copy, i;
  450.  
  451.     base = copysingl( mach, lb - 1 );
  452.  
  453.     if ( ub == INFINITY )
  454.     {
  455.     copy = dupmachine( mach );
  456.     mach = link_machines( mach, link_machines( base, mkclos( copy ) ) );
  457.     }
  458.  
  459.     else
  460.     {
  461.     tail = mkstate( SYM_EPSILON );
  462.  
  463.     for ( i = lb; i < ub; ++i )
  464.         {
  465.         copy = dupmachine( mach );
  466.         tail = mkopt( link_machines( copy, tail ) );
  467.         }
  468.  
  469.     mach = link_machines( mach, link_machines( base, tail ) );
  470.     }
  471.  
  472.     return ( mach );
  473.     }
  474.  
  475.  
  476. /* mkstate - create a state with a transition on a given symbol
  477.  *
  478.  * synopsis
  479.  *
  480.  *   state = mkstate( sym );
  481.  *
  482.  *     state - a new state matching sym
  483.  *     sym   - the symbol the new state is to have an out-transition on
  484.  *
  485.  * note that this routine makes new states in ascending order through the
  486.  * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
  487.  * relies on machines being made in ascending order and that they are
  488.  * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
  489.  * that it admittedly is)
  490.  */
  491.  
  492. int mkstate( sym )
  493. int sym;
  494.  
  495.     {
  496.     if ( ++lastnfa >= current_mns )
  497.     {
  498.     if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
  499.         lerrif( "input rules are too complicated (>= %d NFA states)",
  500.             current_mns );
  501.     
  502.     ++num_reallocs;
  503.  
  504.     transchar = reallocate_integer_array( transchar, current_mns );
  505.     trans1 = reallocate_integer_array( trans1, current_mns );
  506.     trans2 = reallocate_integer_array( trans2, current_mns );
  507.     accptnum = reallocate_integer_array( accptnum, current_mns );
  508.     firstst = reallocate_integer_array( firstst, current_mns );
  509.     finalst = reallocate_integer_array( finalst, current_mns );
  510.     lastst = reallocate_integer_array( lastst, current_mns );
  511.     }
  512.  
  513.     transchar[lastnfa] = sym;
  514.     trans1[lastnfa] = NO_TRANSITION;
  515.     trans2[lastnfa] = NO_TRANSITION;
  516.     accptnum[lastnfa] = NIL;
  517.     firstst[lastnfa] = lastnfa;
  518.     finalst[lastnfa] = lastnfa;
  519.     lastst[lastnfa] = lastnfa;
  520.  
  521.     /* fix up equivalence classes base on this transition.  Note that any
  522.      * character which has its own transition gets its own equivalence class.
  523.      * Thus only characters which are only in character classes have a chance
  524.      * at being in the same equivalence class.  E.g. "a|b" puts 'a' and 'b'
  525.      * into two different equivalence classes.  "[ab]" puts them in the same
  526.      * equivalence class (barring other differences elsewhere in the input).
  527.      */
  528.  
  529.     if ( sym < 0 )
  530.     {
  531.     /* we don't have to update the equivalence classes since that was
  532.      * already done when the ccl was created for the first time
  533.      */
  534.     }
  535.  
  536.     else if ( sym == SYM_EPSILON )
  537.     ++numeps;
  538.  
  539.     else
  540.     {
  541.     if ( useecs )
  542.         mkechar( sym, nextecm, ecgroup );
  543.     }
  544.  
  545.     return ( lastnfa );
  546.     }
  547.  
  548.  
  549. /* mkxtion - make a transition from one state to another
  550.  *
  551.  * synopsis
  552.  *
  553.  *   mkxtion( statefrom, stateto );
  554.  *
  555.  *     statefrom - the state from which the transition is to be made
  556.  *     stateto   - the state to which the transition is to be made
  557.  */
  558.  
  559. mkxtion( statefrom, stateto )
  560. int statefrom, stateto;
  561.  
  562.     {
  563.     if ( trans1[statefrom] == NO_TRANSITION )
  564.     trans1[statefrom] = stateto;
  565.  
  566.     else if ( (transchar[statefrom] != SYM_EPSILON) ||
  567.           (trans2[statefrom] != NO_TRANSITION) )
  568.     flexfatal( "found too many transitions in mkxtion()" );
  569.  
  570.     else
  571.     { /* second out-transition for an epsilon state */
  572.     ++eps2;
  573.     trans2[statefrom] = stateto;
  574.     }
  575.     }
  576.