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