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