mcs/jay/closure.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 static char sccsid[] = "@(#)closure.c   5.3 (Berkeley) 5/24/93";
  39 #endif /* not lint */
  40
  41 #include "defs.h"
  42
  43 short *itemset;
  44 short *itemsetend;
  45 unsigned *ruleset;
  46
  47 static unsigned *first_derives;
  48 static unsigned *EFF;
  49
  50 void
  51 print_first_derives (void);
  52
  53 void
  54 print_closure (int n);
  55
  56 void
  57 print_EFF (void);
  58
  59 static void
  60 set_EFF (void)
  61 {
  62     register unsigned *row;
  63     register int symbol;
  64     register short *sp;
  65     register int rowsize;
  66     register int i;
  67     register int rule;
  68
  69     rowsize = WORDSIZE(nvars);
  70     EFF = NEW2(nvars * rowsize, unsigned);
  71
  72     row = EFF;
  73     for (i = start_symbol; i < nsyms; i++)
  74     {
  75         sp = derives[i];
  76         for (rule = *sp; rule > 0; rule = *++sp)
  77         {
  78             symbol = ritem[rrhs[rule]];
  79             if (ISVAR(symbol))
  80             {
  81                 symbol -= start_symbol;
  82                 SETBIT(row, symbol);
  83             }
  84         }
  85         row += rowsize;
  86     }
  87
  88     reflexive_transitive_closure(EFF, nvars);
  89
  90 #ifdef  DEBUG
  91     print_EFF();
  92 #endif
  93 }
  94
  95 void
  96 set_first_derives (void)
  97 {
  98     register unsigned *rrow;
  99     register unsigned *vrow;
 100     register int j;
 101     register unsigned k;
 102     register unsigned cword;
 103     register short *rp;
 104
 105     int rule;
 106     int i;
 107     int rulesetsize;
 108     int varsetsize;
 109
 110     rulesetsize = WORDSIZE(nrules);
 111     varsetsize = WORDSIZE(nvars);
 112     first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 113
 114     set_EFF();
 115
 116     rrow = first_derives + ntokens * rulesetsize;
 117     for (i = start_symbol; i < nsyms; i++)
 118     {
 119         vrow = EFF + ((i - ntokens) * varsetsize);
 120         k = BITS_PER_WORD;
 121         for (j = start_symbol; j < nsyms; k++, j++)
 122         {
 123             if (k >= BITS_PER_WORD)
 124             {
 125                 cword = *vrow++;
 126                 k = 0;
 127             }
 128
 129             if (cword & (1 << k))
 130             {
 131                 rp = derives[j];
 132                 while ((rule = *rp++) >= 0)
 133                 {
 134                     SETBIT(rrow, rule);
 135                 }
 136             }
 137         }
 138
 139         vrow += varsetsize;
 140         rrow += rulesetsize;
 141     }
 142
 143 #ifdef  DEBUG
 144     print_first_derives();
 145 #endif
 146
 147     FREE(EFF);
 148 }
 149
 150 void
 151 closure (short *nucleus, int n)
 152 {
 153     register int ruleno;
 154     register unsigned word;
 155     register unsigned i;
 156     register short *csp;
 157     register unsigned *dsp;
 158     register unsigned *rsp;
 159     register int rulesetsize;
 160
 161     short *csend;
 162     unsigned *rsend;
 163     int symbol;
 164     int itemno;
 165
 166     rulesetsize = WORDSIZE(nrules);
 167     rsp = ruleset;
 168     rsend = ruleset + rulesetsize;
 169     for (rsp = ruleset; rsp < rsend; rsp++)
 170         *rsp = 0;
 171
 172     csend = nucleus + n;
 173     for (csp = nucleus; csp < csend; ++csp)
 174     {
 175         symbol = ritem[*csp];
 176         if (ISVAR(symbol))
 177         {
 178             dsp = first_derives + symbol * rulesetsize;
 179             rsp = ruleset;
 180             while (rsp < rsend)
 181                 *rsp++ |= *dsp++;
 182         }
 183     }
 184
 185     ruleno = 0;
 186     itemsetend = itemset;
 187     csp = nucleus;
 188     for (rsp = ruleset; rsp < rsend; ++rsp)
 189     {
 190         word = *rsp;
 191         if (word)
 192         {
 193             for (i = 0; i < BITS_PER_WORD; ++i)
 194             {
 195                 if (word & (1 << i))
 196                 {
 197                     itemno = rrhs[ruleno+i];
 198                     while (csp < csend && *csp < itemno)
 199                         *itemsetend++ = *csp++;
 200                     *itemsetend++ = itemno;
 201                     while (csp < csend && *csp == itemno)
 202                         ++csp;
 203                 }
 204             }
 205         }
 206         ruleno += BITS_PER_WORD;
 207     }
 208
 209     while (csp < csend)
 210         *itemsetend++ = *csp++;
 211
 212 #ifdef  DEBUG
 213   print_closure(n);
 214 #endif
 215 }
 216
 217 void
 218 finalize_closure (void)
 219 {
 220   FREE(itemset);
 221   FREE(ruleset);
 222   FREE(first_derives + ntokens * WORDSIZE(nrules));
 223 }
 224
 225 #ifdef  DEBUG
 226
 227 void
 228 print_closure (int n)
 229 {
 230   register short *isp;
 231
 232   printf("\n\nn = %d\n\n", n);
 233   for (isp = itemset; isp < itemsetend; isp++)
 234     printf("   %d\n", *isp);
 235 }
 236
 237 void
 238 print_EFF (void)
 239 {
 240     register int i, j;
 241     register unsigned *rowp;
 242     register unsigned word;
 243     register unsigned k;
 244
 245     printf("\n\nEpsilon Free Firsts\n");
 246
 247     for (i = start_symbol; i < nsyms; i++)
 248     {
 249         printf("\n%s", symbol_name[i]);
 250         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 251         word = *rowp++;
 252
 253         k = BITS_PER_WORD;
 254         for (j = 0; j < nvars; k++, j++)
 255         {
 256             if (k >= BITS_PER_WORD)
 257             {
 258                 word = *rowp++;
 259                 k = 0;
 260             }
 261
 262             if (word & (1 << k))
 263                 printf("  %s", symbol_name[start_symbol + j]);
 264         }
 265     }
 266 }
 267
 268 void
 269 print_first_derives (void)
 270 {
 271     register int i;
 272     register int j;
 273     register unsigned *rp;
 274     register unsigned cword;
 275     register unsigned k;
 276
 277     printf("\n\n\nFirst Derives\n");
 278
 279     for (i = start_symbol; i < nsyms; i++)
 280     {
 281         printf("\n%s derives\n", symbol_name[i]);
 282         rp = first_derives + i * WORDSIZE(nrules);
 283         k = BITS_PER_WORD;
 284         for (j = 0; j <= nrules; k++, j++)
 285         {
 286           if (k >= BITS_PER_WORD)
 287           {
 288               cword = *rp++;
 289               k = 0;
 290           }
 291
 292           if (cword & (1 << k))
 293             printf("   %d\n", j);
 294         }
 295     }
 296
 297   fflush(stdout);
 298 }
 299
 300 #endif