external/bsd/byacc/dist/closure.c

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