util/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 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
 104 closure(nucleus, n)
 105 short *nucleus;
 106 int n;
 107 {
 108     register int ruleno;
 109     register unsigned word;
 110     register unsigned mask;
 111     register short *csp;
 112     register unsigned *dsp;
 113     register unsigned *rsp;
 114     register int rulesetsize;
 115
 116     short *csend;
 117     unsigned *rsend;
 118     int symbol;
 119     int itemno;
 120
 121     rulesetsize = WORDSIZE(nrules);
 122     rsp = ruleset;
 123     rsend = ruleset + rulesetsize;
 124     for (rsp = ruleset; rsp < rsend; rsp++)
 125         *rsp = 0;
 126
 127     csend = nucleus + n;
 128     for (csp = nucleus; csp < csend; ++csp)
 129     {
 130         symbol = ritem[*csp];
 131         if (ISVAR(symbol))
 132         {
 133             dsp = first_derives + symbol * rulesetsize;
 134             rsp = ruleset;
 135             while (rsp < rsend)
 136                 *rsp++ |= *dsp++;
 137         }
 138     }
 139
 140     ruleno = 0;
 141     itemsetend = itemset;
 142     csp = nucleus;
 143     for (rsp = ruleset; rsp < rsend; ++rsp)
 144     {
 145         word = *rsp;
 146         if (word == 0)
 147             ruleno += BITS_PER_WORD;
 148         else
 149         {
 150             mask = 1;
 151             while (mask)
 152             {
 153                 if (word & mask)
 154                 {
 155                     itemno = rrhs[ruleno];
 156                     while (csp < csend && *csp < itemno)
 157                         *itemsetend++ = *csp++;
 158                     *itemsetend++ = itemno;
 159                     while (csp < csend && *csp == itemno)
 160                         ++csp;
 161                 }
 162
 163                     mask <<= 1;
 164                     ++ruleno;
 165             }
 166         }
 167     }
 168
 169     while (csp < csend)
 170         *itemsetend++ = *csp++;
 171
 172 #ifdef  DEBUG
 173   print_closure(n);
 174 #endif
 175 }
 176
 177
 178
 179 finalize_closure()
 180 {
 181   FREE(itemset);
 182   FREE(ruleset);
 183   FREE(first_derives + ntokens * WORDSIZE(nrules));
 184 }
 185
 186
 187 #ifdef  DEBUG
 188
 189 print_closure(n)
 190 int n;
 191 {
 192   register short *isp;
 193
 194   printf("\n\nn = %d\n\n", n);
 195   for (isp = itemset; isp < itemsetend; isp++)
 196     printf("   %d\n", *isp);
 197 }
 198
 199
 200 print_EFF()
 201 {
 202     register int i, j, k;
 203     register unsigned *rowp;
 204     register unsigned word;
 205     register unsigned mask;
 206
 207     printf("\n\nEpsilon Free Firsts\n");
 208
 209     for (i = start_symbol; i < nsyms; i++)
 210     {
 211         printf("\n%s", symbol_name[i]);
 212         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 213         word = *rowp++;
 214
 215         mask = 1;
 216         for (j = 0; j < nvars; j++)
 217         {
 218             if (word & mask)
 219                 printf("  %s", symbol_name[start_symbol + j]);
 220
 221             mask <<= 1;
 222             if (mask == 0)
 223             {
 224                 word = *rowp++;
 225                 mask = 1;
 226             }
 227         }
 228     }
 229 }
 230
 231
 232 print_first_derives()
 233 {
 234   register int i;
 235   register int j;
 236   register unsigned *rp;
 237   register unsigned cword;
 238   register unsigned mask;
 239
 240   printf("\n\n\nFirst Derives\n");
 241
 242   for (i = start_symbol; i < nsyms; i++)
 243     {
 244       printf("\n%s derives\n", symbol_name[i]);
 245       rp = first_derives + i * WORDSIZE(nrules);
 246       cword = *rp++;
 247       mask = 1;
 248       for (j = 0; j <= nrules; j++)
 249         {
 250           if (cword & mask)
 251             printf("   %d\n", j);
 252
 253           mask <<= 1;
 254           if (mask == 0)
 255             {
 256               cword = *rp++;
 257               mask = 1;
 258             }
 259         }
 260     }
 261
 262   fflush(stdout);
 263 }
 264
 265 #endif