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