Home | History | Annotate | Line # | Download | only in dist 
      1 /*	$NetBSD: closure.c,v 1.14 2026/05/03 15:29:19 christos Exp $	*/
      2 
      3 /* Id: closure.c,v 1.15 2025/10/08 00:22:08 tom Exp  */
      4 
      5 #include "defs.h"
      6 
      7 #include <sys/cdefs.h>
      8 __RCSID("$NetBSD: closure.c,v 1.14 2026/05/03 15:29:19 christos Exp $");
      9 
     10 Value_t *itemset;
     11 Value_t *itemsetend;
     12 unsigned *ruleset;
     13 
     14 static unsigned *first_derives;
     15 static unsigned *EFF;
     16 
     17 #ifdef	DEBUG
     18 static void print_closure(int);
     19 static void print_EFF(void);
     20 static void print_first_derives(void);
     21 #endif
     22 
     23 static void
     24 set_EFF(void)
     25 {
     26     unsigned *row;
     27     int symbol;
     28     int rowsize;
     29     int i;
     30     int rule;
     31 
     32     rowsize = WORDSIZE(nvars);
     33     EFF = NEW2(nvars * rowsize, unsigned);
     34 
     35     row = EFF;
     36     for (i = start_symbol; i < nsyms; i++)
     37     {
     38 	const Value_t *sp = derives[i];
     39 	for (rule = *sp; rule > 0; rule = *++sp)
     40 	{
     41 	    symbol = ritem[rrhs[rule]];
     42 	    if (ISVAR(symbol))
     43 	    {
     44 		symbol -= start_symbol;
     45 		SETBIT(row, symbol);
     46 	    }
     47 	}
     48 	row += rowsize;
     49     }
     50 
     51     reflexive_transitive_closure(EFF, nvars);
     52 
     53 #ifdef	DEBUG
     54     print_EFF();
     55 #endif
     56 }
     57 
     58 void
     59 set_first_derives(void)
     60 {
     61     unsigned *rrow;
     62     int j;
     63     unsigned cword = 0;
     64     const Value_t *rp;
     65 
     66     int rule;
     67     int i;
     68     int rulesetsize;
     69     int varsetsize;
     70 
     71     rulesetsize = WORDSIZE(nrules);
     72     varsetsize = WORDSIZE(nvars);
     73     first_derives = NEW2(nvars * rulesetsize, unsigned);
     74 
     75     set_EFF();
     76 
     77     rrow = first_derives;
     78     for (i = start_symbol; i < nsyms; i++)
     79     {
     80 	const unsigned *vrow = EFF + ((i - ntokens) * varsetsize);
     81 	unsigned k = BITS_PER_WORD;
     82 
     83 	for (j = start_symbol; j < nsyms; k++, j++)
     84 	{
     85 	    if (k >= BITS_PER_WORD)
     86 	    {
     87 		cword = *vrow++;
     88 		k = 0;
     89 	    }
     90 
     91 	    if (cword & (1U << k))
     92 	    {
     93 		rp = derives[j];
     94 		while ((rule = *rp++) >= 0)
     95 		{
     96 		    SETBIT(rrow, rule);
     97 		}
     98 	    }
     99 	}
    100 
    101 	rrow += rulesetsize;
    102     }
    103 
    104 #ifdef	DEBUG
    105     print_first_derives();
    106 #endif
    107 
    108     FREE(EFF);
    109 }
    110 
    111 void
    112 closure(Value_t *nucleus, int n)
    113 {
    114     unsigned ruleno;
    115     unsigned i;
    116     Value_t *csp;
    117     const unsigned *dsp;
    118     unsigned *rsp;
    119     int rulesetsize;
    120 
    121     const Value_t *csend;
    122     const unsigned *rsend;
    123     Value_t itemno;
    124 
    125     rulesetsize = WORDSIZE(nrules);
    126     rsend = ruleset + rulesetsize;
    127     for (rsp = ruleset; rsp < rsend; rsp++)
    128 	*rsp = 0;
    129 
    130     csend = nucleus + n;
    131     for (csp = nucleus; csp < csend; ++csp)
    132     {
    133 	int symbol = ritem[*csp];
    134 
    135 	if (ISVAR(symbol))
    136 	{
    137 	    dsp = first_derives + (symbol - ntokens) * rulesetsize;
    138 	    rsp = ruleset;
    139 	    while (rsp < rsend)
    140 		*rsp++ |= *dsp++;
    141 	}
    142     }
    143 
    144     ruleno = 0;
    145     itemsetend = itemset;
    146     csp = nucleus;
    147     for (rsp = ruleset; rsp < rsend; ++rsp)
    148     {
    149 	unsigned word = *rsp;
    150 
    151 	if (word)
    152 	{
    153 	    for (i = 0; i < BITS_PER_WORD; ++i)
    154 	    {
    155 		if (word & (1U << i))
    156 		{
    157 		    itemno = rrhs[ruleno + i];
    158 		    while (csp < csend && *csp < itemno)
    159 			*itemsetend++ = *csp++;
    160 		    *itemsetend++ = itemno;
    161 		    while (csp < csend && *csp == itemno)
    162 			++csp;
    163 		}
    164 	    }
    165 	}
    166 	ruleno += BITS_PER_WORD;
    167     }
    168 
    169     while (csp < csend)
    170 	*itemsetend++ = *csp++;
    171 
    172 #ifdef	DEBUG
    173     print_closure(n);
    174 #endif
    175 }
    176 
    177 void
    178 finalize_closure(void)
    179 {
    180     FREE(itemset);
    181     FREE(ruleset);
    182     FREE(first_derives);
    183 }
    184 
    185 #ifdef	DEBUG
    186 
    187 static void
    188 print_closure(int n)
    189 {
    190     Value_t *isp;
    191 
    192     printf("\n\nn = %d\n\n", n);
    193     for (isp = itemset; isp < itemsetend; isp++)
    194 	printf("   %d\n", *isp);
    195 }
    196 
    197 static void
    198 print_EFF(void)
    199 {
    200     int i, j;
    201     unsigned *rowp;
    202     unsigned word;
    203     unsigned k;
    204 
    205     printf("\n\nEpsilon Free Firsts\n");
    206 
    207     for (i = start_symbol; i < nsyms; i++)
    208     {
    209 	printf("\n%s", symbol_name[i]);
    210 	rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
    211 	word = *rowp++;
    212 
    213 	k = BITS_PER_WORD;
    214 	for (j = 0; j < nvars; k++, j++)
    215 	{
    216 	    if (k >= BITS_PER_WORD)
    217 	    {
    218 		word = *rowp++;
    219 		k = 0;
    220 	    }
    221 
    222 	    if (word & (1 << k))
    223 		printf("  %s", symbol_name[start_symbol + j]);
    224 	}
    225     }
    226 }
    227 
    228 static void
    229 print_first_derives(void)
    230 {
    231     int i;
    232     int j;
    233     unsigned *rp;
    234     unsigned cword = 0;
    235     unsigned k;
    236 
    237     printf("\n\n\nFirst Derives\n");
    238 
    239     for (i = start_symbol; i < nsyms; i++)
    240     {
    241 	printf("\n%s derives\n", symbol_name[i]);
    242 	rp = first_derives + (i - ntokens) * WORDSIZE(nrules);
    243 	k = BITS_PER_WORD;
    244 	for (j = 0; j <= nrules; k++, j++)
    245 	{
    246 	    if (k >= BITS_PER_WORD)
    247 	    {
    248 		cword = *rp++;
    249 		k = 0;
    250 	    }
    251 
    252 	    if (cword & (1 << k))
    253 		printf("   %d\n", j);
    254 	}
    255     }
    256 
    257     fflush(stdout);
    258 }
    259 
    260 #endif
    261