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