external/bsd/byacc/dist/closure.c

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