home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / BYACC.ZIP / CLOSURE.C < prev    next >
C/C++ Source or Header  |  1992-03-16  |  5KB  |  264 lines
  1. #include <stdlib.h>
  2. #include "byacc.h"
  3.  
  4. short *itemset;
  5. short *itemsetend;
  6. unsigned *ruleset;
  7.  
  8. static unsigned *first_derives;
  9. static unsigned *EFF;
  10.  
  11.  
  12. void set_EFF(void)
  13. {
  14.     register unsigned *row;
  15.     register int symbol;
  16.     register short *sp;
  17.     register int rowsize;
  18.     register int i;
  19.     register int rule;
  20.  
  21.     rowsize = WORDSIZE(nvars);
  22.     EFF = NEW2(nvars * rowsize, unsigned);
  23.  
  24.     row = EFF;
  25.     for (i = start_symbol; i < nsyms; i++)
  26.     {
  27.     sp = derives[i];
  28.     for (rule = *sp; rule > 0; rule = *++sp)
  29.     {
  30.         symbol = ritem[rrhs[rule]];
  31.         if (ISVAR(symbol))
  32.         {
  33.         symbol -= start_symbol;
  34.         SETBIT(row, symbol);
  35.         }
  36.     }
  37.     row += rowsize;
  38.     }
  39.  
  40.     reflexive_transitive_closure(EFF, nvars);
  41.  
  42. #ifdef    DEBUG
  43.     print_EFF();
  44. #endif
  45. }
  46.  
  47.  
  48. void set_first_derives(void)
  49. {
  50.   register unsigned *rrow;
  51.   register unsigned *vrow;
  52.   register int j;
  53.   register unsigned mask;
  54.   register unsigned cword;
  55.   register short *rp;
  56.  
  57.   int rule;
  58.   int i;
  59.   int rulesetsize;
  60.   int varsetsize;
  61.  
  62.   rulesetsize = WORDSIZE(nrules);
  63.   varsetsize = WORDSIZE(nvars);
  64.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  65.  
  66.   set_EFF();
  67.  
  68.   rrow = first_derives + ntokens * rulesetsize;
  69.   for (i = start_symbol; i < nsyms; i++)
  70.     {
  71.       vrow = EFF + ((i - ntokens) * varsetsize);
  72.       cword = *vrow++;
  73.       mask = 1;
  74.       for (j = start_symbol; j < nsyms; j++)
  75.     {
  76.       if (cword & mask)
  77.         {
  78.           rp = derives[j];
  79.           while ((rule = *rp++) >= 0)
  80.         {
  81.           SETBIT(rrow, rule);
  82.         }
  83.         }
  84.  
  85.       mask <<= 1;
  86.       if (mask == 0)
  87.         {
  88.           cword = *vrow++;
  89.           mask = 1;
  90.         }
  91.     }
  92.  
  93.       vrow += varsetsize;
  94.       rrow += rulesetsize;
  95.     }
  96.  
  97. #ifdef    DEBUG
  98.   print_first_derives();
  99. #endif
  100.  
  101.   FREE(EFF);
  102. }
  103.  
  104.  
  105. void closure(short *core, 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 = core + n;
  127.     for (csp = core; 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 = core;
  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. void finalize_closure(void)
  179. {
  180.   FREE(itemset);
  181.   FREE(ruleset);
  182.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  183. }
  184.  
  185.  
  186. #ifdef    DEBUG
  187. void
  188. print_closure(int n)
  189. {
  190.   register short *isp;
  191.  
  192.   printf("\n\nn = %d\n\n", n);
  193.   for (isp = itemset; isp < itemsetend; isp++)
  194.     printf("   %d\n", *isp);
  195. }
  196.  
  197. void
  198. print_EFF(void)
  199. {
  200.     register int i, j, k;
  201.     register unsigned *rowp;
  202.     register unsigned word;
  203.     register unsigned mask;
  204.  
  205.     printf("\n\nEpsilon Free Firsts\n");
  206.  
  207.     for (i = start_symbol; i < nsyms; i++)
  208.     {
  209.     printf("\n%s", symbol_name[i]);
  210.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  211.     word = *rowp++;
  212.  
  213.     mask = 1;
  214.     for (j = 0; j < nvars; j++)
  215.     {
  216.         if (word & mask)
  217.         printf("  %s", symbol_name[start_symbol + j]);
  218.  
  219.         mask <<= 1;
  220.         if (mask == 0)
  221.         {
  222.         word = *rowp++;
  223.         mask = 1;
  224.         }
  225.     }
  226.     }
  227. }
  228.  
  229. void
  230. print_first_derives(void)
  231. {
  232.   register int i;
  233.   register int j;
  234.   register unsigned *rp;
  235.   register unsigned cword;
  236.   register unsigned mask;
  237.  
  238.   printf("\n\n\nFirst Derives\n");
  239.  
  240.   for (i = start_symbol; i < nsyms; i++)
  241.     {
  242.       printf("\n%s derives\n", symbol_name[i]);
  243.       rp = first_derives + i * WORDSIZE(nrules);
  244.       cword = *rp++;
  245.       mask = 1;
  246.       for (j = 0; j <= nrules; j++)
  247.         {
  248.       if (cword & mask)
  249.         printf("   %d\n", j);
  250.  
  251.       mask <<= 1;
  252.       if (mask == 0)
  253.         {
  254.           cword = *rp++;
  255.           mask = 1;
  256.         }
  257.     }
  258.     }
  259.  
  260.   fflush(stdout);
  261. }
  262.  
  263. #endif
  264.