home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume14 / flex / part05 / tblcmp.c
Encoding:
C/C++ Source or Header  |  1988-05-02  |  38.4 KB  |  1,594 lines
  1. /* tblcmp - table compression 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. /* bldtbl - build table entries for dfa state
  18.  *
  19.  * synopsis
  20.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  21.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  22.  *
  23.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  24.  * gives the number of the state to enter for a given equivalence class.
  25.  * totaltrans is the total number of transitions out of the state.  Comstate
  26.  * is that state which is the destination of the most transitions out of State.
  27.  * Comfreq is how many transitions there are out of State to Comstate.
  28.  *
  29.  * A note on terminology:
  30.  *    "protos" are transition tables which have a high probability of
  31.  * either being redundant (a state processed later will have an identical
  32.  * transition table) or nearly redundant (a state processed later will have
  33.  * many of the same out-transitions).  A "most recently used" queue of
  34.  * protos is kept around with the hope that most states will find a proto
  35.  * which is similar enough to be usable, and therefore compacting the
  36.  * output tables.
  37.  *    "templates" are a special type of proto.  If a transition table is
  38.  * homogeneous or nearly homogeneous (all transitions go to the same
  39.  * destination) then the odds are good that future states will also go
  40.  * to the same destination state on basically the same character set.
  41.  * These homogeneous states are so common when dealing with large rule
  42.  * sets that they merit special attention.  If the transition table were
  43.  * simply made into a proto, then (typically) each subsequent, similar
  44.  * state will differ from the proto for two out-transitions.  One of these
  45.  * out-transitions will be that character on which the proto does not go
  46.  * to the common destination, and one will be that character on which the
  47.  * state does not go to the common destination.  Templates, on the other
  48.  * hand, go to the common state on EVERY transition character, and therefore
  49.  * cost only one difference.
  50.  */
  51.  
  52. bldtbl( state, statenum, totaltrans, comstate, comfreq )
  53. int state[], statenum, totaltrans, comstate, comfreq;
  54.  
  55.     {
  56.     int extptr, extrct[2][CSIZE + 1];
  57.     int mindiff, minprot, i, d;
  58.     int checkcom;
  59.  
  60.     /* If extptr is 0 then the first array of extrct holds the result of the
  61.      * "best difference" to date, which is those transitions which occur in
  62.      * "state" but not in the proto which, to date, has the fewest differences
  63.      * between itself and "state".  If extptr is 1 then the second array of
  64.      * extrct hold the best difference.  The two arrays are toggled
  65.      * between so that the best difference to date can be kept around and
  66.      * also a difference just created by checking against a candidate "best"
  67.      * proto.
  68.      */
  69.  
  70.     extptr = 0;
  71.  
  72.     /* if the state has too few out-transitions, don't bother trying to
  73.      * compact its tables
  74.      */
  75.  
  76.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  77.     mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  78.  
  79.     else
  80.     {
  81.     /* checkcom is true if we should only check "state" against
  82.      * protos which have the same "comstate" value
  83.      */
  84.  
  85.     checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  86.  
  87.     minprot = firstprot;
  88.     mindiff = totaltrans;
  89.  
  90.     if ( checkcom )
  91.         {
  92.         /* find first proto which has the same "comstate" */
  93.         for ( i = firstprot; i != NIL; i = protnext[i] )
  94.         if ( protcomst[i] == comstate )
  95.             {
  96.             minprot = i;
  97.             mindiff = tbldiff( state, minprot, extrct[extptr] );
  98.             break;
  99.             }
  100.         }
  101.  
  102.     else
  103.         {
  104.         /* since we've decided that the most common destination out
  105.          * of "state" does not occur with a high enough frequency,
  106.          * we set the "comstate" to zero, assuring that if this state
  107.          * is entered into the proto list, it will not be considered
  108.          * a template.
  109.          */
  110.         comstate = 0;
  111.  
  112.         if ( firstprot != NIL )
  113.         {
  114.         minprot = firstprot;
  115.         mindiff = tbldiff( state, minprot, extrct[extptr] );
  116.         }
  117.         }
  118.  
  119.     /* we now have the first interesting proto in "minprot".  If
  120.      * it matches within the tolerances set for the first proto,
  121.      * we don't want to bother scanning the rest of the proto list
  122.      * to see if we have any other reasonable matches.
  123.      */
  124.  
  125.     if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  126.         { /* not a good enough match.  Scan the rest of the protos */
  127.         for ( i = minprot; i != NIL; i = protnext[i] )
  128.         {
  129.         d = tbldiff( state, i, extrct[1 - extptr] );
  130.         if ( d < mindiff )
  131.             {
  132.             extptr = 1 - extptr;
  133.             mindiff = d;
  134.             minprot = i;
  135.             }
  136.         }
  137.         }
  138.  
  139.     /* check if the proto we've decided on as our best bet is close
  140.      * enough to the state we want to match to be usable
  141.      */
  142.  
  143.     if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  144.         {
  145.         /* no good.  If the state is homogeneous enough, we make a
  146.          * template out of it.  Otherwise, we make a proto.
  147.          */
  148.  
  149.         if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  150.         mktemplate( state, statenum, comstate );
  151.  
  152.         else
  153.         {
  154.         mkprot( state, statenum, comstate );
  155.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  156.         }
  157.         }
  158.  
  159.     else
  160.         { /* use the proto */
  161.         mkentry( extrct[extptr], numecs, statenum,
  162.              prottbl[minprot], mindiff );
  163.  
  164.         /* if this state was sufficiently different from the proto
  165.          * we built it from, make it, too, a proto
  166.          */
  167.  
  168.         if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  169.         mkprot( state, statenum, comstate );
  170.  
  171.         /* since mkprot added a new proto to the proto queue, it's possible
  172.          * that "minprot" is no longer on the proto queue (if it happened
  173.          * to have been the last entry, it would have been bumped off).
  174.          * If it's not there, then the new proto took its physical place
  175.          * (though logically the new proto is at the beginning of the
  176.          * queue), so in that case the following call will do nothing.
  177.          */
  178.  
  179.         mv2front( minprot );
  180.         }
  181.     }
  182.     }
  183.  
  184.  
  185. /* cmptmps - compress template table entries
  186.  *
  187.  * synopsis
  188.  *    cmptmps();
  189.  *
  190.  *  template tables are compressed by using the 'template equivalence
  191.  *  classes', which are collections of transition character equivalence
  192.  *  classes which always appear together in templates - really meta-equivalence
  193.  *  classes.  until this point, the tables for templates have been stored
  194.  *  up at the top end of the nxt array; they will now be compressed and have
  195.  *  table entries made for them.
  196.  */
  197.  
  198. cmptmps()
  199.  
  200.     {
  201.     int tmpstorage[CSIZE + 1];
  202.     register int *tmp = tmpstorage, i, j;
  203.     int totaltrans, trans;
  204.  
  205.     peakpairs = numtemps * numecs + tblend;
  206.  
  207.     if ( usemecs )
  208.     {
  209.     /* create equivalence classes base on data gathered on template
  210.      * transitions
  211.      */
  212.  
  213.     nummecs = cre8ecs( tecfwd, tecbck, numecs );
  214.     }
  215.     
  216.     else
  217.     nummecs = numecs;
  218.  
  219.     if ( lastdfa + numtemps + 1 >= current_max_dfas )
  220.     increase_max_dfas();
  221.  
  222.     /* loop through each template */
  223.  
  224.     for ( i = 1; i <= numtemps; ++i )
  225.     {
  226.     totaltrans = 0;    /* number of non-jam transitions out of this template */
  227.  
  228.     for ( j = 1; j <= numecs; ++j )
  229.         {
  230.         trans = tnxt[numecs * i + j];
  231.  
  232.         if ( usemecs )
  233.         {
  234.         /* the absolute value of tecbck is the meta-equivalence class
  235.          * of a given equivalence class, as set up by cre8ecs
  236.          */
  237.         if ( tecbck[j] > 0 )
  238.             {
  239.             tmp[tecbck[j]] = trans;
  240.  
  241.             if ( trans > 0 )
  242.             ++totaltrans;
  243.             }
  244.         }
  245.  
  246.         else
  247.         {
  248.         tmp[j] = trans;
  249.  
  250.         if ( trans > 0 )
  251.             ++totaltrans;
  252.         }
  253.         }
  254.  
  255.     /* it is assumed (in a rather subtle way) in the skeleton that
  256.      * if we're using meta-equivalence classes, the def[] entry for
  257.      * all templates is the jam template, i.e., templates never default
  258.      * to other non-jam table entries (e.g., another template)
  259.      */
  260.  
  261.     /* leave room for the jam-state after the last real state */
  262.     mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  263.     }
  264.     }
  265.  
  266.  
  267.  
  268. /* expand_nxt_chk - expand the next check arrays */
  269.  
  270. expand_nxt_chk()
  271.  
  272.     {
  273.     register int old_max = current_max_xpairs;
  274.  
  275.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  276.  
  277.     ++num_reallocs;
  278.  
  279.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  280.     chk = reallocate_integer_array( chk, current_max_xpairs );
  281.  
  282.     bzero( (char *) (chk + old_max),
  283.        MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  284.     }
  285.  
  286.  
  287. /* find_table_space - finds a space in the table for a state to be placed
  288.  *
  289.  * synopsis
  290.  *     int *state, numtrans, block_start;
  291.  *     int find_table_space();
  292.  *
  293.  *     block_start = find_table_space( state, numtrans );
  294.  *
  295.  * State is the state to be added to the full speed transition table.
  296.  * Numtrans is the number of out-transitions for the state.
  297.  *
  298.  * find_table_space() returns the position of the start of the first block (in
  299.  * chk) able to accommodate the state
  300.  *
  301.  * In determining if a state will or will not fit, find_table_space() must take
  302.  * into account the fact that an end-of-buffer state will be added at [0],
  303.  * and an action number will be added in [-1].
  304.  */
  305.  
  306. int find_table_space( state, numtrans )
  307. int *state, numtrans;
  308.     
  309.     {
  310.     /* firstfree is the position of the first possible occurrence of two
  311.      * consecutive unused records in the chk and nxt arrays
  312.      */
  313.     register int i;
  314.     register int *state_ptr, *chk_ptr;
  315.     register int *ptr_to_last_entry_in_state;
  316.  
  317.     /* if there are too many out-transitions, put the state at the end of
  318.      * nxt and chk
  319.      */
  320.     if ( numtrans > MAX_XTIONS_FOR_FULL_INTERIOR_FIT )
  321.     {
  322.     /* if table is empty, return the first available spot in chk/nxt,
  323.      * which should be 1
  324.      */
  325.     if ( tblend < 2 )
  326.         return ( 1 );
  327.  
  328.     i = tblend - numecs;    /* start searching for table space near the
  329.                  * end of chk/nxt arrays
  330.                  */
  331.     }
  332.  
  333.     else
  334.     i = firstfree;        /* start searching for table space from the
  335.                  * beginning (skipping only the elements
  336.                  * which will definitely not hold the new
  337.                  * state)
  338.                  */
  339.  
  340.     while ( 1 )        /* loops until a space is found */
  341.     {
  342.     if ( i + numecs > current_max_xpairs )
  343.         expand_nxt_chk();
  344.  
  345.     /* loops until space for end-of-buffer and action number are found */
  346.     while ( 1 )
  347.         {
  348.         if ( chk[i - 1] == 0 )    /* check for action number space */
  349.         {
  350.         if ( chk[i] == 0 )    /* check for end-of-buffer space */
  351.             break;
  352.  
  353.         else
  354.             i += 2;    /* since i != 0, there is no use checking to
  355.                  * see if (++i) - 1 == 0, because that's the
  356.                  * same as i == 0, so we skip a space
  357.                  */
  358.         }
  359.  
  360.         else
  361.         ++i;
  362.  
  363.         if ( i + numecs > current_max_xpairs )
  364.         expand_nxt_chk();
  365.         }
  366.  
  367.     /* if we started search from the beginning, store the new firstfree for
  368.      * the next call of find_table_space()
  369.      */
  370.     if ( numtrans <= MAX_XTIONS_FOR_FULL_INTERIOR_FIT )
  371.         firstfree = i + 1;
  372.  
  373.     /* check to see if all elements in chk (and therefore nxt) that are
  374.      * needed for the new state have not yet been taken
  375.      */
  376.  
  377.     state_ptr = &state[1];
  378.     ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  379.  
  380.     for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  381.           ++chk_ptr )
  382.         if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  383.         break;
  384.  
  385.     if ( chk_ptr == ptr_to_last_entry_in_state )
  386.         return ( i );
  387.  
  388.     else
  389.         ++i;
  390.     }
  391.     }
  392.  
  393.  
  394. /* genctbl - generates full speed compressed transition table
  395.  *
  396.  * synopsis
  397.  *     genctbl();
  398.  */
  399.  
  400. genctbl()
  401.  
  402.     {
  403.     register int i;
  404.  
  405.     /* table of verify for transition and offset to next state */
  406.     printf( "static struct yy_trans_info yy_transition[%d] =\n",
  407.         tblend + numecs + 1 );
  408.     printf( "    {\n" );
  409.     
  410.     /* We want the transition to be represented as the offset to the
  411.      * next state, not the actual state number, which is what it currently is.
  412.      * The offset is base[nxt[i]] - base[chk[i]].  That's just the
  413.      * difference between the starting points of the two involved states
  414.      * (to - from).
  415.      *
  416.      * first, though, we need to find some way to put in our end-of-buffer
  417.      * flags and states.  We do this by making a state with absolutely no
  418.      * transitions.  We put it at the end of the table.
  419.      */
  420.     /* at this point, we're guaranteed that there's enough room in nxt[]
  421.      * and chk[] to hold tblend + numecs entries.  We need just two slots.
  422.      * One for the action and one for the end-of-buffer transition.  We
  423.      * now *assume* that we're guaranteed the only character we'll try to
  424.      * index this nxt/chk pair with is EOB, i.e., 0, so we don't have to
  425.      * make sure there's room for jam entries for other characters.
  426.      */
  427.  
  428.     base[lastdfa + 1] = tblend + 2;
  429.     nxt[tblend + 1] = END_OF_BUFFER_ACTION;
  430.     chk[tblend + 1] = numecs + 1;
  431.     chk[tblend + 2] = 1; /* anything but EOB */
  432.     nxt[tblend + 2] = 0; /* so that "make test" won't show arb. differences */
  433.  
  434.     /* make sure every state has a end-of-buffer transition and an action # */
  435.     for ( i = 0; i <= lastdfa; ++i )
  436.     {
  437.     chk[base[i]] = EOB_POSITION;
  438.     chk[base[i] - 1] = ACTION_POSITION;
  439.     nxt[base[i] - 1] = dfaacc[i].dfaacc_state;    /* action number */
  440.     }
  441.  
  442.     for ( i = 0; i <= lastsc * 2; ++i )
  443.     nxt[base[i] - 1] = DEFAULT_ACTION;
  444.  
  445.     dataline = 0;
  446.     datapos = 0;
  447.  
  448.     for ( i = 0; i <= tblend; ++i )
  449.     {
  450.     if ( chk[i] == EOB_POSITION )
  451.         transition_struct_out( 0, base[lastdfa + 1] - i );
  452.  
  453.     else if ( chk[i] == ACTION_POSITION )
  454.         transition_struct_out( 0, nxt[i] );
  455.  
  456.     else if ( chk[i] > numecs || chk[i] == 0 )
  457.         transition_struct_out( 0, 0 );        /* unused slot */
  458.  
  459.     else    /* verify, transition */
  460.         transition_struct_out( chk[i], base[nxt[i]] - (i - chk[i]) );
  461.     }
  462.  
  463.  
  464.     /* here's the final, end-of-buffer state */
  465.     transition_struct_out( chk[tblend + 1], nxt[tblend + 1] );
  466.     transition_struct_out( chk[tblend + 2], nxt[tblend + 2] );
  467.  
  468.     printf( "    };\n" );
  469.     printf( "\n" );
  470.  
  471.     /* table of pointers to start states */
  472.     printf( "static struct yy_trans_info *yy_state_ptr[%d] =\n",
  473.     lastsc * 2 + 1 );
  474.     printf( "    {\n" );
  475.  
  476.     for ( i = 0; i <= lastsc * 2; ++i )
  477.     printf( "    &yy_transition[%d],\n", base[i] );
  478.  
  479.     printf( "    };\n" );
  480.  
  481.     if ( useecs )
  482.     genecs();
  483.     }
  484.  
  485.  
  486. /* gentabs - generate data statements for the transition tables
  487.  *
  488.  * synopsis
  489.  *    gentabs();
  490.  */
  491.  
  492. gentabs()
  493.  
  494.     {
  495.     int i, j, k, *accset, nacc, *acc_array;
  496.     char clower();
  497.  
  498.     /* *everything* is done in terms of arrays starting at 1, so provide
  499.      * a null entry for the zero element of all FTL arrays
  500.      */
  501.     static char ftl_long_decl[] = "static long int %c[%d] =\n    {   0,\n";
  502.     static char ftl_short_decl[] = "static short int %c[%d] =\n    {   0,\n";
  503.     static char ftl_char_decl[] = "static char %c[%d] =\n    {   0,\n";
  504.  
  505.     acc_array = allocate_integer_array( current_max_dfas );
  506.     nummt = 0;
  507.  
  508.     if ( fulltbl )
  509.     jambase = lastdfa + 1;    /* home of "jam" pseudo-state */
  510.  
  511.     printf( "#define YY_JAM %d\n", jamstate );
  512.     printf( "#define YY_JAM_BASE %d\n", jambase );
  513.  
  514.     if ( usemecs )
  515.     printf( "#define YY_TEMPLATE %d\n", lastdfa + 2 );
  516.  
  517.     if ( reject )
  518.     {
  519.     /* write out accepting list and pointer list
  520.      * first we generate the ACCEPT array.  In the process, we compute
  521.      * the indices that will go into the ALIST array, and save the
  522.      * indices in the dfaacc array
  523.      */
  524.  
  525.     printf( accnum > 127 ? ftl_short_decl : ftl_char_decl,
  526.         ACCEPT, max( numas, 1 ) + 1 );
  527.  
  528.     j = 1;    /* index into ACCEPT array */
  529.  
  530.     for ( i = 1; i <= lastdfa; ++i )
  531.         {
  532.         acc_array[i] = j;
  533.  
  534.         if ( accsiz[i] != 0 )
  535.         {
  536.         accset = dfaacc[i].dfaacc_set;
  537.         nacc = accsiz[i];
  538.  
  539.         if ( trace )
  540.             fprintf( stderr, "state # %d accepts: ", i );
  541.  
  542.         for ( k = 1; k <= nacc; ++k )
  543.             {
  544.             ++j;
  545.             mkdata( accset[k] );
  546.  
  547.             if ( trace )
  548.             {
  549.             fprintf( stderr, "[%d]", accset[k] );
  550.  
  551.             if ( k < nacc )
  552.                 fputs( ", ", stderr );
  553.             else
  554.                 putc( '\n', stderr );
  555.             }
  556.             }
  557.         }
  558.         }
  559.  
  560.     /* add accepting number for the "jam" state */
  561.     acc_array[i] = j;
  562.  
  563.     dataend();
  564.     }
  565.     
  566.     else
  567.     {
  568.     for ( i = 1; i <= lastdfa; ++i )
  569.         acc_array[i] = dfaacc[i].dfaacc_state;
  570.     
  571.     acc_array[i] = 0; /* add (null) accepting number for jam state */
  572.     }
  573.  
  574.     /* spit out ALIST array.  If we're doing "reject", it'll be pointers
  575.      * into the ACCEPT array.  Otherwise it's actual accepting numbers.
  576.      * In either case, we just dump the numbers.
  577.      */
  578.  
  579.     /* "lastdfa + 2" is the size of ALIST; includes room for FTL arrays
  580.      * beginning at 0 and for "jam" state
  581.      */
  582.     k = lastdfa + 2;
  583.  
  584.     if ( reject )
  585.     /* we put a "cap" on the table associating lists of accepting
  586.      * numbers with state numbers.  This is needed because we tell
  587.      * where the end of an accepting list is by looking at where
  588.      * the list for the next state starts.
  589.      */
  590.     ++k;
  591.  
  592.     printf( ((reject && numas > 126) || accnum > 127) ?
  593.         ftl_short_decl : ftl_char_decl, ALIST, k );
  594.  
  595.     /* set up default actions */
  596.     for ( i = 1; i <= lastsc * 2; ++i )
  597.     acc_array[i] = DEFAULT_ACTION;
  598.  
  599.     acc_array[end_of_buffer_state] = END_OF_BUFFER_ACTION;
  600.  
  601.     for ( i = 1; i <= lastdfa; ++i )
  602.     {
  603.     mkdata( acc_array[i] );
  604.  
  605.     if ( ! reject && trace && acc_array[i] )
  606.         fprintf( stderr, "state # %d accepts: [%d]\n", i, acc_array[i] );
  607.     }
  608.  
  609.     /* add entry for "jam" state */
  610.     mkdata( acc_array[i] );
  611.  
  612.     if ( reject )
  613.     /* add "cap" for the list */
  614.     mkdata( acc_array[i] );
  615.  
  616.     dataend();
  617.  
  618.     if ( useecs )
  619.     genecs();
  620.  
  621.     if ( usemecs )
  622.     {
  623.     /* write out meta-equivalence classes (used to index templates with) */
  624.  
  625.     if ( trace )
  626.         fputs( "\n\nMeta-Equivalence Classes:\n", stderr );
  627.  
  628.     printf( ftl_char_decl, MATCHARRAY, numecs + 1 );
  629.  
  630.     for ( i = 1; i <= numecs; ++i )
  631.         {
  632.         if ( trace )
  633.         fprintf( stderr, "%d = %d\n", i, abs( tecbck[i] ) );
  634.  
  635.         mkdata( abs( tecbck[i] ) );
  636.         }
  637.  
  638.     dataend();
  639.     }
  640.  
  641.     if ( ! fulltbl )
  642.     {
  643.     int total_states = lastdfa + numtemps;
  644.  
  645.     printf( tblend > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  646.         BASEARRAY, total_states + 1 );
  647.  
  648.     for ( i = 1; i <= lastdfa; ++i )
  649.         {
  650.         register int d = def[i];
  651.  
  652.         if ( base[i] == JAMSTATE )
  653.         base[i] = jambase;
  654.  
  655.         if ( d == JAMSTATE )
  656.         def[i] = jamstate;
  657.  
  658.         else if ( d < 0 )
  659.         {
  660.         /* template reference */
  661.         ++tmpuses;
  662.         def[i] = lastdfa - d + 1;
  663.         }
  664.  
  665.         mkdata( base[i] );
  666.         }
  667.  
  668.     /* generate jam state's base index */
  669.     mkdata( base[i] );
  670.  
  671.     for ( ++i /* skip jam state */; i <= total_states; ++i )
  672.         {
  673.         mkdata( base[i] );
  674.         def[i] = jamstate;
  675.         }
  676.  
  677.     dataend();
  678.  
  679.     printf( tblend > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  680.         DEFARRAY, total_states + 1 );
  681.  
  682.     for ( i = 1; i <= total_states; ++i )
  683.         mkdata( def[i] );
  684.  
  685.     dataend();
  686.  
  687.     printf( lastdfa > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  688.         NEXTARRAY, tblend + 1 );
  689.  
  690.     for ( i = 1; i <= tblend; ++i )
  691.         {
  692.         if ( nxt[i] == 0 || chk[i] == 0 )
  693.         nxt[i] = jamstate;    /* new state is the JAM state */
  694.  
  695.         mkdata( nxt[i] );
  696.         }
  697.  
  698.     dataend();
  699.  
  700.     printf( lastdfa > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  701.         CHECKARRAY, tblend + 1 );
  702.  
  703.     for ( i = 1; i <= tblend; ++i )
  704.         {
  705.         if ( chk[i] == 0 )
  706.         ++nummt;
  707.  
  708.         mkdata( chk[i] );
  709.         }
  710.  
  711.     dataend();
  712.     }
  713.     }
  714.  
  715.  
  716. /* generate equivalence-class tables */
  717.  
  718. genecs()
  719.  
  720.     {
  721.     register int i, j;
  722.     static char ftl_char_decl[] = "static char %c[%d] =\n    {   0,\n";
  723.     int numrows;
  724.  
  725.     printf( ftl_char_decl, ECARRAY, CSIZE + 1 );
  726.  
  727.     for ( i = 1; i <= CSIZE; ++i )
  728.     {
  729.     if ( caseins && (i >= 'A') && (i <= 'Z') )
  730.         ecgroup[i] = ecgroup[clower( i )];
  731.  
  732.     ecgroup[i] = abs( ecgroup[i] );
  733.     mkdata( ecgroup[i] );
  734.     }
  735.  
  736.     dataend();
  737.  
  738.     if ( trace )
  739.     {
  740.     fputs( "\n\nEquivalence Classes:\n\n", stderr );
  741.  
  742.     numrows = (CSIZE + 1) / 8;
  743.  
  744.     for ( j = 1; j <= numrows; ++j )
  745.         {
  746.         for ( i = j; i <= CSIZE; i = i + numrows )
  747.         {
  748.         if ( i >= 1 && i <= 31 )
  749.             fprintf( stderr, "^%c = %-2d",
  750.                  'A' + i - 1, ecgroup[i] );
  751.  
  752.         else if ( i >= 32 && i <= 126 )
  753.             fprintf( stderr, " %c = %-2d", i, ecgroup[i] );
  754.  
  755.         else if ( i == 127 )
  756.             fprintf( stderr, "^@ = %-2d", ecgroup[i] );
  757.  
  758.         else
  759.             fprintf( stderr, "\nSomething Weird: %d = %d\n", i,
  760.                  ecgroup[i] );
  761.  
  762.         putc( '\t', stderr );
  763.         }
  764.  
  765.         putc( '\n', stderr );
  766.         }
  767.     }
  768.     }
  769.  
  770.  
  771. /* inittbl - initialize transition tables
  772.  *
  773.  * synopsis
  774.  *   inittbl();
  775.  *
  776.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  777.  * all "chk" entries to be zero.  Note that templates are built in their
  778.  * own tbase/tdef tables.  They are shifted down to be contiguous
  779.  * with the non-template entries during table generation.
  780.  */
  781. inittbl()
  782.  
  783.     {
  784.     register int i;
  785.  
  786.     bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  787.  
  788.     tblend = 0;
  789.     firstfree = tblend + 1;
  790.     numtemps = 0;
  791.  
  792.     if ( usemecs )
  793.     {
  794.     /* set up doubly-linked meta-equivalence classes
  795.      * these are sets of equivalence classes which all have identical
  796.      * transitions out of TEMPLATES
  797.      */
  798.  
  799.     tecbck[1] = NIL;
  800.  
  801.     for ( i = 2; i <= numecs; ++i )
  802.         {
  803.         tecbck[i] = i - 1;
  804.         tecfwd[i - 1] = i;
  805.         }
  806.  
  807.     tecfwd[numecs] = NIL;
  808.     }
  809.     }
  810.  
  811.  
  812. /* make_tables - generate transition tables
  813.  *
  814.  * synopsis
  815.  *     make_tables();
  816.  *
  817.  * Generates transition tables and finishes generating output file
  818.  */
  819.  
  820. make_tables()
  821.  
  822.     {
  823.     if ( fullspd )
  824.     { /* need to define YY_TRANS_OFFSET_TYPE as a size large
  825.        * enough to hold the biggest offset
  826.        */
  827.     int total_table_size = tblend + numecs + 1;
  828.  
  829.     printf( "#define YY_TRANS_OFFSET_TYPE %s\n",
  830.         total_table_size > MAX_SHORT ? "long" : "short" );
  831.     }
  832.     
  833.     if ( fullspd || fulltbl )
  834.     skelout();
  835.  
  836.     /* compute the tables and copy them to output file */
  837.     if ( fullspd )
  838.     genctbl();
  839.  
  840.     else
  841.     gentabs();
  842.  
  843.     skelout();
  844.  
  845.     (void) fclose( temp_action_file );
  846.     temp_action_file = fopen( action_file_name, "r" );
  847.  
  848.     /* copy prolog from action_file to output file */
  849.     action_out();
  850.  
  851.     skelout();
  852.  
  853.     /* copy actions from action_file to output file */
  854.     action_out();
  855.  
  856.     skelout();
  857.  
  858.     /* copy remainder of input to output */
  859.  
  860.     line_directive_out( stdout );
  861.     (void) flexscan(); /* copy remainder of input to output */
  862.     }
  863.  
  864.  
  865. /* mkdeftbl - make the default, "jam" table entries
  866.  *
  867.  * synopsis
  868.  *   mkdeftbl();
  869.  */
  870.  
  871. mkdeftbl()
  872.  
  873.     {
  874.     int i;
  875.  
  876.     jamstate = lastdfa + 1;
  877.  
  878.     if ( tblend + numecs > current_max_xpairs )
  879.     expand_nxt_chk();
  880.  
  881.     for ( i = 1; i <= numecs; ++i )
  882.     {
  883.     nxt[tblend + i] = 0;
  884.     chk[tblend + i] = jamstate;
  885.     }
  886.  
  887.     jambase = tblend;
  888.  
  889.     base[jamstate] = jambase;
  890.  
  891.     /* should generate a run-time array bounds check if
  892.      * ever used as a default
  893.      */
  894.     def[jamstate] = BAD_SUBSCRIPT;
  895.  
  896.     tblend += numecs;
  897.     ++numtemps;
  898.     }
  899.  
  900.  
  901. /* mkentry - create base/def and nxt/chk entries for transition array
  902.  *
  903.  * synopsis
  904.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  905.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  906.  *
  907.  * "state" is a transition array "numchars" characters in size, "statenum"
  908.  * is the offset to be used into the base/def tables, and "deflink" is the
  909.  * entry to put in the "def" table entry.  If "deflink" is equal to
  910.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  911.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  912.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  913.  * marking transitions to "SAME_TRANS" are treated as though they will be
  914.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  915.  * number of transitions out of the state.  If it is below a certain threshold,
  916.  * the tables are searched for an interior spot that will accommodate the
  917.  * state array.
  918.  */
  919.  
  920. mkentry( state, numchars, statenum, deflink, totaltrans )
  921. register int *state;
  922. int numchars, statenum, deflink, totaltrans;
  923.  
  924.     {
  925.     register int minec, maxec, i, baseaddr;
  926.     int tblbase, tbllast;
  927.  
  928.     if ( totaltrans == 0 )
  929.     { /* there are no out-transitions */
  930.     if ( deflink == JAMSTATE )
  931.         base[statenum] = JAMSTATE;
  932.     else
  933.         base[statenum] = 0;
  934.  
  935.     def[statenum] = deflink;
  936.     return;
  937.     }
  938.  
  939.     for ( minec = 1; minec <= numchars; ++minec )
  940.     {
  941.     if ( state[minec] != SAME_TRANS )
  942.         if ( state[minec] != 0 || deflink != JAMSTATE )
  943.         break;
  944.     }
  945.  
  946.     if ( totaltrans == 1 )
  947.     {
  948.     /* there's only one out-transition.  Save it for later to fill
  949.      * in holes in the tables.
  950.      */
  951.     stack1( statenum, minec, state[minec], deflink );
  952.     return;
  953.     }
  954.  
  955.     for ( maxec = numchars; maxec > 0; --maxec )
  956.     {
  957.     if ( state[maxec] != SAME_TRANS )
  958.         if ( state[maxec] != 0 || deflink != JAMSTATE )
  959.         break;
  960.     }
  961.  
  962.     /* Whether we try to fit the state table in the middle of the table
  963.      * entries we have already generated, or if we just take the state
  964.      * table at the end of the nxt/chk tables, we must make sure that we
  965.      * have a valid base address (i.e., non-negative).  Note that not only are
  966.      * negative base addresses dangerous at run-time (because indexing the
  967.      * next array with one and a low-valued character might generate an
  968.      * array-out-of-bounds error message), but at compile-time negative
  969.      * base addresses denote TEMPLATES.
  970.      */
  971.  
  972.     /* find the first transition of state that we need to worry about. */
  973.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  974.     { /* attempt to squeeze it into the middle of the tabls */
  975.     baseaddr = firstfree;
  976.  
  977.     while ( baseaddr < minec )
  978.         {
  979.         /* using baseaddr would result in a negative base address below
  980.          * find the next free slot
  981.          */
  982.         for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  983.         ;
  984.         }
  985.  
  986.     if ( baseaddr + maxec - minec >= current_max_xpairs )
  987.         expand_nxt_chk();
  988.  
  989.     for ( i = minec; i <= maxec; ++i )
  990.         if ( state[i] != SAME_TRANS )
  991.         if ( state[i] != 0 || deflink != JAMSTATE )
  992.             if ( chk[baseaddr + i - minec] != 0 )
  993.             { /* baseaddr unsuitable - find another */
  994.             for ( ++baseaddr;
  995.                   baseaddr < current_max_xpairs &&
  996.                   chk[baseaddr] != 0;
  997.                   ++baseaddr )
  998.                 ;
  999.  
  1000.             if ( baseaddr + maxec - minec >= current_max_xpairs )
  1001.                 expand_nxt_chk();
  1002.  
  1003.             /* reset the loop counter so we'll start all
  1004.              * over again next time it's incremented
  1005.              */
  1006.  
  1007.             i = minec - 1;
  1008.             }
  1009.     }
  1010.  
  1011.     else
  1012.     {
  1013.     /* ensure that the base address we eventually generate is
  1014.      * non-negative
  1015.      */
  1016.     baseaddr = max( tblend + 1, minec );
  1017.     }
  1018.  
  1019.     tblbase = baseaddr - minec;
  1020.     tbllast = tblbase + maxec;
  1021.  
  1022.     if ( tbllast >= current_max_xpairs )
  1023.     expand_nxt_chk();
  1024.  
  1025.     base[statenum] = tblbase;
  1026.     def[statenum] = deflink;
  1027.  
  1028.     for ( i = minec; i <= maxec; ++i )
  1029.     if ( state[i] != SAME_TRANS )
  1030.         if ( state[i] != 0 || deflink != JAMSTATE )
  1031.         {
  1032.         nxt[tblbase + i] = state[i];
  1033.         chk[tblbase + i] = statenum;
  1034.         }
  1035.  
  1036.     if ( baseaddr == firstfree )
  1037.     /* find next free slot in tables */
  1038.     for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  1039.         ;
  1040.  
  1041.     tblend = max( tblend, tbllast );
  1042.     }
  1043.  
  1044.  
  1045. /* mk1tbl - create table entries for a state (or state fragment) which
  1046.  *            has only one out-transition
  1047.  *
  1048.  * synopsis
  1049.  *   int state, sym, onenxt, onedef;
  1050.  *   mk1tbl( state, sym, onenxt, onedef );
  1051.  */
  1052.  
  1053. mk1tbl( state, sym, onenxt, onedef )
  1054. int state, sym, onenxt, onedef;
  1055.  
  1056.     {
  1057.     if ( firstfree < sym )
  1058.     firstfree = sym;
  1059.  
  1060.     while ( chk[firstfree] != 0 )
  1061.     if ( ++firstfree >= current_max_xpairs )
  1062.         expand_nxt_chk();
  1063.  
  1064.     base[state] = firstfree - sym;
  1065.     def[state] = onedef;
  1066.     chk[firstfree] = state;
  1067.     nxt[firstfree] = onenxt;
  1068.  
  1069.     if ( firstfree > tblend )
  1070.     {
  1071.     tblend = firstfree++;
  1072.  
  1073.     if ( firstfree >= current_max_xpairs )
  1074.         expand_nxt_chk();
  1075.     }
  1076.     }
  1077.  
  1078.  
  1079. /* mkprot - create new proto entry
  1080.  *
  1081.  * synopsis
  1082.  *   int state[], statenum, comstate;
  1083.  *   mkprot( state, statenum, comstate );
  1084.  */
  1085.  
  1086. mkprot( state, statenum, comstate )
  1087. int state[], statenum, comstate;
  1088.  
  1089.     {
  1090.     int i, slot, tblbase;
  1091.  
  1092.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  1093.     {
  1094.     /* gotta make room for the new proto by dropping last entry in
  1095.      * the queue
  1096.      */
  1097.     slot = lastprot;
  1098.     lastprot = protprev[lastprot];
  1099.     protnext[lastprot] = NIL;
  1100.     }
  1101.  
  1102.     else
  1103.     slot = numprots;
  1104.  
  1105.     protnext[slot] = firstprot;
  1106.  
  1107.     if ( firstprot != NIL )
  1108.     protprev[firstprot] = slot;
  1109.  
  1110.     firstprot = slot;
  1111.     prottbl[slot] = statenum;
  1112.     protcomst[slot] = comstate;
  1113.  
  1114.     /* copy state into save area so it can be compared with rapidly */
  1115.     tblbase = numecs * (slot - 1);
  1116.  
  1117.     for ( i = 1; i <= numecs; ++i )
  1118.     protsave[tblbase + i] = state[i];
  1119.     }
  1120.  
  1121.  
  1122. /* mktemplate - create a template entry based on a state, and connect the state
  1123.  *              to it
  1124.  *
  1125.  * synopsis
  1126.  *   int state[], statenum, comstate, totaltrans;
  1127.  *   mktemplate( state, statenum, comstate, totaltrans );
  1128.  */
  1129.  
  1130. mktemplate( state, statenum, comstate )
  1131. int state[], statenum, comstate;
  1132.  
  1133.     {
  1134.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  1135.     char transset[CSIZE + 1];
  1136.     int tsptr;
  1137.  
  1138.     ++numtemps;
  1139.  
  1140.     tsptr = 0;
  1141.  
  1142.     /* calculate where we will temporarily store the transition table
  1143.      * of the template in the tnxt[] array.  The final transition table
  1144.      * gets created by cmptmps()
  1145.      */
  1146.  
  1147.     tmpbase = numtemps * numecs;
  1148.  
  1149.     if ( tmpbase + numecs >= current_max_template_xpairs )
  1150.     {
  1151.     current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  1152.  
  1153.     ++num_reallocs;
  1154.  
  1155.     tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  1156.     }
  1157.  
  1158.     for ( i = 1; i <= numecs; ++i )
  1159.     if ( state[i] == 0 )
  1160.         tnxt[tmpbase + i] = 0;
  1161.     else
  1162.         {
  1163.         transset[tsptr++] = i;
  1164.         tnxt[tmpbase + i] = comstate;
  1165.         }
  1166.  
  1167.     if ( usemecs )
  1168.     mkeccl( transset, tsptr, tecfwd, tecbck, numecs );
  1169.  
  1170.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  1171.  
  1172.     /* we rely on the fact that mkprot adds things to the beginning
  1173.      * of the proto queue
  1174.      */
  1175.  
  1176.     numdiff = tbldiff( state, firstprot, tmp );
  1177.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  1178.     }
  1179.  
  1180.  
  1181. /* mv2front - move proto queue element to front of queue
  1182.  *
  1183.  * synopsis
  1184.  *   int qelm;
  1185.  *   mv2front( qelm );
  1186.  */
  1187.  
  1188. mv2front( qelm )
  1189. int qelm;
  1190.  
  1191.     {
  1192.     if ( firstprot != qelm )
  1193.     {
  1194.     if ( qelm == lastprot )
  1195.         lastprot = protprev[lastprot];
  1196.  
  1197.     protnext[protprev[qelm]] = protnext[qelm];
  1198.  
  1199.     if ( protnext[qelm] != NIL )
  1200.         protprev[protnext[qelm]] = protprev[qelm];
  1201.  
  1202.     protprev[qelm] = NIL;
  1203.     protnext[qelm] = firstprot;
  1204.     protprev[firstprot] = qelm;
  1205.     firstprot = qelm;
  1206.     }
  1207.     }
  1208.  
  1209.  
  1210. /* ntod - convert an ndfa to a dfa
  1211.  *
  1212.  * synopsis
  1213.  *    ntod();
  1214.  *
  1215.  *  creates the dfa corresponding to the ndfa we've constructed.  the
  1216.  *  dfa starts out in state #1.
  1217.  */
  1218. ntod()
  1219.  
  1220.     {
  1221.     int *accset, ds, nacc, newds;
  1222.     int duplist[CSIZE + 1], sym, hashval, numstates, dsize;
  1223.     int targfreq[CSIZE + 1], targstate[CSIZE + 1], state[CSIZE + 1];
  1224.     int *nset, *dset;
  1225.     int targptr, totaltrans, i, comstate, comfreq, targ;
  1226.     int *epsclosure(), snstods(), symlist[CSIZE + 1];
  1227.  
  1228.     /* this is so find_table_space(...) will know where to start looking in
  1229.      * chk/nxt for unused records for space to put in the state
  1230.      */
  1231.     if ( fullspd )
  1232.     firstfree = 0;
  1233.  
  1234.     accset = allocate_integer_array( accnum + 1 );
  1235.     nset = allocate_integer_array( current_max_dfa_size );
  1236.  
  1237.     todo_head = todo_next = 0;
  1238.  
  1239. #define ADD_QUEUE_ELEMENT(element) \
  1240.     if ( ++element >= current_max_dfas ) \
  1241.         { /* check for queue overflowing */ \
  1242.         if ( todo_head == 0 ) \
  1243.         increase_max_dfas(); \
  1244.         else \
  1245.         element = 0; \
  1246.         }
  1247.  
  1248. #define NEXT_QUEUE_ELEMENT(element) ((element + 1) % (current_max_dfas + 1))
  1249.  
  1250.     for ( i = 0; i <= CSIZE; ++i )
  1251.     {
  1252.     duplist[i] = NIL;
  1253.     symlist[i] = false;
  1254.     }
  1255.  
  1256.     for ( i = 0; i <= accnum; ++i )
  1257.     accset[i] = NIL;
  1258.  
  1259.     if ( trace )
  1260.     {
  1261.     dumpnfa( scset[1] );
  1262.     fputs( "\n\nDFA Dump:\n\n", stderr );
  1263.     }
  1264.  
  1265.     inittbl();
  1266.  
  1267.     if ( fullspd )
  1268.     {
  1269.     for ( i = 0; i <= numecs; ++i )
  1270.         state[i] = 0;
  1271.     place_state( state, 0, 0 );
  1272.     }
  1273.  
  1274.     if ( fulltbl )
  1275.     {
  1276.     /* declare it "short" because it's a real long-shot that that
  1277.      * won't be large enough
  1278.      */
  1279.     printf( "static short int %c[][%d] =\n    {\n", NEXTARRAY,
  1280.         numecs + 1 ); /* '}' so vi doesn't get too confused */
  1281.  
  1282.     /* generate 0 entries for state #0 */
  1283.     for ( i = 0; i <= numecs; ++i )
  1284.         mk2data( 0 );
  1285.  
  1286.     /* force ',' and dataflush() next call to mk2data */
  1287.     datapos = NUMDATAITEMS;
  1288.  
  1289.     /* force extra blank line next dataflush() */
  1290.     dataline = NUMDATALINES;
  1291.     }
  1292.  
  1293.     /* create the first states */
  1294.  
  1295.     for ( i = 1; i <= lastsc * 2; ++i )
  1296.     {
  1297.     numstates = 1;
  1298.  
  1299.     /* for each start condition, make one state for the case when
  1300.      * we're at the beginning of the line (the '%' operator) and
  1301.      * one for the case when we're not
  1302.      */
  1303.     if ( i % 2 == 1 )
  1304.         nset[numstates] = scset[(i / 2) + 1];
  1305.     else
  1306.         nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] );
  1307.  
  1308.     nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
  1309.  
  1310.     if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
  1311.         {
  1312.         numas = numas + nacc;
  1313.         totnst = totnst + numstates;
  1314.  
  1315.         todo[todo_next] = ds;
  1316.         ADD_QUEUE_ELEMENT(todo_next);
  1317.         }
  1318.     }
  1319.  
  1320.     if ( fulltbl )
  1321.     {
  1322.     if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
  1323.         flexfatal( "could not create unique end-of-buffer state" );
  1324.  
  1325.     numas += 1;
  1326.  
  1327.     todo[todo_next] = end_of_buffer_state;
  1328.     ADD_QUEUE_ELEMENT(todo_next);
  1329.     }
  1330.  
  1331.     while ( todo_head != todo_next )
  1332.     {
  1333.     targptr = 0;
  1334.     totaltrans = 0;
  1335.  
  1336.     for ( i = 1; i <= numecs; ++i )
  1337.         state[i] = 0;
  1338.  
  1339.     ds = todo[todo_head];
  1340.     todo_head = NEXT_QUEUE_ELEMENT(todo_head);
  1341.  
  1342.     dset = dss[ds];
  1343.     dsize = dfasiz[ds];
  1344.  
  1345.     if ( trace )
  1346.         fprintf( stderr, "state # %d:\n", ds );
  1347.  
  1348.     sympartition( dset, dsize, symlist, duplist );
  1349.  
  1350.     for ( sym = 1; sym <= numecs; ++sym )
  1351.         {
  1352.         if ( symlist[sym] )
  1353.         {
  1354.         symlist[sym] = 0;
  1355.  
  1356.         if ( duplist[sym] == NIL )
  1357.             { /* symbol has unique out-transitions */
  1358.             numstates = symfollowset( dset, dsize, sym, nset );
  1359.             nset = epsclosure( nset, &numstates, accset,
  1360.                        &nacc, &hashval );
  1361.  
  1362.             if ( snstods( nset, numstates, accset,
  1363.                   nacc, hashval, &newds ) )
  1364.             {
  1365.             totnst = totnst + numstates;
  1366.             todo[todo_next] = newds;
  1367.             ADD_QUEUE_ELEMENT(todo_next);
  1368.             numas = numas + nacc;
  1369.             }
  1370.  
  1371.             state[sym] = newds;
  1372.  
  1373.             if ( trace )
  1374.             fprintf( stderr, "\t%d\t%d\n", sym, newds );
  1375.  
  1376.             targfreq[++targptr] = 1;
  1377.             targstate[targptr] = newds;
  1378.             ++numuniq;
  1379.             }
  1380.  
  1381.         else
  1382.             {
  1383.             /* sym's equivalence class has the same transitions
  1384.              * as duplist(sym)'s equivalence class
  1385.              */
  1386.             targ = state[duplist[sym]];
  1387.             state[sym] = targ;
  1388.  
  1389.             if ( trace )
  1390.             fprintf( stderr, "\t%d\t%d\n", sym, targ );
  1391.  
  1392.             /* update frequency count for destination state */
  1393.  
  1394.             i = 0;
  1395.             while ( targstate[++i] != targ )
  1396.             ;
  1397.  
  1398.             ++targfreq[i];
  1399.             ++numdup;
  1400.             }
  1401.  
  1402.         ++totaltrans;
  1403.         duplist[sym] = NIL;
  1404.         }
  1405.         }
  1406.  
  1407.     numsnpairs = numsnpairs + totaltrans;
  1408.  
  1409.     if ( caseins && ! useecs )
  1410.         {
  1411.         register int j;
  1412.  
  1413.         for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
  1414.         state[i] = state[j];
  1415.         }
  1416.  
  1417.     if ( fulltbl )
  1418.         {
  1419.         /* supply array's 0-element */
  1420.         if ( ds == end_of_buffer_state )
  1421.         mk2data( 0 );
  1422.         else
  1423.         mk2data( end_of_buffer_state );
  1424.  
  1425.         for ( i = 1; i <= numecs; ++i )
  1426.         mk2data( state[i] );
  1427.  
  1428.         /* force ',' and dataflush() next call to mk2data */
  1429.         datapos = NUMDATAITEMS;
  1430.  
  1431.         /* force extra blank line next dataflush() */
  1432.         dataline = NUMDATALINES;
  1433.         }
  1434.  
  1435.         else if ( fullspd )
  1436.         place_state( state, ds, totaltrans );
  1437.  
  1438.     else
  1439.         {
  1440.         /* determine which destination state is the most common, and
  1441.          * how many transitions to it there are
  1442.          */
  1443.  
  1444.         comfreq = 0;
  1445.         comstate = 0;
  1446.  
  1447.         for ( i = 1; i <= targptr; ++i )
  1448.         if ( targfreq[i] > comfreq )
  1449.             {
  1450.             comfreq = targfreq[i];
  1451.             comstate = targstate[i];
  1452.             }
  1453.  
  1454.         bldtbl( state, ds, totaltrans, comstate, comfreq );
  1455.         }
  1456.     }
  1457.  
  1458.     if ( fulltbl )
  1459.     dataend();
  1460.  
  1461.     else
  1462.     {
  1463.     cmptmps();  /* create compressed template entries */
  1464.  
  1465.     /* create tables for all the states with only one out-transition */
  1466.     while ( onesp > 0 )
  1467.         {
  1468.         mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
  1469.             onedef[onesp] );
  1470.         --onesp;
  1471.         }
  1472.  
  1473.     mkdeftbl();
  1474.     }
  1475.     
  1476.     }
  1477.  
  1478.  
  1479. /* place_state - place a state into full speed transition table
  1480.  *
  1481.  * synopsis
  1482.  *     int *state, statenum, transnum;
  1483.  *     place_state( state, statenum, transnum );
  1484.  *
  1485.  * State is the statenum'th state.  It is indexed by equivalence class and
  1486.  * gives the number of the state to enter for a given equivalence class.
  1487.  * Transnum is the number of out-transitions for the state.
  1488.  */
  1489.  
  1490. place_state( state, statenum, transnum )
  1491. int *state, statenum, transnum;
  1492.  
  1493.     {
  1494.     register int i;
  1495.     register int *state_ptr;
  1496.     int position = find_table_space( state, transnum );
  1497.  
  1498.     /* base is the table of start positions */
  1499.     base[statenum] = position;
  1500.  
  1501.     /* put in action number marker; this non-zero number makes sure that
  1502.      * find_table_space() knows that this position in chk/nxt is taken
  1503.      * and should not be used for another accepting number in another state
  1504.      */
  1505.     chk[position - 1] = 1;
  1506.  
  1507.     /* put in end-of-buffer marker; this is for the same purposes as above */
  1508.     chk[position] = 1;
  1509.  
  1510.     /* place the state into chk and nxt */
  1511.     state_ptr = &state[1];
  1512.  
  1513.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  1514.     if ( *state_ptr != 0 )
  1515.         {
  1516.         chk[position + i] = i;
  1517.         nxt[position + i] = *state_ptr;
  1518.         }
  1519.  
  1520.     if ( position + numecs > tblend )
  1521.     tblend = position + numecs;
  1522.     }
  1523.  
  1524.  
  1525. /* stack1 - save states with only one out-transition to be processed later
  1526.  *
  1527.  * synopsis
  1528.  *   int statenum, sym, nextstate, deflink;
  1529.  *   stack1( statenum, sym, nextstate, deflink );
  1530.  *
  1531.  * if there's room for another state one the "one-transition" stack, the
  1532.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  1533.  * no room, we process the sucker right now.
  1534.  */
  1535.  
  1536. stack1( statenum, sym, nextstate, deflink )
  1537. int statenum, sym, nextstate, deflink;
  1538.  
  1539.     {
  1540.     if ( onesp >= ONE_STACK_SIZE )
  1541.     mk1tbl( statenum, sym, nextstate, deflink );
  1542.  
  1543.     else
  1544.     {
  1545.     ++onesp;
  1546.     onestate[onesp] = statenum;
  1547.     onesym[onesp] = sym;
  1548.     onenext[onesp] = nextstate;
  1549.     onedef[onesp] = deflink;
  1550.     }
  1551.     }
  1552.  
  1553.  
  1554. /* tbldiff - compute differences between two state tables
  1555.  *
  1556.  * synopsis
  1557.  *   int state[], pr, ext[];
  1558.  *   int tbldiff, numdifferences;
  1559.  *   numdifferences = tbldiff( state, pr, ext )
  1560.  *
  1561.  * "state" is the state array which is to be extracted from the pr'th
  1562.  * proto.  "pr" is both the number of the proto we are extracting from
  1563.  * and an index into the save area where we can find the proto's complete
  1564.  * state table.  Each entry in "state" which differs from the corresponding
  1565.  * entry of "pr" will appear in "ext".
  1566.  * Entries which are the same in both "state" and "pr" will be marked
  1567.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  1568.  * between "state" and "pr" is returned as function value.  Note that this
  1569.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  1570.  */
  1571.  
  1572. int tbldiff( state, pr, ext )
  1573. int state[], pr, ext[];
  1574.  
  1575.     {
  1576.     register int i, *sp = state, *ep = ext, *protp;
  1577.     register int numdiff = 0;
  1578.  
  1579.     protp = &protsave[numecs * (pr - 1)];
  1580.  
  1581.     for ( i = numecs; i > 0; --i )
  1582.     {
  1583.     if ( *++protp == *++sp )
  1584.         *++ep = SAME_TRANS;
  1585.     else
  1586.         {
  1587.         *++ep = *sp;
  1588.         ++numdiff;
  1589.         }
  1590.     }
  1591.  
  1592.     return ( numdiff );
  1593.     }
  1594.