bin/yacc/closure.c

   1 /*      $OpenBSD: closure.c,v 1.15 2017/05/25 20:11:03 tedu Exp $       */
   2 /*      $NetBSD: closure.c,v 1.4 1996/03/19 03:21:29 jtc Exp $  */
   3
   4 /*
   5  * Copyright (c) 1989 The Regents of the University of California.
   6  * All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Robert Paul Corbett.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include "defs.h"
  37
  38 short *itemset;
  39 short *itemsetend;
  40 unsigned *ruleset;
  41
  42 static unsigned *first_derives;
  43 static unsigned *EFF;
  44
  45
  46 #ifdef  DEBUG
  47
  48 static void
  49 print_closure(int n)
  50 {
  51         short *isp;
  52
  53         printf("\n\nn = %d\n\n", n);
  54         for (isp = itemset; isp < itemsetend; isp++)
  55                 printf("   %d\n", *isp);
  56 }
  57
  58 static void
  59 print_EFF(void)
  60 {
  61         int i, j;
  62         unsigned int *rowp;
  63         unsigned int k, word;
  64
  65         printf("\n\nEpsilon Free Firsts\n");
  66
  67         for (i = start_symbol; i < nsyms; i++) {
  68                 printf("\n%s", symbol_name[i]);
  69                 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  70                 word = *rowp++;
  71
  72                 k = BITS_PER_WORD;
  73                 for (j = 0; j < nvars; k++, j++) {
  74                         if (k >= BITS_PER_WORD) {
  75                                 word = *rowp++;
  76                                 k = 0;
  77                         }
  78
  79                         if (word & (1 << k))
  80                                 printf("  %s", symbol_name[start_symbol + j]);
  81                 }
  82         }
  83 }
  84
  85 static void
  86 print_first_derives(void)
  87 {
  88         int i, j;
  89         unsigned int *rp;
  90         unsigned int k, cword = 0;
  91
  92         printf("\n\n\nFirst Derives\n");
  93
  94         for (i = start_symbol; i < nsyms; i++) {
  95                 printf("\n%s derives\n", symbol_name[i]);
  96                 rp = first_derives + i * WORDSIZE(nrules);
  97                 k = BITS_PER_WORD;
  98                 for (j = 0; j <= nrules; k++, j++) {
  99                         if (k >= BITS_PER_WORD) {
 100                                 cword = *rp++;
 101                                 k = 0;
 102                         }
 103
 104                         if (cword & (1 << k))
 105                                 printf("   %d\n", j);
 106                 }
 107         }
 108
 109         fflush(stdout);
 110 }
 111
 112 #endif
 113
 114
 115 static void
 116 set_EFF(void)
 117 {
 118         unsigned int *row;
 119         int symbol, rowsize, i, rule;
 120         short *sp;
 121
 122         rowsize = WORDSIZE(nvars);
 123         EFF = NEW2(nvars * rowsize, unsigned);
 124
 125         row = EFF;
 126         for (i = start_symbol; i < nsyms; i++) {
 127                 sp = derives[i];
 128                 for (rule = *sp; rule > 0; rule = *++sp) {
 129                         symbol = ritem[rrhs[rule]];
 130                         if (ISVAR(symbol)) {
 131                                 symbol -= start_symbol;
 132                                 SETBIT(row, symbol);
 133                         }
 134                 }
 135                 row += rowsize;
 136         }
 137
 138         reflexive_transitive_closure(EFF, nvars);
 139
 140 #ifdef  DEBUG
 141         print_EFF();
 142 #endif
 143 }
 144
 145
 146 void
 147 set_first_derives(void)
 148 {
 149         unsigned int *rrow, *vrow;
 150         unsigned int k, cword = 0;
 151         int i, j, rule, rulesetsize, varsetsize;
 152         short *rp;
 153
 154         rulesetsize = WORDSIZE(nrules);
 155         varsetsize = WORDSIZE(nvars);
 156         first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 157
 158         set_EFF();
 159
 160         rrow = first_derives + ntokens * rulesetsize;
 161         for (i = start_symbol; i < nsyms; i++) {
 162                 vrow = EFF + ((i - ntokens) * varsetsize);
 163                 k = BITS_PER_WORD;
 164                 for (j = start_symbol; j < nsyms; k++, j++) {
 165                         if (k >= BITS_PER_WORD) {
 166                                 cword = *vrow++;
 167                                 k = 0;
 168                         }
 169
 170                         if (cword & (1 << k)) {
 171                                 rp = derives[j];
 172                                 while ((rule = *rp++) >= 0) {
 173                                         SETBIT(rrow, rule);
 174                                 }
 175                         }
 176                 }
 177                 rrow += rulesetsize;
 178         }
 179
 180 #ifdef  DEBUG
 181         print_first_derives();
 182 #endif
 183
 184         free(EFF);
 185 }
 186
 187
 188 void
 189 closure(short *nucleus, int n)
 190 {
 191         unsigned int i, word;
 192         short *csp, *csend;
 193         unsigned int *dsp, *rsp, *rsend;
 194         int rulesetsize;
 195         int ruleno, symbol, itemno;
 196
 197         rulesetsize = WORDSIZE(nrules);
 198         rsend = ruleset + rulesetsize;
 199         memset(ruleset, 0, rulesetsize * sizeof(*ruleset));
 200
 201         csend = nucleus + n;
 202         for (csp = nucleus; csp < csend; ++csp) {
 203                 symbol = ritem[*csp];
 204                 if (ISVAR(symbol)) {
 205                         dsp = first_derives + symbol * rulesetsize;
 206                         rsp = ruleset;
 207                         while (rsp < rsend)
 208                                 *rsp++ |= *dsp++;
 209                 }
 210         }
 211
 212         ruleno = 0;
 213         itemsetend = itemset;
 214         csp = nucleus;
 215         for (rsp = ruleset; rsp < rsend; ++rsp) {
 216                 word = *rsp;
 217                 if (word) {
 218                         for (i = 0; i < BITS_PER_WORD; ++i) {
 219                                 if (word & (1 << i)) {
 220                                         itemno = rrhs[ruleno+i];
 221                                         while (csp < csend && *csp < itemno)
 222                                                 *itemsetend++ = *csp++;
 223                                         *itemsetend++ = itemno;
 224                                         while (csp < csend && *csp == itemno)
 225                                                 ++csp;
 226                                 }
 227                         }
 228                 }
 229                 ruleno += BITS_PER_WORD;
 230         }
 231
 232         while (csp < csend)
 233                 *itemsetend++ = *csp++;
 234
 235 #ifdef  DEBUG
 236   print_closure(n);
 237 #endif
 238 }
 239
 240
 241
 242 void
 243 finalize_closure(void)
 244 {
 245         free(itemset);
 246         free(ruleset);
 247         free(first_derives + ntokens * WORDSIZE(nrules));
 248 }