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