closure.c

   1 /* $Id: closure.c,v 1.7 2009/10/27 09:30:14 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 & (1 << k))
  83             {
  84                 rp = derives[j];
  85                 while ((rule = *rp++) >= 0)
  86                 {
  87                     SETBIT(rrow, rule);
  88                 }
  89             }
  90         }
  91
  92         vrow += varsetsize;
  93         rrow += rulesetsize;
  94     }
  95
  96 #ifdef  DEBUG
  97     print_first_derives();
  98 #endif
  99
 100     FREE(EFF);
 101 }
 102
 103 void
 104 closure(short *nucleus, int n)
 105 {
 106     unsigned ruleno;
 107     unsigned word;
 108     unsigned i;
 109     Value_t *csp;
 110     unsigned *dsp;
 111     unsigned *rsp;
 112     int rulesetsize;
 113
 114     Value_t *csend;
 115     unsigned *rsend;
 116     int symbol;
 117     Value_t itemno;
 118
 119     rulesetsize = WORDSIZE(nrules);
 120     rsp = ruleset;
 121     rsend = ruleset + rulesetsize;
 122     for (rsp = ruleset; rsp < rsend; rsp++)
 123         *rsp = 0;
 124
 125     csend = nucleus + n;
 126     for (csp = nucleus; csp < csend; ++csp)
 127     {
 128         symbol = ritem[*csp];
 129         if (ISVAR(symbol))
 130         {
 131             dsp = first_derives + symbol * rulesetsize;
 132             rsp = ruleset;
 133             while (rsp < rsend)
 134                 *rsp++ |= *dsp++;
 135         }
 136     }
 137
 138     ruleno = 0;
 139     itemsetend = itemset;
 140     csp = nucleus;
 141     for (rsp = ruleset; rsp < rsend; ++rsp)
 142     {
 143         word = *rsp;
 144         if (word)
 145         {
 146             for (i = 0; i < BITS_PER_WORD; ++i)
 147             {
 148                 if (word & (1 << i))
 149                 {
 150                     itemno = rrhs[ruleno + i];
 151                     while (csp < csend && *csp < itemno)
 152                         *itemsetend++ = *csp++;
 153                     *itemsetend++ = itemno;
 154                     while (csp < csend && *csp == itemno)
 155                         ++csp;
 156                 }
 157             }
 158         }
 159         ruleno += BITS_PER_WORD;
 160     }
 161
 162     while (csp < csend)
 163         *itemsetend++ = *csp++;
 164
 165 #ifdef  DEBUG
 166     print_closure(n);
 167 #endif
 168 }
 169
 170 void
 171 finalize_closure(void)
 172 {
 173     FREE(itemset);
 174     FREE(ruleset);
 175     FREE(first_derives + ntokens * WORDSIZE(nrules));
 176 }
 177
 178 #ifdef  DEBUG
 179
 180 void
 181 print_closure(int n)
 182 {
 183     short *isp;
 184
 185     printf("\n\nn = %d\n\n", n);
 186     for (isp = itemset; isp < itemsetend; isp++)
 187         printf("   %d\n", *isp);
 188 }
 189
 190 void
 191 print_EFF(void)
 192 {
 193     int i, j;
 194     unsigned *rowp;
 195     unsigned word;
 196     unsigned k;
 197
 198     printf("\n\nEpsilon Free Firsts\n");
 199
 200     for (i = start_symbol; i < nsyms; i++)
 201     {
 202         printf("\n%s", symbol_name[i]);
 203         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 204         word = *rowp++;
 205
 206         k = BITS_PER_WORD;
 207         for (j = 0; j < nvars; k++, j++)
 208         {
 209             if (k >= BITS_PER_WORD)
 210             {
 211                 word = *rowp++;
 212                 k = 0;
 213             }
 214
 215             if (word & (1 << k))
 216                 printf("  %s", symbol_name[start_symbol + j]);
 217         }
 218     }
 219 }
 220
 221 void
 222 print_first_derives(void)
 223 {
 224     int i;
 225     int j;
 226     unsigned *rp;
 227     unsigned cword = 0;
 228     unsigned k;
 229
 230     printf("\n\n\nFirst Derives\n");
 231
 232     for (i = start_symbol; i < nsyms; i++)
 233     {
 234         printf("\n%s derives\n", symbol_name[i]);
 235         rp = first_derives + i * WORDSIZE(nrules);
 236         k = BITS_PER_WORD;
 237         for (j = 0; j <= nrules; k++, j++)
 238         {
 239             if (k >= BITS_PER_WORD)
 240             {
 241                 cword = *rp++;
 242                 k = 0;
 243             }
 244
 245             if (cword & (1 << k))
 246                 printf("   %d\n", j);
 247         }
 248     }
 249
 250     fflush(stdout);
 251 }
 252
 253 #endif