contrib/byacc/closure.c

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