usr.bin/yacc/closure.c

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