fatbase

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

lr0.c (9178B)


      1 /* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $	 */
      2 /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 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 extern short *itemset;
     39 extern short *itemsetend;
     40 extern unsigned *ruleset;
     41 
     42 int nstates;
     43 core *first_state;
     44 shifts *first_shift;
     45 reductions *first_reduction;
     46 
     47 short get_state(int);
     48 core *new_state(int);
     49 
     50 void allocate_itemsets(void);
     51 void allocate_storage(void);
     52 void append_states(void);
     53 void free_storage(void);
     54 void generate_states(void);
     55 void initialize_states(void);
     56 void new_itemsets(void);
     57 void save_shifts(void);
     58 void save_reductions(void);
     59 void set_derives(void);
     60 void print_derives(void);
     61 void set_nullable(void);
     62 
     63 static core **state_set;
     64 static core *this_state;
     65 static core *last_state;
     66 static shifts *last_shift;
     67 static reductions *last_reduction;
     68 
     69 static int nshifts;
     70 static short *shift_symbol;
     71 
     72 static short *redset;
     73 static short *shiftset;
     74 
     75 static short **kernel_base;
     76 static short **kernel_end;
     77 static short *kernel_items;
     78 
     79 void
     80 allocate_itemsets(void)
     81 {
     82 	short *itemp, *item_end;
     83 	int i, count, max, symbol;
     84 	short *symbol_count;
     85 
     86 	count = 0;
     87 	symbol_count = NEW2(nsyms, short);
     88 
     89 	item_end = ritem + nitems;
     90 	for (itemp = ritem; itemp < item_end; itemp++) {
     91 		symbol = *itemp;
     92 		if (symbol >= 0) {
     93 			count++;
     94 			symbol_count[symbol]++;
     95 		}
     96 	}
     97 
     98 	kernel_base = NEW2(nsyms, short *);
     99 	kernel_items = NEW2(count, short);
    100 
    101 	count = 0;
    102 	max = 0;
    103 	for (i = 0; i < nsyms; i++) {
    104 		kernel_base[i] = kernel_items + count;
    105 		count += symbol_count[i];
    106 		if (max < symbol_count[i])
    107 			max = symbol_count[i];
    108 	}
    109 
    110 	shift_symbol = symbol_count;
    111 	kernel_end = NEW2(nsyms, short *);
    112 }
    113 
    114 void
    115 allocate_storage(void)
    116 {
    117 	allocate_itemsets();
    118 	shiftset = NEW2(nsyms, short);
    119 	redset = NEW2(nrules + 1, short);
    120 	state_set = NEW2(nitems, core *);
    121 }
    122 
    123 void
    124 append_states(void)
    125 {
    126 	int i, j, symbol;
    127 
    128 #ifdef	TRACE
    129 	fprintf(stderr, "Entering append_states()\n");
    130 #endif
    131 	for (i = 1; i < nshifts; i++) {
    132 		symbol = shift_symbol[i];
    133 		j = i;
    134 		while (j > 0 && shift_symbol[j - 1] > symbol) {
    135 			shift_symbol[j] = shift_symbol[j - 1];
    136 			j--;
    137 		}
    138 		shift_symbol[j] = symbol;
    139 	}
    140 
    141 	for (i = 0; i < nshifts; i++) {
    142 		symbol = shift_symbol[i];
    143 		shiftset[i] = get_state(symbol);
    144 	}
    145 }
    146 
    147 void
    148 free_storage(void)
    149 {
    150 	free(shift_symbol);
    151 	free(redset);
    152 	free(shiftset);
    153 	free(kernel_base);
    154 	free(kernel_end);
    155 	free(kernel_items);
    156 	free(state_set);
    157 }
    158 
    159 
    160 void
    161 generate_states(void)
    162 {
    163 	allocate_storage();
    164 	itemset = NEW2(nitems, short);
    165 	ruleset = NEW2(WORDSIZE(nrules), unsigned);
    166 	set_first_derives();
    167 	initialize_states();
    168 
    169 	while (this_state) {
    170 		closure(this_state->items, this_state->nitems);
    171 		save_reductions();
    172 		new_itemsets();
    173 		append_states();
    174 
    175 		if (nshifts > 0)
    176 			save_shifts();
    177 
    178 		this_state = this_state->next;
    179 	}
    180 
    181 	finalize_closure();
    182 	free_storage();
    183 }
    184 
    185 
    186 
    187 short
    188 get_state(int symbol)
    189 {
    190 	int n, found, key;
    191 	short *isp1, *isp2, *iend;
    192 	core *sp;
    193 
    194 #ifdef	TRACE
    195 	fprintf(stderr, "Entering get_state(%d)\n", symbol);
    196 #endif
    197 
    198 	isp1 = kernel_base[symbol];
    199 	iend = kernel_end[symbol];
    200 	n = iend - isp1;
    201 
    202 	key = *isp1;
    203 	assert(0 <= key && key < nitems);
    204 	sp = state_set[key];
    205 	if (sp) {
    206 		found = 0;
    207 		while (!found) {
    208 			if (sp->nitems == n) {
    209 				found = 1;
    210 				isp1 = kernel_base[symbol];
    211 				isp2 = sp->items;
    212 
    213 				while (found && isp1 < iend) {
    214 					if (*isp1++ != *isp2++)
    215 						found = 0;
    216 				}
    217 			}
    218 			if (!found) {
    219 				if (sp->link) {
    220 					sp = sp->link;
    221 				} else {
    222 					sp = sp->link = new_state(symbol);
    223 					found = 1;
    224 				}
    225 			}
    226 		}
    227 	} else {
    228 		state_set[key] = sp = new_state(symbol);
    229 	}
    230 
    231 	return (sp->number);
    232 }
    233 
    234 
    235 void
    236 initialize_states(void)
    237 {
    238 	int i;
    239 	short *start_derives;
    240 	core *p;
    241 
    242 	start_derives = derives[start_symbol];
    243 	for (i = 0; start_derives[i] >= 0; ++i)
    244 		continue;
    245 
    246 	p = malloc(sizeof(core) + i * sizeof(short));
    247 	if (p == NULL)
    248 		no_space();
    249 
    250 	p->next = 0;
    251 	p->link = 0;
    252 	p->number = 0;
    253 	p->accessing_symbol = 0;
    254 	p->nitems = i;
    255 
    256 	for (i = 0; start_derives[i] >= 0; ++i)
    257 		p->items[i] = rrhs[start_derives[i]];
    258 
    259 	first_state = last_state = this_state = p;
    260 	nstates = 1;
    261 }
    262 
    263 void
    264 new_itemsets(void)
    265 {
    266 	int i, shiftcount;
    267 	short *isp, *ksp;
    268 	int symbol;
    269 
    270 	memset(kernel_end, 0, nsyms * sizeof(short *));
    271 
    272 	shiftcount = 0;
    273 	isp = itemset;
    274 	while (isp < itemsetend) {
    275 		i = *isp++;
    276 		symbol = ritem[i];
    277 		if (symbol > 0) {
    278 			ksp = kernel_end[symbol];
    279 			if (!ksp) {
    280 				shift_symbol[shiftcount++] = symbol;
    281 				ksp = kernel_base[symbol];
    282 			}
    283 			*ksp++ = i + 1;
    284 			kernel_end[symbol] = ksp;
    285 		}
    286 	}
    287 
    288 	nshifts = shiftcount;
    289 }
    290 
    291 
    292 
    293 core *
    294 new_state(int symbol)
    295 {
    296 	int n;
    297 	core *p;
    298 	short *isp1, *isp2, *iend;
    299 
    300 #ifdef	TRACE
    301 	fprintf(stderr, "Entering new_state(%d)\n", symbol);
    302 #endif
    303 
    304 	if (nstates >= MAXSHORT)
    305 		fatal("too many states");
    306 
    307 	isp1 = kernel_base[symbol];
    308 	iend = kernel_end[symbol];
    309 	n = iend - isp1;
    310 
    311 	p = allocate(sizeof(core) + (n - 1) * sizeof(short));
    312 	p->accessing_symbol = symbol;
    313 	p->number = nstates;
    314 	p->nitems = n;
    315 
    316 	isp2 = p->items;
    317 	while (isp1 < iend)
    318 		*isp2++ = *isp1++;
    319 
    320 	last_state->next = p;
    321 	last_state = p;
    322 
    323 	nstates++;
    324 
    325 	return (p);
    326 }
    327 
    328 
    329 void
    330 save_shifts(void)
    331 {
    332 	shifts *p;
    333 	short *sp1, *sp2, *send;
    334 
    335 	p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
    336 
    337 	p->number = this_state->number;
    338 	p->nshifts = nshifts;
    339 
    340 	sp1 = shiftset;
    341 	sp2 = p->shift;
    342 	send = shiftset + nshifts;
    343 
    344 	while (sp1 < send)
    345 		*sp2++ = *sp1++;
    346 
    347 	if (last_shift) {
    348 		last_shift->next = p;
    349 		last_shift = p;
    350 	} else {
    351 		first_shift = p;
    352 		last_shift = p;
    353 	}
    354 }
    355 
    356 
    357 void
    358 save_reductions(void)
    359 {
    360 	short *isp, *rp1, *rp2;
    361 	int item, count;
    362 	reductions *p;
    363 	short *rend;
    364 
    365 	count = 0;
    366 	for (isp = itemset; isp < itemsetend; isp++) {
    367 		item = ritem[*isp];
    368 		if (item < 0) {
    369 			redset[count++] = -item;
    370 		}
    371 	}
    372 
    373 	if (count) {
    374 		p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
    375 
    376 		p->number = this_state->number;
    377 		p->nreds = count;
    378 
    379 		rp1 = redset;
    380 		rp2 = p->rules;
    381 		rend = rp1 + count;
    382 
    383 		while (rp1 < rend)
    384 			*rp2++ = *rp1++;
    385 
    386 		if (last_reduction) {
    387 			last_reduction->next = p;
    388 			last_reduction = p;
    389 		} else {
    390 			first_reduction = p;
    391 			last_reduction = p;
    392 		}
    393 	}
    394 }
    395 
    396 void
    397 set_derives(void)
    398 {
    399 	int i, k, lhs;
    400 	short *rules;
    401 
    402 	derives = NEW2(nsyms, short *);
    403 	rules = NEW2(nvars + nrules, short);
    404 
    405 	k = 0;
    406 	for (lhs = start_symbol; lhs < nsyms; lhs++) {
    407 		derives[lhs] = rules + k;
    408 		for (i = 0; i < nrules; i++) {
    409 			if (rlhs[i] == lhs) {
    410 				rules[k] = i;
    411 				k++;
    412 			}
    413 		}
    414 		rules[k] = -1;
    415 		k++;
    416 	}
    417 
    418 #ifdef	DEBUG
    419 	print_derives();
    420 #endif
    421 }
    422 
    423 void
    424 free_derives(void)
    425 {
    426 	free(derives[start_symbol]);
    427 	free(derives);
    428 }
    429 
    430 #ifdef	DEBUG
    431 void
    432 print_derives(void)
    433 {
    434 	int i;
    435 	short *sp;
    436 
    437 	printf("\nDERIVES\n\n");
    438 
    439 	for (i = start_symbol; i < nsyms; i++) {
    440 		printf("%s derives ", symbol_name[i]);
    441 		for (sp = derives[i]; *sp >= 0; sp++) {
    442 			printf("  %d", *sp);
    443 		}
    444 		putchar('\n');
    445 	}
    446 
    447 	putchar('\n');
    448 }
    449 #endif
    450 
    451 void
    452 set_nullable(void)
    453 {
    454 	int i, j;
    455 	int empty;
    456 	int done;
    457 
    458 	nullable = calloc(1, nsyms);
    459 	if (nullable == NULL)
    460 		no_space();
    461 
    462 	done = 0;
    463 	while (!done) {
    464 		done = 1;
    465 		for (i = 1; i < nitems; i++) {
    466 			empty = 1;
    467 			while ((j = ritem[i]) >= 0) {
    468 				if (!nullable[j])
    469 					empty = 0;
    470 				++i;
    471 			}
    472 			if (empty) {
    473 				j = rlhs[-j];
    474 				if (!nullable[j]) {
    475 					nullable[j] = 1;
    476 					done = 0;
    477 				}
    478 			}
    479 		}
    480 	}
    481 
    482 #ifdef DEBUG
    483 	for (i = 0; i < nsyms; i++) {
    484 		if (nullable[i])
    485 			printf("%s is nullable\n", symbol_name[i]);
    486 		else
    487 			printf("%s is not nullable\n", symbol_name[i]);
    488 	}
    489 #endif
    490 }
    491 
    492 void
    493 free_nullable(void)
    494 {
    495 	free(nullable);
    496 }
    497 
    498 void
    499 lr0(void)
    500 {
    501 	set_derives();
    502 	set_nullable();
    503 	generate_states();
    504 }