home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 200-299 / ff299.lzh / Yacc / closure.c < prev    next >
C/C++ Source or Header  |  1989-12-30  |  5KB  |  265 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 mask;
  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.       cword = *vrow++;
  72.       mask = 1;
  73.       for (j = start_symbol; j < nsyms; j++)
  74.         {
  75.           if (cword & mask)
  76.             {
  77.               rp = derives[j];
  78.               while ((rule = *rp++) >= 0)
  79.                 {
  80.                   SETBIT(rrow, rule);
  81.                 }
  82.             }
  83.  
  84.           mask <<= 1;
  85.           if (mask == 0)
  86.             {
  87.               cword = *vrow++;
  88.               mask = 1;
  89.             }
  90.         }
  91.  
  92.       vrow += varsetsize;
  93.       rrow += rulesetsize;
  94.     }
  95.  
  96. #ifdef  DEBUG
  97.   print_first_derives();
  98. #endif
  99.  
  100.   FREE(EFF);
  101. }
  102.  
  103. void closure(ccore, n)
  104.   short *ccore;
  105.   int n;
  106. {
  107.     register int ruleno;
  108.     register unsigned word;
  109.     register unsigned mask;
  110.     register short *csp;
  111.     register unsigned *dsp;
  112.     register unsigned *rsp;
  113.     register int rulesetsize;
  114.  
  115.     short *csend;
  116.     unsigned *rsend;
  117.     int symbol;
  118.     int itemno;
  119.  
  120.     rulesetsize = WORDSIZE(nrules);
  121.     rsp = ruleset;
  122.     rsend = ruleset + rulesetsize;
  123.     for (rsp = ruleset; rsp < rsend; rsp++)
  124.         *rsp = 0;
  125.  
  126.     csend = ccore + n;
  127.     for (csp = ccore; csp < csend; ++csp)
  128.     {
  129.         symbol = ritem[*csp];
  130.         if (ISVAR(symbol))
  131.         {
  132.             dsp = first_derives + symbol * rulesetsize;
  133.             rsp = ruleset;
  134.             while (rsp < rsend)
  135.                 *rsp++ |= *dsp++;
  136.         }
  137.     }
  138.  
  139.     ruleno = 0;
  140.     itemsetend = itemset;
  141.     csp = ccore;
  142.     for (rsp = ruleset; rsp < rsend; ++rsp)
  143.     {
  144.         word = *rsp;
  145.         if (word == 0)
  146.             ruleno += BITS_PER_WORD;
  147.         else
  148.         {
  149.             mask = 1;
  150.             while (mask)
  151.             {
  152.                 if (word & mask)
  153.                 {
  154.                     itemno = rrhs[ruleno];
  155.                     while (csp < csend && *csp < itemno)
  156.                         *itemsetend++ = *csp++;
  157.                     *itemsetend++ = itemno;
  158.                     while (csp < csend && *csp == itemno)
  159.                         ++csp;
  160.                 }
  161.  
  162.                     mask <<= 1;
  163.                     ++ruleno;
  164.             }
  165.         }
  166.     }
  167.  
  168.     while (csp < csend)
  169.         *itemsetend++ = *csp++;
  170.  
  171. #ifdef  DEBUG
  172.   print_closure(n);
  173. #endif
  174. }
  175.  
  176.  
  177.  
  178. finalize_closure()
  179. {
  180.   FREE(itemset);
  181.   FREE(ruleset);
  182.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  183. }
  184.  
  185.  
  186. #ifdef  DEBUG
  187.  
  188. print_closure(n)
  189. int n;
  190. {
  191.   register short *isp;
  192.  
  193.   printf("\n\nn = %d\n\n", n);
  194.   for (isp = itemset; isp < itemsetend; isp++)
  195.     printf("   %d\n", *isp);
  196. }
  197.  
  198.  
  199. print_EFF()
  200. {
  201.     register int i, j, k;
  202.     register unsigned *rowp;
  203.     register unsigned word;
  204.     register unsigned mask;
  205.  
  206.     printf("\n\nEpsilon Free Firsts\n");
  207.  
  208.     for (i = start_symbol; i < nsyms; i++)
  209.     {
  210.         printf("\n%s", symbol_name[i]);
  211.         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  212.         word = *rowp++;
  213.  
  214.         mask = 1;
  215.         for (j = 0; j < nvars; j++)
  216.         {
  217.             if (word & mask)
  218.                 printf("  %s", symbol_name[start_symbol + j]);
  219.  
  220.             mask <<= 1;
  221.             if (mask == 0)
  222.             {
  223.                 word = *rowp++;
  224.                 mask = 1;
  225.             }
  226.         }
  227.     }
  228. }
  229.  
  230.  
  231. print_first_derives()
  232. {
  233.   register int i;
  234.   register int j;
  235.   register unsigned *rp;
  236.   register unsigned cword;
  237.   register unsigned mask;
  238.  
  239.   printf("\n\n\nFirst Derives\n");
  240.  
  241.   for (i = start_symbol; i < nsyms; i++)
  242.     {
  243.       printf("\n%s derives\n", symbol_name[i]);
  244.       rp = first_derives + i * WORDSIZE(nrules);
  245.       cword = *rp++;
  246.       mask = 1;
  247.       for (j = 0; j <= nrules; j++)
  248.         {
  249.           if (cword & mask)
  250.             printf("   %d\n", j);
  251.  
  252.           mask <<= 1;
  253.           if (mask == 0)
  254.             {
  255.               cword = *rp++;
  256.               mask = 1;
  257.             }
  258.         }
  259.     }
  260.  
  261.   fflush(stdout);
  262. }
  263.  
  264. #endif
  265.