fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

closure.c (5486B)


      1 /*	$OpenBSD: closure.c,v 1.13 2014/03/13 01:18:22 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 void
     47 set_EFF(void)
     48 {
     49 	unsigned int *row;
     50 	int symbol, rowsize, i, rule;
     51 	short *sp;
     52 
     53 	rowsize = WORDSIZE(nvars);
     54 	EFF = NEW2(nvars * rowsize, unsigned);
     55 
     56 	row = EFF;
     57 	for (i = start_symbol; i < nsyms; i++) {
     58 		sp = derives[i];
     59 		for (rule = *sp; rule > 0; rule = *++sp) {
     60 			symbol = ritem[rrhs[rule]];
     61 			if (ISVAR(symbol)) {
     62 				symbol -= start_symbol;
     63 				SETBIT(row, symbol);
     64 			}
     65 		}
     66 		row += rowsize;
     67 	}
     68 
     69 	reflexive_transitive_closure(EFF, nvars);
     70 
     71 #ifdef	DEBUG
     72 	print_EFF();
     73 #endif
     74 }
     75 
     76 
     77 void
     78 set_first_derives(void)
     79 {
     80 	unsigned int *rrow, *vrow;
     81 	unsigned int k, cword = 0;
     82 	int i, j, rule, rulesetsize, varsetsize;
     83 	short *rp;
     84 
     85 	rulesetsize = WORDSIZE(nrules);
     86 	varsetsize = WORDSIZE(nvars);
     87 	first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
     88 
     89 	set_EFF();
     90 
     91 	rrow = first_derives + ntokens * rulesetsize;
     92 	for (i = start_symbol; i < nsyms; i++) {
     93 		vrow = EFF + ((i - ntokens) * varsetsize);
     94 		k = BITS_PER_WORD;
     95 		for (j = start_symbol; j < nsyms; k++, j++) {
     96 			if (k >= BITS_PER_WORD) {
     97 				cword = *vrow++;
     98 				k = 0;
     99 			}
    100 
    101 			if (cword & (1 << k)) {
    102 				rp = derives[j];
    103 				while ((rule = *rp++) >= 0) {
    104 					SETBIT(rrow, rule);
    105 				}
    106 			}
    107 		}
    108 
    109 		vrow += varsetsize;
    110 		rrow += rulesetsize;
    111 	}
    112 
    113 #ifdef	DEBUG
    114 	print_first_derives();
    115 #endif
    116 
    117 	free(EFF);
    118 }
    119 
    120 
    121 void
    122 closure(short *nucleus, int n)
    123 {
    124 	unsigned int i, word;
    125 	short *csp, *csend;
    126 	unsigned int *dsp, *rsp, *rsend;
    127 	int rulesetsize;
    128 	int ruleno, symbol, itemno;
    129 
    130 	rulesetsize = WORDSIZE(nrules);
    131 	rsend = ruleset + rulesetsize;
    132 	memset(ruleset, 0, rulesetsize * sizeof(*ruleset));
    133 
    134 	csend = nucleus + n;
    135 	for (csp = nucleus; csp < csend; ++csp) {
    136 		symbol = ritem[*csp];
    137 		if (ISVAR(symbol)) {
    138 			dsp = first_derives + symbol * rulesetsize;
    139 			rsp = ruleset;
    140 			while (rsp < rsend)
    141 				*rsp++ |= *dsp++;
    142 		}
    143 	}
    144 
    145 	ruleno = 0;
    146 	itemsetend = itemset;
    147 	csp = nucleus;
    148 	for (rsp = ruleset; rsp < rsend; ++rsp) {
    149 		word = *rsp;
    150 		if (word) {
    151 			for (i = 0; i < BITS_PER_WORD; ++i) {
    152 				if (word & (1 << i)) {
    153 					itemno = rrhs[ruleno+i];
    154 					while (csp < csend && *csp < itemno)
    155 						*itemsetend++ = *csp++;
    156 					*itemsetend++ = itemno;
    157 					while (csp < csend && *csp == itemno)
    158 						++csp;
    159 				}
    160 			}
    161 		}
    162 		ruleno += BITS_PER_WORD;
    163 	}
    164 
    165 	while (csp < csend)
    166 		*itemsetend++ = *csp++;
    167 
    168 #ifdef	DEBUG
    169   print_closure(n);
    170 #endif
    171 }
    172 
    173 
    174 
    175 void
    176 finalize_closure(void)
    177 {
    178 	free(itemset);
    179 	free(ruleset);
    180 	free(first_derives + ntokens * WORDSIZE(nrules));
    181 }
    182 
    183 
    184 #ifdef	DEBUG
    185 
    186 void
    187 print_closure(int n)
    188 {
    189 	short *isp;
    190 
    191 	printf("\n\nn = %d\n\n", n);
    192 	for (isp = itemset; isp < itemsetend; isp++)
    193 		printf("   %d\n", *isp);
    194 }
    195 
    196 void
    197 print_EFF(void)
    198 {
    199 	int i, j;
    200 	unsigned int *rowp;
    201 	unsigned int k, word;
    202 
    203 	printf("\n\nEpsilon Free Firsts\n");
    204 
    205 	for (i = start_symbol; i < nsyms; i++) {
    206 		printf("\n%s", symbol_name[i]);
    207 		rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
    208 		word = *rowp++;
    209 
    210 		k = BITS_PER_WORD;
    211 		for (j = 0; j < nvars; k++, j++) {
    212 			if (k >= BITS_PER_WORD) {
    213 				word = *rowp++;
    214 				k = 0;
    215 			}
    216 
    217 			if (word & (1 << k))
    218 				printf("  %s", symbol_name[start_symbol + j]);
    219 		}
    220 	}
    221 }
    222 
    223 void
    224 print_first_derives(void)
    225 {
    226 	int i, j;
    227 	unsigned int *rp;
    228 	unsigned int k, cword = 0;
    229 
    230 	printf("\n\n\nFirst Derives\n");
    231 
    232 	for (i = start_symbol; i < nsyms; i++) {
    233 		printf("\n%s derives\n", symbol_name[i]);
    234 		rp = first_derives + i * WORDSIZE(nrules);
    235 		k = BITS_PER_WORD;
    236 		for (j = 0; j <= nrules; k++, j++) {
    237 			if (k >= BITS_PER_WORD) {
    238 				cword = *rp++;
    239 				k = 0;
    240 			}
    241 
    242 			if (cword & (1 << k))
    243 				printf("   %d\n", j);
    244 		}
    245 	}
    246 
    247 	fflush(stdout);
    248 }
    249 
    250 #endif