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