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