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