external/bsd/byacc/dist/closure.c

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