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
  51 set_EFF()
  52 {
  53     register unsigned *row;
  54     register int symbol;
  55     register short *sp;
  56     register int rowsize;
  57     register int i;
  58     register int rule;
  59
  60     rowsize = WORDSIZE(nvars);
  61     EFF = NEW2(nvars * rowsize, unsigned);
  62
  63     row = EFF;
  64     for (i = start_symbol; i < nsyms; i++)
  65     {
  66         sp = derives[i];
  67         for (rule = *sp; rule > 0; rule = *++sp)
  68         {
  69             symbol = ritem[rrhs[rule]];
  70             if (ISVAR(symbol))
  71             {
  72                 symbol -= start_symbol;
  73                 SETBIT(row, symbol);
  74             }
  75         }
  76         row += rowsize;
  77     }
  78
  79     reflexive_transitive_closure(EFF, nvars);
  80
  81 #ifdef  DEBUG
  82     print_EFF();
  83 #endif
  84 }
  85
  86
  87 set_first_derives()
  88 {
  89     register unsigned *rrow;
  90     register unsigned *vrow;
  91     register int j;
  92     register unsigned k;
  93     register unsigned cword;
  94     register short *rp;
  95
  96     int rule;
  97     int i;
  98     int rulesetsize;
  99     int varsetsize;
 100
 101     rulesetsize = WORDSIZE(nrules);
 102     varsetsize = WORDSIZE(nvars);
 103     first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 104
 105     set_EFF();
 106
 107     rrow = first_derives + ntokens * rulesetsize;
 108     for (i = start_symbol; i < nsyms; i++)
 109     {
 110         vrow = EFF + ((i - ntokens) * varsetsize);
 111         k = BITS_PER_WORD;
 112         for (j = start_symbol; j < nsyms; k++, j++)
 113         {
 114             if (k >= BITS_PER_WORD)
 115             {
 116                 cword = *vrow++;
 117                 k = 0;
 118             }
 119
 120             if (cword & (1 << k))
 121             {
 122                 rp = derives[j];
 123                 while ((rule = *rp++) >= 0)
 124                 {
 125                     SETBIT(rrow, rule);
 126                 }
 127             }
 128         }
 129
 130         vrow += varsetsize;
 131         rrow += rulesetsize;
 132     }
 133
 134 #ifdef  DEBUG
 135     print_first_derives();
 136 #endif
 137
 138     FREE(EFF);
 139 }
 140
 141
 142 closure(nucleus, n)
 143 short *nucleus;
 144 int n;
 145 {
 146     register int ruleno;
 147     register unsigned word;
 148     register unsigned i;
 149     register short *csp;
 150     register unsigned *dsp;
 151     register unsigned *rsp;
 152     register int rulesetsize;
 153
 154     short *csend;
 155     unsigned *rsend;
 156     int symbol;
 157     int itemno;
 158
 159     rulesetsize = WORDSIZE(nrules);
 160     rsp = ruleset;
 161     rsend = ruleset + rulesetsize;
 162     for (rsp = ruleset; rsp < rsend; rsp++)
 163         *rsp = 0;
 164
 165     csend = nucleus + n;
 166     for (csp = nucleus; csp < csend; ++csp)
 167     {
 168         symbol = ritem[*csp];
 169         if (ISVAR(symbol))
 170         {
 171             dsp = first_derives + symbol * rulesetsize;
 172             rsp = ruleset;
 173             while (rsp < rsend)
 174                 *rsp++ |= *dsp++;
 175         }
 176     }
 177
 178     ruleno = 0;
 179     itemsetend = itemset;
 180     csp = nucleus;
 181     for (rsp = ruleset; rsp < rsend; ++rsp)
 182     {
 183         word = *rsp;
 184         if (word)
 185         {
 186             for (i = 0; i < BITS_PER_WORD; ++i)
 187             {
 188                 if (word & (1 << i))
 189                 {
 190                     itemno = rrhs[ruleno+i];
 191                     while (csp < csend && *csp < itemno)
 192                         *itemsetend++ = *csp++;
 193                     *itemsetend++ = itemno;
 194                     while (csp < csend && *csp == itemno)
 195                         ++csp;
 196                 }
 197             }
 198         }
 199         ruleno += BITS_PER_WORD;
 200     }
 201
 202     while (csp < csend)
 203         *itemsetend++ = *csp++;
 204
 205 #ifdef  DEBUG
 206   print_closure(n);
 207 #endif
 208 }
 209
 210
 211
 212 finalize_closure()
 213 {
 214   FREE(itemset);
 215   FREE(ruleset);
 216   FREE(first_derives + ntokens * WORDSIZE(nrules));
 217 }
 218
 219
 220 #ifdef  DEBUG
 221
 222 print_closure(n)
 223 int n;
 224 {
 225   register short *isp;
 226
 227   printf("\n\nn = %d\n\n", n);
 228   for (isp = itemset; isp < itemsetend; isp++)
 229     printf("   %d\n", *isp);
 230 }
 231
 232
 233 print_EFF()
 234 {
 235     register int i, j;
 236     register unsigned *rowp;
 237     register unsigned word;
 238     register unsigned k;
 239
 240     printf("\n\nEpsilon Free Firsts\n");
 241
 242     for (i = start_symbol; i < nsyms; i++)
 243     {
 244         printf("\n%s", symbol_name[i]);
 245         rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 246         word = *rowp++;
 247
 248         k = BITS_PER_WORD;
 249         for (j = 0; j < nvars; k++, j++)
 250         {
 251             if (k >= BITS_PER_WORD)
 252             {
 253                 word = *rowp++;
 254                 k = 0;
 255             }
 256
 257             if (word & (1 << k))
 258                 printf("  %s", symbol_name[start_symbol + j]);
 259         }
 260     }
 261 }
 262
 263
 264 print_first_derives()
 265 {
 266     register int i;
 267     register int j;
 268     register unsigned *rp;
 269     register unsigned cword;
 270     register unsigned k;
 271
 272     printf("\n\n\nFirst Derives\n");
 273
 274     for (i = start_symbol; i < nsyms; i++)
 275     {
 276         printf("\n%s derives\n", symbol_name[i]);
 277         rp = first_derives + i * WORDSIZE(nrules);
 278         k = BITS_PER_WORD;
 279         for (j = 0; j <= nrules; k++, j++)
 280         {
 281           if (k >= BITS_PER_WORD)
 282           {
 283               cword = *rp++;
 284               k = 0;
 285           }
 286
 287           if (cword & (1 << k))
 288             printf("   %d\n", j);
 289         }
 290     }
 291
 292   fflush(stdout);
 293 }
 294
 295 #endif