home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 2 / goldfish_vol2_cd1.bin / files / dev / c / yacc / src / closure.c next >
C/C++ Source or Header  |  1993-07-09  |  4KB  |  256 lines
  1. #include "defs.h"
  2.  
  3. short *itemset;
  4. short *itemsetend;
  5. unsigned *ruleset;
  6.  
  7. static unsigned *first_derives;
  8. static unsigned *EFF;
  9.  
  10.  
  11. set_EFF()
  12. {
  13.     register unsigned *row;
  14.     register int symbol;
  15.     register short *sp;
  16.     register int rowsize;
  17.     register int i;
  18.     register int rule;
  19.  
  20.     rowsize = WORDSIZE(nvars);
  21.     EFF = NEW2(nvars * rowsize, unsigned);
  22.  
  23.     row = EFF;
  24.     for (i = start_symbol; i < nsyms; i++)
  25.     {
  26.     sp = derives[i];
  27.     for (rule = *sp; rule > 0; rule = *++sp)
  28.     {
  29.         symbol = ritem[rrhs[rule]];
  30.         if (ISVAR(symbol))
  31.         {
  32.         symbol -= start_symbol;
  33.         SETBIT(row, symbol);
  34.         }
  35.     }
  36.     row += rowsize;
  37.     }
  38.  
  39.     reflexive_transitive_closure(EFF, nvars);
  40.  
  41. #ifdef    DEBUG
  42.     print_EFF();
  43. #endif
  44. }
  45.  
  46.  
  47. set_first_derives()
  48. {
  49.     register unsigned *rrow;
  50.     register unsigned *vrow;
  51.     register int j;
  52.     register unsigned k;
  53.     register unsigned cword;
  54.     register short *rp;
  55.  
  56.     int rule;
  57.     int i;
  58.     int rulesetsize;
  59.     int varsetsize;
  60.  
  61.     rulesetsize = WORDSIZE(nrules);
  62.     varsetsize = WORDSIZE(nvars);
  63.     first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  64.  
  65.     set_EFF();
  66.  
  67.     rrow = first_derives + ntokens * rulesetsize;
  68.     for (i = start_symbol; i < nsyms; i++)
  69.     {
  70.     vrow = EFF + ((i - ntokens) * varsetsize);
  71.     k = BITS_PER_WORD;
  72.     for (j = start_symbol; j < nsyms; k++, j++)
  73.     {
  74.         if (k >= BITS_PER_WORD)
  75.         {
  76.         cword = *vrow++;
  77.         k = 0;
  78.         }
  79.  
  80.         if (cword & (1 << k))
  81.         {
  82.         rp = derives[j];
  83.         while ((rule = *rp++) >= 0)
  84.         {
  85.             SETBIT(rrow, rule);
  86.         }
  87.         }
  88.     }
  89.  
  90.     vrow += varsetsize;
  91.     rrow += rulesetsize;
  92.     }
  93.  
  94. #ifdef    DEBUG
  95.     print_first_derives();
  96. #endif
  97.  
  98.     FREE(EFF);
  99. }
  100.  
  101.  
  102. closure(nucleus, n)
  103. short *nucleus;
  104. int n;
  105. {
  106.     register int ruleno;
  107.     register unsigned word;
  108.     register unsigned i;
  109.     register short *csp;
  110.     register unsigned *dsp;
  111.     register unsigned *rsp;
  112.     register int rulesetsize;
  113.  
  114.     short *csend;
  115.     unsigned *rsend;
  116.     int symbol;
  117.     int itemno;
  118.  
  119.     rulesetsize = WORDSIZE(nrules);
  120.     rsp = ruleset;
  121.     rsend = ruleset + rulesetsize;
  122.     for (rsp = ruleset; rsp < rsend; rsp++)
  123.     *rsp = 0;
  124.  
  125.     csend = nucleus + n;
  126.     for (csp = nucleus; csp < csend; ++csp)
  127.     {
  128.     symbol = ritem[*csp];
  129.     if (ISVAR(symbol))
  130.     {
  131.         dsp = first_derives + symbol * rulesetsize;
  132.         rsp = ruleset;
  133.         while (rsp < rsend)
  134.         *rsp++ |= *dsp++;
  135.     }
  136.     }
  137.  
  138.     ruleno = 0;
  139.     itemsetend = itemset;
  140.     csp = nucleus;
  141.     for (rsp = ruleset; rsp < rsend; ++rsp)
  142.     {
  143.     word = *rsp;
  144.     if (word)
  145.     {
  146.         for (i = 0; i < BITS_PER_WORD; ++i)
  147.         {
  148.         if (word & (1 << i))
  149.         {
  150.             itemno = rrhs[ruleno+i];
  151.             while (csp < csend && *csp < itemno)
  152.             *itemsetend++ = *csp++;
  153.             *itemsetend++ = itemno;
  154.             while (csp < csend && *csp == itemno)
  155.             ++csp;
  156.         }
  157.         }
  158.     }
  159.     ruleno += BITS_PER_WORD;
  160.     }
  161.  
  162.     while (csp < csend)
  163.     *itemsetend++ = *csp++;
  164.  
  165. #ifdef    DEBUG
  166.   print_closure(n);
  167. #endif
  168. }
  169.  
  170.  
  171.  
  172. finalize_closure()
  173. {
  174.   FREE(itemset);
  175.   FREE(ruleset);
  176.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  177. }
  178.  
  179.  
  180. #ifdef    DEBUG
  181.  
  182. print_closure(n)
  183. int n;
  184. {
  185.   register short *isp;
  186.  
  187.   printf("\n\nn = %d\n\n", n);
  188.   for (isp = itemset; isp < itemsetend; isp++)
  189.     printf("   %d\n", *isp);
  190. }
  191.  
  192.  
  193. print_EFF()
  194. {
  195.     register int i, j;
  196.     register unsigned *rowp;
  197.     register unsigned word;
  198.     register unsigned k;
  199.  
  200.     printf("\n\nEpsilon Free Firsts\n");
  201.  
  202.     for (i = start_symbol; i < nsyms; i++)
  203.     {
  204.     printf("\n%s", symbol_name[i]);
  205.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  206.     word = *rowp++;
  207.  
  208.     k = BITS_PER_WORD;
  209.     for (j = 0; j < nvars; k++, j++)
  210.     {
  211.         if (k >= BITS_PER_WORD)
  212.         {
  213.         word = *rowp++;
  214.         k = 0;
  215.         }
  216.  
  217.         if (word & (1 << k))
  218.         printf("  %s", symbol_name[start_symbol + j]);
  219.     }
  220.     }
  221. }
  222.  
  223.  
  224. print_first_derives()
  225. {
  226.     register int i;
  227.     register int j;
  228.     register unsigned *rp;
  229.     register unsigned cword;
  230.     register unsigned k;
  231.  
  232.     printf("\n\n\nFirst Derives\n");
  233.  
  234.     for (i = start_symbol; i < nsyms; i++)
  235.     {
  236.     printf("\n%s derives\n", symbol_name[i]);
  237.     rp = first_derives + i * WORDSIZE(nrules);
  238.     k = BITS_PER_WORD;
  239.     for (j = 0; j <= nrules; k++, j++)
  240.         {
  241.       if (k >= BITS_PER_WORD)
  242.       {
  243.           cword = *rp++;
  244.           k = 0;
  245.       }
  246.  
  247.       if (cword & (1 << k))
  248.         printf("   %d\n", j);
  249.     }
  250.     }
  251.  
  252.   fflush(stdout);
  253. }
  254.  
  255. #endif
  256.