commands/byacc/closure.c

   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