home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 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.