closure.c

   1 /* $Id: closure.c,v 1.12 2020/09/10 17:22:08 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     int rowsize;
  25     int i;
  26     int rule;
  27
  28     rowsize = WORDSIZE(nvars);
  29     EFF = NEW2(nvars * rowsize, unsigned);
  30
  31     row = EFF;
  32     for (i = start_symbol; i < nsyms; i++)
  33     {
  34         Value_t *sp = derives[i];
  35         for (rule = *sp; rule > 0; rule = *++sp)
  36         {
  37             symbol = ritem[rrhs[rule]];
  38             if (ISVAR(symbol))
  39             {
  40                 symbol -= start_symbol;
  41                 SETBIT(row, symbol);
  42             }
  43         }
  44         row += rowsize;
  45     }
  46
  47     reflexive_transitive_closure(EFF, nvars);
  48
  49 #ifdef  DEBUG
  50     print_EFF();
  51 #endif
  52 }
  53
  54 void
  55 set_first_derives(void)
  56 {
  57     unsigned *rrow;
  58     int j;
  59     unsigned cword = 0;
  60     Value_t *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_base = NEW2(nvars * rulesetsize, unsigned);
  70     first_derives = first_base - ntokens * rulesetsize;
  71
  72     set_EFF();
  73
  74     rrow = first_derives + ntokens * rulesetsize;
  75     for (i = start_symbol; i < nsyms; i++)
  76     {
  77         unsigned *vrow = EFF + ((i - ntokens) * varsetsize);
  78         unsigned k = BITS_PER_WORD;
  79
  80         for (j = start_symbol; j < nsyms; k++, j++)
  81         {
  82             if (k >= BITS_PER_WORD)
  83             {
  84                 cword = *vrow++;
  85                 k = 0;
  86             }
  87
  88             if (cword & (unsigned)(1 << k))
  89             {
  90                 rp = derives[j];
  91                 while ((rule = *rp++) >= 0)
  92                 {
  93                     SETBIT(rrow, rule);
  94                 }
  95             }
  96         }
  97
  98         rrow += rulesetsize;
  99     }
 100
 101 #ifdef  DEBUG
 102     print_first_derives();
 103 #endif
 104
 105     FREE(EFF);
 106 }
 107
 108 void
 109 closure(Value_t *nucleus, int n)
 110 {
 111     unsigned ruleno;
 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     Value_t itemno;
 121
 122     rulesetsize = WORDSIZE(nrules);
 123     rsend = ruleset + rulesetsize;
 124     for (rsp = ruleset; rsp < rsend; rsp++)
 125         *rsp = 0;
 126
 127     csend = nucleus + n;
 128     for (csp = nucleus; csp < csend; ++csp)
 129     {
 130         int symbol = ritem[*csp];
 131
 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         unsigned word = *rsp;
 147
 148         if (word)
 149         {
 150             for (i = 0; i < BITS_PER_WORD; ++i)
 151             {
 152                 if (word & (unsigned)(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_base);
 180 }
 181
 182 #ifdef  DEBUG
 183
 184 static void
 185 print_closure(int n)
 186 {
 187     Value_t *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 static 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 static 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