home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 213b.lha / Flex / Flex1 / dfa.c < prev    next >
C/C++ Source or Header  |  1996-02-14  |  11KB  |  475 lines
  1. /* dfa - DFA 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. /* epsclosure - construct the epsilon closure of a set of ndfa states
  18.  *
  19.  * synopsis
  20.  *    int t[current_max_dfa_size], numstates, accset[accnum + 1], nacc;
  21.  *    int hashval;
  22.  *    int *epsclosure();
  23.  *    t = epsclosure( t, &numstates, accset, &nacc, &hashval );
  24.  *
  25.  * NOTES
  26.  *    the epsilon closure is the set of all states reachable by an arbitrary
  27.  *  number of epsilon transitions which themselves do not have epsilon
  28.  *  transitions going out, unioned with the set of states which have non-null
  29.  *  accepting numbers.  t is an array of size numstates of nfa state numbers.
  30.  *  Upon return, t holds the epsilon closure and numstates is updated.  accset
  31.  *  holds a list of the accepting numbers, and the size of accset is given
  32.  *  by nacc.  t may be subjected to reallocation if it is not large enough
  33.  *  to hold the epsilon closure.
  34.  *
  35.  *    hashval is the hash value for the dfa corresponding to the state set
  36.  */
  37.  
  38. int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
  39. int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
  40.  
  41.     {
  42.     register int stkpos, ns, tsp;
  43.     int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
  44.     int stkend, nstate;
  45.     static int did_stk_init = false, *stk; 
  46.  
  47. #define MARK_STATE(state) \
  48.     trans1[state] = trans1[state] - MARKER_DIFFERENCE;
  49.  
  50. #define IS_MARKED(state) (trans1[state] < 0)
  51.  
  52. #define UNMARK_STATE(state) \
  53.     trans1[state] = trans1[state] + MARKER_DIFFERENCE;
  54.  
  55. #define CHECK_ACCEPT(state) \
  56.     { \
  57.     nfaccnum = accptnum[state]; \
  58.     if ( nfaccnum != NIL ) \
  59.         accset[++nacc] = nfaccnum; \
  60.     }
  61.  
  62. #define DO_REALLOCATION \
  63.     { \
  64.     current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
  65.     ++num_reallocs; \
  66.     t = reallocate_integer_array( t, current_max_dfa_size ); \
  67.     stk = reallocate_integer_array( stk, current_max_dfa_size ); \
  68.     } \
  69.  
  70. #define PUT_ON_STACK(state) \
  71.     { \
  72.     if ( ++stkend >= current_max_dfa_size ) \
  73.         DO_REALLOCATION \
  74.     stk[stkend] = state; \
  75.     MARK_STATE(state) \
  76.     }
  77.  
  78. #define ADD_STATE(state) \
  79.     { \
  80.     if ( ++numstates >= current_max_dfa_size ) \
  81.         DO_REALLOCATION \
  82.     t[numstates] = state; \
  83.     hashval = hashval + state; \
  84.     }
  85.  
  86. #define STACK_STATE(state) \
  87.     { \
  88.     PUT_ON_STACK(state) \
  89.     CHECK_ACCEPT(state) \
  90.     if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
  91.         ADD_STATE(state) \
  92.     }
  93.  
  94.     if ( ! did_stk_init )
  95.     {
  96.     stk = allocate_integer_array( current_max_dfa_size );
  97.     did_stk_init = true;
  98.     }
  99.  
  100.     nacc = stkend = hashval = 0;
  101.  
  102.     for ( nstate = 1; nstate <= numstates; ++nstate )
  103.     {
  104.     ns = t[nstate];
  105.  
  106.     /* the state could be marked if we've already pushed it onto
  107.      * the stack
  108.      */
  109.     if ( ! IS_MARKED(ns) )
  110.         PUT_ON_STACK(ns)
  111.  
  112.     CHECK_ACCEPT(ns)
  113.     hashval = hashval + ns;
  114.     }
  115.  
  116.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  117.     {
  118.     ns = stk[stkpos];
  119.     transsym = transchar[ns];
  120.  
  121.     if ( transsym == SYM_EPSILON )
  122.         {
  123.         tsp = trans1[ns] + MARKER_DIFFERENCE;
  124.  
  125.         if ( tsp != NO_TRANSITION )
  126.         {
  127.         if ( ! IS_MARKED(tsp) )
  128.             STACK_STATE(tsp)
  129.  
  130.         tsp = trans2[ns];
  131.  
  132.         if ( tsp != NO_TRANSITION )
  133.             if ( ! IS_MARKED(tsp) )
  134.             STACK_STATE(tsp)
  135.         }
  136.         }
  137.     }
  138.  
  139.     /* clear out "visit" markers */
  140.  
  141.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  142.     {
  143.     if ( IS_MARKED(stk[stkpos]) )
  144.         {
  145.         UNMARK_STATE(stk[stkpos])
  146.         }
  147.     else
  148.         flexfatal( "consistency check failed in epsclosure()" );
  149.     }
  150.  
  151.     *ns_addr = numstates;
  152.     *hv_addr = hashval;
  153.     *nacc_addr = nacc;
  154.  
  155.     return ( t );
  156.     }
  157.  
  158.  
  159.  
  160. /* increase_max_dfas - increase the maximum number of DFAs */
  161.  
  162. increase_max_dfas()
  163.  
  164.     {
  165.     int old_max = current_max_dfas;
  166.  
  167.     current_max_dfas += MAX_DFAS_INCREMENT;
  168.  
  169.     ++num_reallocs;
  170.  
  171.     base = reallocate_integer_array( base, current_max_dfas );
  172.     def = reallocate_integer_array( def, current_max_dfas );
  173.     dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
  174.     accsiz = reallocate_integer_array( accsiz, current_max_dfas );
  175.     dhash = reallocate_integer_array( dhash, current_max_dfas );
  176.     todo = reallocate_integer_array( todo, current_max_dfas );
  177.     dss = reallocate_integer_pointer_array( dss, current_max_dfas );
  178.     dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
  179.  
  180.     /* fix up todo queue */
  181.     if ( todo_next < todo_head )
  182.     { /* queue was wrapped around the end */
  183.     register int i;
  184.  
  185.     for ( i = 0; i < todo_next; ++i )
  186.         todo[old_max + i] = todo[i];
  187.     
  188.     todo_next += old_max;
  189.     }
  190.     }
  191.  
  192.  
  193. /* snstods - converts a set of ndfa states into a dfa state
  194.  *
  195.  * synopsis
  196.  *    int sns[numstates], numstates, newds, accset[accnum + 1], nacc, hashval;
  197.  *    int snstods();
  198.  *    is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
  199.  *
  200.  * on return, the dfa state number is in newds.
  201.  */
  202.  
  203. int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
  204. int sns[], numstates, accset[], nacc, hashval, *newds_addr;
  205.  
  206.     {
  207.     int didsort = 0;
  208.     register int i, j;
  209.     int newds, *oldsns;
  210.     char *malloc();
  211.  
  212.     for ( i = 1; i <= lastdfa; ++i )
  213.     if ( hashval == dhash[i] )
  214.         {
  215.         if ( numstates == dfasiz[i] )
  216.         {
  217.         oldsns = dss[i];
  218.  
  219.         if ( ! didsort )
  220.             {
  221.             /* we sort the states in sns so we can compare it to
  222.              * oldsns quickly.  we use bubble because there probably
  223.              * aren't very many states
  224.              */
  225.             bubble( sns, numstates );
  226.             didsort = 1;
  227.             }
  228.  
  229.         for ( j = 1; j <= numstates; ++j )
  230.             if ( sns[j] != oldsns[j] )
  231.             break;
  232.  
  233.         if ( j > numstates )
  234.             {
  235.             ++dfaeql;
  236.             *newds_addr = i;
  237.             return ( 0 );
  238.             }
  239.  
  240.         ++hshcol;
  241.         }
  242.  
  243.         else
  244.         ++hshsave;
  245.         }
  246.  
  247.     /* make a new dfa */
  248.  
  249.     if ( ++lastdfa >= current_max_dfas )
  250.     increase_max_dfas();
  251.  
  252.     newds = lastdfa;
  253.  
  254.     if ( ! (dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) )) )
  255.     flexfatal( "dynamic memory failure in snstods()" );
  256.  
  257.     /* if we haven't already sorted the states in sns, we do so now, so that
  258.      * future comparisons with it can be made quickly
  259.      */
  260.  
  261.     if ( ! didsort )
  262.     bubble( sns, numstates );
  263.  
  264.     for ( i = 1; i <= numstates; ++i )
  265.     dss[newds][i] = sns[i];
  266.  
  267.     dfasiz[newds] = numstates;
  268.     dhash[newds] = hashval;
  269.  
  270.     if ( nacc == 0 )
  271.     {
  272.     dfaacc[newds].dfaacc_state = 0;
  273.     accsiz[newds] = 0;
  274.     }
  275.  
  276.     else if ( reject )
  277.     {
  278.     /* we sort the accepting set in increasing order so the disambiguating
  279.      * rule that the first rule listed is considered match in the event of
  280.      * ties will work.  We use a bubble sort since the list is probably
  281.      * quite small.
  282.      */
  283.  
  284.     bubble( accset, nacc );
  285.  
  286.     dfaacc[newds].dfaacc_state =
  287.         (int) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );
  288.  
  289.     if ( ! dfaacc[newds].dfaacc_state )
  290.         flexfatal( "dynamic memory failure in snstods()" );
  291.  
  292.     /* save the accepting set for later */
  293.     for ( i = 1; i <= nacc; ++i )
  294.         dfaacc[newds].dfaacc_set[i] = accset[i];
  295.  
  296.     accsiz[newds] = nacc;
  297.     }
  298.  
  299.     else
  300.     { /* find lowest numbered rule so the disambiguating rule will work */
  301.     j = accnum + 1;
  302.  
  303.     for ( i = 1; i <= nacc; ++i )
  304.         if ( accset[i] < j )
  305.         j = accset[i];
  306.  
  307.     dfaacc[newds].dfaacc_state = j;
  308.     }
  309.  
  310.     *newds_addr = newds;
  311.  
  312.     return ( 1 );
  313.     }
  314.  
  315.  
  316. /* symfollowset - follow the symbol transitions one step
  317.  *
  318.  * synopsis
  319.  *    int ds[current_max_dfa_size], dsize, transsym;
  320.  *    int nset[current_max_dfa_size], numstates;
  321.  *    numstates = symfollowset( ds, dsize, transsym, nset );
  322.  */
  323.  
  324. int symfollowset( ds, dsize, transsym, nset )
  325. int ds[], dsize, transsym, nset[];
  326.  
  327.     {
  328.     int ns, tsp, sym, i, j, lenccl, ch, numstates;
  329.     int ccllist;
  330.  
  331.     numstates = 0;
  332.  
  333.     for ( i = 1; i <= dsize; ++i )
  334.     { /* for each nfa state ns in the state set of ds */
  335.     ns = ds[i];
  336.     sym = transchar[ns];
  337.     tsp = trans1[ns];
  338.  
  339.     if ( sym < 0 )
  340.         { /* it's a character class */
  341.         sym = -sym;
  342.         ccllist = cclmap[sym];
  343.         lenccl = ccllen[sym];
  344.  
  345.         if ( cclng[sym] )
  346.         {
  347.         for ( j = 0; j < lenccl; ++j )
  348.             { /* loop through negated character class */
  349.             ch = ccltbl[ccllist + j];
  350.  
  351.             if ( ch > transsym )
  352.             break;    /* transsym isn't in negated ccl */
  353.  
  354.             else if ( ch == transsym )
  355.             /* next 2 */ goto bottom;
  356.             }
  357.  
  358.         /* didn't find transsym in ccl */
  359.         nset[++numstates] = tsp;
  360.         }
  361.  
  362.         else
  363.         for ( j = 0; j < lenccl; ++j )
  364.             {
  365.             ch = ccltbl[ccllist + j];
  366.  
  367.             if ( ch > transsym )
  368.             break;
  369.  
  370.             else if ( ch == transsym )
  371.             {
  372.             nset[++numstates] = tsp;
  373.             break;
  374.             }
  375.             }
  376.         }
  377.  
  378.     else if ( sym >= 'A' && sym <= 'Z' && caseins )
  379.         flexfatal( "consistency check failed in symfollowset" );
  380.  
  381.     else if ( sym == SYM_EPSILON )
  382.         { /* do nothing */
  383.         }
  384.  
  385.     else if ( ecgroup[sym] == transsym )
  386.         nset[++numstates] = tsp;
  387.  
  388. bottom:
  389.     ;
  390.     }
  391.  
  392.     return ( numstates );
  393.     }
  394.  
  395.  
  396. /* sympartition - partition characters with same out-transitions
  397.  *
  398.  * synopsis
  399.  *    integer ds[current_max_dfa_size], numstates, duplist[numecs];
  400.  *    symlist[numecs];
  401.  *    sympartition( ds, numstates, symlist, duplist );
  402.  */
  403.  
  404. sympartition( ds, numstates, symlist, duplist )
  405. int ds[], numstates, duplist[];
  406. int symlist[];
  407.  
  408.     {
  409.     int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
  410.  
  411.     /* partitioning is done by creating equivalence classes for those
  412.      * characters which have out-transitions from the given state.  Thus
  413.      * we are really creating equivalence classes of equivalence classes.
  414.      */
  415.  
  416.     for ( i = 1; i <= numecs; ++i )
  417.     { /* initialize equivalence class list */
  418.     duplist[i] = i - 1;
  419.     dupfwd[i] = i + 1;
  420.     }
  421.  
  422.     duplist[1] = NIL;
  423.     dupfwd[numecs] = NIL;
  424.  
  425.     for ( i = 1; i <= numstates; ++i )
  426.     {
  427.     ns = ds[i];
  428.     tch = transchar[ns];
  429.  
  430.     if ( tch != SYM_EPSILON )
  431.         {
  432.         if ( tch < -lastccl || tch > CSIZE )
  433.         flexfatal( "bad transition character detected in sympartition()" );
  434.  
  435.         if ( tch > 0 )
  436.         { /* character transition */
  437.         mkechar( ecgroup[tch], dupfwd, duplist );
  438.         symlist[ecgroup[tch]] = 1;
  439.         }
  440.  
  441.         else
  442.         { /* character class */
  443.         tch = -tch;
  444.  
  445.         lenccl = ccllen[tch];
  446.         cclp = cclmap[tch];
  447.         mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs );
  448.  
  449.         if ( cclng[tch] )
  450.             {
  451.             j = 0;
  452.  
  453.             for ( k = 0; k < lenccl; ++k )
  454.             {
  455.             ich = ccltbl[cclp + k];
  456.  
  457.             for ( ++j; j < ich; ++j )
  458.                 symlist[j] = 1;
  459.             }
  460.  
  461.             for ( ++j; j <= numecs; ++j )
  462.             symlist[j] = 1;
  463.             }
  464.  
  465.         else
  466.             for ( k = 0; k < lenccl; ++k )
  467.             {
  468.             ich = ccltbl[cclp + k];
  469.             symlist[ich] = 1;
  470.             }
  471.         }
  472.         }
  473.     }
  474.     }
  475.