contrib/byacc/closure.c

   1 /* $Id: closure.c,v 1.9 2010/06/09 08:21:47 tom Exp $ */
   2
   3 #include "defs.h"
   4
   5 Value_t *itemset;
   6 Value_t *itemsetend;
   7 unsigned *ruleset;
   8
   9 static unsigned *first_derives;
  10 static unsigned *EFF;
  11
  12 static void
  13 set_EFF(void)
  14 {
  15     unsigned *row;
  16     int symbol;
  17     short *sp;
  18     int rowsize;
  19     int i;
  20     int rule;
  21
  22     rowsize = WORDSIZE(nvars);
  23     EFF = NEW2(nvars * rowsize, unsigned);
  24
  25     row = EFF;
  26     for (i = start_symbol; i < nsyms; i++)
  27     {
  28         sp = derives[i];
  29         for (rule = *sp; rule > 0; rule = *++sp)
  30         {
  31             symbol = ritem[rrhs[rule]];
  32             if (ISVAR(symbol))
  33             {
  34                 symbol -= start_symbol;
  35                 SETBIT(row, symbol);
  36             }
  37         }
  38         row += rowsize;
  39     }
  40
  41     reflexive_transitive_closure(EFF, nvars);
  42
  43 #ifdef  DEBUG
  44     print_EFF();
  45 #endif
  46 }
  47
  48 void
  49 set_first_derives(void)
  50 {
  51     unsigned *rrow;
  52     unsigned *vrow;
  53     int j;
  54     unsigned k;
  55     unsigned cword = 0;
  56     short *rp;
  57
  58     int rule;
  59     int i;
  60     int rulesetsize;
  61     int varsetsize;
  62
  63     rulesetsize = WORDSIZE(nrules);
  64     varsetsize = WORDSIZE(nvars);
  65     first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  66
  67     set_EFF();
  68
  69     rrow = first_derives + ntokens * rulesetsize;
  70     for (i = start_symbol; i < nsyms; i++)
  71     {
  72         vrow = EFF + ((i - ntokens) * varsetsize);
  73         k = BITS_PER_WORD;
  74         for (j = start_symbol; j < nsyms; k++, j++)
  75         {
  76             if (k >= BITS_PER_WORD)
  77             {
  78                 cword = *vrow++;
  79                 k = 0;
  80             }
  81
  82             if (cword & (unsigned)(1 << k))
  83             {
  84                 rp = derives[j];
  85                 while ((rule = *rp++) >= 0)
  86                 {
  87                     SETBIT(rrow, rule);
  88                 }
  89             }
  90         }
  91
  92         rrow += rulesetsize;
  93     }
  94
  95 #ifdef  DEBUG
  96     print_first_derives();
  97 #endif
  98
  99     FREE(EFF);
 100 }
 101
 102 void
 103 closure(short *nucleus, int n)
 104 {
 105     unsigned ruleno;
 106     unsigned word;
 107     unsigned i;
 108     Value_t *csp;
 109     unsigned *dsp;
 110     unsigned *rsp;
 111     int rulesetsize;
 112
 113     Value_t *csend;
 114     unsigned *rsend;
 115     int symbol;
 116     Value_t itemno;
 117
 118     rulesetsize = WORDSIZE(nrules);
 119     rsend = ruleset + rulesetsize;
 120     for (rsp = ruleset; rsp < rsend; rsp++)
 121         *rsp = 0;
 122
 123     csend = nucleus + n;
 124     for (csp = nucleus; csp < csend; ++csp)
 125     {
 126         symbol = ritem[*csp];
 127         if (ISVAR(symbol))
 128         {
 129             dsp = first_derives + symbol * rulesetsize;
 130             rsp = ruleset;
 131             while (rsp < rsend)
 132                 *rsp++ |= *dsp++;
 133         }
 134     }
 135
 136     ruleno = 0;
 137     itemsetend = itemset;
 138     csp = nucleus;
 139     for (rsp = ruleset; rsp < rsend; ++rsp)
 140     {
 141         word = *rsp;
 142         if (word)
 143         {
 144             for (i = 0; i < BITS_PER_WORD; ++i)
 145             {
 146                 if (word & (unsigned)(1 << i))
 147                 {
 148                     itemno = rrhs[ruleno + i];
 149                     while (csp < csend && *csp < itemno)
 150                         *itemsetend++ = *csp++;
 151                     *itemsetend++ = itemno;
 152                     while (csp < csend && *csp == itemno)
 153                         ++csp;
 154                 }
 155             }
 156         }
 157         ruleno += BITS_PER_WORD;
 158     }
 159
 160     while (csp < csend)
 161         *itemsetend++ = *csp++;
 162
 163 #ifdef  DEBUG
 164     print_closure(n);
 165 #endif
 166 }
 167
 168 void
 169 finalize_closure(void)
 170 {
 171     FREE(itemset);
 172     FREE(ruleset);
 173     FREE(first_derives + ntokens * WORDSIZE(nrules));
 174 }
 175
 176 #ifdef  DEBUG
 177
 178 void
 179 print_closure(int n)
 180 {
 181     short *isp;
 182
 183     printf("\n\nn = %d\n\n", n);
 184     for (isp = itemset; isp < itemsetend; isp++)
 185         printf("   %d\n", *isp);
 186 }
 187
 188 void
 189 print_EFF(void)
 190 {
 191     int i, j;
 192     unsigned *rowp;
 193     unsigned word;
 194     unsigned k;
 195
 196     printf("\n\nEpsilon Free Firsts\n");
 197
 198     for (i = start_symbol; i < nsyms; i++)
 199     {
 200         printf("\n%s", symbol_name[i]);
 201         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 202         word = *rowp++;
 203
 204         k = BITS_PER_WORD;
 205         for (j = 0; j < nvars; k++, j++)
 206         {
 207             if (k >= BITS_PER_WORD)
 208             {
 209                 word = *rowp++;
 210                 k = 0;
 211             }
 212
 213             if (word & (1 << k))
 214                 printf("  %s", symbol_name[start_symbol + j]);
 215         }
 216     }
 217 }
 218
 219 void
 220 print_first_derives(void)
 221 {
 222     int i;
 223     int j;
 224     unsigned *rp;
 225     unsigned cword = 0;
 226     unsigned k;
 227
 228     printf("\n\n\nFirst Derives\n");
 229
 230     for (i = start_symbol; i < nsyms; i++)
 231     {
 232         printf("\n%s derives\n", symbol_name[i]);
 233         rp = first_derives + i * WORDSIZE(nrules);
 234         k = BITS_PER_WORD;
 235         for (j = 0; j <= nrules; k++, j++)
 236         {
 237             if (k >= BITS_PER_WORD)
 238             {
 239                 cword = *rp++;
 240                 k = 0;
 241             }
 242
 243             if (cword & (1 << k))
 244                 printf("   %d\n", j);
 245         }
 246     }
 247
 248     fflush(stdout);
 249 }
 250
 251 #endif